text: /*
   * Copyright (C) 2013 Google Inc. All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are
   * met:
   *
   *     * Redistributions of source code must retain the above copyright
   * notice, this list of conditions and the following disclaimer.
   *     * Redistributions in binary form must reproduce the above
   * copyright notice, this list of conditions and the following disclaimer
   * in the documentation and/or other materials provided with the
   * distribution.
   *     * Neither the name of Google Inc. nor the names of its
   * contributors may be used to endorse or promote products derived from
   * this software without specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  
  #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_
  #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_
  
  #include "base/check_op.h"
  
  namespace WTF {
  
  //
  // TreeNode is generic, ContainerNode-like linked tree data structure.
  // There are a few notable difference between TreeNode and Node:
  //
  //  * Each TreeNode node is NOT ref counted. The user have to retain its
  //    lifetime somehow.
  //    FIXME: lifetime management could be parameterized so that ref counted
  //    implementations can be used.
  //  * It checks invalid input. The callers have to ensure that given
  //    parameter is sound.
  //  * There is no branch-leaf difference. Every node can be a parent of other
  //    node.
  //
  // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling
  // pointers.
  // As it is used in HTMLImport it is safe since they all die together.
  template <class T>
  class TreeNode {
   public:
    typedef T NodeType;
  
    TreeNode()
        : next_(nullptr),
          previous_(nullptr),
          parent_(nullptr),
          first_child_(nullptr),
          last_child_(nullptr) {}
  
    NodeType* Next() const { return next_; }
    NodeType* Previous() const { return previous_; }
    NodeType* Parent() const { return parent_; }
    NodeType* FirstChild() const { return first_child_; }
    NodeType* LastChild() const { return last_child_; }
    NodeType* Here() const {
      return static_cast<NodeType*>(const_cast<TreeNode*>(this));
    }
  
    bool Orphan() const {
      return !parent_ && !next_ && !previous_ && !first_child_ && !last_child_;
    }
    bool HasChildren() const { return first_child_; }
  
    void InsertBefore(NodeType* new_child, NodeType* ref_child) {
      DCHECK(!new_child->Parent());
      DCHECK(!new_child->Next());
      DCHECK(!new_child->Previous());
  
      DCHECK(!ref_child || this == ref_child->Parent());
  
      if (!ref_child) {
        AppendChild(new_child);
        return;
      }
  
      NodeType* new_previous = ref_child->Previous();
      new_child->parent_ = Here();
      new_child->next_ = ref_child;
      new_child->previous_ = new_previous;
      ref_child->previous_ = new_child;
      if (new_previous)
        new_previous->next_ = new_child;
      else
        first_child_ = new_child;
    }
  
    void AppendChild(NodeType* child) {
      DCHECK(!child->Parent());
      DCHECK(!child->Next());
      DCHECK(!child->Previous());
  
      child->parent_ = Here();
  
      if (!last_child_) {
        DCHECK(!first_child_);
        last_child_ = first_child_ = child;
        return;
      }
  
      DCHECK(!last_child_->next_);
      NodeType* old_last = last_child_;
      last_child_ = child;
  
      child->previous_ = old_last;
      old_last->next_ = child;
    }
  
    NodeType* RemoveChild(NodeType* child) {
      DCHECK_EQ(child->Parent(), this);
  
      if (first_child_ == child)
        first_child_ = child->Next();
      if (last_child_ == child)
        last_child_ = child->Previous();
  
      NodeType* old_next = child->Next();
      NodeType* old_previous = child->Previous();
      child->parent_ = child->next_ = child->previous_ = nullptr;
  
      if (old_next)
        old_next->previous_ = old_previous;
      if (old_previous)
        old_previous->next_ = old_next;
  
      return child;
    }
  
    void TakeChildrenFrom(NodeType* old_parent) {
      DCHECK_NE(old_parent, this);
      while (old_parent->HasChildren()) {
        NodeType* child = old_parent->FirstChild();
        old_parent->RemoveChild(child);
        AppendChild(child);
      }
    }
  
   private:
    NodeType* next_;
    NodeType* previous_;
    NodeType* parent_;
    NodeType* first_child_;
    NodeType* last_child_;
  };
  
  template <class T>
  inline typename TreeNode<T>::NodeType* TraverseNext(
      const TreeNode<T>* current,
      const TreeNode<T>* stay_within = nullptr) {
    if (typename TreeNode<T>::NodeType* next = current->FirstChild())
      return next;
    if (current == stay_within)
      return nullptr;
    if (typename TreeNode<T>::NodeType* next = current->Next())
      return next;
    for (typename TreeNode<T>::NodeType* parent = current->Parent(); parent;
         parent = parent->Parent()) {
      if (parent == stay_within)
        return nullptr;
      if (typename TreeNode<T>::NodeType* next = parent->Next())
        return next;
    }
  
    return nullptr;
  }
  
  template <class T>
  inline typename TreeNode<T>::NodeType* TraverseFirstPostOrder(
      const TreeNode<T>* current) {
    typename TreeNode<T>::NodeType* first = current->Here();
    while (first->FirstChild())
      first = first->FirstChild();
    return first;
  }
  
  template <class T>
  inline typename TreeNode<T>::NodeType* TraverseNextPostOrder(
      const TreeNode<T>* current,
      const TreeNode<T>* stay_within = nullptr) {
    if (current == stay_within)
      return nullptr;
  
    typename TreeNode<T>::NodeType* next = current->Next();
    if (!next)
      return current->Parent();
    while (next->FirstChild())
      next = next->FirstChild();
    return next;
  }
  
  }  // namespace WTF
  
  using WTF::TreeNode;
  using WTF::TraverseNext;
  using WTF::TraverseNextPostOrder;
  
  #endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_
  