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
UnorderedUnrankedPattern.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 UnorderedUnrankedPattern;
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
51#include "UnrankedPattern.h"
52#include <alphabet/GapSymbol.h>
53
54namespace tree {
55
56class GeneralAlphabet;
57class SubtreeWildcard;
58class SubtreeGap;
59
72template < class SymbolType >
73class UnorderedUnrankedPattern final : public core::Components < UnorderedUnrankedPattern < SymbolType >, ext::set < SymbolType >, component::Set, GeneralAlphabet, SymbolType, component::Value, std::tuple < SubtreeWildcard, SubtreeGap > > {
78
86 void checkAlphabet ( const ext::tree < SymbolType > & data ) const;
87
88public:
97
104 explicit UnorderedUnrankedPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::tree < SymbolType > pattern );
105
112
119 return this->template accessComponent < GeneralAlphabet > ( ).get ( );
120 }
121
128 return std::move ( this->template accessComponent < GeneralAlphabet > ( ).get ( ) );
129 }
130
136 void extendAlphabet ( const ext::set < SymbolType > & symbols ) {
137 this->template accessComponent < GeneralAlphabet > ( ).add ( symbols );
138 }
139
145 const SymbolType & getSubtreeWildcard ( ) const & {
146 return this->template accessComponent < SubtreeWildcard > ( ).get ( );
147 }
148
155 return std::move ( this->template accessComponent < SubtreeWildcard > ( ).get ( ) );
156 }
157
163 const SymbolType & getSubtreeGap ( ) const & {
164 return this->template accessComponent < SubtreeGap > ( ).get ( );
165 }
166
173 return std::move ( this->template accessComponent < SubtreeGap > ( ).get ( ) );
174 }
175
181 const ext::tree < SymbolType > & getContent ( ) const &;
182
188 ext::tree < SymbolType > && getContent ( ) &&;
189
197 void setTree ( ext::tree < SymbolType > pattern );
198
206 auto operator <=> ( const UnorderedUnrankedPattern & other ) const {
207 return std::tie ( getAlphabet ( ), getContent ( ), getSubtreeWildcard ( ), getSubtreeGap ( ) ) <=> std::tie ( other.getAlphabet ( ), other.getContent ( ), other.getSubtreeWildcard ( ), other.getSubtreeGap ( ) );
208 }
209
217 bool operator == ( const UnorderedUnrankedPattern & other ) const {
218 return std::tie ( getAlphabet ( ), getContent ( ), getSubtreeWildcard ( ), getSubtreeGap ( ) ) == std::tie ( other.getAlphabet ( ), other.getContent ( ), other.getSubtreeWildcard ( ), other.getSubtreeGap ( ) );
219 }
220
230 out << "(UnorderedUnrankedPattern ";
231 out << "alphabet = " << instance.getAlphabet ( );
232 out << "content = " << instance.getContent ( );
233 out << "subtreeWildcard = " << instance.getSubtreeWildcard ( );
234 out << "subtreeGap = " << instance.getSubtreeGap ( );
235 out << ")";
236 return out;
237 }
238
244 void nicePrint ( ext::ostream & os ) const;
245};
246
247template < class SymbolType >
248UnorderedUnrankedPattern < SymbolType >::UnorderedUnrankedPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set < SymbolType > alphabet, ext::tree < SymbolType > pattern ) : core::Components < UnorderedUnrankedPattern, ext::set < SymbolType >, component::Set, GeneralAlphabet, SymbolType, component::Value, std::tuple < SubtreeWildcard, SubtreeGap > > ( std::move ( alphabet ), std::move ( subtreeWildcard ), std::move ( subtreeGap ) ), m_content ( std::move ( pattern ) ) {
249 checkAlphabet ( m_content );
250}
251
252template < class SymbolType >
253UnorderedUnrankedPattern < SymbolType >::UnorderedUnrankedPattern ( SymbolType subtreeWildcard, SymbolType subtreeGap, ext::tree < SymbolType > pattern ) : UnorderedUnrankedPattern ( subtreeWildcard, subtreeGap, ext::set < SymbolType > ( pattern.prefix_begin ( ), pattern.prefix_end ( ) ) + ext::set < SymbolType > { subtreeWildcard, subtreeGap }, pattern ) {
254}
255
256template < class SymbolType >
257UnorderedUnrankedPattern < SymbolType >::UnorderedUnrankedPattern ( const UnrankedPattern < SymbolType > & other ) : UnorderedUnrankedPattern ( other.getSubtreeWildcard ( ), other.getSubtreeGap ( ), other.getAlphabet ( ), other.getContent ( ) ) {
258}
259
260template < class SymbolType >
262 return m_content;
263}
264
265template < class SymbolType >
267 return std::move ( m_content );
268}
269
270template < class SymbolType >
272 ext::set < SymbolType > minimalAlphabet ( data.prefix_begin ( ), data.prefix_end ( ) );
273 std::set_difference ( minimalAlphabet.begin ( ), minimalAlphabet.end ( ), getAlphabet ( ).begin ( ), getAlphabet ( ).end ( ), ext::callback_iterator ( [ ] ( const SymbolType & ) {
274 throw TreeException ( "Input symbols not in the alphabet." );
275 } ) );
276}
277
278template < class SymbolType >
280 checkAlphabet ( pattern );
281
282 this->m_content = std::move ( pattern );
283}
284
285template < class SymbolType >
287 m_content.nicePrint ( os );
288}
289
290} /* namespace tree */
291
292namespace core {
293
299template < class SymbolType >
300class SetConstraint< tree::UnorderedUnrankedPattern < SymbolType >, SymbolType, tree::GeneralAlphabet > {
301public:
310 static bool used ( const tree::UnorderedUnrankedPattern < SymbolType > & pattern, const SymbolType & symbol ) {
311 const ext::tree<SymbolType>& m_content = pattern.getContent ( );
312 return std::find(m_content.prefix_begin(), m_content.prefix_end(), symbol) != m_content.prefix_end() || pattern.template accessComponent < tree::SubtreeWildcard > ( ).get ( ) == symbol;
313 }
314
324 return true;
325 }
326
334 }
335};
336
342template < class SymbolType >
343class ElementConstraint< tree::UnorderedUnrankedPattern < SymbolType >, SymbolType, tree::SubtreeWildcard > {
344public:
353 static bool available ( const tree::UnorderedUnrankedPattern < SymbolType > & pattern, const SymbolType & symbol ) {
354 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
355 }
356
366 }
367};
368
374template < class SymbolType >
375class ElementConstraint< tree::UnorderedUnrankedPattern < SymbolType >, SymbolType, tree::SubtreeGap > {
376public:
385 static bool available ( const tree::UnorderedUnrankedPattern < SymbolType > & pattern, const SymbolType & symbol ) {
386 return pattern.template accessComponent < tree::GeneralAlphabet > ( ).get ( ).count ( symbol );
387 }
388
398 }
399};
400
406template < class SymbolType >
407struct normalize < tree::UnorderedUnrankedPattern < SymbolType > > {
409 DefaultSymbolType wildcard = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getSubtreeWildcard ( ) );
410 DefaultSymbolType gap = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getSubtreeGap ( ) );
412 ext::tree < DefaultSymbolType > content = tree::TreeNormalize::normalizeTree ( std::move ( value ).getContent ( ) );
413
414 return tree::UnorderedUnrankedPattern < > ( std::move ( wildcard ), std::move ( gap ), std::move ( alphabet ), std::move ( content ) );
415 }
416};
417
418} /* namespace core */
419
420extern template class tree::UnorderedUnrankedPattern < >;
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::UnorderedUnrankedPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnorderedUnrankedPattern.h:353
static void valid(const tree::UnorderedUnrankedPattern< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedPattern.h:365
static void valid(const tree::UnorderedUnrankedPattern< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedPattern.h:397
static bool available(const tree::UnorderedUnrankedPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnorderedUnrankedPattern.h:385
Definition: components.hpp:25
static bool used(const tree::UnorderedUnrankedPattern< SymbolType > &pattern, const SymbolType &symbol)
Definition: UnorderedUnrankedPattern.h:310
static void valid(const tree::UnorderedUnrankedPattern< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedPattern.h:333
static bool available(const tree::UnorderedUnrankedPattern< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedPattern.h:323
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
Definition: TreeException.h:15
static ext::tree< DefaultSymbolType > normalizeTree(ext::tree< SymbolType > &&tree)
Definition: TreeNormalize.h:29
Tree pattern represented in its natural representation. The representation is so called unranked,...
Definition: UnorderedUnrankedPattern.h:73
const SymbolType & getSubtreeGap() const &
Definition: UnorderedUnrankedPattern.h:163
const ext::tree< SymbolType > & getContent() const &
Definition: UnorderedUnrankedPattern.h:261
void extendAlphabet(const ext::set< SymbolType > &symbols)
Definition: UnorderedUnrankedPattern.h:136
bool operator==(const UnorderedUnrankedPattern &other) const
Definition: UnorderedUnrankedPattern.h:217
friend ext::ostream & operator<<(ext::ostream &out, const UnorderedUnrankedPattern &instance)
Definition: UnorderedUnrankedPattern.h:229
ext::set< SymbolType > && getAlphabet() &&
Definition: UnorderedUnrankedPattern.h:127
SymbolType && getSubtreeGap() &&
Definition: UnorderedUnrankedPattern.h:172
void nicePrint(ext::ostream &os) const
Definition: UnorderedUnrankedPattern.h:286
const SymbolType & getSubtreeWildcard() const &
Definition: UnorderedUnrankedPattern.h:145
UnorderedUnrankedPattern(SymbolType subtreeWildcard, SymbolType subtreeGap, ext::set< SymbolType > alphabet, ext::tree< SymbolType > pattern)
Creates a new instance of the pattern with concrete alphabet, content, and wildcard.
Definition: UnorderedUnrankedPattern.h:248
SymbolType && getSubtreeWildcard() &&
Definition: UnorderedUnrankedPattern.h:154
const ext::set< SymbolType > & getAlphabet() const &
Definition: UnorderedUnrankedPattern.h:118
void setTree(ext::tree< SymbolType > pattern)
Definition: UnorderedUnrankedPattern.h:279
Tree pattern represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedPattern.h:73
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
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::UnorderedUnrankedPattern< > eval(tree::UnorderedUnrankedPattern< SymbolType > &&value)
Definition: UnorderedUnrankedPattern.h:408
Definition: normalize.hpp:13