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
UnorderedUnrankedTree.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 UnorderedUnrankedTree;
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 "UnrankedTree.h"
52
53namespace tree {
54
55class GeneralAlphabet;
56
68template < class SymbolType >
69class UnorderedUnrankedTree final : public core::Components < UnorderedUnrankedTree < SymbolType >, ext::set < SymbolType >, component::Set, GeneralAlphabet > {
74
82 void checkAlphabet ( const ext::tree < SymbolType > & data ) const;
83
84public:
92
99
105 explicit UnorderedUnrankedTree ( const UnrankedTree < SymbolType > & other );
106
113 return this->template accessComponent < GeneralAlphabet > ( ).get ( );
114 }
115
122 return std::move ( this->template accessComponent < GeneralAlphabet > ( ).get ( ) );
123 }
124
130 void extendAlphabet ( const ext::set < SymbolType > & symbols ) {
131 this->template accessComponent < GeneralAlphabet > ( ).add ( symbols );
132 }
133
139 const ext::tree < SymbolType > & getContent ( ) const &;
140
146 ext::tree < SymbolType > && getContent ( ) &&;
147
155 void setTree ( ext::tree < SymbolType > data );
156
164 auto operator <=> ( const UnorderedUnrankedTree & other ) const {
165 return std::tie ( getAlphabet ( ), getContent ( ) ) <=> std::tie ( other.getAlphabet ( ), other.getContent ( ) );
166 }
167
175 bool operator == ( const UnorderedUnrankedTree & other ) const {
176 return std::tie ( getAlphabet ( ), getContent ( ) ) == std::tie ( other.getAlphabet ( ), other.getContent ( ) );
177 }
178
187 friend ext::ostream & operator << ( ext::ostream & out, const UnorderedUnrankedTree & instance ) {
188 out << "(UnorderedUnrankedTree ";
189 out << "alphabet = " << instance.getAlphabet ( );
190 out << "content = " << instance.getContent ( );
191 out << ")";
192 return out;
193 }
194
200 void nicePrint ( ext::ostream & os ) const;
201};
202
203template < class SymbolType >
205 checkAlphabet ( m_content );
206}
207
208template < class SymbolType >
210}
211
212template < class SymbolType >
214}
215
216template < class SymbolType >
218 return m_content;
219}
220
221template < class SymbolType >
223 return std::move ( m_content );
224}
225
226template < class SymbolType >
228 ext::set < SymbolType > minimalAlphabet ( data.prefix_begin ( ), data.prefix_end ( ) );
229 std::set_difference ( minimalAlphabet.begin ( ), minimalAlphabet.end ( ), getAlphabet ( ).begin ( ), getAlphabet ( ).end ( ), ext::callback_iterator ( [ ] ( const SymbolType & ) {
230 throw TreeException ( "Input symbols not in the alphabet." );
231 } ) );
232}
233
234template < class SymbolType >
236 checkAlphabet ( data );
237
238 this->m_content = std::move ( data );
239}
240
241template < class SymbolType >
243 m_content.nicePrint ( os );
244}
245
246} /* namespace tree */
247
248namespace core {
249
255template < class SymbolType >
256class SetConstraint< tree::UnorderedUnrankedTree < SymbolType >, SymbolType, tree::GeneralAlphabet > {
257public:
266 static bool used ( const tree::UnorderedUnrankedTree < SymbolType > & tree, const SymbolType & symbol ) {
267 const ext::tree<SymbolType>& m_content = tree.getContent ( );
268 return std::find(m_content.prefix_begin(), m_content.prefix_end(), symbol) != m_content.prefix_end();
269 }
270
280 return true;
281 }
282
290 }
291};
292
298template < class SymbolType >
299struct normalize < tree::UnorderedUnrankedTree < SymbolType > > {
302 ext::tree < DefaultSymbolType > content = tree::TreeNormalize::normalizeTree ( std::move ( value ).getContent ( ) );
303
304 return tree::UnorderedUnrankedTree < > ( std::move ( alphabet ), std::move ( content ) );
305 }
306};
307
308} /* namespace core */
309
310extern template class tree::UnorderedUnrankedTree < >;
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
Definition: components.hpp:181
static bool available(const tree::UnorderedUnrankedTree< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedTree.h:279
static void valid(const tree::UnorderedUnrankedTree< SymbolType > &, const SymbolType &)
Definition: UnorderedUnrankedTree.h:289
static bool used(const tree::UnorderedUnrankedTree< SymbolType > &tree, const SymbolType &symbol)
Definition: UnorderedUnrankedTree.h:266
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: 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: UnorderedUnrankedTree.h:69
const ext::set< SymbolType > & getAlphabet() const &
Definition: UnorderedUnrankedTree.h:112
UnorderedUnrankedTree(ext::set< SymbolType > alphabet, ext::tree< SymbolType > tree)
Creates a new instance of the pattern with concrete alphabet and content.
Definition: UnorderedUnrankedTree.h:204
void setTree(ext::tree< SymbolType > data)
Definition: UnorderedUnrankedTree.h:235
ext::set< SymbolType > && getAlphabet() &&
Definition: UnorderedUnrankedTree.h:121
friend ext::ostream & operator<<(ext::ostream &out, const UnorderedUnrankedTree &instance)
Definition: UnorderedUnrankedTree.h:187
void nicePrint(ext::ostream &os) const
Definition: UnorderedUnrankedTree.h:242
void extendAlphabet(const ext::set< SymbolType > &symbols)
Definition: UnorderedUnrankedTree.h:130
const ext::tree< SymbolType > & getContent() const &
Definition: UnorderedUnrankedTree.h:217
bool operator==(const UnorderedUnrankedTree &other) const
Definition: UnorderedUnrankedTree.h:175
Tree represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedTree.h:69
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::UnorderedUnrankedTree< > eval(tree::UnorderedUnrankedTree< SymbolType > &&value)
Definition: UnorderedUnrankedTree.h:300
Definition: normalize.hpp:13