Rudiments
linkedlistinlines.h
1 // Copyright (c) 2003 David Muse
2 // See the COPYING file for more information
3 
4 #include <rudiments/stdio.h>
5 #include <rudiments/private/rudimentsinlines.h>
6 
7 #define LINKEDLIST_TEMPLATE template <class valuetype>
8 
9 #define LINKEDLIST_CLASS linkedlist<valuetype>
10 
11 LINKEDLIST_TEMPLATE
12 RUDIMENTS_TEMPLATE_INLINE
13 LINKEDLIST_CLASS::linkedlist() {
14  first=NULL;
15  last=NULL;
16 }
17 
18 LINKEDLIST_TEMPLATE
19 RUDIMENTS_TEMPLATE_INLINE
20 LINKEDLIST_CLASS::~linkedlist() {
21  clear();
22 }
23 
24 LINKEDLIST_TEMPLATE
25 RUDIMENTS_TEMPLATE_INLINE
26 void LINKEDLIST_CLASS::append(valuetype value) {
28  node->setValue(value);
29  append(node);
30 }
31 
32 LINKEDLIST_TEMPLATE
33 RUDIMENTS_TEMPLATE_INLINE
34 void LINKEDLIST_CLASS::append(linkedlistnode<valuetype> *node) {
35  if (last) {
36  last->setNext(node);
37  node->setPrevious(last);
38  last=node;
39  } else {
40  first=node;
41  last=first;
42  }
43 }
44 
45 LINKEDLIST_TEMPLATE
46 RUDIMENTS_TEMPLATE_INLINE
47 bool LINKEDLIST_CLASS::insert(uint64_t index, valuetype value) {
49  node->setValue(value);
50  return insert(index,node);
51 }
52 
53 LINKEDLIST_TEMPLATE
54 RUDIMENTS_TEMPLATE_INLINE
55 bool LINKEDLIST_CLASS::insert(uint64_t index, linkedlistnode<valuetype> *node) {
56 
57  // handle insert into index 0
58  if (!index) {
59  node->setNext(first);
60  first->setPrevious(node);
61  first=(linkedlistnode<valuetype> *)node;
62  return true;
63  }
64 
65  // handle general insert
66  linkedlistnode<valuetype> *current=getNodeByIndex(index-1);
67  if (!current) {
68  return false;
69  }
70  node->setPrevious(current);
71  node->setNext(current->getNext());
72  current->getNext()->setPrevious(node);
73  current->setNext(node);
74  return true;
75 }
76 
77 LINKEDLIST_TEMPLATE
78 RUDIMENTS_TEMPLATE_INLINE
79 bool LINKEDLIST_CLASS::setValueByIndex(uint64_t index, valuetype value) {
80  linkedlistnode<valuetype> *current=getNodeByIndex(index);
81  if (current) {
82  current->setValue(value);
83  return true;
84  }
85  return false;
86 }
87 
88 LINKEDLIST_TEMPLATE
89 RUDIMENTS_TEMPLATE_INLINE
90 bool LINKEDLIST_CLASS::removeByIndex(uint64_t index) {
91  return removeNode(getNodeByIndex(index));
92 }
93 
94 LINKEDLIST_TEMPLATE
95 RUDIMENTS_TEMPLATE_INLINE
96 bool LINKEDLIST_CLASS::removeByValue(valuetype value) {
97  for (linkedlistnode<valuetype> *current=first; current;
98  current=(linkedlistnode<valuetype> *)current->getNext()) {
99  if (!current->compare(value)) {
100  return removeNode(current);
101  }
102  }
103  return false;
104 }
105 
106 LINKEDLIST_TEMPLATE
107 RUDIMENTS_TEMPLATE_INLINE
108 bool LINKEDLIST_CLASS::removeAllByValue(valuetype value) {
109 
110  linkedlistnode<valuetype> *current=first;
112  while (current) {
113  if (!current->compare(value)) {
114  next=(linkedlistnode<valuetype> *)current->getNext();
115  if (!removeNode(current)) {
116  return false;
117  }
118  current=next;
119  } else {
120  current=(linkedlistnode<valuetype> *)current->getNext();
121  }
122  }
123  return true;
124 }
125 
126 LINKEDLIST_TEMPLATE
127 RUDIMENTS_TEMPLATE_INLINE
128 bool LINKEDLIST_CLASS::removeNode(linkedlistnode<valuetype> *node) {
129  if (!node) {
130  return false;
131  }
132  if (node->getNext()) {
133  node->getNext()->setPrevious(node->getPrevious());
134  }
135  if (node->getPrevious()) {
136  node->getPrevious()->setNext(node->getNext());
137  }
138  if (node==first) {
139  first=(linkedlistnode<valuetype> *)node->getNext();
140  }
141  if (node==last) {
142  last=(linkedlistnode<valuetype> *)node->getPrevious();
143  }
144  delete node;
145  return true;
146 }
147 
148 LINKEDLIST_TEMPLATE
149 RUDIMENTS_TEMPLATE_INLINE
150 bool LINKEDLIST_CLASS::getValueByIndex(uint64_t index, valuetype *value) {
151  linkedlistnode<valuetype> *current=getNodeByIndex(index);
152  if (current) {
153  *value=current->getValue();
154  return true;
155  }
156  return false;
157 }
158 
159 LINKEDLIST_TEMPLATE
160 RUDIMENTS_TEMPLATE_INLINE
161 uint64_t LINKEDLIST_CLASS::getLength() const {
162  uint64_t length=0;
163  for (linkedlistnode<valuetype> *current=first; current;
164  current=(linkedlistnode<valuetype> *)current->getNext()) {
165  length++;
166  }
167  return length;
168 }
169 
170 LINKEDLIST_TEMPLATE
171 RUDIMENTS_TEMPLATE_INLINE
172 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getFirstNode() {
173  return (linkedlistnode<valuetype> *)first;
174 }
175 
176 LINKEDLIST_TEMPLATE
177 RUDIMENTS_TEMPLATE_INLINE
178 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getLastNode() {
179  return (linkedlistnode<valuetype> *)last;
180 }
181 
182 LINKEDLIST_TEMPLATE
183 RUDIMENTS_TEMPLATE_INLINE
184 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByIndex(uint64_t index) {
185  linkedlistnode<valuetype> *current=
186  (linkedlistnode<valuetype> *)first;
187  for (uint64_t i=0; current && i<index; i++) {
188  current=(linkedlistnode<valuetype> *)current->getNext();
189  }
190  return current;
191 }
192 
193 LINKEDLIST_TEMPLATE
194 RUDIMENTS_TEMPLATE_INLINE
195 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByValue(valuetype value) {
196  return getNodeByValue((linkedlistnode<valuetype> *)first,value);
197 }
198 
199 LINKEDLIST_TEMPLATE
200 RUDIMENTS_TEMPLATE_INLINE
201 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByValue(
202  linkedlistnode<valuetype> *startnode,
203  valuetype value) {
204  for (linkedlistnode<valuetype> *current=startnode; current;
205  current=(linkedlistnode<valuetype> *)current->getNext()) {
206  if (!current->compare(value)) {
207  return current;
208  }
209  }
210  return NULL;
211 }
212 
213 LINKEDLIST_TEMPLATE
214 RUDIMENTS_TEMPLATE_INLINE
215 void LINKEDLIST_CLASS::clear() {
217  linkedlistnode<valuetype> *current=first;
218  while (current) {
219  next=(linkedlistnode<valuetype> *)current->getNext();
220  delete current;
221  current=next;
222  }
223  first=NULL;
224  last=NULL;
225 }
226 
227 LINKEDLIST_TEMPLATE
228 RUDIMENTS_TEMPLATE_INLINE
229 void LINKEDLIST_CLASS::print() const {
230  uint64_t i=0;
231  for (linkedlistnode<valuetype> *current=first; current;
232  current=(linkedlistnode<valuetype> *)current->getNext()) {
233  stdoutput.printf("index %lld: ",(long long)i);
234  current->print();
235  stdoutput.printf("\n");
236  i++;
237  }
238 }