list.h

   1 #ifndef LIST_CLASS
   2 #define LIST_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : list                                                              *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1998-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18
  19
  20 namespace nodes {
  21
  22 class node;  // forward.
  23
  24 //! Implements a guarded, doubly linked list structure.
  25 /*!
  26   The list is viewed one element at a time, through the monocular of an
  27   iterator, which keeps track of the current position in the list.  the
  28   iterator's cursor can be shifted around at will.  nodes can be added to
  29   the list before or after the cursor, and the node pointed at by the cursor
  30   can be queried or modified.  Using multiple iterators is fine as long as
  31   you guarantee that they either are all just reading the list or that you
  32   have a valid access pattern of reads and writes such that no iterator's
  33   cursor is affected.  Note that this list is not thread safe.
  34 */
  35
  36 class list
  37 {
  38 public:
  39   list();
  40     //!< constructs a blank list.
  41
  42   ~list();
  43     //!< invalidates all contents of the list and destroys all child nodes.
  44
  45   int elements() const;
  46     //!< returns the number of items currently in the list.
  47     /*!< this is a costly operation. */
  48
  49   bool empty() const;
  50     //!< returns true if the list is empty.
  51     /*!< this is really quick compared to checking the number of elements. */
  52
  53   //! iterators allow the list to be traversed.
  54   /*! NOTE: it is an error to use an iterator on one list with a different
  55   list; the methods will do nothing or return empty results in this
  56   situation. */
  57
  58   class iterator {
  59   public:
  60     iterator(const list *mgr, node *start) : _cursor(start), _manager(mgr) {}
  61       //!< opens up an iterator on a list.
  62       /*!< the preferred method to construct an iterator is to use the
  63       head/tail functions in list. */
  64
  65     void operator ++();  //!< go to next item.
  66     void operator --();  //!< go to previous item.
  67     void operator ++(int) { ++(*this); }  //!< post-fix synonym for ++.
  68     void operator --(int) { --(*this); }  //!< post-fix synonym for --.
  69
  70
  71     void next() { (*this)++; }  //!< synonym for ++.
  72     void previous() { (*this)--; }  //!< synonyms for --.
  73
  74     bool operator ==(const iterator &to_compare) const;
  75       //!< returns true if the two iterators are at the same position.
  76
  77     bool is_head() const;
  78       //!< returns true if the cursor is at the head of the list.
  79       /*!< Note: head() and tail() only return true if the iterator is
  80       actually positioned _at_ the head or tail guard.  for example, if the
  81       cursor is pointing at the last actual element in the list (but not at
  82       the guard itself), then is_tail() returns false.  so, in iteration,
  83       your iterator will actually go past the last valid element before
  84       is_tail() returns true.  thus it is very important to check is_tail()
  85       *before* looking at the node with observe() or access(), since those
  86       two will shift the list position to the nearest valid node and away
  87       from the guard. */
  88     bool is_tail() const;
  89       //!< returns true if the cursor is at the tail of the list.
  90
  91     void jump_head();  //!< set the iterator to the head.
  92     void jump_tail();  //!< set the iterator to the tail.
  93
  94     const node *observe();  //!< peek at the current element.
  95       /*!< Note: observe() and access() will return the first element if the
  96       list is positioned at the head (or the last if at the tail), and will
  97       not return NIL for these two positions as long as the list has some
  98       elements in it.  the cursor will also have been moved to point at the
  99       element that is returned.
 100       Another Note: it is extremely important that you do not mess with the
 101       links owned by the node (or at least the first two links).
 102       A Third Note: these two functions can return NIL if the list is empty. */
 103     node *access();  //!< obtain access to the current element.
 104
 105   private:
 106     node *_cursor;  //!< the current position.
 107     friend class list;  //!< lists have full access to this object.
 108     const list *_manager;  //!< our friendly manager.
 109   };
 110
 111   iterator head() const { return iterator(this, _head); }
 112     //!< returns an iterator located at the head of the list.
 113   iterator tail() const { return iterator(this, _tail); }
 114     //!< returns an iterator located at the tail of the list.
 115
 116   int index(const iterator &it) const { return items_from_head(it); }
 117     //!< returns the zero-based index of the cursor's position from the head.
 118     /*!< this is a synonym for items_from_head(). */
 119
 120   bool set_index(iterator &to_set, int new_index);
 121     //!< positions the iterator "to_set" at the index specified.
 122
 123   // storage and retrieval actions.
 124   // Note: all of these methods shift the iterator onto the next valid node
 125   // if it is positioned at the beginning or end of the list.
 126
 127   void append(iterator &where, node *new_node);
 128     //!< adds a "new_node" into the list immediately after "where".
 129     /*!< the nodes previously following the current node (if any) will follow
 130     after the "new_node".  this does not change the current position.
 131     ownership of "new_node" is taken over by the list. */
 132
 133   void insert(iterator &where, node *new_node);
 134     //!< places a "new_node" immediately before the current node in the list.
 135     /*!< the "new_node" will follow the prior precursor to the current node.
 136     this does not change the current position.  ownership of "new_node"
 137     is taken over by the list.  after the call, the iterator points at
 138     the new node. */
 139
 140   node *remove(iterator &where);
 141     //!< extracts the current item from "where" and repairs the hole.
 142     /*!< NIL is returned if the list was empty.  the current position is set
 143     to the node that used to be after the node that has been removed.  after
 144     the call, the iterator points at the new node. */
 145
 146   void zap(iterator &where);
 147     //!< wipes out the item at "where", including its contents.
 148     /*!< the current position is reset to the item after the now defunct
 149     item (or the tail). */
 150
 151   void zap_all();
 152     //!< destroys all the list elements and makes the list empty.
 153     /*!< any existing iterators will be invalidated by this. */
 154
 155   // the following positioning functions could fail if the request is out of
 156   // bounds.  for example, forward cannot go beyond the end of the list.  in
 157   // such cases, false is returned and the list pointer is not moved.
 158
 159   bool forward(iterator &where, int count);
 160     //!< moves the list pointer "count" items towards the tail.
 161     /*!< Note: forward and backward operate on elements; the head and tail
 162     guard are not included in the count.  Also, negative values of "count"
 163     are ignored. */
 164   bool backward(iterator &where, int count);
 165     //!< moves the list pointer "count" items towards the head.
 166
 167   int items_from_head(const iterator &where) const;
 168     //!< Returns the number of elements between the current item and the head.
 169     /*!< zero is returned if this is at the first element or the head. */
 170   int items_from_tail(const iterator &where) const;
 171     //!< Returns the number of elements between the current item and the tail.
 172     /*!< zero is returned if this is at the last element or the tail. */
 173
 174 private:
 175   friend class iterator;
 176   node *_head;  //!< pointer to the first item.
 177   node *_tail;  //!< pointer to the last item.
 178
 179   bool skip_or_ignore(iterator &where, int count);
 180     //!< zips the list to the position indicated by "count", if it can.
 181
 182   // not permitted.
 183   list(const list &);
 184   list &operator =(const list &);
 185 };
 186
 187 } // namespace.
 188
 189 #endif
 190