Newer
Older
#include <alib/vector>
#include <alib/deque>
#include <alib/forward_tree>
namespace {
struct RankedArityChecker {
bool operator ()( char symbol, unsigned wantedRank ) const {
switch ( symbol ) {
case 'a':
return wantedRank == 2;
case 'b':
return wantedRank == 1;
default:
return wantedRank == 0;
}
}
};
static void print_tree ( const ext::forward_tree < char > & tree, std::string indent ) {
std::cout << indent << tree.getData ( ) << std::endl;
for ( const ext::forward_tree < char > & child : tree.getChildren ( ) ) {
print_tree ( child, indent + " " );
}
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
TEST_CASE ( "Forward Tree", "[unit][std][container]" ) {
SECTION ( "Tree Std Structure" ) {
ext::forward_tree < char > t ( 'a', ext::forward_tree < char > ( 'a' ), ext::forward_tree < char > ( 'b', ext::forward_tree < char > ( 'a' ), ext::forward_tree < char > ( 'b' ) ) );
ext::forward_tree < char > t2 ( 'c' );
t2.insert ( t2.begin ( ), { 'c', ext::forward_tree < char > ( 'b' ) } );
std::swap ( t2.getChildren ( ).front (), t.getChildren().front ( ) );
CHECK ( t2 == ext::forward_tree < char > ( 'c', ext::forward_tree < char > ( 'a' ) ) );
CHECK ( t == ext::forward_tree < char > ( 'a', ext::forward_tree < char > ( 'c', ext::forward_tree < char > ( 'b' ) ), ext::forward_tree < char > ( 'b', ext::forward_tree < char > ( 'a' ), ext::forward_tree < char > ( 'b' ) ) ) );
std::swap ( t2.getChildren ( ).front (), t.getChildren().front ( ) );
t2.insert ( t2.end ( ), t );
ext::vector < char > data = { 'd', 'e' };
t2.insert ( t2.end ( ), data.begin ( ), data.end ( ) );
print_tree ( t, "");
t2.erase ( std::prev ( t2.end ( ) ) );
t2.push_back ( 'f' );
print_tree ( t2, "");
CHECK( ( char ) t2 ( 1, 1 ) == 'b' );
t2 ( 1, 1 ) = 'c';
CHECK( ( char ) t2 ( 1, 1 ) == 'c' );
ext::forward_tree < char >::const_prefix_iterator beg = t2.prefix_begin ( );
beg++;
beg++;
beg++;
beg++;
beg++;
beg++;
beg++;
beg--;
beg--;
beg--;
beg--;
beg--;
beg--;
beg--;
CHECK ( beg == t2.prefix_begin ( ) );
std::cout << t2 << std::endl;
std::stringstream ss;
ss << t2;
CHECK ( ss.str ( ) == "[0c[1c[2b],1a[2a,2c[3a,3b]],1d,1f]]" );
ext::vector < std::pair < unsigned, char > > expectedPrefix = { { 0, 'c' }, { 1, 'c' }, { 2, 'b' }, { 1, 'a' }, { 2, 'a' }, { 2, 'c' }, { 3, 'a' }, { 3, 'b' }, { 1, 'd' }, { 1, 'f' } };
ext::vector < std::pair < unsigned, char > >::const_iterator ref = expectedPrefix.begin ( );
for ( ext::forward_tree < char >::const_prefix_iterator iter = t2.prefix_begin ( ); iter != t2.prefix_end ( ); ++iter ) {
CHECK ( iter.getLevel ( ) == ref->first );
CHECK ( * iter == ref->second );
++iter;
--iter;
++ref;
}
ext::vector < ext::tuple < unsigned, char, bool > > expectedStructure = { ext::make_tuple ( 0u, 'c', false ), ext::make_tuple ( 1u, 'c', false ), ext::make_tuple ( 2u, 'b', false ), ext::make_tuple ( 2u, 'b', true ), ext::make_tuple ( 1u, 'c', true ), ext::make_tuple ( 1u, 'a', false ), ext::make_tuple ( 2u, 'a', false ), ext::make_tuple ( 2u, 'a', true ), ext::make_tuple ( 2u, 'c', false ), ext::make_tuple ( 3u, 'a', false ), ext::make_tuple ( 3u, 'a', true ), ext::make_tuple ( 3u, 'b', false ), ext::make_tuple ( 3u, 'b', true ), ext::make_tuple ( 2u, 'c', true ), ext::make_tuple ( 1u, 'a', true ), ext::make_tuple ( 1u, 'd', false ), ext::make_tuple ( 1u, 'd', true ), ext::make_tuple ( 1u, 'f', false ), ext::make_tuple ( 1u, 'f', true ), ext::make_tuple ( 0u, 'c', true ) };
ext::vector < ext::tuple < unsigned, char, bool > >::const_iterator ref2 = expectedStructure.begin ( );
for ( ext::forward_tree < char >::const_structure_iterator iter = t2.structure_begin ( ); iter != t2.structure_end ( ); ++iter ) {
CHECK ( iter.getLevel ( ) == std::get < 0 > ( * ref2 ) );
CHECK ( * iter == std::get < 1 > ( * ref2 ) );
CHECK ( iter.getVirtual ( ) == std::get < 2 > ( * ref2 ) );
++iter;
--iter;
++ref2;
}
ext::vector < std::pair < unsigned, char > > expectedPostfix = { { 2, 'b' }, { 1, 'c' }, { 2, 'a' }, { 3, 'a' }, { 3, 'b' }, { 2, 'c' }, { 1, 'a' }, { 1, 'd' }, { 1, 'f' }, { 0, 'c' } };
ext::vector < std::pair < unsigned, char > >::const_iterator ref3 = expectedPostfix.begin ( );
for ( ext::forward_tree < char >::const_postfix_iterator iter = t2.postfix_begin ( ); iter != t2.postfix_end ( ); ++iter ) {
CHECK ( iter.getLevel ( ) == ref3->first );
CHECK ( * iter == ref3->second );
++iter;
--iter;
++ref3;
}
ext::forward_tree < char > cmp1 ( 'a' );
ext::forward_tree < char > cmp2 ( 'b' );
ext::forward_tree < char > cmp3 ( 'c' );
CHECK ( cmp1 < cmp2 );
CHECK ( cmp2 < cmp3 );
CHECK ( cmp2 <= cmp3 );
CHECK ( cmp2 == cmp2 );
CHECK ( cmp1 != cmp2 );