00001 #include "SundanceRivaraTreeNode.hpp" 00002 #include "PlayaExceptions.hpp" 00003 00004 using namespace Sundance::Rivara; 00005 using namespace Sundance; 00006 using namespace Sundance; 00007 using namespace Teuchos; 00008 00009 TreeNode::TreeNode() 00010 : parent_(0), left_(0), right_(0) 00011 {;} 00012 00013 void TreeNode::deleteChildren() 00014 { 00015 if (left_ != 0) delete left_; 00016 if (right_ != 0) delete right_; 00017 } 00018 00019 const TreeNode* TreeNode::first() const 00020 { 00021 /* keep walking left as long as possible */ 00022 if (left_ != 0) return left_->first(); 00023 return this; 00024 } 00025 00026 const TreeNode* TreeNode::last() const 00027 { 00028 /* keep walking right as long as possible */ 00029 if (right_ != 0) return right_->last(); 00030 return this; 00031 } 00032 00033 bool TreeNode::isRightChild() const 00034 { 00035 /* return true if I am the right child of my parent */ 00036 if (parent_!=0 && parent_->right_ == this) return true; 00037 return false; 00038 } 00039 00040 bool TreeNode::isLeftChild() const 00041 { 00042 /* return true if I am the left child of my parent */ 00043 if (parent_!=0 && parent_->left_ == this) return true; 00044 return false; 00045 } 00046 00047 const TreeNode* TreeNode::next() const 00048 { 00049 00050 /* walk up the tree until we are at either the root or are the 00051 * left child */ 00052 TreeNode* pos = const_cast<TreeNode*>(this); 00053 00054 while (pos->isRightChild()) 00055 { 00056 pos = pos->parent_; 00057 } 00058 00059 /* if we are the left child, begin at the leftmost leaf of 00060 * the right sibling tree */ 00061 if (pos->isLeftChild()) 00062 { 00063 return pos->parent_->right_->first(); 00064 } 00065 00066 /* if we are at the root, there are no more unwalked leaves */ 00067 if (pos->parent_==0) return pos->parent_; 00068 00069 /* if we get to this point, there's a bug in this code */ 00070 TEUCHOS_TEST_FOR_EXCEPT(true); 00071 00072 return pos->parent_; 00073 } 00074 00075 int TreeNode::numLeaves() const 00076 { 00077 if (hasChildren()) 00078 { 00079 return left_->numLeaves() + right_->numLeaves(); 00080 } 00081 return 1; 00082 } 00083 00084 00085 00086 00087