#ifndef DOUBLY_LINKED_LIST_CLASS
#define DOUBLY_LINKED_LIST_CLASS

/*
*  Name   : doubly_linked_list
*  Author : Chris Koeritz
**
* Copyright (c) 1998-$now By Author.  This program is free software; you can
* redistribute it and/or modify it under the terms of the GNU General Public
* License as published by the Free Software Foundation; either version 2 of
* the License or (at your option) any later version.  This is online at:
*     http://www.fsf.org/copyleft/gpl.html
* Please send any updates to: fred@gruntose.com
*/

namespace nodes {

class node;  // forward.

//! Implements a guarded, doubly linked list structure.
/*!
  The list is viewed one element at a time, through the monocular of an
  iterator, which keeps track of the current position in the list.  the
  iterator's cursor can be shifted around at will.  nodes can be added to
  the list before or after the cursor, and the node pointed at by the cursor
  can be queried or modified.  Using multiple iterators is fine as long as
  you guarantee that they either are all just reading the list or that you
  have a valid access pattern of reads and writes such that no iterator's
  cursor is affected.  Note that this list is not thread safe.
*/


//hmmm: is this class really for real?  it's doing all sorts of stuff with nodes, rather than with the list object itself.
// consider dropping the current implementation and providing more standard list operations, on an object that is actually using itself in its definition, rather than a different class (node).
// this would be easy to do if we just break down and define the dl list as a node itself.  then we have something to work with.

//current iterator implementation here is bunk.


class doubly_linked_list
{
public:
  doubly_linked_list();
    //!< constructs a blank list.

  ~doubly_linked_list();
    //!< invalidates all contents of the list and destroys all child nodes.

  int elements() const;
    //!< returns the number of items currently in the list.
    /*!< this is a costly operation. */

  bool empty() const;
    //!< returns true if the list is empty.
    /*!< this is really quick compared to checking the number of elements. */

  //! iterators allow the list to be traversed.
  /*! NOTE: it is an error to use an iterator on one list with a different
  list; the methods will do nothing or return empty results in this
  situation. */

  class iterator {
  public:
    iterator(const doubly_linked_list *mgr, node *start) : _cursor(start), _manager(mgr) {}
      //!< opens up an iterator on a list.
      /*!< the preferred method to construct an iterator is to use the
      head/tail functions in list. */

    void operator ++();  //!< go to next item.
    void operator --();  //!< go to previous item.
    void operator ++(int) { ++(*this); }  //!< post-fix synonym for ++.
    void operator --(int) { --(*this); }  //!< post-fix synonym for --.

  
    void next() { (*this)++; }  //!< synonym for ++.
    void previous() { (*this)--; }  //!< synonyms for --.

    bool operator ==(const iterator &to_compare) const;
      //!< returns true if the two iterators are at the same position.

    bool is_head() const;
      //!< returns true if the cursor is at the head of the list.
      /*!< Note: head() and tail() only return true if the iterator is
      actually positioned _at_ the head or tail guard.  for example, if the
      cursor is pointing at the last actual element in the list (but not at
      the guard itself), then is_tail() returns false.  so, in iteration,
      your iterator will actually go past the last valid element before
      is_tail() returns true.  thus it is very important to check is_tail()
      *before* looking at the node with observe() or access(), since those
      two will shift the list position to the nearest valid node and away
      from the guard. */
    bool is_tail() const;
      //!< returns true if the cursor is at the tail of the list.

    void jump_head();  //!< set the iterator to the head.
    void jump_tail();  //!< set the iterator to the tail.

    const node *observe();  //!< peek at the current element.
      /*!< Note: observe() and access() will return the first element if the
      list is positioned at the head (or the last if at the tail), and will
      not return NULL_POINTER for these two positions as long as the list has some
      elements in it.  the cursor will also have been moved to point at the
      element that is returned.
      Another Note: it is extremely important that you do not mess with the
      links owned by the node (or at least the first two links).
      A Third Note: these two functions can return NULL_POINTER if the list is empty. */
    node *access();  //!< obtain access to the current element.

  private:
    node *_cursor;  //!< the current position.
    friend class doubly_linked_list;  //!< lists have full access to this object.
    const doubly_linked_list *_manager;  //!< our friendly manager.
  };

  iterator head() const { return iterator(this, _head); }
    //!< returns an iterator located at the head of the list.
  iterator tail() const { return iterator(this, _tail); }
    //!< returns an iterator located at the tail of the list.

  int index(const iterator &it) const { return items_from_head(it); }
    //!< returns the zero-based index of the cursor's position from the head.
    /*!< this is a synonym for items_from_head(). */

  bool set_index(iterator &to_set, int new_index);
    //!< positions the iterator "to_set" at the index specified.

  // storage and retrieval actions.
  // Note: all of these methods shift the iterator onto the next valid node
  // if it is positioned at the beginning or end of the list.

  void append(iterator &where, node *new_node);
    //!< adds a "new_node" into the list immediately after "where".
    /*!< the nodes previously following the current node (if any) will follow
    after the "new_node".  this does not change the current position.
    ownership of "new_node" is taken over by the list. */

  void insert(iterator &where, node *new_node);
    //!< places a "new_node" immediately before the current node in the list.
    /*!< the "new_node" will follow the prior precursor to the current node.
    this does not change the current position.  ownership of "new_node"
    is taken over by the list.  after the call, the iterator points at
    the new node. */

  node *remove(iterator &where);
    //!< extracts the current item from "where" and repairs the hole.
    /*!< NULL_POINTER is returned if the list was empty.  the current position is set
    to the node that used to be after the node that has been removed.  after
    the call, the iterator points at the new node. */

  void zap(iterator &where);
    //!< wipes out the item at "where", including its contents.
    /*!< the current position is reset to the item after the now defunct
    item (or the tail). */

  void zap_all();
    //!< destroys all the list elements and makes the list empty.
    /*!< any existing iterators will be invalidated by this. */

  // the following positioning functions could fail if the request is out of
  // bounds.  for example, forward cannot go beyond the end of the list.  in
  // such cases, false is returned and the list pointer is not moved.

  bool forward(iterator &where, int count);
    //!< moves the list pointer "count" items towards the tail.
    /*!< Note: forward and backward operate on elements; the head and tail
    guard are not included in the count.  Also, negative values of "count"
    are ignored. */
  bool backward(iterator &where, int count);
    //!< moves the list pointer "count" items towards the head.

  int items_from_head(const iterator &where) const;
    //!< Returns the number of elements between the current item and the head.
    /*!< zero is returned if this is at the first element or the head. */
  int items_from_tail(const iterator &where) const;
    //!< Returns the number of elements between the current item and the tail.
    /*!< zero is returned if this is at the last element or the tail. */

private:
  friend class iterator;
  node *_head;  //!< pointer to the first item.
  node *_tail;  //!< pointer to the last item.

  bool skip_or_ignore(iterator &where, int count);
    //!< zips the list to the position indicated by "count", if it can.

  // not permitted.
  doubly_linked_list(const doubly_linked_list &);
  doubly_linked_list &operator =(const doubly_linked_list &);
};

} // namespace.

#endif