]>
Dogcows Code - chaz/openbox/blob - src/LinkedList.cc
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();
This page took 0.05596 seconds and 4 git commands to generate.