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