Home | History | Annotate | Download | only in wtf 
      1 /*
      2  * Copyright (C) 2013 Google Inc. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions are
      6  * met:
      7  *
      8  *     * Redistributions of source code must retain the above copyright
      9  * notice, this list of conditions and the following disclaimer.
     10  *     * Redistributions in binary form must reproduce the above
     11  * copyright notice, this list of conditions and the following disclaimer
     12  * in the documentation and/or other materials provided with the
     13  * distribution.
     14  *     * Neither the name of Google Inc. nor the names of its
     15  * contributors may be used to endorse or promote products derived from
     16  * this software without specific prior written permission.
     17  *
     18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29  */
     30 
     31 #ifndef TreeNode_h
     32 #define TreeNode_h
     33 
     34 #include "wtf/Assertions.h"
     35 
     36 namespace WTF {
     37 
     38 //
     39 // TreeNode is generic, ContainerNode-like linked tree data structure.
     40 // There are a few notable difference between TreeNode and Node:
     41 //
     42 //  * Each TreeNode node is NOT ref counted. The user have to retain its lifetime somehow.
     43 //    FIXME: lifetime management could be parameterized so that ref counted implementations can be used.
     44 //  * It ASSERT()s invalid input. The callers have to ensure that given parameter is sound.
     45 //  * There is no branch-leaf difference. Every node can be a parent of other node.
     46 //
     47 template <class T>
     48 class TreeNode {
     49 public:
     50     typedef T NodeType;
     51 
     52     TreeNode()
     53         : m_next(0)
     54         , m_previous(0)
     55         , m_parent(0)
     56         , m_firstChild(0)
     57         , m_lastChild(0)
     58     {
     59     }
     60 
     61     NodeType* next() const { return m_next; }
     62     NodeType* previous() const { return m_previous; }
     63     NodeType* parent() const { return m_parent; }
     64     NodeType* firstChild() const { return m_firstChild; }
     65     NodeType* lastChild() const { return m_lastChild; }
     66     NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); }
     67 
     68     bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; }
     69     bool hasChildren() const { return m_firstChild; }
     70 
     71     void insertBefore(NodeType* newChild, NodeType* refChild)
     72     {
     73         ASSERT(!newChild->parent());
     74         ASSERT(!newChild->next());
     75         ASSERT(!newChild->previous());
     76 
     77         ASSERT(!refChild || this == refChild->parent());
     78 
     79         if (!refChild) {
     80             appendChild(newChild);
     81             return;
     82         }
     83 
     84         NodeType* newPrevious = refChild->previous();
     85         newChild->m_parent = here();
     86         newChild->m_next = refChild;
     87         newChild->m_previous = newPrevious;
     88         refChild->m_previous = newChild;
     89         if (newPrevious)
     90             newPrevious->m_next = newChild;
     91         else
     92             m_firstChild = newChild;
     93     }
     94 
     95     void appendChild(NodeType* child)
     96     {
     97         ASSERT(!child->parent());
     98         ASSERT(!child->next());
     99         ASSERT(!child->previous());
    100 
    101         child->m_parent = here();
    102 
    103         if (!m_lastChild) {
    104             ASSERT(!m_firstChild);
    105             m_lastChild = m_firstChild = child;
    106             return;
    107         }
    108 
    109         ASSERT(!m_lastChild->m_next);
    110         NodeType* oldLast = m_lastChild;
    111         m_lastChild = child;
    112 
    113         child->m_previous = oldLast;
    114         oldLast->m_next = child;
    115     }
    116 
    117     NodeType* removeChild(NodeType* child)
    118     {
    119         ASSERT(child->parent() == this);
    120 
    121         if (m_firstChild == child)
    122             m_firstChild = child->next();
    123         if (m_lastChild == child)
    124             m_lastChild = child->previous();
    125 
    126         NodeType* oldNext = child->next();
    127         NodeType* oldPrevious = child->previous();
    128         child->m_parent = child->m_next = child->m_previous = 0;
    129 
    130         if (oldNext)
    131             oldNext->m_previous = oldPrevious;
    132         if (oldPrevious)
    133             oldPrevious->m_next = oldNext;
    134 
    135         return child;
    136     }
    137 
    138 private:
    139     NodeType* m_next;
    140     NodeType* m_previous;
    141     NodeType* m_parent;
    142     NodeType* m_firstChild;
    143     NodeType* m_lastChild;
    144 };
    145 
    146 template<class T>
    147 inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
    148 {
    149     if (typename TreeNode<T>::NodeType* next = current->firstChild())
    150         return next;
    151     if (current == stayWithin)
    152         return 0;
    153     if (typename TreeNode<T>::NodeType* next = current->next())
    154         return next;
    155     for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) {
    156         if (parent == stayWithin)
    157             return 0;
    158         if (typename TreeNode<T>::NodeType* next = parent->next())
    159             return next;
    160     }
    161 
    162     return 0;
    163 }
    164 
    165 template<class T>
    166 inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current)
    167 {
    168     typename TreeNode<T>::NodeType* first = current->here();
    169     while (first->firstChild())
    170         first = first->firstChild();
    171     return first;
    172 }
    173 
    174 template<class T>
    175 inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
    176 {
    177     if (current == stayWithin)
    178         return 0;
    179 
    180     typename TreeNode<T>::NodeType* next = current->next();
    181     if (!next)
    182         return current->parent();
    183     while (next->firstChild())
    184         next = next->firstChild();
    185     return next;
    186 }
    187 
    188 }
    189 
    190 using WTF::TreeNode;
    191 using WTF::traverseNext;
    192 using WTF::traverseNextPostOrder;
    193 
    194 #endif
    195