00001 #ifndef PARSE_TREE_HH
00002 #define PARSE_TREE_HH
00003
00155 #include <vector>
00156 #include <utility>
00157
00158 #ifdef _MSC_VER
00159 #pragma warning(disable : 4786) // disable this nagging warning about the limitations of the mirkosoft debugger
00160 #endif
00161
00162 namespace gp_parse_tree
00163 {
00164
00165 #include "node_pool.h"
00166
00168 template <class T>
00169 inline void do_the_swap(T& a, T& b)
00170 {
00171 T tmp = a;
00172 a = b;
00173 b = tmp;
00174 }
00175
00176 template <class T> class parse_tree
00177 {
00178 public :
00179
00180
00181 class subtree
00182 {
00183
00184
00185
00186
00187
00188
00189 #if (defined(__GNUC__) || defined(_MSC_VER)) && !(defined(_MT) || defined(MACOSX) || defined(__APPLE__)) // not multithreaded (or MACOSX - J. Eggermont)
00190 Node_alloc<T> node_allocator;
00191 Tree_alloc<subtree> tree_allocator;
00192 #else
00193 Standard_Node_alloc<T> node_allocator;
00194 Standard_alloc<subtree> tree_allocator;
00195 #endif
00196
00197 public :
00198
00199 typedef subtree* iterator;
00200 typedef const subtree* const_iterator;
00201
00202
00203
00204 subtree(void) : content(node_allocator.allocate()), args(0), parent(0), _cumulative_size(0), _depth(0), _size(1)
00205 {}
00206 subtree(const subtree& s)
00207 : content(node_allocator.allocate()),
00208 args(0),
00209 parent(0),
00210 _cumulative_size(1),
00211 _depth(1),
00212 _size(1)
00213 {
00214 copy(s);
00215 }
00216
00217 subtree(const T& t) : content(node_allocator.allocate()), args(0), parent(0), _cumulative_size(0), _depth(0), _size(1)
00218 { copy(t); }
00219
00220 template <class It>
00221 subtree(It b, It e) : content(node_allocator.allocate()), args(0), parent(0), _cumulative_size(0), _depth(0), _size(1)
00222 {
00223 init(b, --e);
00224 }
00225
00226 virtual ~subtree(void) { tree_allocator.deallocate(args, arity()); node_allocator.deallocate(content); }
00227
00228 subtree& operator=(const subtree& s)
00229 {
00230 if (s.get_root() == get_root())
00231 {
00232 subtree anotherS = s;
00233 return copy(anotherS);
00234 }
00235
00236 copy(s);
00237 updateAfterInsert();
00238 return *this;
00239 }
00240
00241 subtree& operator=(const T& t) { copy(t); updateAfterInsert(); return *this; }
00242
00243
00244
00245 T& operator*(void) { return *content; }
00246 const T& operator*(void) const { return *content; }
00247 T* operator->(void) { return content; }
00248 const T* operator->(void) const { return content; }
00249
00250
00251
00252 bool operator==(const subtree& other) const
00253 {
00254 if (! (*content == *other.content))
00255 return false;
00256
00257 for (int i = 0; i < arity(); i++)
00258 {
00259 if (!(args[i] == other.args[i]))
00260 return false;
00261 }
00262
00263 return true;
00264 }
00265
00266 bool operator !=(const subtree& other) const
00267 {
00268 return !operator==(other);
00269 }
00270
00271
00272 int arity(void) const { return content->arity(); }
00273
00274
00275 template <class RetVal>
00276 void apply(RetVal& v) const { (*content)(v, begin()); }
00277
00278 template <class RetVal, class It>
00279 void apply(RetVal& v, It values) const
00280 {
00281 (*content)(v, begin(), values);
00282 }
00283
00284 template <class RetVal, class It>
00285 void apply_mem_func(RetVal& v, It misc, void (T::* f)(RetVal&, typename subtree::iterator, It))
00286 {
00287 (content->*f)(v, begin(), misc);
00288 }
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300 template <class Pred>
00301 void find_nodes(std::vector<subtree*>& result, Pred& p)
00302 {
00303 if (p(*content))
00304 {
00305 result.push_back(this);
00306 }
00307
00308 for (int i = 0; i < arity(); ++i)
00309 {
00310 args[i].find_nodes(result, p);
00311 }
00312 }
00313
00314 template <class Pred>
00315 void find_nodes(std::vector<const subtree*>& result, Pred& p) const
00316 {
00317 if (p(*content))
00318 {
00319 result.push_back(this);
00320 }
00321
00322 for (int i = 0; i < arity(); ++i)
00323 {
00324 args[i].find_nodes(result, p);
00325 }
00326 }
00327
00328
00329
00330 iterator begin(void) { return args; }
00331 const_iterator begin(void) const { return args; }
00332
00333 iterator end(void) { return args + arity(); }
00334 const_iterator end(void) const { return args + arity(); }
00335
00336 subtree& operator[](int i) { return *(begin() + i); }
00337 const subtree& operator[](int i) const { return *(begin() + i); }
00338
00339
00340
00341 size_t size(void) const { return _size; }
00342
00343 size_t cumulative_size(void) const { return _cumulative_size; }
00344 size_t depth(void) const { return _depth; }
00345
00346 const subtree& select_cumulative(size_t which) const
00347 { return imp_select_cumulative(which); }
00348
00349 subtree& select_cumulative(size_t which)
00350 { return const_cast<subtree&>(imp_select_cumulative(which)); }
00351
00352 subtree& get_node(size_t which)
00353 { return const_cast<subtree&>(imp_get_node(which));}
00354 const subtree& get_node(size_t which) const
00355 { return imp_get_node(which); }
00356
00357 subtree* get_parent(void) { return parent; }
00358 const subtree* get_parent(void) const { return parent; }
00359
00360 void clear(void)
00361 { tree_allocator.deallocate(args, arity()); args = 0; *content = T(); parent = 0; _cumulative_size = 0; _depth = 0; _size = 0; }
00362
00363 void swap(subtree& y)
00364 {
00365 do_the_swap(content, y.content);
00366 do_the_swap(args, y.args);
00367
00368 adopt();
00369 y.adopt();
00370
00371 do_the_swap(parent, y.parent);
00372
00373 do_the_swap(_cumulative_size, y._cumulative_size);
00374 do_the_swap(_depth, y._depth);
00375 do_the_swap(_size, y._size);
00376 updateAfterInsert();
00377 }
00378
00379 protected :
00380
00381 virtual void updateAfterInsert(void)
00382 {
00383 _depth = 0;
00384 _size = 1;
00385 _cumulative_size = 0;
00386
00387 for (iterator it = begin(); it != end(); ++it)
00388 {
00389 _size += it->size();
00390 _cumulative_size += it->_cumulative_size;
00391 _depth = it->_depth > _depth? it->_depth: _depth;
00392 }
00393 _cumulative_size += _size;
00394 _depth++;
00395
00396 if (parent)
00397 parent->updateAfterInsert();
00398 }
00399
00400 private :
00401
00402 const subtree& imp_select_cumulative(size_t which) const
00403 {
00404 if (which >= (_cumulative_size - size()))
00405 return *this;
00406
00407
00408 for (int i = arity() - 1; i >= 0; --i)
00409 {
00410 if (which < args[i]._cumulative_size)
00411 return args[i].imp_select_cumulative(which);
00412 which -= args[i]._cumulative_size;
00413 }
00414
00415 return *this;
00416 }
00417
00418 const subtree& imp_get_node(size_t which) const
00419 {
00420 if (which == size() - 1)
00421 return *this;
00422
00423 for (int i = arity() - 1; i >= 0; --i)
00424 {
00425 unsigned c_size = args[i].size();
00426 if (which < c_size)
00427 return args[i].imp_get_node(which);
00428 which -= c_size;
00429 }
00430
00431 return *this;
00432 }
00433
00434 const subtree* get_root(void) const
00435 {
00436 if (parent == 0)
00437 return this;
00438
00439
00440 return parent->get_root();
00441 }
00442 subtree& copy(const subtree& s)
00443 {
00444 int old_arity = arity();
00445
00446 int new_arity = s.arity();
00447
00448 if (new_arity != old_arity)
00449 {
00450 tree_allocator.deallocate(args, old_arity);
00451
00452 args = tree_allocator.allocate(new_arity);
00453 }
00454
00455 switch(new_arity)
00456 {
00457 case 3 : args[2].copy(s.args[2]); args[2].parent = this;
00458 case 2 : args[1].copy(s.args[1]); args[1].parent = this;
00459 case 1 : args[0].copy(s.args[0]); args[0].parent = this;
00460 case 0 : break;
00461 default :
00462 {
00463 for (int i = 0; i < new_arity; ++i)
00464 {
00465 args[i].copy(s.args[i]);
00466 args[i].parent = this;
00467 }
00468 }
00469 }
00470
00471 *content = *s.content;
00472 _size = s._size;
00473 _depth = s._depth;
00474 _cumulative_size = s._cumulative_size;
00475
00476 return *this;
00477 }
00478
00479 subtree& copy(const T& t)
00480 {
00481 int oldArity = arity();
00482
00483 if (content != &t)
00484 *content = t;
00485 else
00486 oldArity = -1;
00487
00488 int ar = arity();
00489
00490 if (ar != oldArity)
00491 {
00492 if (oldArity != -1)
00493 tree_allocator.deallocate(args, oldArity);
00494
00495 args = tree_allocator.allocate(ar);
00496
00497
00498
00499
00500
00501 }
00502
00503 adopt();
00504 updateAfterInsert();
00505 return *this;
00506 }
00507
00508 void disown(void)
00509 {
00510 switch(arity())
00511 {
00512 case 3 : args[2].parent = 0;
00513 case 2 : args[1].parent = 0;
00514 case 1 : args[0].parent = 0; break;
00515 case 0 : break;
00516 default :
00517 {
00518 for (iterator it = begin(); it != end(); ++it)
00519 {
00520 it->parent = 0;
00521 }
00522 }
00523 }
00524
00525 }
00526
00527 void adopt(void)
00528 {
00529 switch(arity())
00530 {
00531 case 3 : args[2].parent = this;
00532 case 2 : args[1].parent = this;
00533 case 1 : args[0].parent = this; break;
00534 case 0 : break;
00535 default :
00536 {
00537 for (iterator it = begin(); it != end(); ++it)
00538 {
00539 it->parent = this;
00540 }
00541 }
00542 }
00543 }
00544
00545 template <class It>
00546 void init(It b, It& last)
00547 {
00548 *this = *last;
00549
00550 #ifndef NDEBUG
00551 if (last == b && arity() > 0)
00552 {
00553 throw "subtree::init()";
00554 }
00555 #endif
00556
00557 for (int i = 0; i < arity(); ++i)
00558 {
00559 args[i].parent = 0;
00560 args[i].init(b, --last);
00561 args[i].parent = this;
00562 }
00563
00564 updateAfterInsert();
00565 }
00566
00567 T* content;
00568 subtree* args;
00569 subtree* parent;
00570
00571 size_t _cumulative_size;
00572 size_t _depth;
00573 size_t _size;
00574 };
00575
00576
00577
00578 typedef T value_type;
00579
00580
00581
00582 parse_tree(void) : _root(), pushed() {}
00583 parse_tree(const parse_tree& org) : _root(org._root), pushed(org.pushed) { }
00584 parse_tree(const subtree& sub) : _root(sub), pushed() { }
00585
00586 template <class It>
00587 parse_tree(It b, It e) : _root(b, e), pushed() {}
00588
00589 virtual ~parse_tree(void) {}
00590
00591 parse_tree& operator=(const parse_tree& org) { return copy(org); }
00592 parse_tree& operator=(const subtree& sub)
00593 { return copy(sub); }
00594
00595
00596
00597
00598 bool operator==(const parse_tree& other) const
00599 { return _root == other._root; }
00600
00601 bool operator !=(const parse_tree& other) const
00602 { return !operator==(other); }
00603
00604
00605
00606 size_t size(void) const { return _root.size(); }
00607 size_t depth(void) const { return _root.depth(); }
00608 void clear(void) { _root.clear(); pushed.resize(0); }
00609
00610
00611
00612 template <class RetVal>
00613 void apply(RetVal& v) const
00614 { _root.apply(v); }
00615
00616 template <class RetVal, class It>
00617 void apply(RetVal& v, It varValues) const
00618 { _root.apply(v, varValues); }
00619
00620 template <class RetVal, class It>
00621 void apply_mem_func(RetVal& v, It misc, void (T::* f)(RetVal&, typename subtree::iterator, It))
00622 {
00623 _root.apply_mem_func(v, misc, f);
00624 }
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634 template <class Pred>
00635 void find_nodes(std::vector<subtree*>& result, Pred& p)
00636 {
00637 _root.find_nodes(result, p);
00638 }
00639
00640 template <class Pred>
00641 void find_nodes(std::vector<const subtree*>& result, Pred& p) const
00642 {
00643 _root.find_nodes(p);
00644 }
00645
00646
00647 void swap(parse_tree<T>& other)
00648 {
00649 do_the_swap(pushed, other.pushed);
00650 _root.swap(other._root);
00651 }
00652
00653
00654
00655 class base_iterator
00656 {
00657 public :
00658
00659 base_iterator() {}
00660 base_iterator(subtree* n) { node = n; }
00661
00662 base_iterator& operator=(const base_iterator& org)
00663 { node = org.node; return *this; }
00664
00665 bool operator==(const base_iterator& org) const
00666 { return node == org.node; }
00667 bool operator!=(const base_iterator& org) const
00668 { return !operator==(org); }
00669
00670 base_iterator operator+(size_t n) const
00671 {
00672 base_iterator tmp = *this;
00673
00674 for(;n != 0; --n)
00675 {
00676 ++tmp;
00677 }
00678
00679 return tmp;
00680 }
00681
00682 base_iterator& operator++(void)
00683 {
00684 subtree* parent = node->get_parent();
00685
00686 if (parent == 0)
00687 {
00688 node = 0;
00689 return *this;
00690 }
00691
00692 typename subtree::iterator it;
00693 for (it = parent->begin(); it != parent->end(); ++it)
00694 {
00695 if (node == &(*it))
00696 break;
00697 }
00698
00699 if (it == parent->begin())
00700 node = parent;
00701 else
00702 {
00703 node = &(--it)->get_node(0);
00704 }
00705
00706 return *this;
00707 }
00708
00709 base_iterator operator++(int)
00710 {
00711 base_iterator tmp = *this;
00712 operator++();
00713 return tmp;
00714 }
00715
00716 protected :
00717 subtree* node;
00718 };
00719
00720 class iterator : public base_iterator
00721 {
00722 public:
00723
00724 using base_iterator::node;
00725
00726 typedef std::forward_iterator_tag iterator_category;
00727 typedef subtree value_type;
00728 typedef size_t distance_type;
00729 typedef size_t difference_type;
00730 typedef subtree* pointer;
00731 typedef subtree& reference;
00732
00733 iterator() : base_iterator() {}
00734 iterator(subtree* n): base_iterator(n) {}
00735 iterator& operator=(const iterator& org)
00736 { base_iterator::operator=(org); return *this; }
00737
00738 subtree& operator*(void) { return *node; }
00739 subtree* operator->(void) { return node; }
00740 };
00741
00742
00743
00744 class embedded_iterator : public base_iterator
00745 {
00746 public:
00747
00748 using base_iterator::node;
00749
00750 typedef std::forward_iterator_tag iterator_category;
00751 typedef T value_type;
00752 typedef size_t distance_type;
00753 typedef size_t difference_type;
00754 typedef T* pointer;
00755 typedef T& reference;
00756
00757 embedded_iterator() : base_iterator() {}
00758 embedded_iterator(subtree* n): base_iterator(n) {}
00759 embedded_iterator& operator=(const embedded_iterator& org)
00760 { base_iterator::operator=(org); return *this; }
00761
00762 T& operator*(void) { return **node; }
00763 T* operator->(void) { return &**node; }
00764 };
00765
00766 class base_const_iterator
00767 {
00768 public:
00769
00770 base_const_iterator() {}
00771 base_const_iterator(const subtree* n) { node = n; }
00772
00773 base_const_iterator& operator=(const base_const_iterator& org)
00774 { node = org.node; return *this; }
00775
00776 bool operator==(const base_const_iterator& org) const
00777 { return node == org.node; }
00778 bool operator!=(const base_const_iterator& org) const
00779 { return !operator==(org); }
00780
00781 base_const_iterator& operator++(void)
00782 {
00783 const subtree* parent = node->get_parent();
00784
00785 if (parent == 0)
00786 {
00787 node = 0;
00788 return *this;
00789 }
00790
00791 typename subtree::const_iterator it;
00792
00793 for (it = parent->begin(); it != parent->end(); ++it)
00794 {
00795 if (node == &(*it))
00796 break;
00797 }
00798
00799 if (it == parent->begin())
00800 node = parent;
00801 else
00802 node = &(--it)->get_node(0);
00803 return *this;
00804 }
00805
00806 base_const_iterator operator++(int)
00807 {
00808 base_const_iterator tmp = *this;
00809 operator++();
00810 return tmp;
00811 }
00812
00813 protected :
00814
00815 const subtree* node;
00816 };
00817
00818 class const_iterator : public base_const_iterator
00819 {
00820 public:
00821
00822 using base_iterator::node;
00823
00824 typedef std::forward_iterator_tag iterator_category;
00825 typedef const subtree value_type;
00826 typedef size_t distance_type;
00827 typedef size_t difference_type;
00828 typedef const subtree* pointer;
00829 typedef const subtree& reference;
00830
00831 const_iterator() : base_const_iterator() {}
00832 const_iterator(const subtree* n): base_const_iterator(n) {}
00833 const_iterator& operator=(const const_iterator& org)
00834 { base_const_iterator::operator=(org); return *this; }
00835
00836 const subtree& operator*(void) { return *node; }
00837 const subtree* operator->(void) { return node; }
00838 };
00839
00840 class embedded_const_iterator : public base_const_iterator
00841 {
00842 public:
00843
00844 using base_const_iterator::node;
00845
00846 typedef std::forward_iterator_tag iterator_category;
00847 typedef const T value_type;
00848 typedef size_t distance_type;
00849 typedef size_t difference_type;
00850 typedef const T* pointer;
00851 typedef const T& reference;
00852
00853 embedded_const_iterator() : base_const_iterator() {}
00854 embedded_const_iterator(const subtree* n): base_const_iterator(n) {}
00855 embedded_const_iterator& operator=(const embedded_const_iterator& org)
00856 { base_const_iterator::operator=(org); return *this; }
00857
00858 embedded_const_iterator operator+(size_t n) const
00859 {
00860 embedded_const_iterator tmp = *this;
00861
00862 for(;n != 0; --n)
00863 {
00864 ++tmp;
00865 }
00866
00867 return tmp;
00868 }
00869
00870 const T& operator*(void) const { return **node; }
00871 const T* operator->(void) const { return node->operator->(); }
00872 };
00873
00874
00875
00876 iterator begin(void) { return iterator(&operator[](0)); }
00877 const_iterator begin(void) const { return const_iterator(&operator[](0)); }
00878 iterator end(void) { return iterator(0); }
00879 const_iterator end(void) const { return const_iterator(0);}
00880
00881 embedded_iterator ebegin(void) { return embedded_iterator(&operator[](0)); }
00882 embedded_const_iterator ebegin(void) const { return embedded_const_iterator(&operator[](0)); }
00883 embedded_iterator eend(void) { return embedded_iterator(0); }
00884 embedded_const_iterator eend(void) const { return embedded_const_iterator(0);}
00885
00886 bool empty(void) const { return size() == 0; }
00887 bool valid(void) const { return pushed.empty(); }
00888
00889
00890
00891 void push_back(const parse_tree<T>& tree)
00892 {
00893 if (!empty())
00894 pushed.push_back(_root);
00895
00896 _root = tree.back();
00897 }
00898
00899 void push_back(const T& t)
00900 {
00901 if (!empty())
00902 pushed.push_back(_root);
00903
00904 _root = t;
00905
00906 for (typename subtree::iterator it = _root.begin(); it != _root.end(); it++)
00907 {
00908 *it = pushed.back();
00909 pushed.pop_back();
00910 }
00911
00912 }
00913
00914
00915
00916 subtree& back(void) { return _root; }
00917 const subtree& back(void) const { return _root; }
00918 subtree& root(void) { return _root; }
00919 const subtree& root(void) const { return _root; }
00920
00921 subtree& front(void) { return _root[0]; }
00922 const subtree& front(void) const { return _root[0]; }
00923
00924 subtree& operator[](size_t i)
00925 { return const_cast<subtree&>(_root.get_node(i)); }
00926 const subtree& operator[](size_t i) const
00927 { return _root.get_node(i); }
00928
00929 subtree& get_cumulative(size_t i)
00930 { return const_cast<subtree&>(_root.get_cumulative(i)); }
00931 const subtree& get_cumulative(size_t i) const
00932 { return get_cumulative(i); }
00933
00934 private :
00935
00936 parse_tree& copy(const parse_tree& org)
00937 {
00938 _root = org._root;
00939 pushed = org.pushed;
00940
00941 return *this;
00942 }
00943
00944 parse_tree& copy(const subtree& sub)
00945 { _root = sub; pushed.resize(0); return *this; }
00946
00947 subtree _root;
00948 std::vector<subtree > pushed;
00949 };
00950
00951
00952 }
00953
00954 namespace std
00955 {
00956
00957 template <class T> inline
00958 std::forward_iterator_tag iterator_category(typename gp_parse_tree::parse_tree<T>::embedded_iterator)
00959 {
00960 return std::forward_iterator_tag();
00961 }
00962
00963 template <class T> inline
00964 ptrdiff_t* distance_type(typename gp_parse_tree::parse_tree<T>::embedded_iterator)
00965 {
00966 return 0;
00967 }
00968
00969 template <class T> inline
00970 std::forward_iterator_tag iterator_category(typename gp_parse_tree::parse_tree<T>::iterator)
00971 {
00972 return std::forward_iterator_tag();
00973 }
00974
00975 template <class T> inline
00976 ptrdiff_t* distance_type(typename gp_parse_tree::parse_tree<T>::iterator)
00977 {
00978 return 0;
00979 }
00980
00981
00982
00983
00984
00985
00986
00987
00988
00989
00990
00991
00992
00993
00994
00995
00996 }
00997
00998
00999 #endif