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