BALL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
composite.h
Go to the documentation of this file.
1 // -*- Mode: C++; tab-width: 2; -*-
2 // vi: set ts=2:
3 //
4 
5 #ifndef BALL_CONCEPT_COMPOSITE_H
6 #define BALL_CONCEPT_COMPOSITE_H
7 
8 #ifndef BALL_COMMON_H
9 # include <BALL/common.h>
10 #endif
11 
12 #ifndef BALL_CONCEPT_PERSISTENTOBJECT_H
14 #endif
15 
16 #ifndef BALL_CONCEPT_COMPARATOR_H
17 # include <BALL/CONCEPT/comparator.h>
18 #endif
19 
20 #ifndef BALL_CONCEPT_BIDIRECTIONALITERATOR_H
22 #endif
23 
24 #ifndef BALL_CONCEPT_OBJECT_H
25 # include <BALL/CONCEPT/object.h>
26 #endif
27 
28 #ifndef BALL_CONCEPT_SELECTABLE_H
29 # include <BALL/CONCEPT/selectable.h>
30 #endif
31 
32 #ifndef BALL_CONCEPT_VISITOR_H
33 # include <BALL/CONCEPT/visitor.h>
34 #endif
35 
36 #ifndef BALL_CONCEPT_PROCESSOR_H
37 # include <BALL/CONCEPT/processor.h>
38 #endif
39 
40 #ifndef BALL_CONCEPT_TIMESTAMP_H
41 # include <BALL/CONCEPT/timeStamp.h>
42 #endif
43 
45 namespace BALL
46 {
70  : public PersistentObject,
71  public Selectable
72  {
73  public:
74 
78 
79 #ifndef BALL_KERNEL_PREDICATE_TYPE
80 #define BALL_KERNEL_PREDICATE_TYPE
81 
87 #endif
88 
91  enum StampType
92  {
95  MODIFICATION = 1,
98  SELECTION = 2,
101  BOTH = 3
102  };
104 
106 
107  static UnaryProcessor<Composite> DEFAULT_PROCESSOR;
108  static KernelPredicateType DEFAULT_UNARY_PREDICATE;
109 
113 
117  Composite()
118  ;
119 
128  Composite(const Composite& composite, bool deep = true)
129  ;
130 
136  virtual ~Composite()
137  ;
138 
150  virtual void clear()
151  ;
152 
162  virtual void destroy()
163  ;
164 
177  void destroy(bool virtual_destroy)
178  ;
179 
187  void* clone(Composite& root) const
188  ;
189 
191 
195 
201  virtual void persistentWrite(PersistenceManager& pm, const char* name = 0) const;
202 
207  virtual void persistentRead(PersistenceManager& pm);
208 
210 
214 
220  void set(const Composite& composite, bool deep = true) ;
221 
226  Composite& operator = (const Composite& composite) ;
227 
234  void get(Composite& composite, bool deep = true) const ;
235 
240  Size getDegree() const ;
241 
246  Size count(const KernelPredicateType& predicate) const ;
247 
251  Size countDescendants() const ;
252 
258  Size getPathLength(const Composite& composite) const ;
259 
264  Size getDepth() const ;
265 
270  Size getHeight() const
271  ;
272 
276  Composite& getRoot() ;
277 
281  const Composite& getRoot() const ;
282 
287  Composite* getLowestCommonAncestor(const Composite& composite)
288  ;
289 
294  const Composite* getLowestCommonAncestor(const Composite& composite) const
295  ;
296 
305  template <typename T>
306  T* getAncestor(const T& /* dummy */)
307  ;
308 
315  template <typename T>
316  const T* getAncestor(const T& /* dummy */) const ;
317 
325  template <typename T>
326  T* getPrevious(const T& /* dummy */) ;
327 
335  template <typename T>
336  const T* getPrevious(const T& dummy) const ;
337 
345  template <typename T>
346  T* getNext(const T& /* dummy */) ;
347 
355  template <typename T>
356  const T* getNext(const T& dummy) const ;
357 
361  Composite* getParent() ;
362 
366  const Composite* getParent() const ;
367 
374  Composite* getChild(Index index) ;
375 
382  const Composite* getChild(Index index) const ;
383 
392  Composite* getSibling(Index index) ;
393 
402  const Composite* getSibling(Index index) const ;
403 
407  Composite* getFirstChild() ;
408 
412  const Composite* getFirstChild() const ;
413 
417  Composite* getLastChild() ;
418 
422  const Composite* getLastChild() const ;
423 
427  const PreciseTime& getModificationTime() const ;
428 
432  const PreciseTime& getSelectionTime() const ;
433 
443  void stamp(StampType stamp = BOTH) ;
444 
450  void prependChild(Composite& composite) ;
451 
459  void appendChild(Composite& composite) ;
460 
480  static bool insertParent(Composite& parent, Composite& first,
481  Composite& last, bool destroy_parent = true)
482  ;
483 
493  void insertBefore(Composite& composite) ;
494 
504  void insertAfter(Composite& composite) ;
505 
514  void spliceBefore(Composite& composite) ;
515 
524  void spliceAfter(Composite& composite) ;
525 
535  void splice(Composite& composite) ;
536 
545  bool removeChild(Composite& child) ;
546 
547 
560  Size removeSelected() ;
561 
574  Size removeUnselected();
575 
584  void replace(Composite& composite) ;
585 
594  void swap(Composite& composite) ;
595 
604  virtual void select() ;
605 
614  virtual void deselect() ;
616 
619 
626  bool operator == (const Composite& composite) const ;
627 
631  bool operator != (const Composite& composite) const
632  ;
633 
637  bool isEmpty() const ;
638 
642  bool isRoot() const ;
643 
646  bool isRootOf(const Composite& composite) const ;
647 
650  bool isInterior() const ;
651 
654  bool hasChild() const ;
655 
658  bool isChildOf(const Composite& composite) const ;
659 
662  bool isFirstChild() const ;
663 
666  bool isFirstChildOf(const Composite& composite) const ;
667 
670  bool isLastChild() const ;
671 
674  bool isLastChildOf(const Composite& composite) const ;
675 
678  bool hasParent() const ;
679 
682  bool isParentOf(const Composite& composite) const ;
683 
687  bool hasSibling() const ;
688 
691  bool isSiblingOf(const Composite& composite) const ;
692 
696  bool hasPreviousSibling() const ;
697 
700  bool isPreviousSiblingOf(const Composite& composite) const ;
701 
705  bool hasNextSibling() const ;
706 
709  bool isNextSiblingOf(const Composite& composite) const ;
710 
713  bool isDescendantOf(const Composite& composite) const ;
714 
717  template <typename T>
718  bool hasAncestor(const T& dummy) const ;
719 
722  bool isAncestorOf(const Composite& composite) const ;
723 
727  bool isRelatedWith(const Composite& composite) const ;
728 
732  bool isHomomorph(const Composite& composite) const ;
733 
743  bool containsSelection() const ;
745 
751  virtual bool isValid() const ;
752 
757  virtual void dump(std::ostream& s = std::cout, Size depth = 0) const
758  ;
759 
761 
763 
770  void host(Visitor<Composite>& visitor);
771 
776  template <typename T>
777  bool applyAncestor(UnaryProcessor<T>& processor);
778 
783  template <typename T>
784  bool applyChild(UnaryProcessor<T>& processor);
785 
793  template <typename T>
794  bool applyDescendantPreorder(UnaryProcessor<T>& processor);
795 
803  template <typename T>
804  bool applyDescendantPostorder(UnaryProcessor<T>& processor);
805 
813  template <typename T>
814  bool applyDescendant(UnaryProcessor<T>& processor);
815 
822  template <typename T>
823  bool applyPreorder(UnaryProcessor<T>& processor);
824 
831  template <typename T>
832  bool applyPostorder(UnaryProcessor<T>& processor);
833 
840  template <typename T>
841  bool apply(UnaryProcessor<T>& processor);
842 
847  template <typename T>
848  bool applyLevel(UnaryProcessor<T>& processor, long level);
850 
851 
852 
854  {
855  public:
856 
858  AncestorIteratorTraits()
859 
860  : bound_(0),
861  ancestor_(0)
862  {
863  }
864 
866  AncestorIteratorTraits(const Composite& composite)
867 
868  : bound_(const_cast<Composite*>(&composite)),
869  ancestor_(0)
870  {
871  }
872 
874  AncestorIteratorTraits(const AncestorIteratorTraits& traits)
875 
876  : bound_(traits.bound_),
877  ancestor_(traits.ancestor_)
878  {
879  }
880 
882  const AncestorIteratorTraits& operator = (const AncestorIteratorTraits& traits)
883 
884  {
885  bound_ = traits.bound_;
886  ancestor_ = traits.ancestor_;
887  return *this;
888  }
889 
890  BALL_INLINE Composite* getContainer() { return bound_; }
891 
892  BALL_INLINE const Composite* getContainer() const { return bound_; }
893 
894  BALL_INLINE bool isSingular() const { return (bound_ == 0); }
895 
896  BALL_INLINE Composite* getPosition() { return ancestor_; }
897 
898  BALL_INLINE Composite* const& getPosition() const { return ancestor_; }
899 
900  BALL_INLINE bool operator == (const AncestorIteratorTraits& traits) const { return (ancestor_ == traits.ancestor_); }
901 
902  BALL_INLINE bool operator != (const AncestorIteratorTraits& traits) const { return !(ancestor_ == traits.ancestor_); }
903 
904  BALL_INLINE bool isValid() const { return (bound_ != 0 && ancestor_ != 0); }
905 
906  BALL_INLINE void invalidate() { bound_ = ancestor_ = 0; }
907 
908  BALL_INLINE void toBegin() { ancestor_ = bound_->parent_; }
909 
910  BALL_INLINE bool isBegin() const { return (ancestor_ == bound_->parent_); }
911 
912  BALL_INLINE void toEnd() { ancestor_ = 0; }
913 
914  BALL_INLINE bool isEnd() const { return (ancestor_ == 0); }
915 
916  BALL_INLINE Composite& getData() { return *ancestor_; }
917 
918  BALL_INLINE const Composite& getData() const { return *ancestor_; }
919 
920  BALL_INLINE void forward() { ancestor_ = ancestor_->parent_; }
921 
922  private:
923 
924  Composite* bound_;
925  Composite* ancestor_;
926  };
927 
929 
932 
933  AncestorIterator beginAncestor()
934  {
935  return AncestorIterator::begin(*this);
936  }
937 
938  AncestorIterator endAncestor()
939  {
940  return AncestorIterator::end(*this);
941  }
942 
945 
946  AncestorConstIterator beginAncestor() const
947  {
948  return AncestorConstIterator::begin(*this);
949  }
950 
951  AncestorConstIterator endAncestor() const
952  {
953  return AncestorConstIterator::end(*this);
954  }
955 
957  {
958  public:
959 
961 
962  : bound_(0),
963  child_(0)
964  {
965  }
966 
968 
969  : bound_((Composite *)&composite),
970  child_(0)
971  {
972  }
973 
975 
976  : bound_(traits.bound_),
977  child_(traits.child_)
978  {
979  }
980 
982 
983  {
984  bound_ = traits.bound_;
985  child_ = traits.child_;
986  return *this;
987  }
988 
989  BALL_INLINE Composite* getContainer() { return bound_; }
990 
991  BALL_INLINE const Composite* getContainer() const { return bound_; }
992 
993  BALL_INLINE bool isSingular() const { return (bound_ == 0); }
994 
995  BALL_INLINE Composite* getPosition() { return child_; }
996 
997  BALL_INLINE Composite* const& getPosition() const { return child_; }
998 
999  BALL_INLINE bool operator == (const ChildCompositeIteratorTraits& traits) const { return (child_ == traits.child_); }
1000 
1001  BALL_INLINE bool operator != (const ChildCompositeIteratorTraits& traits) const { return !(child_ == traits.child_); }
1002 
1003  BALL_INLINE bool isValid() const { return (bound_ != 0 && child_ != 0); }
1004 
1005  BALL_INLINE void invalidate() { bound_ = child_ = 0; }
1006 
1007  BALL_INLINE void toBegin() { child_ = bound_->first_child_; }
1008 
1009  BALL_INLINE bool isBegin() const { return (child_ == bound_->first_child_); }
1010 
1011  BALL_INLINE void toEnd() { child_ = 0; }
1012 
1013  BALL_INLINE bool isEnd() const { return (child_ == 0); }
1014 
1015  BALL_INLINE void toRBegin() { child_ = bound_->last_child_; }
1016 
1017  BALL_INLINE bool isRBegin() const { return (child_ == bound_->last_child_); }
1018 
1019  BALL_INLINE void toREnd() { child_ = 0; }
1020 
1021  BALL_INLINE bool isREnd() const { return (child_ == 0); }
1022 
1023  BALL_INLINE Composite& getData() { return *child_; }
1024 
1025  BALL_INLINE const Composite& getData() const { return *child_; }
1026 
1027  BALL_INLINE void forward() { child_ = child_->next_; }
1028 
1029  BALL_INLINE void backward()
1030  {
1031  if (child_ == 0)
1032  {
1033  // Allow decrementation for past-the-end iterators
1034  child_ = bound_->last_child_;
1035  }
1036  else
1037  {
1038  child_ = child_->previous_;
1039  }
1040  }
1041 
1042  private:
1043 
1046  };
1047 
1049 
1052 
1053  ChildCompositeIterator beginChildComposite()
1054 
1055  {
1056  return ChildCompositeIterator::begin(*this);
1057  }
1058 
1059  ChildCompositeIterator endChildComposite()
1060 
1061  {
1062  return ChildCompositeIterator::end(*this);
1063  }
1064 
1065 
1066 
1069 
1070  ChildCompositeConstIterator beginChildComposite() const
1071 
1072  {
1073  return ChildCompositeConstIterator::begin(*this);
1074  }
1075 
1076  ChildCompositeConstIterator endChildComposite() const
1077 
1078  {
1079  return ChildCompositeConstIterator::end(*this);
1080  }
1081 
1082 
1083 
1084  typedef std::reverse_iterator<ChildCompositeIterator> ChildCompositeReverseIterator;
1085 
1086  ChildCompositeReverseIterator rbeginChildComposite()
1087  {
1088  return ChildCompositeReverseIterator(endChildComposite());
1089  }
1090 
1091  ChildCompositeReverseIterator rendChildComposite()
1092  {
1093  return ChildCompositeReverseIterator(beginChildComposite());
1094  }
1095 
1096 
1097 
1098  typedef std::reverse_iterator<ChildCompositeConstIterator> ChildCompositeConstReverseIterator;
1099 
1100  ChildCompositeConstReverseIterator rbeginChildComposite() const
1101  {
1102  return ChildCompositeConstReverseIterator(endChildComposite());
1103  }
1104 
1105  ChildCompositeConstReverseIterator rendChildComposite() const
1106  {
1107  return ChildCompositeConstReverseIterator(beginChildComposite());
1108  }
1109 
1111  {
1112  public:
1113 
1115 
1116  : bound_(0),
1117  position_(0)
1118  {
1119  }
1120 
1122 
1123  : bound_(const_cast<Composite*>(&composite)),
1124  position_(0)
1125  {
1126  }
1127 
1129 
1130  : bound_(traits.bound_),
1131  position_(traits.position_)
1132  {
1133  }
1134 
1136 
1137  BALL_INLINE bool isValid() const
1138  {
1139  return ((bound_ != 0) && (position_ != 0));
1140  }
1141 
1143  {
1144  bound_ = traits.bound_;
1145  position_ = traits.position_;
1146  return *this;
1147  }
1148 
1149  BALL_INLINE Composite* getContainer() { return bound_; }
1150 
1151  BALL_INLINE const Composite* getContainer() const { return bound_; }
1152 
1153  BALL_INLINE bool isSingular() const { return (bound_ == 0); }
1154 
1155  BALL_INLINE Composite* getPosition() { return position_; }
1156 
1157  BALL_INLINE const Composite* getPosition() const { return position_; }
1158  BALL_INLINE void setPosition(Composite* position) { position_ = position; }
1159 
1160 
1161  BALL_INLINE Composite& getData() { return *position_; }
1162 
1163  BALL_INLINE const Composite& getData() const { return *position_; }
1164 
1165  BALL_INLINE bool operator == (const CompositeIteratorTraits& traits) const
1166  {
1167  return (position_ == traits.position_);
1168  }
1169 
1170  BALL_INLINE bool operator != (const CompositeIteratorTraits& traits) const
1171  {
1172  return !(position_ == traits.position_);
1173  }
1174 
1175  BALL_INLINE void invalidate()
1176  {
1177  bound_ = 0;
1178  position_ = 0;
1179  }
1180 
1181  BALL_INLINE void toBegin()
1182  {
1183  position_ = bound_;
1184  }
1185 
1186  BALL_INLINE bool isBegin() const
1187  {
1188  return (position_ == bound_);
1189  }
1190 
1191  BALL_INLINE void toEnd()
1192  {
1193  position_ = 0;
1194  }
1195 
1196  BALL_INLINE bool isEnd() const
1197  {
1198  return (position_ == 0);
1199  }
1200 
1201  BALL_INLINE void toRBegin()
1202  {
1203  if (bound_ != 0)
1204  {
1205  position_ = findPreviousPosition(0);
1206  }
1207  }
1208 
1209  BALL_INLINE bool isRBegin() const
1210  {
1211  return (position_ == findPreviousPosition(0));
1212  }
1213 
1214  BALL_INLINE void toREnd()
1215  {
1216  position_ = bound_;
1217  }
1218 
1219  BALL_INLINE bool isREnd() const
1220  {
1221  return (position_ == bound_);
1222  }
1223 
1224  BALL_INLINE void forward()
1225  {
1226  position_ = findNextPosition(position_);
1227  }
1228 
1229  BALL_INLINE void backward()
1230  {
1231  position_ = findPreviousPosition(position_);
1232  }
1233 
1234  protected:
1235 
1238 
1241 
1242  Composite* findPreviousPosition(Composite* p) const
1243  {
1244  // If we are at the root of the iterator, the
1245  // decrementing it results in an invalid iterator
1246  // (past-the-end).
1247  if (p == bound_)
1248  {
1249  return 0;
1250  }
1251  // If we decrement a past-the-end-iterator, we
1252  // start at the root and "fall down" on the right
1253  // hand side following the last_child_ pointers
1254  // until we hit bottom.
1255  else if (p == 0)
1256  {
1257  if (bound_->last_child_ == 0)
1258  {
1259  return bound_;
1260  }
1261  else
1262  {
1263  p = bound_->last_child_;
1264  }
1265  while (p->last_child_ != 0)
1266  {
1267  p = p->last_child_;
1268  }
1269  }
1270  // Normally, we just grab the guy to the
1271  // left in the doubly-linked child list.
1272  else if (p->previous_ != 0)
1273  {
1274  p = p->previous_;
1275 
1276  // If the guy to the left hast children,
1277  // we do the drop on the rigth again.
1278  while (p->last_child_ != 0)
1279  {
1280  p = p->last_child_;
1281  }
1282  }
1283  // Finally, if we can't go down and we can't go
1284  // left, we have to go upwards.
1285  else if (p != bound_)
1286  {
1287  p = p->parent_;
1288  }
1289 
1290  return p;
1291  }
1292 
1293  Composite* findNextPosition(Composite* p) const
1294  {
1295  // If we are in a past-the-end position, we stay put.
1296  if (p == 0)
1297  {
1298  return 0;
1299  }
1300  // Otherwise, we try the first child. If there's one,
1301  // that's our next position.
1302  else
1303  {
1304  if (p->first_child_ != 0)
1305  {
1306  p = p->first_child_;
1307  }
1308  else
1309  {
1310  // If we are already in the root node, we are done.
1311  if (p == bound_)
1312  {
1313  return 0;
1314  }
1315  // Otherwise, we try to walk to the right at the current level.
1316  if (p->next_ != 0)
1317  {
1318  p = p->next_;
1319  }
1320  // If that doesn't work out, we'll have to climb up again.
1321  // Now, we either revisit a node we have already been to, or we
1322  // are trying to climb up *beyond* our iteration root (bound_).
1323  // In the latter case, we return a past-the-end-iterator (0).
1324  else
1325  {
1326  // If we could not walk left or right and we are at the root
1327  // again, then we are done with the iteration (this is the
1328  // case if bound_ is a leaf node).
1329  while (p->next_ == 0)
1330  {
1331  p = p->parent_;
1332  if ((p == bound_) || (p == 0))
1333  {
1334  return 0;
1335  }
1336  }
1337  p = p->next_;
1338  }
1339  }
1340  }
1341  return p;
1342  }
1343  };
1344 
1346 
1349 
1350  CompositeIterator beginComposite() { return CompositeIterator::begin(*this); }
1351 
1352  CompositeIterator endComposite() { return CompositeIterator::end(*this); }
1353 
1356 
1357  CompositeConstIterator beginComposite() const
1358  {
1359  return CompositeConstIterator::begin(*this);
1360  }
1361 
1362  CompositeConstIterator endComposite() const
1363  {
1364  return CompositeConstIterator::end(*this);
1365  }
1366 
1367 
1368  typedef std::reverse_iterator<CompositeIterator> CompositeReverseIterator;
1369 
1370  CompositeReverseIterator rbeginComposite()
1371  {
1372  return CompositeReverseIterator(endComposite());
1373  }
1374 
1375  CompositeReverseIterator rendComposite()
1376  {
1377  return CompositeReverseIterator(beginComposite());
1378  }
1379 
1380 
1381  typedef std::reverse_iterator<CompositeConstIterator> CompositeConstReverseIterator;
1382 
1383  CompositeConstReverseIterator rbeginComposite() const
1384  {
1385  return CompositeConstReverseIterator(endComposite());
1386  }
1387 
1388  CompositeConstReverseIterator rendComposite() const
1389  {
1390  return CompositeConstReverseIterator(beginComposite());
1391  }
1392 
1393  /*
1394  * This function removes and deletes all composites that are
1395  * supplied in the list of children.
1396  */
1397  void deleteChildrenList_(std::list<Composite*>& composites);
1398 
1399  private:
1400 
1402  Size getHeight_(Size size, Size& max_height) const ;
1403 
1405  Size countDescendants_() const ;
1406 
1408  void clone_(Composite& parent, Composite& stack) const ;
1409 
1410  // \throws Exception::GeneralException
1411  template <typename T>
1412  bool applyLevelNostart_(UnaryProcessor<T>& processor, long level);
1413 
1414  // \throws Exception::GeneralException
1415  template <typename T>
1416  bool applyChildNostart_(UnaryProcessor<T>& processor);
1417 
1418  // \throws Exception::GeneralException
1419  template <typename T>
1420  bool applyPreorderNostart_(UnaryProcessor<T>& processor);
1421 
1422  // \throws Exception::GeneralException
1423  template <typename T>
1424  bool applyDescendantPreorderNostart_(UnaryProcessor<T>& processor);
1425 
1426  // \throws Exception::GeneralException
1427  template <typename T>
1428  bool applyDescendantPostorderNostart_(UnaryProcessor<T>& processor);
1429 
1430 
1431  void updateSelection_();
1432  void determineSelection_();
1433  void select_(bool update_parent = true);
1434  void deselect_(bool update_parent = true);
1435 
1436  // private attributes
1437 
1444  unsigned char properties_;
1450  };
1451 
1452  template <typename T>
1454  {
1455  if (processor.start() == false)
1456  {
1457  return false;
1458  }
1459 
1460  Processor::Result result;
1461 
1462  for (Composite* composite = parent_; composite != 0; composite = composite->parent_)
1463  {
1464  T* t_ptr;
1465  if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
1466  {
1467  result = processor(*t_ptr);
1468  if (result <= Processor::BREAK)
1469  {
1470  return (result == Processor::BREAK);
1471  }
1472  }
1473  }
1474 
1475  return processor.finish();
1476  }
1477 
1478  template <typename T>
1480  {
1481  return processor.start() && applyChildNostart_(processor) && processor.finish();
1482  }
1483 
1484  template <typename T>
1486  {
1488 
1489  for (Composite* composite = first_child_;
1490  composite != 0; composite = composite->next_)
1491  {
1492  T* t_ptr;
1493  if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
1494  {
1495  result = processor(*t_ptr);
1496  if (result <= Processor::BREAK)
1497  {
1498  break;
1499  }
1500  }
1501  }
1502 
1503  return (result >= Processor::BREAK);
1504  }
1505 
1506  template <typename T>
1508  {
1509  return processor.start() && applyDescendantPreorderNostart_(processor) && processor.finish();
1510  }
1511 
1512  template <typename T>
1514  {
1515  Processor::Result result;
1516 
1517  for (Composite* composite = first_child_;
1518  composite != 0; composite = composite->next_)
1519  {
1520  T* t_ptr;
1521  if ((t_ptr = dynamic_cast<T*>(composite)) != 0)
1522  {
1523  result = processor(*t_ptr);
1524 
1525  if (result <= Processor::BREAK)
1526  {
1527  return (result == Processor::BREAK);
1528  }
1529  }
1530 
1531  if (composite->first_child_ != 0 && composite->applyDescendantPreorderNostart_(processor) == false)
1532  {
1533  return false;
1534  }
1535  }
1536 
1537  return true;
1538  }
1539 
1540  template <typename T>
1542  {
1543  return processor.start() && applyDescendantPostorderNostart_(processor) && processor.finish();
1544  }
1545 
1546  template <typename T>
1548  {
1549  Processor::Result result;
1550 
1551  for (Composite* composite = first_child_;
1552  composite != 0; composite = composite->next_)
1553  {
1554  if (composite->first_child_ != 0 &&
1555  composite->applyDescendantPostorderNostart_(processor) == false)
1556  {
1557  return false;
1558  }
1559 
1560  T* t_ptr = dynamic_cast<T*>(composite);
1561  if (t_ptr != 0)
1562  {
1563  result = processor(*t_ptr);
1564 
1565  if (result <= Processor::BREAK)
1566  {
1567  return (result == Processor::BREAK);
1568  }
1569  }
1570  }
1571 
1572  return true;
1573  }
1574 
1575  template <typename T>
1577  {
1578  if (!processor.start() || !applyDescendantPostorderNostart_(processor))
1579  {
1580  return false;
1581  }
1582 
1583  T* t_ptr = dynamic_cast<T*>(this);
1584 
1585  return (t_ptr != 0 &&
1586  processor(*t_ptr) >= Processor::BREAK &&
1587  processor.finish() );
1588  }
1589 
1590  template <typename T>
1591  bool Composite::applyLevel(UnaryProcessor<T>& processor, long level)
1592  {
1593  return processor.start() && applyLevelNostart_(processor, level) && processor.finish();
1594  }
1595 
1596  template <typename T>
1598  {
1599  if (level == 0)
1600  {
1601  T* t_ptr = dynamic_cast<T*>(this);
1602  if (t_ptr != 0)
1603  {
1604  Processor::Result result = processor(*t_ptr);
1605 
1606  if (result <= Processor::BREAK)
1607  {
1608  return (result == Processor::BREAK);
1609  }
1610  }
1611  }
1612  else
1613  {
1614  if (--level == 0)
1615  {
1616  return applyChildNostart_(processor);
1617  }
1618  else
1619  {
1620  if (level > 0)
1621  {
1622  for (Composite* composite = first_child_;
1623  composite != 0; composite = composite->next_)
1624  {
1625  if (composite->first_child_ != 0 && composite->applyLevelNostart_(processor, level) == false)
1626  {
1627  return false;
1628  }
1629  }
1630  }
1631  }
1632  }
1633  return true;
1634  }
1635 
1636  template <typename T>
1638  {
1639  Processor::Result result;
1640  bool return_value;
1641  T* t_ptr = dynamic_cast<T*>(this);
1642  if (t_ptr != 0)
1643  {
1644  result = processor(*t_ptr);
1645 
1646  if (result <= Processor::BREAK)
1647  {
1648  return_value = (result == Processor::BREAK);
1649  }
1650  else
1651  {
1652  return_value = applyDescendantPreorderNostart_(processor);
1653  }
1654  }
1655  else
1656  {
1657  return_value = applyDescendantPreorderNostart_(processor);
1658  }
1659 
1660  return return_value;
1661  }
1662 
1663  template <typename T>
1665  {
1666  return applyDescendantPreorder(processor);
1667  }
1668 
1669  template <typename T>
1671  {
1672  return processor.start() && applyPreorderNostart_(processor) && processor.finish();
1673  }
1674 
1675  template <typename T>
1676  BALL_INLINE
1678  {
1679  return applyPreorder(processor);
1680  }
1681 
1682  template <typename T>
1683  BALL_INLINE
1684  T* Composite::getAncestor(const T& /* dummy */)
1685 
1686  {
1687  T* T_ptr = 0;
1688 
1689  for (Composite* composite_ptr = parent_;
1690  composite_ptr != 0; composite_ptr = composite_ptr->parent_)
1691  {
1692  T_ptr = dynamic_cast<T*>(composite_ptr);
1693  if (T_ptr != 0)
1694  {
1695  break;
1696  }
1697  }
1698 
1699  return T_ptr;
1700  }
1701 
1702  template <typename T>
1703  BALL_INLINE
1704  const T* Composite::getAncestor(const T& /* dummy */) const
1705 
1706  {
1707  T* t_ptr = 0;
1708  for (Composite* composite_ptr = parent_;
1709  composite_ptr != 0; composite_ptr = composite_ptr->parent_)
1710  {
1711  if ((t_ptr = dynamic_cast<T*>(composite_ptr)) != 0)
1712  {
1713  break;
1714  }
1715  }
1716 
1717  return const_cast<const T*>(t_ptr);
1718  }
1719 
1720  template <typename T>
1721  BALL_INLINE
1722  T* Composite::getPrevious(const T& /* dummy */)
1723 
1724  {
1725  // create an iterator bound to the root of the subtree
1727 
1728  // set its position to the current composite
1729  it.getTraits().setPosition(this);
1730 
1731  // walk back until we find something
1732  // or we cannot walk any further
1733  if (+it)
1734  {
1735  do
1736  {
1737  --it;
1738  }
1739  while (+it && !RTTI::isKindOf<T>(*it));
1740  }
1741 
1742  // return a NULL pointer if nothing was found
1743  Composite* ptr = 0;
1744  if (+it)
1745  {
1746  ptr = &*it;
1747  }
1748 
1749  return dynamic_cast<T*>(ptr);
1750  }
1751 
1752  template <typename T>
1753  BALL_INLINE
1754  const T* Composite::getPrevious(const T& dummy) const
1755 
1756  {
1757  // cast away the constness of this and call the non-const method
1758  Composite* nonconst_this = const_cast<Composite*>(this);
1759 
1760  return const_cast<const T*>(nonconst_this->getPrevious(dummy));
1761  }
1762 
1763  template <typename T>
1764  BALL_INLINE
1765  T* Composite::getNext(const T& /* dummy */)
1766 
1767  {
1768  // create an iterator bound to the root of the subtree
1770 
1771  // set its position to the current composite
1772  it.getTraits().setPosition(this);
1773 
1774  // walk forward until we find something
1775  // or we cannot walk any further
1776  do
1777  {
1778  it++;
1779  }
1780  while (it.isValid() && !RTTI::isKindOf<T>(*it));
1781 
1782 
1783  // return a NULL pointer if nothing was found
1784  Composite* ptr = 0;
1785  if (+it)
1786  {
1787  ptr = &*it;
1788  }
1789 
1790  return dynamic_cast<T*>(ptr);
1791  }
1792 
1793  template <typename T>
1794  BALL_INLINE
1795  const T* Composite::getNext(const T& dummy) const
1796 
1797  {
1798  // cast away the constness of this and call the non-const method
1799  Composite* nonconst_this = const_cast<Composite*>(this);
1800 
1801  return const_cast<const T*>(nonconst_this->getNext(dummy));
1802  }
1803 
1804  template <typename T>
1805  BALL_INLINE
1806  bool Composite::hasAncestor(const T& dummy ) const
1807 
1808  {
1809  return (getAncestor(dummy) != 0);
1810  }
1811 
1812 # ifndef BALL_NO_INLINE_FUNCTIONS
1813 # include <BALL/CONCEPT/composite.iC>
1814 # endif
1815 
1816 
1817 } // namespace BALL
1818 
1819 #endif // BALL_CONCEPT_COMPOSITE_H