Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
PrefixRankedBarPattern.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
27
28namespace tree {
29
30template < class SymbolType = DefaultSymbolType >
31class PrefixRankedBarPattern;
32
33} /* namespace tree */
34
35
36#include <ext/algorithm>
37
38#include <alib/set>
39#include <alib/vector>
40#include <alib/tree>
41#include <alib/deque>
42
43#include <core/components.hpp>
45
46#include <tree/TreeException.h>
48
49#include <alphabet/BarSymbol.h>
52
53#include <core/normalize.hpp>
55
56#include <string/LinearString.h>
57
58#include "RankedPattern.h"
59#include "PrefixRankedBarTree.h"
60
61namespace tree {
62
63class GeneralAlphabet;
64class SubtreeWildcard;
65class BarSymbols;
66class VariablesBarSymbol;
67
84template < class SymbolType >
85class PrefixRankedBarPattern final : public core::Components < PrefixRankedBarPattern < SymbolType >, ext::set < common::ranked_symbol < SymbolType > >, component::Set, std::tuple < GeneralAlphabet, BarSymbols >, common::ranked_symbol < SymbolType >, component::Value, std::tuple < SubtreeWildcard, VariablesBarSymbol > > {
90
96 void arityChecksum ( const ext::vector < common::ranked_symbol < SymbolType > > & data );
97
98public:
109
119
128
135
142
149 return this->template accessComponent < GeneralAlphabet > ( ).get ( );
150 }
151
158 return std::move ( this->template accessComponent < GeneralAlphabet > ( ).get ( ) );
159 }
160
167 this->template accessComponent < GeneralAlphabet > ( ).add ( symbols );
168 }
169
176 return this->template accessComponent < BarSymbols > ( ).get ( );
177 }
178
185 return std::move ( this->template accessComponent < BarSymbols > ( ).get ( ) );
186 }
187
194 this->template accessComponent < BarSymbols > ( ).add ( bars );
195 }
196
203 return this->template accessComponent < SubtreeWildcard > ( ).get ( );
204 }
205
212 return std::move ( this->template accessComponent < SubtreeWildcard > ( ).get ( ) );
213 }
214
221 return this->template accessComponent < VariablesBarSymbol > ( ).get ( );
222 }
223
230 return std::move ( this->template accessComponent < VariablesBarSymbol > ( ).get ( ) );
231 }
232
239
245 ext::vector < common::ranked_symbol < SymbolType > > && getContent ( ) &&;
246
254 void setContent ( ext::vector < common::ranked_symbol < SymbolType > > data );
255
259 bool isEmpty ( ) const;
260
268 auto operator <=> ( const PrefixRankedBarPattern & other ) const {
269 return std::tie ( m_Data, getAlphabet(), getSubtreeWildcard(), getBars(), getVariablesBar() ) <=> std::tie ( other.m_Data, other.getAlphabet(), other.getSubtreeWildcard(), other.getBars(), other.getVariablesBar() );
270 }
271
279 bool operator == ( const PrefixRankedBarPattern & other ) const {
280 return std::tie ( m_Data, getAlphabet(), getSubtreeWildcard(), getBars(), getVariablesBar() ) == std::tie ( other.m_Data, other.getAlphabet(), other.getSubtreeWildcard(), other.getBars(), other.getVariablesBar() );
281 }
282
291 friend ext::ostream & operator << ( ext::ostream & out, const PrefixRankedBarPattern & instance ) {
292 out << "(PrefixRankedBarPattern";
293 out << " alphabet = " << instance.getAlphabet ( );
294 out << " bars = " << instance.getBars ( );
295 out << " variablesBar = " << instance.getVariablesBar ( );
296 out << " content = " << instance.getContent ( );
297 out << " subtreeWildcard = " << instance.getSubtreeWildcard ( );
298 out << ")";
299 return out;
300 }
301
309 }
310};
311
312template < class SymbolType >
313PrefixRankedBarPattern < SymbolType >::PrefixRankedBarPattern ( ext::set < common::ranked_symbol < SymbolType > > bars, common::ranked_symbol < SymbolType > variablesBar, common::ranked_symbol < SymbolType > subtreeWildcard, ext::set < common::ranked_symbol < SymbolType > > alphabet, ext::vector < common::ranked_symbol < SymbolType > > data ) : core::Components < PrefixRankedBarPattern, ext::set < common::ranked_symbol < SymbolType > >, component::Set, std::tuple < GeneralAlphabet, BarSymbols >, common::ranked_symbol < SymbolType >, component::Value, std::tuple < SubtreeWildcard, VariablesBarSymbol > > ( std::move ( alphabet ), std::move ( bars ), std::move ( subtreeWildcard ), std::move ( variablesBar ) ) {
314 setContent ( std::move ( data ) );
315}
316
317template < class SymbolType >
319}
320
321template < class SymbolType >
322PrefixRankedBarPattern < SymbolType >::PrefixRankedBarPattern ( SymbolType barBase, common::ranked_symbol < SymbolType > variablesBar, const RankedPattern < SymbolType > & tree ) : PrefixRankedBarPattern ( TreeAuxiliary::computeBars ( tree.getAlphabet ( ), barBase ) + ext::set < common::ranked_symbol < SymbolType > > { variablesBar }, variablesBar, tree.getSubtreeWildcard ( ), tree.getAlphabet ( ) + TreeAuxiliary::computeBars ( tree.getAlphabet ( ), barBase ) + ext::set < common::ranked_symbol < SymbolType > > { variablesBar, tree.getSubtreeWildcard ( ) }, TreeAuxiliary::treeToPrefix ( tree.getContent ( ), tree.getSubtreeWildcard ( ), barBase, variablesBar ) ) {
323}
324
325template < class SymbolType >
326PrefixRankedBarPattern < SymbolType >::PrefixRankedBarPattern ( const PrefixRankedBarTree < SymbolType > & tree ) : PrefixRankedBarPattern ( tree.getBars() + ext::set < common::ranked_symbol < SymbolType > > { alphabet::VariablesBarSymbol::instance < common::ranked_symbol < SymbolType > > ( ) }, alphabet::VariablesBarSymbol::instance < common::ranked_symbol < SymbolType > > ( ), alphabet::WildcardSymbol::instance < common::ranked_symbol < SymbolType > > ( ), tree.getAlphabet ( ) + ext::set < common::ranked_symbol < SymbolType > > { alphabet::VariablesBarSymbol::instance < common::ranked_symbol < SymbolType > > ( ), alphabet::WildcardSymbol::instance < common::ranked_symbol < SymbolType > > ( ) }, tree.getContent ( ) ) {
327}
328
329template < class SymbolType >
330PrefixRankedBarPattern < SymbolType >::PrefixRankedBarPattern ( const RankedPattern < SymbolType > & tree ) : PrefixRankedBarPattern ( alphabet::BarSymbol::instance < SymbolType > ( ), alphabet::VariablesBarSymbol::instance < common::ranked_symbol < SymbolType > > ( ), tree ) {
331}
332
333template < class SymbolType >
335 return this->m_Data;
336}
337
338template < class SymbolType >
340 return std::move ( this->m_Data );
341}
342
343template < class SymbolType >
345 arityChecksum ( data );
346
347 ext::set < common::ranked_symbol < SymbolType > > minimalAlphabet ( data.begin ( ), data.end ( ) );
348 std::set_difference ( minimalAlphabet.begin ( ), minimalAlphabet.end ( ), getAlphabet ( ).begin ( ), getAlphabet ( ).end ( ), ext::callback_iterator ( [ ] ( const common::ranked_symbol < SymbolType > & ) {
349 throw TreeException ( "Input symbols not in the alphabet." );
350 } ) );
351
352 this->m_Data = std::move ( data );
353}
354
355template < class SymbolType >
357 struct Data {
358 int terminals;
359 int bars;
360 int types;
361 };
362
363 Data accRes = std::accumulate ( data.begin ( ), data.end ( ), Data { 1, 1, 0 }, [ * this ] ( const Data & current, const common::ranked_symbol < SymbolType > & symbol ) {
364 if ( getBars ( ).contains ( symbol ) || symbol == getVariablesBar ( ) )
365 return Data { current.terminals, static_cast < int > ( current.bars + symbol.getRank ( ) - 1 ), current.types - 1 };
366 else
367 return Data { static_cast < int > ( current.terminals + symbol.getRank ( ) - 1 ), current.bars, current.types + 1 };
368 } );
369
370 if ( accRes.terminals != 0 || accRes.bars != 0 || accRes.types != 0 )
371 throw TreeException ( "The string does not form a tree" );
372
373 for ( unsigned i = 1; i < data.size ( ); ++ i )
374 if ( data [ i - 1 ] == getSubtreeWildcard ( ) && data [ i ] != getVariablesBar ( ) )
375 throw TreeException ( "Inconsystency of SubtreeWildcard and variablesBar" );
376}
377
378template < class SymbolType >
380 return this->m_Data.empty ( );
381}
382
383} /* namespace tree */
384
385namespace core {
386
392template < class SymbolType >
393class SetConstraint< tree::PrefixRankedBarPattern < SymbolType >, common::ranked_symbol < SymbolType >, tree::GeneralAlphabet > {
394public:
405
406 return std::find ( content.begin ( ), content.end ( ), symbol ) != content.end ( ) || pattern.template accessComponent < tree::VariablesBarSymbol > ( ).get ( ) == symbol || pattern.template accessComponent < tree::BarSymbols > ( ).get ( ).count ( symbol ) || pattern.template accessComponent < tree::SubtreeWildcard > ( ).get ( ) == symbol;
407 }
408
418 return true;
419 }
420
428 }
429};
430
436template < class SymbolType >
437class SetConstraint< tree::PrefixRankedBarPattern < SymbolType >, common::ranked_symbol < SymbolType >, tree::BarSymbols > {
438public:
449
450 return std::find ( content.begin ( ), content.end ( ), symbol ) != content.end ( ) || pattern.template accessComponent < tree::VariablesBarSymbol > ( ).get ( ) == symbol;
451 }
452
462 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
463 }
464
472 }
473};
474
480template < class SymbolType >
481class ElementConstraint< tree::PrefixRankedBarPattern < SymbolType >, common::ranked_symbol < SymbolType >, tree::SubtreeWildcard > {
482public:
492 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
493}
494
504 if( symbol.getRank() != 0 )
505 throw tree::TreeException ( "SubtreeWildcard symbol has nonzero arity" );
506 }
507};
508
514template < class SymbolType >
515class ElementConstraint< tree::PrefixRankedBarPattern < SymbolType >, common::ranked_symbol < SymbolType >, tree::VariablesBarSymbol > {
516public:
526 return pattern.template accessComponent < tree::BarSymbols > ( ).get ( ).count ( symbol );
527 }
528
538 if( symbol.getRank ( ) != 0 )
539 throw tree::TreeException ( "VariablesBarSymbol has nonzero arity" );
540 }
541};
542
548template < class SymbolType >
549struct normalize < tree::PrefixRankedBarPattern < SymbolType > > {
551 common::ranked_symbol < DefaultSymbolType > variablesBars = alphabet::SymbolNormalize::normalizeRankedSymbol ( std::move ( value ).getVariablesBar ( ) );
552 common::ranked_symbol < DefaultSymbolType > wildcard = alphabet::SymbolNormalize::normalizeRankedSymbol ( std::move ( value ).getSubtreeWildcard ( ) );
556
557 return tree::PrefixRankedBarPattern < > ( std::move ( bars ), std::move ( variablesBars ), std::move ( wildcard ), std::move ( alphabet ), std::move ( content ) );
558 }
559};
560
561} /* namespace core */
562
563extern template class tree::PrefixRankedBarPattern < >;
564
static ext::vector< common::ranked_symbol< DefaultSymbolType > > normalizeRankedSymbols(ext::vector< common::ranked_symbol< SymbolType > > &&symbols)
Definition: SymbolNormalize.h:113
static common::ranked_symbol< DefaultSymbolType > normalizeRankedSymbol(common::ranked_symbol< SymbolType > &&symbol)
Definition: SymbolNormalize.h:81
static ext::set< common::ranked_symbol< DefaultSymbolType > > normalizeRankedAlphabet(ext::set< common::ranked_symbol< SymbolType > > &&symbols)
Definition: SymbolNormalize.h:59
static Base instance()
Factory for the symbol construction of the symbol based on given type.
Definition: WildcardSymbol.h:83
Definition: ranked_symbol.hpp:20
const size_t & getRank() const &
Definition: ranked_symbol.hpp:83
Definition: components.hpp:181
static bool available(const tree::PrefixRankedBarPattern< SymbolType > &pattern, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:491
static void valid(const tree::PrefixRankedBarPattern< SymbolType > &, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:503
static bool available(const tree::PrefixRankedBarPattern< SymbolType > &pattern, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:525
static void valid(const tree::PrefixRankedBarPattern< SymbolType > &, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:537
Definition: components.hpp:25
static bool available(const tree::PrefixRankedBarPattern< SymbolType > &, const common::ranked_symbol< SymbolType > &)
Definition: PrefixRankedBarPattern.h:417
static void valid(const tree::PrefixRankedBarPattern< SymbolType > &, const common::ranked_symbol< SymbolType > &)
Definition: PrefixRankedBarPattern.h:427
static bool used(const tree::PrefixRankedBarPattern< SymbolType > &pattern, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:403
static bool available(const tree::PrefixRankedBarPattern< SymbolType > &pattern, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:461
static bool used(const tree::PrefixRankedBarPattern< SymbolType > &pattern, const common::ranked_symbol< SymbolType > &symbol)
Definition: PrefixRankedBarPattern.h:447
static void valid(const tree::PrefixRankedBarPattern< SymbolType > &, const common::ranked_symbol< SymbolType > &)
Definition: PrefixRankedBarPattern.h:471
Definition: setComponents.hpp:26
Output iterator calling a callback function on assignment.
Definition: iterator.hpp:923
Definition: ostream.h:14
Definition: set.hpp:44
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
auto end() &
Inherited behavior of end for non-const instance.
Definition: set.hpp:129
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
Linear string.
Definition: LinearString.h:57
Tree pattern represented as linear sequece as result of preorder traversal with additional bar symbol...
Definition: PrefixRankedBarPattern.h:85
PrefixRankedBarPattern(ext::set< common::ranked_symbol< SymbolType > > bars, common::ranked_symbol< SymbolType > variablesBar, common::ranked_symbol< SymbolType > subtreeWildcard, ext::set< common::ranked_symbol< SymbolType > > alphabet, ext::vector< common::ranked_symbol< SymbolType > > data)
Creates a new instance of the pattern with concrete alphabet, bars, content, wildcard,...
Definition: PrefixRankedBarPattern.h:313
void extendBars(const ext::set< common::ranked_symbol< SymbolType > > &bars)
Definition: PrefixRankedBarPattern.h:193
const common::ranked_symbol< SymbolType > & getVariablesBar() const &
Definition: PrefixRankedBarPattern.h:220
bool operator==(const PrefixRankedBarPattern &other) const
Definition: PrefixRankedBarPattern.h:279
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedBarPattern.h:202
const ext::set< common::ranked_symbol< SymbolType > > & getAlphabet() const &
Definition: PrefixRankedBarPattern.h:148
void extendAlphabet(const ext::set< common::ranked_symbol< SymbolType > > &symbols)
Definition: PrefixRankedBarPattern.h:166
common::ranked_symbol< SymbolType > && getVariablesBar() &&
Definition: PrefixRankedBarPattern.h:229
common::ranked_symbol< SymbolType > && getSubtreeWildcard() &&
Definition: PrefixRankedBarPattern.h:211
bool isEmpty() const
Definition: PrefixRankedBarPattern.h:379
const ext::set< common::ranked_symbol< SymbolType > > & getBars() const &
Definition: PrefixRankedBarPattern.h:175
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarPattern.h:334
friend ext::ostream & operator<<(ext::ostream &out, const PrefixRankedBarPattern &instance)
Definition: PrefixRankedBarPattern.h:291
void setContent(ext::vector< common::ranked_symbol< SymbolType > > data)
Definition: PrefixRankedBarPattern.h:344
ext::set< common::ranked_symbol< SymbolType > > && getAlphabet() &&
Definition: PrefixRankedBarPattern.h:157
ext::set< common::ranked_symbol< SymbolType > > && getBars() &&
Definition: PrefixRankedBarPattern.h:184
Tree structure represented as linear sequece as result of preorder traversal with additional bar symb...
Definition: PrefixRankedBarTree.h:78
Tree pattern represented in its natural representation. The representation is so called ranked,...
Definition: RankedPattern.h:72
static ext::set< common::ranked_symbol< SymbolType > > computeBars(const ext::set< common::ranked_symbol< SymbolType > > &alphabet, const SymbolType &barBase)
Definition: TreeAuxiliary.h:89
static ext::vector< common::ranked_symbol< SymbolType > > treeToPrefix(const ext::tree< common::ranked_symbol< SymbolType > > &tree)
Definition: TreeAuxiliary.h:185
Definition: TreeException.h:15
Definition: BarSymbol.cpp:12
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
Definition: Permutation.hpp:18
Definition: normalize.hpp:10
Definition: sigHandler.cpp:20
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
auto begin(Container &&cont) -> decltype(std::forward(cont).begin())
Definition: iterator.hpp:900
void end()
Definition: measurements.cpp:19
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
Definition: BackwardOccurrenceTest.h:17
static tree::PrefixRankedBarPattern< > eval(tree::PrefixRankedBarPattern< SymbolType > &&value)
Definition: PrefixRankedBarPattern.h:550
Definition: normalize.hpp:13