Dogcows Code - chaz/yoink/blob - src/Moof/Tree.hh

   1
   2 /*******************************************************************************
   3
   4  Copyright (c) 2009, Charles McGarvey
   5  All rights reserved.
   6
   7  Redistribution   and   use  in  source  and  binary  forms,  with  or  without
   8  modification, are permitted provided that the following conditions are met:
   9
  10    * Redistributions  of  source  code  must retain the above copyright notice,
  11      this list of conditions and the following disclaimer.
  12    * Redistributions  in binary form must reproduce the above copyright notice,
  13      this  list of conditions and the following disclaimer in the documentation
  14      and/or other materials provided with the distribution.
  15
  16  THIS  SOFTWARE  IS  PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  AND  ANY  EXPRESS  OR  IMPLIED  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  DISCLAIMED.  IN  NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  20  FOR  ANY  DIRECT,  INDIRECT,  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  DAMAGES  (INCLUDING,  BUT  NOT  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  22  SERVICES;  LOSS  OF  USE,  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  23  CAUSED  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  24  OR  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  25  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26
  27 *******************************************************************************/
  28
  29 #ifndef _MOOF_TREE_HH_
  30 #define _MOOF_TREE_HH_
  31
  32 #include <boost/shared_ptr.hpp>
  33 #include <boost/weak_ptr.hpp>
  34
  35
  36 namespace Mf {
  37
  38
  39 template <typename T>
  40 class Tree
  41 {
  42 public:
  43         typedef boost::shared_ptr<Tree> Ptr;
  44         typedef boost::weak_ptr<Tree>   WeakPtr;
  45
  46         T               node;
  47
  48 protected:
  49         WeakPtr parent_;
  50         WeakPtr prevSibling_;
  51         Ptr             next_;
  52         WeakPtr lastDescendant_;
  53
  54         inline static void init(Ptr itself)
  55         {
  56                 itself->prevSibling_ = itself;
  57                 itself->lastDescendant_ = itself;
  58         }
  59
  60         Tree() {}
  61
  62         explicit Tree(const T& item) :
  63                 node(item) {}
  64
  65 public:
  66
  67         inline void print() const
  68         {
  69                 std::cout << "==================" << std::endl;
  70                 std::cout << "    Node: " << getThis() << std::endl;
  71                 std::cout << "  Parent: " << parent_.lock() << std::endl;
  72                 std::cout << " PrevSib: " << prevSibling_.lock() << std::endl;
  73                 std::cout << "    Next: " << next_ << std::endl;
  74                 std::cout << "LastDesc: " << lastDescendant_.lock() << std::endl;
  75                 //std::cout << "   Value: " << node << std::endl;
  76                 std::cout << "==================" << std::endl;
  77         }
  78
  79         inline static Ptr createNewNode()
  80         {
  81                 Ptr newNode = Ptr(new Tree<T>());
  82         }
  83
  84         inline static Ptr createNewNode(const T& item)
  85         {
  86                 Ptr newNode = Ptr(new Tree<T>(item));
  87                 init(newNode);
  88                 return newNode;
  89         }
  90
  91         inline Ptr getNext() const
  92         {
  93                 return next_;
  94         }
  95
  96         inline Ptr getPrevious() const
  97         {
  98                 Ptr parent = getParent();
  99
 100                 if (parent)
 101                 {
 102                         if (parent->getNext().get() == this)
 103                         {
 104                                 return parent;
 105                         }
 106                         else
 107                         {
 108                                 return prevSibling_.lock()->getLastDescendant();
 109                         }
 110                 }
 111
 112                 return Ptr();
 113         }
 114
 115         inline Ptr getFirstChild() const
 116         {
 117                 if (next_ && next_->getParent().get() == this)
 118                 {
 119                         return next_;
 120                 }
 121
 122                 return Ptr();
 123         }
 124
 125         inline Ptr getLastChild() const
 126         {
 127                 Ptr child = getFirstChild();
 128
 129                 if (child)
 130                 {
 131                         child = child->prevSibling_.lock();
 132                 }
 133
 134                 return child;
 135         }
 136
 137         inline Ptr getChild(int index) const
 138         {
 139                 Ptr child = getFirstChild();
 140
 141                 for (int i = 0; child && i < index; ++i)
 142                 {
 143                         child = child->getNextSibling();
 144                 }
 145
 146                 return child;
 147         }
 148
 149         inline Ptr getNextSibling() const
 150         {
 151                 Ptr sibling = getLastDescendant()->getNext();
 152
 153                 if (sibling && sibling->getParent() != getParent())
 154                 {
 155                         return Ptr();
 156                 }
 157
 158                 return sibling;
 159         }
 160
 161         inline Ptr getPreviousSibling() const
 162         {
 163                 Ptr parent = getParent();
 164
 165                 if (parent && parent->getNext().get() != this)
 166                 {
 167                         return prevSibling_.lock();
 168                 }
 169
 170                 return Ptr();
 171         }
 172
 173         inline Ptr getParent() const
 174         {
 175                 return parent_.lock();
 176         }
 177
 178         inline Ptr getLastDescendant() const
 179         {
 180                 return lastDescendant_.lock();
 181         }
 182
 183         inline Ptr getThis() const
 184         {
 185                 if (next_)
 186                 {
 187                         return next_->getPrevious();
 188                 }
 189
 190                 return getLastDescendant();
 191         }
 192
 193         inline bool isRoot() const
 194         {
 195                 return getParent().get() == 0;
 196         }
 197
 198         inline bool isLeaf() const
 199         {
 200                 return getLastDescendant().get() == this;
 201         }
 202
 203         inline bool isDescendantOf(Ptr ancestor) const
 204         {
 205                 Ptr temp = getParent();
 206
 207                 while (temp)
 208                 {
 209                         if (temp.get() == this) return true;
 210
 211                         temp = temp->getParent();
 212                 }
 213
 214                 return false;
 215         }
 216
 217
 218         class Iterator
 219         {
 220                 Ptr current;
 221
 222         public:
 223
 224         };
 225
 226
 227         void addChild(Ptr subtree)
 228         {
 229         //WeakPtr       parent_;
 230         //WeakPtr       prevSibling_;
 231         //Ptr           next_;
 232         //WeakPtr       lastDescendant_;
 233
 234                 subtree->remove();
 235
 236                 Ptr firstChild = getFirstChild();
 237                 Ptr lastChild = getLastChild();
 238                 Ptr nextSibling = getNextSibling();
 239                 Ptr lastDescendant = getLastDescendant();
 240                 Ptr newLastDescendant = subtree->getLastDescendant();
 241                 Ptr parent = getThis();
 242
 243                 // 1. If parent is leaf, set parent.next to subtree.
 244
 245                 if (isLeaf())
 246                 {
 247                         next_ = subtree;
 248                 }
 249
 250                 // 2. Set parent.last_descendant to subtree.last_descendant.
 251
 252                 Ptr temp = parent;
 253                 while (temp && temp->getLastDescendant() == lastDescendant)
 254                 {
 255                         temp->lastDescendant_ = newLastDescendant;
 256                         temp = temp->getParent();
 257                 }
 258
 259                 // 3. Set subtree.parent to parent.
 260
 261                 subtree->parent_ = parent;
 262
 263                 // 4. Set parent.first_child.prev_sibling to subtree.
 264
 265                 if (firstChild)
 266                 {
 267                         firstChild->prevSibling_ = subtree;
 268                 }
 269
 270                 // 5. Set subtree.prev_sibling to parent.last_child.
 271                 // 6. Set parent.last_child.last_descendant.next to subtree.
 272
 273                 if (lastChild)
 274                 {
 275                         subtree->prevSibling_ = lastChild;
 276                         lastChild->getLastDescendant()->next_ = subtree;
 277                 }
 278                 else
 279                 {
 280                         subtree->prevSibling_ = subtree;
 281                 }
 282
 283                 // 7. Set subtree.last_descendant.next to parent.next_sibling.
 284
 285                 if (nextSibling)
 286                 {
 287                         subtree->getLastDescendant()->next_ = nextSibling;
 288                 }
 289         }
 290
 291         void remove()
 292         {
 293                 Ptr parent = getParent();
 294                 Ptr prevSibling = getPreviousSibling();
 295                 Ptr nextSibling = getNextSibling();
 296                 Ptr lastDescendant = getLastDescendant();
 297                 Ptr previous = getPrevious();
 298
 299                 Ptr newLastDescendant;
 300
 301                 // 1. Fix last descendant of each direct ancestor.
 302
 303                 if (prevSibling) newLastDescendant = prevSibling->getLastDescendant();
 304                 else             newLastDescendant = parent;
 305
 306                 Ptr temp = parent;
 307                 while (temp && temp->getLastDescendant() == lastDescendant)
 308                 {
 309                         temp->lastDescendant_ = newLastDescendant;
 310                         temp = temp->getParent();
 311                 }
 312
 313                 // 2. Fix next of previous.
 314
 315                 if (previous)
 316                 {
 317                         previous->next_ = nextSibling;
 318                 }
 319
 320                 // 3. Fix the previous sibling of next sibling.
 321
 322                 if (nextSibling)
 323                 {
 324                         nextSibling->prevSibling_ = prevSibling;
 325                 }
 326
 327                 // 4. Once detached, the subtree root has no parent or siblings.
 328
 329                 parent_.reset();
 330                 prevSibling_ = getThis();
 331         }
 332
 333 };
 334
 335
 336 } // namespace Mf
 337
 338 #endif // _MOOF_TREE_HH_
 339
 340 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 341