text: /*
   * Copyright (C) 2011 Apple 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:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. 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.
   *
   * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS 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 APPLE INC. OR ITS 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 DoublyLinkedList_h
  #define DoublyLinkedList_h
  
  namespace WTF {
  
  template <typename Node> class DoublyLinkedList {
  public:
      DoublyLinkedList();
      
      bool isEmpty();
  
      Node* head();
  
      void append(Node*);
      void remove(Node*);
  
  private:
      Node* m_head;
      Node* m_tail;
  };
  
  template <typename Node> inline DoublyLinkedList<Node>::DoublyLinkedList()
      : m_head(0)
      , m_tail(0)
  {
  }
  
  template <typename Node> inline bool DoublyLinkedList<Node>::isEmpty()
  {
      return !m_head;
  }
  
  template <typename Node> inline Node* DoublyLinkedList<Node>::head()
  {
      return m_head;
  }
  
  template <typename Node> inline void DoublyLinkedList<Node>::append(Node* node)
  {
      if (!m_tail) {
          ASSERT(!m_head);
          m_head = node;
          m_tail = node;
          node->setPrev(0);
          node->setNext(0);
          return;
      }
  
      ASSERT(m_head);
      m_tail->setNext(node);
      node->setPrev(m_tail);
      node->setNext(0);
      m_tail = node;
  }
  
  template <typename Node> inline void DoublyLinkedList<Node>::remove(Node* node)
  {
      if (node->prev()) {
          ASSERT(node != m_head);
          node->prev()->setNext(node->next());
      } else {
          ASSERT(node == m_head);
          m_head = node->next();
      }
  
      if (node->next()) {
          ASSERT(node != m_tail);
          node->next()->setPrev(node->prev());
      } else {
          ASSERT(node == m_tail);
          m_tail = node->prev();
      }
  }
  
  } // namespace WTF
  
  using WTF::DoublyLinkedList;
  
  #endif
  