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
UnrankedNonlinearPattern.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 UnrankedNonlinearPattern;
32
33} /* namespace tree */
34
35
36#include <ext/iostream>
37#include <ext/algorithm>
38
39#include <alib/string>
40#include <alib/set>
41#include <alib/tree>
42
43#include <core/components.hpp>
44
45#include <tree/TreeException.h>
47
48#include <core/normalize.hpp>
50
52#include <alphabet/GapSymbol.h>
53
54namespace tree {
55
56class GeneralAlphabet;
57class SubtreeWildcard;
58class SubtreeGap;
59class NonlinearAlphabet;
60
74template < class SymbolType >
75class UnrankedNonlinearPattern final : public core::Components < UnrankedNonlinearPattern < SymbolType >, ext::set < SymbolType >, component::Set, std::tuple < GeneralAlphabet, NonlinearAlphabet >, SymbolType, component::Value, std::tuple < SubtreeWildcard, SubtreeGap > > {
80
88 void checkAlphabet ( const ext::tree < SymbolType > & data ) const;
89
90public:
100 explicit UnrankedNonlinearPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set < SymbolType > nonlinearVariables, ext::set < SymbolType > alphabet, ext::tree < SymbolType > pattern );
101
110 explicit UnrankedNonlinearPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set < SymbolType > nonlinearVariables, ext::tree < SymbolType > pattern );
111
119 explicit UnrankedNonlinearPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::tree < SymbolType > pattern );
120
127
134 return this->template accessComponent < GeneralAlphabet > ( ).get ( );
135 }
136
143 return std::move ( this->template accessComponent < GeneralAlphabet > ( ).get ( ) );
144 }
145
151 void extendAlphabet ( const ext::set < SymbolType > & symbols ) {
152 this->template accessComponent < GeneralAlphabet > ( ).add ( symbols );
153 }
154
160 const SymbolType & getSubtreeWildcard ( ) const & {
161 return this->template accessComponent < SubtreeWildcard > ( ).get ( );
162 }
163
170 return std::move ( this->template accessComponent < SubtreeWildcard > ( ).get ( ) );
171 }
172
178 const SymbolType & getSubtreeGap ( ) const & {
179 return this->template accessComponent < SubtreeGap > ( ).get ( );
180 }
181
188 return std::move ( this->template accessComponent < SubtreeGap > ( ).get ( ) );
189 }
190
197 return this->template accessComponent < NonlinearAlphabet > ( ).get ( );
198 }
199
206 return std::move ( this->template accessComponent < NonlinearAlphabet > ( ).get ( ) );
207 }
208
214 const ext::tree < SymbolType > & getContent ( ) const &;
215
221 ext::tree < SymbolType > && getContent ( ) &&;
222
230 void setTree ( ext::tree < SymbolType > pattern );
231
239 auto operator <=> ( const UnrankedNonlinearPattern & other ) const {
240 return std::tie ( m_content, getAlphabet(), getSubtreeWildcard(), getNonlinearVariables() ) <=> std::tie ( other.m_content, other.getAlphabet(), other.getSubtreeWildcard(), getNonlinearVariables() );
241 }
242
250 bool operator == ( const UnrankedNonlinearPattern & other ) const {
251 return std::tie ( m_content, getAlphabet(), getSubtreeWildcard(), getNonlinearVariables() ) == std::tie ( other.m_content, other.getAlphabet(), other.getSubtreeWildcard(), getNonlinearVariables() );
252 }
253
263 out << "(UnrankedNonlinearPattern ";
264 out << " alphabet = " << instance.getAlphabet ( );
265 out << " content = " << instance.getContent ( );
266 out << " nonlinearVariables = " << instance.getNonlinearVariables ( );
267 out << " subtreeWildcard = " << instance.getSubtreeWildcard ( );
268 out << " subtreeGap = " << instance.getSubtreeGap ( );
269 out << ")";
270 return out;
271 }
272
278 void nicePrint ( ext::ostream & out ) const;
279};
280
281template < class SymbolType >
282UnrankedNonlinearPattern < SymbolType >::UnrankedNonlinearPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set < SymbolType > nonlinearVariables, ext::set < SymbolType > alphabet, ext::tree < SymbolType > pattern ) : core::Components < UnrankedNonlinearPattern, ext::set < SymbolType >, component::Set, std::tuple < GeneralAlphabet, NonlinearAlphabet >, SymbolType, component::Value, std::tuple < SubtreeWildcard, SubtreeGap > > ( std::move ( alphabet ), std::move ( nonlinearVariables ), std::move ( subtreeWildcard ), std::move ( subtreeGap ) ), m_content ( std::move ( pattern ) ) {
283 checkAlphabet ( m_content );
284}
285
286template < class SymbolType >
287UnrankedNonlinearPattern < SymbolType >::UnrankedNonlinearPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set < SymbolType > nonlinearVariables, ext::tree < SymbolType > pattern ) : UnrankedNonlinearPattern ( subtreeWildcard, subtreeGap, nonlinearVariables, ext::set < SymbolType > ( pattern.prefix_begin ( ), pattern.prefix_end ( ) ) + nonlinearVariables + ext::set < SymbolType > { subtreeWildcard, subtreeGap }, pattern ) {
288}
289
290template < class SymbolType >
292}
293
294template < class SymbolType >
295UnrankedNonlinearPattern < SymbolType >::UnrankedNonlinearPattern ( const RankedNonlinearPattern < SymbolType > & other ) : UnrankedNonlinearPattern ( other.getSubtreeWildcard ( ).getSymbol ( ), alphabet::GapSymbol::instance < SymbolType > ( ), TreeAuxiliary::unrankSymbols ( other.getAlphabet ( ) ) + ext::set < SymbolType > { alphabet::GapSymbol::instance < SymbolType > ( ) }, TreeAuxiliary::rankedToUnranked ( other.getContent ( ) ) ) {
296}
297
298template < class SymbolType >
300 return m_content;
301}
302
303template < class SymbolType >
305 return std::move ( m_content );
306}
307
308template < class SymbolType >
310 ext::set < SymbolType > minimalAlphabet ( data.prefix_begin ( ), data.prefix_end ( ) );
311 std::set_difference ( minimalAlphabet.begin ( ), minimalAlphabet.end ( ), getAlphabet ( ).begin ( ), getAlphabet ( ).end ( ), ext::callback_iterator ( [ ] ( const SymbolType & ) {
312 throw TreeException ( "Input symbols not in the alphabet." );
313 } ) );
314}
315
316template < class SymbolType >
318 checkAlphabet ( pattern );
319
320 this->m_content = std::move ( pattern );
321}
322
323template < class SymbolType >
325 m_content.nicePrint ( out );
326}
327
328} /* namespace tree */
329
330namespace core {
331
337template < class SymbolType >
338class SetConstraint< tree::UnrankedNonlinearPattern < SymbolType >, SymbolType, tree::GeneralAlphabet > {
339public:
348 static bool used ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol ) {
349 const ext::tree<SymbolType>& m_content = pattern.getContent ( );
350 return std::find(m_content.prefix_begin(), m_content.prefix_end(), symbol) != m_content.prefix_end() || pattern.template accessComponent < tree::SubtreeWildcard > ( ).get ( ) == symbol || pattern.template accessComponent < tree::NonlinearAlphabet > ( ).get ( ).count ( symbol );
351 }
352
362 return true;
363 }
364
372 }
373};
374
380template < class SymbolType >
381class SetConstraint< tree::UnrankedNonlinearPattern < SymbolType >, SymbolType, tree::NonlinearAlphabet > {
382public:
392 return false;
393 }
394
403 static bool available ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol ) {
404 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
405 }
406
415 static void valid ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol) {
416 if ( pattern.template accessComponent < tree::SubtreeWildcard > ( ).get ( ) == symbol )
417 throw tree::TreeException ( "Symbol " + ext::to_string ( symbol ) + "cannot be set as nonlinear variable since it is already subtree wildcard" );
418 }
419};
420
426template < class SymbolType >
427class ElementConstraint< tree::UnrankedNonlinearPattern < SymbolType >, SymbolType, tree::SubtreeWildcard > {
428public:
437 static bool available ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol ) {
438 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
439 }
440
449 static void valid ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol) {
450 if ( pattern.template accessComponent < tree::NonlinearAlphabet > ( ).get ( ).count ( symbol ) )
451 throw tree::TreeException ( "Symbol " + ext::to_string ( symbol ) + "cannot be set as subtree wildcard since it is already nonlinear variable" );
452 }
453};
454
460template < class SymbolType >
461class ElementConstraint< tree::UnrankedNonlinearPattern < SymbolType >, SymbolType, tree::SubtreeGap > {
462public:
471 static bool available ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol ) {
472 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
473 }
474
483 static void valid ( const tree::UnrankedNonlinearPattern < SymbolType > & pattern, const SymbolType & symbol) {
484 if ( pattern.template accessComponent < tree::NonlinearAlphabet > ( ).get ( ).count ( symbol ) )
485 throw tree::TreeException ( "Symbol " + ext::to_string ( symbol ) + "cannot be set as subtree wildcard since it is already nonlinear variable" );
486 }
487};
488
494template < class SymbolType >
495struct normalize < tree::UnrankedNonlinearPattern < SymbolType > > {
497 DefaultSymbolType wildcard = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getSubtreeWildcard ( ) );
498 DefaultSymbolType gap = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getSubtreeGap ( ) );
499 ext::set < DefaultSymbolType > nonlinearAlphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonlinearVariables ( ) );
501 ext::tree < DefaultSymbolType > content = tree::TreeNormalize::normalizeTree ( std::move ( value ).getContent ( ) );
502
503 return tree::UnrankedNonlinearPattern < > ( std::move ( wildcard ), std::move ( gap ), std::move ( nonlinearAlphabet ), std::move ( alphabet ), std::move ( content ) );
504 }
505};
506
507} /* namespace core */
508
509extern template class tree::UnrankedNonlinearPattern < >;
510
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static DefaultSymbolType normalizeSymbol(SymbolType &&symbol)
Definition: SymbolNormalize.h:68
Definition: components.hpp:181
static bool available(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:437
static void valid(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:449
static bool available(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:471
static void valid(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:483
Definition: components.hpp:25
static void valid(const tree::UnrankedNonlinearPattern< SymbolType > &, const SymbolType &)
Definition: UnrankedNonlinearPattern.h:371
static bool available(const tree::UnrankedNonlinearPattern< SymbolType > &, const SymbolType &)
Definition: UnrankedNonlinearPattern.h:361
static bool used(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:348
static void valid(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:415
static bool used(const tree::UnrankedNonlinearPattern< SymbolType > &, const SymbolType &)
Definition: UnrankedNonlinearPattern.h:391
static bool available(const tree::UnrankedNonlinearPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnrankedNonlinearPattern.h:403
Definition: setComponents.hpp:26
Output iterator calling a callback function on assignment.
Definition: iterator.hpp:923
Definition: ostream.h:14
Definition: set.hpp:44
Class introducing a tree with interface trying to be close to the interface of standard library conta...
Definition: tree.hpp:52
const_prefix_iterator prefix_begin() const
Getter of the prefix iterator to the root node.
Definition: tree.hpp:904
const_prefix_iterator prefix_end() const
Getter of the prefix iterator one after the last node in the prefix traversal.
Definition: tree.hpp:914
Definition: Object.h:16
Nonlinear tree pattern represented in its natural representation. The representation is so called ran...
Definition: RankedNonlinearPattern.h:74
static ext::set< SymbolType > unrankSymbols(const ext::set< common::ranked_symbol< SymbolType > > &alphabet)
Definition: TreeAuxiliary.h:82
static ext::tree< SymbolType > rankedToUnranked(const ext::tree< common::ranked_symbol< SymbolType > > &tree)
Definition: TreeAuxiliary.h:151
Definition: TreeException.h:15
static ext::tree< DefaultSymbolType > normalizeTree(ext::tree< SymbolType > &&tree)
Definition: TreeNormalize.h:29
Nonlinear tree pattern represented in its natural representation. The representation is so called unr...
Definition: UnrankedNonlinearPattern.h:75
void nicePrint(ext::ostream &out) const
Definition: UnrankedNonlinearPattern.h:324
ext::set< SymbolType > && getNonlinearVariables() &&
Definition: UnrankedNonlinearPattern.h:205
ext::set< SymbolType > && getAlphabet() &&
Definition: UnrankedNonlinearPattern.h:142
SymbolType && getSubtreeWildcard() &&
Definition: UnrankedNonlinearPattern.h:169
const ext::set< SymbolType > & getNonlinearVariables() const &
Definition: UnrankedNonlinearPattern.h:196
const SymbolType & getSubtreeGap() const &
Definition: UnrankedNonlinearPattern.h:178
const ext::set< SymbolType > & getAlphabet() const &
Definition: UnrankedNonlinearPattern.h:133
void setTree(ext::tree< SymbolType > pattern)
Definition: UnrankedNonlinearPattern.h:317
UnrankedNonlinearPattern(SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set< SymbolType > nonlinearVariables, ext::set< SymbolType > alphabet, ext::tree< SymbolType > pattern)
Creates a new instance of the pattern with concrete alphabet, content, wildcard, and nonlinear variab...
Definition: UnrankedNonlinearPattern.h:282
friend ext::ostream & operator<<(ext::ostream &out, const UnrankedNonlinearPattern &instance)
Definition: UnrankedNonlinearPattern.h:262
void extendAlphabet(const ext::set< SymbolType > &symbols)
Definition: UnrankedNonlinearPattern.h:151
bool operator==(const UnrankedNonlinearPattern &other) const
Definition: UnrankedNonlinearPattern.h:250
SymbolType && getSubtreeGap() &&
Definition: UnrankedNonlinearPattern.h:187
const SymbolType & getSubtreeWildcard() const &
Definition: UnrankedNonlinearPattern.h:160
const ext::tree< SymbolType > & getContent() const &
Definition: UnrankedNonlinearPattern.h:299
Definition: BarSymbol.cpp:12
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
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
std::string to_string(const T &value)
To string method designated for objects that can be casted to string.
Definition: string.hpp:131
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::UnrankedNonlinearPattern< > eval(tree::UnrankedNonlinearPattern< SymbolType > &&value)
Definition: UnrankedNonlinearPattern.h:496
Definition: normalize.hpp:13