1 // LinkedList.cc for Openbox
2 // Copyright (c) 1997 - 2000 Brad Hughes (bhughes@tcac.net)
4 // Permission is hereby granted, free of charge, to any person obtaining a
5 // copy of this software and associated documentation files (the "Software"),
6 // to deal in the Software without restriction, including without limitation
7 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 // and/or sell copies of the Software, and to permit persons to whom the
9 // Software is furnished to do so, subject to the following conditions:
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 // DEALINGS IN THE SOFTWARE.
22 // stupid macros needed to access some functions in version 2 of the GNU C
28 #include "LinkedList.h"
31 # include "../config.h"
32 #endif // HAVE_CONFIG_H
36 #endif // HAVE_STDIO_H
39 __llist_iterator::__llist_iterator(__llist *l) {
40 // initialize the iterator...
44 if (! list->iterators)
45 list->iterators = new __llist;
47 list->iterators->insert(this);
54 __llist_iterator::~__llist_iterator(void) {
55 if (list && list->iterators)
56 list->iterators->remove(this);
60 void *__llist_iterator::current(void) {
61 // return the current node data... if any
62 return ((node) ? node->getData() : 0);
66 void __llist_iterator::reset(void) {
67 // update the iterator's current node to the first node in the linked list
73 const int __llist_iterator::set(const int index) {
74 // set the current node to index
76 if (index < list->elements && index >= 0 && list->_first) {
79 for (register int i = 0; i < index; i++)
80 node = node->getNext();
86 node = (__llist_node *) 0;
91 void __llist_iterator::operator++(void) {
92 // iterate to the next node in the list...
93 node = ((node) ? node->getNext() : 0);
97 void __llist_iterator::operator++(int) {
98 // iterate to the next node in the list...
99 node = ((node) ? node->getNext() : 0);
103 __llist::__llist(void *d) {
104 // initialize the linked list...
105 _first = (__llist_node *) 0;
106 _last = (__llist_node *) 0;
107 iterators = (__llist *) 0;
114 __llist::~__llist(void) {
115 // remove all the items in the list...
116 for (register int i = 0; i < elements; i++)
120 __llist_node *n = iterators->_first;
123 __llist_iterator *p = (__llist_iterator *) n->getData();
124 p->list = (__llist *) 0;
125 p->node = (__llist_node *) 0;
135 const int __llist::insert(void *d, int index) {
136 // insert item into linked list at specified index...
138 __llist_node *nnode = new __llist_node;
139 if (! nnode) return -1;
141 if ((! _first) || (! _last)) {
142 // list is empty... insert the item as the first item, regardless of the
146 _first->setNext((__llist_node *) 0);
150 // if index is 0... prepend the data on the list
153 nnode->setNext(_first);
156 } else if ((index == -1) || (index == elements)) {
157 // if index is -1... append the data on the list
160 nnode->setNext((__llist_node *) 0);
161 _last->setNext(nnode);
164 } else if (index < elements) {
165 // otherwise... insert the item at the position specified by index
166 __llist_node *inode = _first;
168 for (register int i = 1; i < index; i++) {
170 inode = inode->getNext();
179 if ((! inode) || inode == _last) {
180 nnode->setNext((__llist_node *) 0);
181 _last->setNext(nnode);
185 nnode->setNext(inode->getNext());
186 inode->setNext(nnode);
195 const int __llist::remove(void *d) {
196 // remove list item whose data pointer address matches the pointer address
199 if ((! _first) || (! _last))
202 if (_first->getData() == d) {
203 // remove the first item in the list...
204 __llist_node *node = _first;
205 _first = _first->getNext();
207 if (iterators && iterators->_first) {
208 __llist_node *n = iterators->_first;
210 ((__llist_iterator *) n->getData())->reset();
219 // iterate through the list and remove the first occurance of the item
221 // NOTE: we don't validate _first in this assignment, because it is checked
222 // for validity above...
223 __llist_node *rnode = _first->getNext(), *prev = _first;
225 for (register int i = 1; i < elements; i++) {
227 if (rnode->getData() == d) {
228 // we found the item... update the previous node and delete the
229 // now useless rnode...
230 prev->setNext(rnode->getNext());
235 if (iterators && iterators->_first) {
236 __llist_node *n = iterators->_first;
238 ((__llist_iterator *) n->getData())->reset();
248 rnode = rnode->getNext();
258 void *__llist::remove(const int index) {
259 if (index >= elements || index < 0 || (! _first) || (! _last))
262 // remove list item at specified index within the list
264 // remove the first item in the list...
265 __llist_node *node = _first;
266 void *data_return = _first->getData();
268 _first = _first->getNext();
270 if (iterators && iterators->_first) {
271 __llist_node *n = iterators->_first;
273 ((__llist_iterator *) n->getData())->reset();
283 __llist_node *rnode = _first->getNext(), *prev = _first;
284 void *data_return = (void *) 0;
286 for (register int i = 1; i < index; i++) {
289 rnode = rnode->getNext();
295 if (! rnode) return (void *) 0;
297 prev->setNext(rnode->getNext());
298 data_return = rnode->getData();
303 if (iterators && iterators->_first) {
304 __llist_node *n = iterators->_first;
306 ((__llist_iterator *) n->getData())->reset();
312 data_return = rnode->getData();
321 void *__llist::find(const int index) {
322 if (index >= elements || index < 0 || (! _first) || (! _last))
325 if (index == 0) // return the first item
327 if (index == (elements - 1)) // return the last item
330 __llist_node *fnode = _first->getNext();
332 for (register int i = 1; i < index; i++) {
334 fnode = fnode->getNext();
339 return fnode->getData();
343 void *__llist::first(void) {
345 return _first->getData();
351 void *__llist::last(void) {
353 return _last->getData();