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 #include <rudiments/private/linkedlistutilinlines.h>
7 
8 #define LINKEDLIST_TEMPLATE template <class valuetype>
9 
10 #define LINKEDLIST_CLASS linkedlist<valuetype>
11 
12 LINKEDLIST_TEMPLATE
13 RUDIMENTS_TEMPLATE_INLINE
14 LINKEDLIST_CLASS::linkedlist() {
15  first=NULL;
16  last=NULL;
17  length=0;
18 }
19 
20 LINKEDLIST_TEMPLATE
21 RUDIMENTS_TEMPLATE_INLINE
22 LINKEDLIST_CLASS::~linkedlist() {
23  clear();
24 }
25 
26 LINKEDLIST_TEMPLATE
27 RUDIMENTS_TEMPLATE_INLINE
28 void LINKEDLIST_CLASS::append(valuetype value) {
29  append(new linkedlistnode<valuetype>(value));
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  length++;
44 }
45 
46 LINKEDLIST_TEMPLATE
47 RUDIMENTS_TEMPLATE_INLINE
48 bool LINKEDLIST_CLASS::insert(uint64_t index, valuetype value) {
49  return insert(index,new linkedlistnode<valuetype>(value));
50 }
51 
52 LINKEDLIST_TEMPLATE
53 RUDIMENTS_TEMPLATE_INLINE
54 bool LINKEDLIST_CLASS::insert(uint64_t index, linkedlistnode<valuetype> *node) {
55 
56  // handle insert into index 0
57  if (!index) {
58  node->setNext(first);
59  first->setPrevious(node);
60  first=node;
61  length++;
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  length++;
75  return true;
76 }
77 
78 LINKEDLIST_TEMPLATE
79 RUDIMENTS_TEMPLATE_INLINE
80 bool LINKEDLIST_CLASS::setValueByIndex(uint64_t index, valuetype value) {
81  linkedlistnode<valuetype> *current=getNodeByIndex(index);
82  if (current) {
83  current->setValue(value);
84  return true;
85  }
86  return false;
87 }
88 
89 LINKEDLIST_TEMPLATE
90 RUDIMENTS_TEMPLATE_INLINE
91 bool LINKEDLIST_CLASS::removeByIndex(uint64_t index) {
92  return removeNode(getNodeByIndex(index));
93 }
94 
95 LINKEDLIST_TEMPLATE
96 RUDIMENTS_TEMPLATE_INLINE
97 bool LINKEDLIST_CLASS::removeByValue(valuetype value) {
98  for (linkedlistnode<valuetype> *current=first;
99  current; current=current->getNext()) {
100  if (!current->compare(value)) {
101  return removeNode(current);
102  }
103  }
104  return false;
105 }
106 
107 LINKEDLIST_TEMPLATE
108 RUDIMENTS_TEMPLATE_INLINE
109 bool LINKEDLIST_CLASS::removeAllByValue(valuetype value) {
110 
111  linkedlistnode<valuetype> *current=first;
113  while (current) {
114  next=current->getNext();
115  if (!current->compare(value) && !removeNode(current)) {
116  return false;
117  }
118  current=next;
119  }
120  return true;
121 }
122 
123 LINKEDLIST_TEMPLATE
124 RUDIMENTS_TEMPLATE_INLINE
125 bool LINKEDLIST_CLASS::removeNode(linkedlistnode<valuetype> *node) {
126  if (!node) {
127  return false;
128  }
129  if (node->getNext()) {
130  node->getNext()->setPrevious(node->getPrevious());
131  }
132  if (node->getPrevious()) {
133  node->getPrevious()->setNext(node->getNext());
134  }
135  if (node==first) {
136  first=node->getNext();
137  }
138  if (node==last) {
139  last=node->getPrevious();
140  }
141  delete node;
142  length--;
143  return true;
144 }
145 
146 LINKEDLIST_TEMPLATE
147 RUDIMENTS_TEMPLATE_INLINE
148 bool LINKEDLIST_CLASS::getValueByIndex(uint64_t index, valuetype *value) {
149  linkedlistnode<valuetype> *current=getNodeByIndex(index);
150  if (current) {
151  *value=current->getValue();
152  return true;
153  }
154  return false;
155 }
156 
157 LINKEDLIST_TEMPLATE
158 RUDIMENTS_TEMPLATE_INLINE
159 uint64_t LINKEDLIST_CLASS::getLength() const {
160  return length;
161 }
162 
163 LINKEDLIST_TEMPLATE
164 RUDIMENTS_TEMPLATE_INLINE
165 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getFirstNode() {
166  return (linkedlistnode<valuetype> *)first;
167 }
168 
169 LINKEDLIST_TEMPLATE
170 RUDIMENTS_TEMPLATE_INLINE
171 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getLastNode() {
172  return (linkedlistnode<valuetype> *)last;
173 }
174 
175 LINKEDLIST_TEMPLATE
176 RUDIMENTS_TEMPLATE_INLINE
177 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByIndex(uint64_t index) {
178  linkedlistnode<valuetype> *current=
179  (linkedlistnode<valuetype> *)first;
180  for (uint64_t i=0; current && i<index; i++) {
181  current=current->getNext();
182  }
183  return current;
184 }
185 
186 LINKEDLIST_TEMPLATE
187 RUDIMENTS_TEMPLATE_INLINE
188 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByValue(valuetype value) {
189  return getNodeByValue((linkedlistnode<valuetype> *)first,value);
190 }
191 
192 LINKEDLIST_TEMPLATE
193 RUDIMENTS_TEMPLATE_INLINE
194 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNodeByValue(
195  linkedlistnode<valuetype> *startnode,
196  valuetype value) {
197  for (linkedlistnode<valuetype> *current=startnode;
198  current; current=current->getNext()) {
199  if (!current->compare(value)) {
200  return current;
201  }
202  }
203  return NULL;
204 }
205 
206 LINKEDLIST_TEMPLATE
207 RUDIMENTS_TEMPLATE_INLINE
208 void LINKEDLIST_CLASS::clear() {
210  linkedlistnode<valuetype> *current=first;
211  while (current) {
212  next=current->getNext();
213  delete current;
214  current=next;
215  }
216  first=NULL;
217  last=NULL;
218  length=0;
219 }
220 
221 LINKEDLIST_TEMPLATE
222 RUDIMENTS_TEMPLATE_INLINE
223 void LINKEDLIST_CLASS::print() const {
224  uint64_t i=0;
225  for (linkedlistnode<valuetype> *current=first;
226  current; current=current->getNext()) {
227  stdoutput.printf("index %lld: ",(long long)i);
228  current->print();
229  stdoutput.printf("\n");
230  i++;
231  }
232 }
233 
234 #define LINKEDLISTNODE_TEMPLATE template <class valuetype>
235 
236 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype>
237 
238 LINKEDLISTNODE_TEMPLATE
239 RUDIMENTS_TEMPLATE_INLINE
240 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
241  this->value=value;
242  previous=NULL;
243  next=NULL;
244 }
245 
246 LINKEDLISTNODE_TEMPLATE
247 RUDIMENTS_TEMPLATE_INLINE
248 LINKEDLISTNODE_CLASS::~linkedlistnode() {
249 }
250 
251 LINKEDLISTNODE_TEMPLATE
252 RUDIMENTS_TEMPLATE_INLINE
253 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
254  this->value=value;
255 }
256 
257 LINKEDLISTNODE_TEMPLATE
258 RUDIMENTS_TEMPLATE_INLINE
259 valuetype LINKEDLISTNODE_CLASS::getValue() const {
260  return value;
261 }
262 
263 LINKEDLISTNODE_TEMPLATE
264 RUDIMENTS_TEMPLATE_INLINE
265 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
266  this->previous=previous;
267 }
268 
269 LINKEDLISTNODE_TEMPLATE
270 RUDIMENTS_TEMPLATE_INLINE
271 void LINKEDLISTNODE_CLASS::setNext(LINKEDLISTNODE_CLASS *next) {
272  this->next=next;
273 }
274 
275 LINKEDLISTNODE_TEMPLATE
276 RUDIMENTS_TEMPLATE_INLINE
277 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
278  return previous;
279 }
280 
281 LINKEDLISTNODE_TEMPLATE
282 RUDIMENTS_TEMPLATE_INLINE
283 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
284  return next;
285 }
286 
287 LINKEDLISTNODE_TEMPLATE
288 RUDIMENTS_TEMPLATE_INLINE
289 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value) const {
290  return _linkedlistutil_compare(this->value,value);
291 }
292 
293 LINKEDLISTNODE_TEMPLATE
294 RUDIMENTS_TEMPLATE_INLINE
295 void LINKEDLISTNODE_CLASS::print() const {
296  _linkedlistutil_print(value);
297 }