00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef CEYLAN_TREE_H_
00028 #define CEYLAN_TREE_H_
00029
00030
00031 #include "CeylanVisitable.h"
00032 #include "CeylanVisitor.h"
00033 #include "CeylanException.h"
00034 #include "CeylanLogPlug.h"
00035 #include "CeylanStringUtils.h"
00036
00037
00038
00039 #include <string>
00040 #include <list>
00041
00042
00043
00044 namespace Ceylan
00045 {
00046
00047
00048
00056 class CEYLAN_DLL TreeException : public Ceylan::Exception
00057 {
00058
00059 public:
00060
00061 explicit TreeException( const std::string & reason ) ;
00062
00063 virtual ~TreeException() throw() ;
00064
00065 } ;
00066
00067
00068
00069
00070 template <typename Content> class Tree ;
00071
00072
00073
00078 template <typename Content>
00079 class TreeVisitor : public Ceylan::Visitor
00080 {
00081
00082 public:
00083
00084 explicit TreeVisitor() ;
00085
00086 virtual ~TreeVisitor() throw() ;
00087
00088
00090 virtual void visit( Tree<Content> & tree ) = 0 ;
00091
00092
00094 virtual void visit( Content & content ) = 0 ;
00095
00096 } ;
00097
00098
00099
00100 template <typename Content>
00101 TreeVisitor<Content>::TreeVisitor()
00102 {
00103
00104 }
00105
00106
00107 template <typename Content>
00108 TreeVisitor<Content>::~TreeVisitor() throw()
00109 {
00110
00111 }
00112
00113
00114
00116 typedef Ceylan::Uint32 Height ;
00117
00118
00119
00125 template <typename Content>
00126 class TreeHeightAwareVisitor : public Ceylan::Visitor
00127 {
00128
00129
00130 public:
00131
00132
00133
00139 explicit TreeHeightAwareVisitor() ;
00140
00141
00143 virtual ~TreeHeightAwareVisitor() throw() ;
00144
00145
00146
00155 virtual Height getHeight() const ;
00156
00157
00158
00167 virtual void incrementHeight() ;
00168
00169
00170
00179 virtual void decrementHeight() ;
00180
00181
00182
00214 } ;
00215
00216
00217
00218 template <typename Content>
00219 TreeHeightAwareVisitor<Content>::TreeHeightAwareVisitor()
00220 {
00221
00222 }
00223
00224
00225
00226 template <typename Content>
00227 TreeHeightAwareVisitor<Content>::~TreeHeightAwareVisitor() throw()
00228 {
00229
00230 }
00231
00232
00233
00234 template <typename Content>
00235 Height TreeHeightAwareVisitor<Content>::getHeight() const
00236 {
00237
00238
00239 return 0 ;
00240 }
00241
00242
00243
00244 template <typename Content>
00245 void TreeHeightAwareVisitor<Content>::incrementHeight()
00246 {
00247
00248
00249
00250 }
00251
00252
00253
00254 template <typename Content>
00255 void TreeHeightAwareVisitor<Content>::decrementHeight()
00256 {
00257
00258
00259
00260 }
00261
00262
00263
00264
00279 template <typename Content>
00280 class Tree : public Ceylan::Visitable
00281 {
00282
00283
00284 public:
00285
00286
00288 typedef std::list< Tree<Content>* > SubTreeList ;
00289
00290
00291
00292
00293
00294
00300 explicit Tree() ;
00301
00302
00303
00314 explicit Tree( Content & content ) ;
00315
00316
00317
00323 virtual ~Tree() throw() ;
00324
00325
00326
00327
00328
00329
00330
00341 virtual void accept( Visitor & visitor ) ;
00342
00343
00344
00345
00346
00347
00348
00356 virtual bool hasContent() const ;
00357
00358
00359
00369 virtual Content & getContent() ;
00370
00371
00372
00383 virtual const Content & getContentAsConst() const ;
00384
00385
00386
00398 virtual void setContent( Content & newContent ) ;
00399
00400
00401
00402
00403
00404
00405
00410 virtual const SubTreeList & getSons() const ;
00411
00412
00413
00423 virtual Tree * getFather( Tree & child ) ;
00424
00425
00426
00438 virtual void addSon( Tree & subtree ) ;
00439
00440
00441
00462 virtual void traverseDepthFirst( TreeVisitor<Content> & treeVisitor,
00463 bool visitContent = true ) ;
00464
00465
00466
00487 virtual void traverseBreadthFirst(
00488 TreeVisitor<Content> & treeVisitor,
00489 bool visitContent = true ) ;
00490
00491
00492
00499 virtual void appendSonsContents(
00500 std::list<Content *> & toBeAugmented ) ;
00501
00502
00503
00504
00505
00506
00507
00519 virtual Tree * getNodeOf( const Content & content ) ;
00520
00521
00522
00543 virtual Content * getFatherContent( const Content & content ) ;
00544
00545
00546
00556 virtual void appendSonsContentsOf( const Content & content,
00557 std::list<Content *> & toBeAugmented ) ;
00558
00559
00560
00571 virtual const std::string toString(
00572 Ceylan::VerbosityLevels level = Ceylan::high ) const ;
00573
00574
00575
00576
00577
00578 protected:
00579
00580
00581
00586 Content * _content ;
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596 #pragma warning( push )
00597 #pragma warning( disable : 4251 )
00598
00603 SubTreeList _sons ;
00604
00605 #pragma warning( pop )
00606
00607
00608
00609
00610 private:
00611
00612
00613
00623 Tree( const Tree & source ) ;
00624
00625
00633 Tree & operator = ( const Tree & source ) ;
00634
00635
00636 } ;
00637
00638
00639
00640
00641
00642
00643
00644 template <typename Content>
00645 Tree<Content>::Tree() :
00646 _content( 0 ),
00647 _sons()
00648 {
00649
00650 }
00651
00652
00653
00654 template <typename Content>
00655 Tree<Content>::Tree( Content & content ) :
00656 _content( &content ),
00657 _sons()
00658 {
00659
00660 }
00661
00662
00663
00664 template <typename Content>
00665 Tree<Content>::~Tree() throw()
00666 {
00667
00668 if ( _content != 0 )
00669 delete _content ;
00670
00671 for ( typename SubTreeList::iterator it = _sons.begin();
00672 it != _sons.end(); it++ )
00673 {
00674 delete (*it) ;
00675 }
00676
00677
00678 _sons.clear() ;
00679
00680 }
00681
00682
00683
00684 template <typename Content>
00685 const std::list< Tree<Content>* > & Tree<Content>::getSons() const
00686 {
00687
00688 return _sons ;
00689
00690 }
00691
00692
00693
00694 template <typename Content>
00695 Tree<Content> * Tree<Content>::getFather( Tree<Content> & child )
00696 {
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707 for ( typename SubTreeList::iterator it = _sons.begin();
00708 it != _sons.end(); it++ )
00709 if ( *it == & child )
00710 return this ;
00711
00712
00713
00714 for ( typename SubTreeList::iterator it = _sons.begin();
00715 it != _sons.end(); it++ )
00716 {
00717 Tree * returned = (*it)->getFather( child ) ;
00718 if ( returned != 0 )
00719 return returned ;
00720 }
00721
00722 return 0 ;
00723
00724 }
00725
00726
00727
00728 template <typename Content>
00729 void Tree<Content>::accept( Visitor & visitor )
00730 {
00731
00732
00733
00734 TreeHeightAwareVisitor<Content> * actualVisitor =
00735 dynamic_cast<TreeHeightAwareVisitor<Content> *>( &visitor ) ;
00736
00737 if ( actualVisitor == 0 )
00738 throw VisitException( "Tree<Content>::accept failed: "
00739 "the visitor (" + visitor.toString() + ") is not a "
00740 "TreeHeightAwareVisitor." ) ;
00741
00742
00743 if ( _content != 0 )
00744 _content->accept( *actualVisitor ) ;
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778 actualVisitor->incrementHeight() ;
00779
00780
00781 for ( typename SubTreeList::iterator it = _sons.begin();
00782 it != _sons.end(); it++ )
00783 (*it)->accept( *actualVisitor ) ;
00784
00785 actualVisitor->decrementHeight() ;
00786
00787 }
00788
00789
00790
00791 template <typename Content>
00792 bool Tree<Content>::hasContent() const
00793 {
00794
00795 return ( _content != 0 ) ;
00796
00797 }
00798
00799
00800
00801 template <typename Content>
00802 Content & Tree<Content>::getContent()
00803 {
00804
00805 if ( _content == 0 )
00806 throw TreeException( "Tree<Content>::getContent: "
00807 "no available content to return." ) ;
00808
00809 return *_content ;
00810
00811 }
00812
00813
00814
00815 template <typename Content>
00816 const Content & Tree<Content>::getContentAsConst() const
00817 {
00818
00819 if ( _content == 0 )
00820 throw TreeException( "Tree<Content>::getContentAsConst: "
00821 "no available content to return." ) ;
00822
00823 return *_content ;
00824
00825 }
00826
00827
00828
00829 template <typename Content>
00830 void Tree<Content>::setContent( Content & newContent )
00831 {
00832
00833 if ( _content != 0 )
00834 delete _content ;
00835
00836 _content = & newContent ;
00837
00838 }
00839
00840
00841
00842 template <typename Content>
00843 void Tree<Content>::addSon( Tree<Content> & subtree )
00844 {
00845
00846 for ( typename SubTreeList::const_iterator it = _sons.begin();
00847 it != _sons.end(); it++ )
00848 if ( *it == &subtree )
00849 throw Ceylan::TreeException( "Tree<Content>::addSon: "
00850 "following son was already registered: "
00851 + subtree.toString() ) ;
00852
00853 _sons.push_back( &subtree ) ;
00854
00855 }
00856
00857
00858
00859 template <typename Content>
00860 void Tree<Content>::traverseDepthFirst( TreeVisitor<Content> & treeVisitor,
00861 bool visitContent )
00862 {
00863
00864
00865 for ( typename SubTreeList::iterator it = _sons.begin();
00866 it != _sons.end(); it++ )
00867 (*it)->traverseDepthFirst( treeVisitor, visitContent ) ;
00868
00869
00870 treeVisitor.visit( *this ) ;
00871
00872 if ( visitContent && _content != 0 )
00873 treeVisitor.visit( *_content ) ;
00874
00875 }
00876
00877
00878
00879 template <typename Content>
00880 void Tree<Content>::traverseBreadthFirst(
00881 TreeVisitor<Content> & treeVisitor, bool visitContent )
00882 {
00883
00884
00885 treeVisitor.visit( *this ) ;
00886
00887 if ( visitContent && _content != 0 )
00888 treeVisitor.visit( *_content ) ;
00889
00890
00891 for ( typename SubTreeList::iterator it = _sons.begin();
00892 it != _sons.end(); it++ )
00893 (*it)->traverseBreadthFirst( treeVisitor, visitContent ) ;
00894
00895 }
00896
00897
00898
00899 template <typename Content>
00900 void Tree<Content>::appendSonsContents(
00901 std::list<Content *> & toBeAugmented )
00902 {
00903
00904 for ( typename SubTreeList::iterator it = _sons.begin();
00905 it != _sons.end(); it++ )
00906 {
00907
00908 Content * retrieved = (*it)->_content ;
00909 if ( retrieved != 0 )
00910 toBeAugmented.push_back( retrieved ) ;
00911
00912 }
00913
00914 }
00915
00916
00917
00918 template <typename Content>
00919 Tree<Content> * Tree<Content>::getNodeOf( const Content & content )
00920 {
00921
00922
00923 if ( this->_content == & content )
00924 return this ;
00925
00926
00927 for ( typename SubTreeList::iterator it = _sons.begin();
00928 it != _sons.end(); it++ )
00929 {
00930 Tree<Content> * returned = (*it)->getNodeOf( content ) ;
00931 if ( returned != 0 )
00932 return returned ;
00933 }
00934
00935 return 0 ;
00936
00937 }
00938
00939
00940
00941 template <typename Content>
00942 Content * Tree<Content>::getFatherContent( const Content & content )
00943 {
00944
00945
00946
00947
00948
00949
00950
00951
00952
00953
00954 for ( typename SubTreeList::iterator it = _sons.begin();
00955 it != _sons.end(); it++ )
00956 if ( (*it)->_content == & content )
00957 return this->_content ;
00958
00959
00960
00961 for ( typename SubTreeList::iterator it = _sons.begin();
00962 it != _sons.end(); it++ )
00963 {
00964 Content * returned = (*it)->getFatherContent( content ) ;
00965 if ( returned != 0 )
00966 return returned ;
00967 }
00968
00969 return 0 ;
00970
00971 }
00972
00973
00974
00975 template <typename Content>
00976 void Tree<Content>::appendSonsContentsOf( const Content & content,
00977 std::list<Content *> & toBeAugmented )
00978 {
00979
00980 Tree<Content> * father = this->getNodeOf( content ) ;
00981
00982
00983 if ( father == 0 )
00984 return ;
00985
00986
00987 father->appendSonsContents( toBeAugmented ) ;
00988
00989 }
00990
00991
00992
00993 template <typename Content>
00994 const std::string Tree<Content>::toString( Ceylan::VerbosityLevels level )
00995 const
00996 {
00997
00998 std::string res = "Tree " ;
00999
01000 if ( _content !=0 )
01001 res += "whose local content is: '"
01002 + _content->toString( level ) + "'" ;
01003 else
01004 res += "with no local content" ;
01005
01006 if ( _sons.empty() )
01007 return res + ". No registred subtree" ;
01008
01009 res += ". Following subtrees are registered: " ;
01010
01011 std::list<std::string> subtrees ;
01012
01013 for ( typename SubTreeList::const_iterator it =
01014 _sons.begin(); it != _sons.end(); it++ )
01015 {
01016 subtrees.push_back( (*it)->toString( level ) ) ;
01017 }
01018
01019 return res + Ceylan::formatStringList( subtrees ) ;
01020
01021 }
01022
01023
01024 }
01025
01026
01027
01028 #endif // CEYLAN_TREE_H_
01029