Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
ExactPatternMatch.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <ext/foreach>
9
10#include <alib/set>
11#include <alib/tree>
12#include <alib/deque>
13
14#include <tree/ranked/UnorderedRankedTree.h>
15#include <tree/ranked/UnorderedRankedPattern.h>
16
17#include <tree/ranked/RankedTree.h>
18#include <tree/ranked/RankedPattern.h>
19#include <tree/ranked/RankedNonlinearPattern.h>
20#include <tree/ranked/RankedExtendedPattern.h>
21#include <tree/ranked/PrefixRankedTree.h>
22#include <tree/ranked/PrefixRankedPattern.h>
23#include <tree/ranked/PrefixRankedNonlinearPattern.h>
24#include <tree/ranked/PrefixRankedBarTree.h>
25#include <tree/ranked/PrefixRankedBarPattern.h>
26#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
27#include <tree/unranked/UnrankedTree.h>
28#include <tree/unranked/UnrankedPattern.h>
29#include <tree/unranked/UnrankedExtendedPattern.h>
30#include <tree/unranked/UnorderedUnrankedTree.h>
31#include <tree/unranked/UnorderedUnrankedPattern.h>
32
33#include <tree/properties/SubtreeJumpTable.h>
34#include <tree/properties/ExactSubtreeRepeatsNaive.h>
35#include <tree/exact/ForwardOccurrenceTest.h>
36
37namespace arbology {
38
39namespace exact {
40
41class ExactPatternMatch {
42public:
47 template < class SymbolType >
48 static ext::set < unsigned > match ( const tree::UnorderedUnrankedTree < SymbolType > & subject, const tree::UnorderedUnrankedPattern < SymbolType > & pattern );
49
50 template < class SymbolType >
51 static ext::set < unsigned > match ( const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedPattern < SymbolType > & pattern );
52 template < class SymbolType >
53 static ext::set < unsigned > match ( const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedExtendedPattern < SymbolType > & pattern );
54
55 template < class SymbolType >
56 static ext::set < unsigned > match ( const tree::UnorderedRankedTree < SymbolType > & subject, const tree::UnorderedRankedPattern < SymbolType > & pattern );
57
58 template < class SymbolType >
59 static ext::set < unsigned > match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedPattern < SymbolType > & pattern );
60 template < class SymbolType >
61 static ext::set < unsigned > match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedNonlinearPattern < SymbolType > & pattern );
62 template < class SymbolType >
63 static ext::set < unsigned > match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedExtendedPattern < SymbolType > & pattern );
64
65 template < class SymbolType >
66 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern );
67 template < class SymbolType >
68 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
69
70 template < class SymbolType >
71 static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern );
72 template < class SymbolType >
73 static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
74
75private:
76 template < class SymbolType >
77 static bool matchHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
78 template < class SymbolType >
79 static bool matchHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard );
80 template < class SymbolType >
81 static bool matchHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable, const ext::set < common::ranked_symbol < SymbolType > > & nodeWildcards );
82 template < class SymbolType >
83 static bool matchHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const ext::tree < common::ranked_symbol < unsigned > > & repeats, ext::map < common::ranked_symbol < SymbolType >, unsigned > & variablesSetting );
84
85 template < class SymbolType >
86 static bool matchHelper ( typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
87 template < class SymbolType >
88 static bool matchHelper ( typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard );
89
90 template < class SymbolType >
91 static void matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const ext::set < SymbolType > & nodeWildcards );
92 template < class SymbolType >
93 static void matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
94 template < class SymbolType >
95 static void matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard );
96 template < class SymbolType, class RepeatsType >
97 static void matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const ext::set < SymbolType > & nonlinearVariables, const ext::tree < RepeatsType > & repeats );
98
99 template < class SymbolType >
100 static bool matchUnorderedHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
101 template < class SymbolType >
102 static bool matchUnorderedHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable );
103
104 template < class SymbolType >
105 static bool matchUnorderedHelper ( typename ext::vector < ext::reference_wrapper < const ext::tree < SymbolType > > >::const_iterator subjectIter, typename ext::vector < ext::reference_wrapper < const ext::tree < SymbolType > > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
106
107 template < class SymbolType >
108 static void matchUnorderedInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable );
109 template < class SymbolType >
110 static void matchUnorderedInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap );
111
112};
113
114template < class SymbolType >
115bool ExactPatternMatch::matchHelper ( typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
116 if ( patternIter == patternEnd )
117 return subjectIter == subjectEnd;
118
119 if ( patternIter->getData ( ) == subtreeGap ) {
120 if ( matchHelper ( subjectIter, subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap ) )
121 return true;
122
123 while ( subjectIter != subjectEnd ) {
124 ++ subjectIter;
125 if ( matchHelper ( subjectIter, subjectEnd, patternIter, patternEnd, subtreeVariable, subtreeGap ) )
126 return true;
127 }
128
129 return false;
130 } else if ( subjectIter != subjectEnd ) {
131 if ( matchHelper ( * subjectIter, * patternIter, subtreeVariable, subtreeGap ) )
132 return matchHelper ( std::next ( subjectIter ), subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap );
133
134 return false;
135 } else {
136 return false;
137 }
138}
139
140template < class SymbolType >
141bool ExactPatternMatch::matchHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
142 if ( pattern.getData ( ) == subtreeVariable ) return true;
143
144 if ( subject.getData ( ) != pattern.getData ( ) ) return false;
145
146 return matchHelper ( subject.getChildren ( ).begin ( ), subject.getChildren ( ).end ( ), pattern.getChildren ( ).begin ( ), pattern.getChildren ( ).end ( ), subtreeVariable, subtreeGap );
147}
148
149template < class SymbolType >
150bool ExactPatternMatch::matchHelper ( typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard ) {
151 if ( patternIter == patternEnd )
152 return subjectIter == subjectEnd;
153
154 if ( patternIter->getData ( ) == subtreeGap ) {
155 if ( matchHelper ( subjectIter, subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap, nodeWildcard ) )
156 return true;
157
158 while ( subjectIter != subjectEnd ) {
159 ++ subjectIter;
160 if ( matchHelper ( subjectIter, subjectEnd, patternIter, patternEnd, subtreeVariable, subtreeGap, nodeWildcard ) )
161 return true;
162 }
163
164 return false;
165 } else if ( subjectIter != subjectEnd ) {
166 if ( matchHelper ( * subjectIter, * patternIter, subtreeVariable, subtreeGap, nodeWildcard ) )
167 return matchHelper ( std::next ( subjectIter ), subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap, nodeWildcard );
168
169 return false;
170 } else {
171 return false;
172 }
173}
174
175template < class SymbolType >
176bool ExactPatternMatch::matchHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard ) {
177 if ( pattern.getData ( ) == subtreeVariable ) return true;
178
179 if ( subject.getData ( ) != pattern.getData ( ) && nodeWildcard != pattern.getData ( ) ) return false;
180
181 return matchHelper ( subject.getChildren ( ).begin ( ), subject.getChildren ( ).end ( ), pattern.getChildren ( ).begin ( ), pattern.getChildren ( ).end ( ), subtreeVariable, subtreeGap, nodeWildcard );
182}
183
184template < class SymbolType >
185bool ExactPatternMatch::matchHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable, const ext::set < common::ranked_symbol < SymbolType > > & nodeWildcards ) {
186 if ( pattern.getData ( ) == subtreeVariable ) return true;
187
188 if ( subject.getData ( ) != pattern.getData ( ) && ( ! nodeWildcards.contains ( pattern.getData ( ) ) || pattern.getData ( ).getRank ( ) != subject.getData ( ).getRank ( ) ) )
189 return false;
190
191 // ranked symbols are the same; test for number of children is not needed
192 for ( const ext::tuple < const ext::tree < common::ranked_symbol < SymbolType > > &, const ext::tree < common::ranked_symbol < SymbolType > > & > & childs : ext::make_tuple_foreach ( subject.getChildren ( ), pattern.getChildren ( ) ) )
193 if ( !matchHelper ( std::get < 0 > ( childs ), std::get < 1 > ( childs ), subtreeVariable, nodeWildcards ) ) return false;
194
195 return true;
196}
197
198template < class SymbolType >
199bool ExactPatternMatch::matchHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const ext::tree < common::ranked_symbol < unsigned > > & repeats, ext::map < common::ranked_symbol < SymbolType >, unsigned > & variablesSetting ) {
200 if ( pattern.getData ( ) == subtreeVariable ) return true;
201
202 if ( nonlinearVariables.count ( pattern.getData ( ) ) ) {
203 auto setting = variablesSetting.find ( pattern.getData ( ) );
204
205 if ( setting != variablesSetting.end ( ) ) return repeats.getData ( ).getSymbol ( ) == setting->second;
206
207 variablesSetting.insert ( std::make_pair ( pattern.getData ( ), repeats.getData ( ).getSymbol ( ) ) );
208
209 return true;
210 }
211
212 if ( subject.getData ( ) != pattern.getData ( ) ) return false;
213
214 // ranked symbols are the same; test for number of children is not needed
215 for ( const ext::tuple < const ext::tree < common::ranked_symbol < SymbolType > > &, const ext::tree < common::ranked_symbol < SymbolType > > &, const ext::tree < common::ranked_symbol < unsigned > > & > & childs : ext::make_tuple_foreach ( subject.getChildren ( ), pattern.getChildren ( ), repeats.getChildren ( ) ) )
216 if ( !matchHelper ( std::get < 0 > ( childs ), std::get < 1 > ( childs ), subtreeVariable, nonlinearVariables, std::get < 2 > ( childs ), variablesSetting ) ) return false;
217
218 return true;
219}
220
221template < class SymbolType >
222void ExactPatternMatch::matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const ext::set < SymbolType > & nodeWildcards ) {
223 if ( matchHelper ( subject, pattern, subtreeVariable, nodeWildcards ) ) occ.insert ( index );
224
225 index++;
226
227 for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
228 matchInternal ( index, occ, child, pattern, subtreeVariable, nodeWildcards );
229}
230
231template < class SymbolType >
232void ExactPatternMatch::matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
233 if ( matchHelper ( subject, pattern, subtreeVariable, subtreeGap ) ) occ.insert ( index );
234
235 index++;
236
237 for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
238 matchInternal ( index, occ, child, pattern, subtreeVariable, subtreeGap );
239}
240
241template < class SymbolType >
242void ExactPatternMatch::matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap, const SymbolType & nodeWildcard ) {
243 if ( matchHelper ( subject, pattern, subtreeVariable, subtreeGap, nodeWildcard ) ) occ.insert ( index );
244
245 index++;
246
247 for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
248 matchInternal ( index, occ, child, pattern, subtreeVariable, subtreeGap, nodeWildcard );
249}
250
251template < class SymbolType, class RepeatsType >
252void ExactPatternMatch::matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const ext::set < SymbolType > & nonlinearVariables, const ext::tree < RepeatsType > & repeats ) {
253 ext::map < SymbolType, unsigned > variablesSetting;
254
255 if ( matchHelper ( subject, pattern, subtreeVariable, nonlinearVariables, repeats, variablesSetting ) ) occ.insert ( index );
256
257 index++;
258
259 for ( const ext::tuple < const ext::tree < SymbolType > &, const ext::tree < RepeatsType > & > & childs : ext::make_tuple_foreach ( subject.getChildren ( ), repeats.getChildren ( ) ) )
260 matchInternal ( index, occ, std::get < 0 > ( childs ), pattern, subtreeVariable, nonlinearVariables, std::get < 1 > ( childs ) );
261}
262
263template < class SymbolType >
264bool ExactPatternMatch::matchUnorderedHelper ( typename ext::vector < ext::reference_wrapper < const ext::tree < SymbolType > > >::const_iterator subjectIter, typename ext::vector < ext::reference_wrapper < const ext::tree < SymbolType > > >::const_iterator subjectEnd, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternIter, typename ext::vector < ext::tree < SymbolType > >::const_iterator patternEnd, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
265 if ( patternIter == patternEnd )
266 return subjectIter == subjectEnd;
267
268 if ( patternIter->getData ( ) == subtreeGap ) {
269 if ( matchUnorderedHelper ( subjectIter, subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap ) )
270 return true;
271
272 while ( subjectIter != subjectEnd ) {
273 ++ subjectIter;
274 if ( matchUnorderedHelper ( subjectIter, subjectEnd, patternIter, patternEnd, subtreeVariable, subtreeGap ) )
275 return true;
276 }
277
278 return false;
279 } else if ( subjectIter != subjectEnd ) {
280 if ( matchUnorderedHelper ( subjectIter->get ( ), * patternIter, subtreeVariable, subtreeGap ) )
281 return matchUnorderedHelper ( std::next ( subjectIter ), subjectEnd, std::next ( patternIter ), patternEnd, subtreeVariable, subtreeGap );
282
283 return false;
284 } else {
285 return false;
286 }
287}
288
289template < class SymbolType >
290bool ExactPatternMatch::matchUnorderedHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
291 if ( pattern.getData ( ) == subtreeVariable ) return true;
292
293 if ( subject.getData ( ) != pattern.getData ( ) ) return false;
294
295 ext::vector < ext::reference_wrapper < const ext::tree < SymbolType > > > subjectChildrenRefs;
296 for ( const auto & child : subject.getChildren ( ) ) {
297 subjectChildrenRefs.emplace_back ( child );
298 }
299
300 do {
301 if ( matchUnorderedHelper ( subjectChildrenRefs.begin ( ), subjectChildrenRefs.end ( ), pattern.getChildren ( ).begin ( ), pattern.getChildren ( ).end ( ), subtreeVariable, subtreeGap ) )
302 return true;
303 } while ( next_permutation ( subjectChildrenRefs.begin ( ), subjectChildrenRefs.end ( ) ) );
304
305 return false;
306}
307
308template < class SymbolType >
309bool ExactPatternMatch::matchUnorderedHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern, const common::ranked_symbol < SymbolType > & subtreeVariable ) {
310 if ( pattern.getData ( ) == subtreeVariable ) return true;
311
312 if ( subject.getData ( ) != pattern.getData ( ) ) return false;
313
314 auto testPermutation = [ ] ( const auto & subjectChildren, const auto & patternChildren, const common::ranked_symbol < SymbolType > & subtreeVar ) {
315 // ranked symbols are the same; test for number of children is not needed
316 for ( const ext::tuple < const ext::tree < common::ranked_symbol < SymbolType > > &, const ext::reference_wrapper < const ext::tree < common::ranked_symbol < SymbolType > > > & > & childs : ext::make_tuple_foreach ( subjectChildren, patternChildren ) )
317 if ( ! matchUnorderedHelper ( std::get < 0 > ( childs ), std::get < 1 > ( childs ).get ( ), subtreeVar ) )
318 return false;
319
320 return true;
321 };
322
323 ext::vector < ext::reference_wrapper < const ext::tree < common::ranked_symbol < SymbolType > > > > patternChildrenRefs;
324 for ( const auto & child : pattern.getChildren ( ) ) {
325 patternChildrenRefs.emplace_back ( child );
326 }
327
328 do {
329 if ( testPermutation ( subject.getChildren ( ), patternChildrenRefs, subtreeVariable ) )
330 return true;
331 } while ( next_permutation ( patternChildrenRefs.begin ( ), patternChildrenRefs.end ( ) ) );
332
333 return false;
334}
335
336template < class SymbolType >
337void ExactPatternMatch::matchUnorderedInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable ) {
338 if ( matchUnorderedHelper ( subject, pattern, subtreeVariable ) ) occ.insert ( index );
339
340 index++;
341
342 for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
343 matchUnorderedInternal ( index, occ, child, pattern, subtreeVariable );
344}
345
346template < class SymbolType >
347void ExactPatternMatch::matchUnorderedInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern, const SymbolType & subtreeVariable, const SymbolType & subtreeGap ) {
348 if ( matchUnorderedHelper ( subject, pattern, subtreeVariable, subtreeGap ) ) occ.insert ( index );
349
350 index++;
351
352 for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
353 matchUnorderedInternal ( index, occ, child, pattern, subtreeVariable, subtreeGap );
354}
355
356template < class SymbolType >
357ext::set < unsigned > ExactPatternMatch::match ( const tree::UnorderedUnrankedTree < SymbolType > & subject, const tree::UnorderedUnrankedPattern < SymbolType > & pattern ) {
358 unsigned i = 0;
359 ext::set < unsigned > occ;
360
361 matchUnorderedInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), pattern.getSubtreeGap ( ) );
362 return occ;
363}
364
365template < class SymbolType >
366ext::set < unsigned > ExactPatternMatch::match ( const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedPattern < SymbolType > & pattern ) {
367 unsigned i = 0;
368 ext::set < unsigned > occ;
369
370 matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), pattern.getSubtreeGap ( ) );
371 return occ;
372}
373
374template < class SymbolType >
375ext::set < unsigned > ExactPatternMatch::match ( const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedExtendedPattern < SymbolType > & pattern ) {
376 unsigned i = 0;
377 ext::set < unsigned > occ;
378
379 matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), pattern.getSubtreeGap ( ), pattern.getNodeWildcard ( ) );
380 return occ;
381}
382
383template < class SymbolType >
384ext::set < unsigned > ExactPatternMatch::match ( const tree::UnorderedRankedTree < SymbolType > & subject, const tree::UnorderedRankedPattern < SymbolType > & pattern ) {
385 unsigned i = 0;
386 ext::set < unsigned > occ;
387
388 matchUnorderedInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ) );
389 return occ;
390}
391
392template < class SymbolType >
393ext::set < unsigned > ExactPatternMatch::match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedPattern < SymbolType > & pattern ) {
394 unsigned i = 0;
395 ext::set < unsigned > occ;
396
397 matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), { } );
398 return occ;
399}
400
401template < class SymbolType >
402ext::set < unsigned > ExactPatternMatch::match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedNonlinearPattern < SymbolType > & pattern ) {
403 unsigned i = 0;
404 ext::set < unsigned > occ;
405
406 tree::RankedTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
407
408 matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), pattern.getNonlinearVariables ( ), repeats.getContent ( ) );
409 return occ;
410}
411
412template < class SymbolType >
413ext::set < unsigned > ExactPatternMatch::match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedExtendedPattern < SymbolType > & pattern ) {
414 unsigned i = 0;
415 ext::set < unsigned > occ;
416
417 matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ), pattern.getSubtreeWildcard ( ), pattern.getNodeWildcards ( ) );
418 return occ;
419}
420
421template < class SymbolType >
422ext::set < unsigned > ExactPatternMatch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern ) {
423 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
424
425 ext::set < unsigned > occ;
426
427 for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
428 unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i );
429
430 if ( j == pattern.getContent ( ).size ( ) )
431 occ.insert ( i );
432 }
433
434 return occ;
435}
436
437template < class SymbolType >
438ext::set < unsigned > ExactPatternMatch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
439 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
440 tree::PrefixRankedTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
441
442 ext::set < unsigned > occ;
443
444 for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
445 unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i );
446
447 if ( j == pattern.getContent ( ).size ( ) )
448 occ.insert ( i );
449 }
450
451 return occ;
452}
453
454template < class SymbolType >
455ext::set < unsigned > ExactPatternMatch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
456 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
457
458 ext::set < unsigned > occ;
459
460 for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
461 unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i );
462
463 if ( j == pattern.getContent ( ).size ( ) )
464 occ.insert ( i );
465 }
466
467 return occ;
468}
469
470template < class SymbolType >
471ext::set < unsigned > ExactPatternMatch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
472 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
473 tree::PrefixRankedBarTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
474
475 ext::set < unsigned > occ;
476
477 for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
478 unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i );
479
480 if ( j == pattern.getContent ( ).size ( ) )
481 occ.insert ( i );
482 }
483
484 return occ;
485}
486
487} /* namespace exact */
488
489} /* namespace arbology */
490
arbology::exact::ExactPatternMatch
Definition: ExactPatternMatch.h:41
arbology::exact::ExactPatternMatch::match
static ext::set< unsigned > match(const tree::UnorderedUnrankedTree< SymbolType > &subject, const tree::UnorderedUnrankedPattern< SymbolType > &pattern)
Definition: ExactPatternMatch.h:357
common::ranked_symbol
Definition: ranked_symbol.hpp:20
ext::map
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
ext::reference_wrapper
Class extending the reference wrapper class from the standard library. Original reason is to allow it...
Definition: functional.hpp:108
ext::set
Definition: set.hpp:44
ext::tree
Class introducing a tree with interface trying to be close to the interface of standard library conta...
Definition: tree.hpp:52
ext::tree::getData
T & getData()
Getter of the value in the root node.
Definition: tree.hpp:100
ext::tree::getChildren
ext::vector< tree > & getChildren()
Getter of children of the root node.
Definition: tree.hpp:120
ext::tuple
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
ext::vector
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
ext::vector::begin
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
ext::vector::end
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
tree::PrefixRankedBarNonlinearPattern
Nonlinear tree pattern represented as linear sequece as result of preorder traversal with additional ...
Definition: PrefixRankedBarNonlinearPattern.h:91
tree::PrefixRankedBarNonlinearPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarNonlinearPattern.h:434
tree::PrefixRankedBarPattern
Tree pattern represented as linear sequece as result of preorder traversal with additional bar symbol...
Definition: PrefixRankedBarPattern.h:85
tree::PrefixRankedBarPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarPattern.h:334
tree::PrefixRankedBarTree
Tree structure represented as linear sequece as result of preorder traversal with additional bar symb...
Definition: PrefixRankedBarTree.h:78
tree::PrefixRankedBarTree::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarTree.h:273
tree::PrefixRankedNonlinearPattern
Nonlinear tree pattern represented as linear sequece as result of preorder traversal....
Definition: PrefixRankedNonlinearPattern.h:82
tree::PrefixRankedNonlinearPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedNonlinearPattern.h:333
tree::PrefixRankedPattern
Tree pattern represented as linear sequece as result of preorder traversal. The representation is so ...
Definition: PrefixRankedPattern.h:77
tree::PrefixRankedPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedPattern.h:262
tree::PrefixRankedTree
Tree structure represented as linear sequece as result of preorder traversal. The representation is s...
Definition: PrefixRankedTree.h:71
tree::PrefixRankedTree::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedTree.h:235
tree::RankedExtendedPattern
Extended tree pattern represented in its natural representation. The representation is so called rank...
Definition: RankedExtendedPattern.h:74
tree::RankedExtendedPattern::getNodeWildcards
const ext::set< common::ranked_symbol< SymbolType > > & getNodeWildcards() const &
Definition: RankedExtendedPattern.h:155
tree::RankedExtendedPattern::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: RankedExtendedPattern.h:281
tree::RankedExtendedPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: RankedExtendedPattern.h:182
tree::RankedNonlinearPattern
Nonlinear tree pattern represented in its natural representation. The representation is so called ran...
Definition: RankedNonlinearPattern.h:74
tree::RankedNonlinearPattern::getNonlinearVariables
const ext::set< common::ranked_symbol< SymbolType > > & getNonlinearVariables() const &
Definition: RankedNonlinearPattern.h:183
tree::RankedNonlinearPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: RankedNonlinearPattern.h:165
tree::RankedNonlinearPattern::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: RankedNonlinearPattern.h:286
tree::RankedPattern
Tree pattern represented in its natural representation. The representation is so called ranked,...
Definition: RankedPattern.h:72
tree::RankedPattern::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: RankedPattern.h:251
tree::RankedPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: RankedPattern.h:153
tree::RankedTree
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: RankedTree.h:72
tree::RankedTree::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: RankedTree.h:252
tree::UnorderedRankedPattern
Tree pattern represented in its natural representation. The representation is so called ranked,...
Definition: UnorderedRankedPattern.h:72
tree::UnorderedRankedPattern::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: UnorderedRankedPattern.h:251
tree::UnorderedRankedPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: UnorderedRankedPattern.h:153
tree::UnorderedRankedTree
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: UnorderedRankedTree.h:70
tree::UnorderedRankedTree::getContent
const ext::tree< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: UnorderedRankedTree.h:228
tree::UnorderedUnrankedPattern
Tree pattern represented in its natural representation. The representation is so called unranked,...
Definition: UnorderedUnrankedPattern.h:73
tree::UnorderedUnrankedPattern::getSubtreeGap
const SymbolType & getSubtreeGap() const &
Definition: UnorderedUnrankedPattern.h:163
tree::UnorderedUnrankedPattern::getContent
const ext::tree< SymbolType > & getContent() const &
Definition: UnorderedUnrankedPattern.h:261
tree::UnorderedUnrankedPattern::getSubtreeWildcard
const SymbolType & getSubtreeWildcard() const &
Definition: UnorderedUnrankedPattern.h:145
tree::UnorderedUnrankedTree
Tree pattern represented in its natural representation. The representation is so called unranked,...
Definition: UnorderedUnrankedTree.h:69
tree::UnorderedUnrankedTree::getContent
const ext::tree< SymbolType > & getContent() const &
Definition: UnorderedUnrankedTree.h:217
tree::UnrankedExtendedPattern
Extended tree pattern represented in its natural representation. The representation is so called unra...
Definition: UnrankedExtendedPattern.h:76
tree::UnrankedExtendedPattern::getNodeWildcard
const SymbolType & getNodeWildcard() const &
Definition: UnrankedExtendedPattern.h:150
tree::UnrankedExtendedPattern::getSubtreeGap
const SymbolType & getSubtreeGap() const &
Definition: UnrankedExtendedPattern.h:186
tree::UnrankedExtendedPattern::getSubtreeWildcard
const SymbolType & getSubtreeWildcard() const &
Definition: UnrankedExtendedPattern.h:168
tree::UnrankedExtendedPattern::getContent
const ext::tree< SymbolType > & getContent() const &
Definition: UnrankedExtendedPattern.h:285
tree::UnrankedPattern
Tree pattern represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedPattern.h:73
tree::UnrankedPattern::getContent
const ext::tree< SymbolType > & getContent() const &
Definition: UnrankedPattern.h:263
tree::UnrankedPattern::getSubtreeGap
const SymbolType & getSubtreeGap() const &
Definition: UnrankedPattern.h:165
tree::UnrankedPattern::getSubtreeWildcard
const SymbolType & getSubtreeWildcard() const &
Definition: UnrankedPattern.h:147
tree::UnrankedTree
Tree represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedTree.h:69
tree::UnrankedTree::getContent
const ext::tree< SymbolType > & getContent() const &
Definition: UnrankedTree.h:217
tree::exact::ForwardOccurrenceTest::occurrence
static size_t occurrence(const PrefixRankedBarTree< SymbolType > &subject, const ext::vector< int > &subjectSubtreeJumpTable, const PrefixRankedBarTree< SymbolType > &pattern, size_t subjectPosition, size_t patternStartIndex=0)
Definition: ForwardOccurrenceTest.h:42
tree::properties::SubtreeJumpTable::compute
static ext::vector< int > compute(const tree::PrefixRankedBarTree< SymbolType > &subject)
Definition: SubtreeJumpTable.h:49
arbology
Definition: BoyerMooreHorspool.h:22
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
automaton::properties::SymbolType
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
ext::make_tuple_foreach
const_tuple_foreach< Types ... > make_tuple_foreach(const Types &... args)
Function construction of foreach tuple pack helper.
Definition: foreach.hpp:280
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
std::get
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2