Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
ReversedQuickSearchBadCharacterShiftTable.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/set>
9#include <alib/map>
10
15
17
18namespace tree {
19
20namespace properties {
21
26public:
27 template < class SymbolType >
29 template < class SymbolType >
31 template < class SymbolType >
33 template < class SymbolType >
35
36};
37
38template < class SymbolType >
41}
42
43template < class SymbolType >
46
48
49 // initialisation of bcs table to the size of the pattern plus one
50 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
51 if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( symbol ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
52
53 bcs.insert ( std::make_pair ( symbol, pattern.getContent ( ).size ( ) + 1 ) );
54 }
55
56 // find the distance between the beginning of the pattern and the index
57 // of the first symbol representing the variable's bar
58 size_t firstSBarOffset = FirstVariableOffsetFront::offset ( pattern ) + 1;
59
60 // limit the shift by occurrence of the last variable
61 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
62 if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( symbol ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
63
64 size_t tmp = firstSBarOffset + 1;
65
66 if ( pattern.getBars ( ).count ( symbol ) )
67 // size of the smallest subtree containing given terminal depend
68 // on the arity of the terminal
69 tmp += symbol.getRank ( ) * 2;
70 else
71 tmp -= 1;
72
73 if ( bcs[symbol] > tmp )
74 bcs[symbol] = tmp;
75 }
76
77 // limit the shift by position of symbols within the pattern
78 for ( unsigned i = pattern.getContent ( ).size ( ); i > 0; i-- ) {
79 if ( ( pattern.getContent ( )[i-1] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[i-1] ) ) || ( pattern.getContent ( )[i-1] == pattern.getVariablesBar ( ) ) ) continue;
80
81 size_t tmp = i;
82
83 if ( bcs[pattern.getContent ( )[i-1]] > tmp )
84 bcs[pattern.getContent ( )[i-1]] = tmp;
85 }
86
87 return bcs;
88}
89
90template < class SymbolType >
93}
94
95template < class SymbolType >
98
100
101 // initialisation of bcs table to the size of the pattern plus one
102 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
103 if ( symbol == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( symbol ) ) continue;
104
105 bcs.insert ( std::make_pair ( symbol, pattern.getContent ( ).size ( ) + 1 ) );
106 }
107
108 // find the distance between the beginning of the pattern and the index
109 // of the first symbol representing the variable's bar
110 size_t firstSOffset = FirstVariableOffsetFront::offset ( pattern );
111
112 // limit the shift by occurrence of the last variable
113 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
114 if ( symbol == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( symbol ) ) continue;
115
116 if ( bcs[symbol] > firstSOffset + 1 )
117 bcs[symbol] = firstSOffset + 1;
118 }
119
120 // limit the shift by position of symbols within the pattern
121 for ( unsigned i = pattern.getContent ( ).size ( ) - 1; i > 0; i-- ) {
122 if ( pattern.getContent ( )[i-1] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[i-1] ) ) continue;
123 size_t tmp = i;
124
125 if ( bcs[pattern.getContent ( )[i-1]] > tmp )
126 bcs[pattern.getContent ( )[i-1]] = tmp;
127 }
128
129 return bcs;
130}
131
132} /* namespace properties */
133
134} /* namespace tree */
135
Definition: ranked_symbol.hpp:20
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
Definition: set.hpp:44
Nonlinear tree pattern represented as linear sequece as result of preorder traversal with additional ...
Definition: PrefixRankedBarNonlinearPattern.h:91
const ext::set< common::ranked_symbol< SymbolType > > & getBars() const &
Definition: PrefixRankedBarNonlinearPattern.h:232
const ext::set< common::ranked_symbol< SymbolType > > & getNonlinearVariables() const &
Definition: PrefixRankedBarNonlinearPattern.h:277
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedBarNonlinearPattern.h:259
const ext::set< common::ranked_symbol< SymbolType > > & getAlphabet() const &
Definition: PrefixRankedBarNonlinearPattern.h:205
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarNonlinearPattern.h:434
const common::ranked_symbol< SymbolType > & getVariablesBar() const &
Definition: PrefixRankedBarNonlinearPattern.h:295
Tree pattern represented as linear sequece as result of preorder traversal with additional bar symbol...
Definition: PrefixRankedBarPattern.h:85
Nonlinear tree pattern represented as linear sequece as result of preorder traversal....
Definition: PrefixRankedNonlinearPattern.h:82
const ext::set< common::ranked_symbol< SymbolType > > & getNonlinearVariables() const &
Definition: PrefixRankedNonlinearPattern.h:208
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedNonlinearPattern.h:333
const ext::set< common::ranked_symbol< SymbolType > > & getAlphabet() const &
Definition: PrefixRankedNonlinearPattern.h:163
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedNonlinearPattern.h:190
Tree pattern represented as linear sequece as result of preorder traversal. The representation is so ...
Definition: PrefixRankedPattern.h:77
static size_t offset(const tree::PrefixRankedPattern< SymbolType > &pattern)
Definition: FirstVariableOffsetFront.h:33
Definition: ReversedQuickSearchBadCharacterShiftTable.h:25
static ext::map< common::ranked_symbol< SymbolType >, size_t > bcs(const tree::PrefixRankedBarPattern< SymbolType > &pattern)
Definition: ReversedQuickSearchBadCharacterShiftTable.h:39
Definition: BarSymbol.cpp:12
int i
Definition: AllEpsilonClosure.h:118
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: BackwardOccurrenceTest.h:17