Beamlib  3.0.1
This is the Beam C++ class library.
BList_func.h
Go to the documentation of this file.
1 /*******************************************************************************
2  * BList_func.h BEAM List implementation based upong stdc++ lists
3  * T.Barnaby, BEAM Ltd, 4/8/00
4  * Copyright (c) 2022 All Right Reserved, Beam Ltd, https://www.beam.ltd.uk
5  * For license see LICENSE.txt at the root of the beamlib source tree.
6  *******************************************************************************
7  */
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include <string.h>
21 #include <memory.h>
22 
23 template <class T> BList<T>::BList() {
24  onodes = nodeCreate();
25  onodes->next = onodes;
26  onodes->prev = onodes;
27  olength = 0;
28 }
29 
30 template <class T> BList<T>::BList(const BList<T>& l) {
31  onodes = nodeCreate();
32  onodes->next = onodes;
33  onodes->prev = onodes;
34  olength = 0;
35  append((BList<T>&)l);
36 }
37 
38 template <class T> BList<T>::~BList() {
39  clear();
40  delete [] (char*)onodes;
41 }
42 
43 template <class T> void BList<T>::start(BIter& i) const {
44  i = onodes->next;
45 }
46 
47 template <class T> BIter BList<T>::begin() const {
48  return onodes->next;
49 }
50 
51 template <class T> BIter BList<T>::end() const {
52  return onodes->prev;
53 }
54 
55 template <class T> BIter BList<T>::end(BIter& i) const {
56  i = onodes->prev;
57  return onodes->prev;
58 }
59 
60 template <class T> void BList<T>::next(BIter& i) const {
61  BNode* n = i;
62 
63  if(n != onodes)
64  n = n->next;
65  i = n;
66 }
67 
68 template <class T> void BList<T>::prev(BIter& i) {
69  BNode* n = i;
70 
71  if(n != onodes)
72  n = n->prev;
73  i = n;
74 }
75 
76 template <class T> BIter BList<T>::goTo(int pos) const {
77  BIter i;
78  int c;
79 
80  for(i = begin(), c = 0; (c < pos) && !isEnd(i); next(i), c++);
81  return i;
82 }
83 
84 template <class T> int BList<T>::position(BIter i) {
85  BIter ii;
86  int c;
87 
88  for(ii = begin(), c = 0; !isEnd(ii); next(ii), c++){
89  if(ii == i)
90  return c;
91  }
92  return -1;
93 }
94 
95 template <class T> unsigned int BList<T>::number() const {
96  return olength;
97 }
98 
99 template <class T> unsigned int BList<T>::size() const {
100  return number();
101 }
102 
103 template <class T> int BList<T>::isStart(BIter& i) const {
104  Node* n = (Node*)(BNode*)i;
105 
106  return (n == onodes->next);
107 }
108 
109 template <class T> int BList<T>::isEnd(BIter& i) const {
110  Node* n = (Node*)(BNode*)i;
111 
112  return (n == onodes);
113 }
114 
115 template <class T> void BList<T>::clear(){
116  BIter i;
117 
118  for(start(i); !isEnd(i); )
119  del(i);
120 }
121 
122 template <class T> T& BList<T>::front(){
123  return get(begin());
124 }
125 
126 template <class T> T& BList<T>::rear(){
127  return get(end());
128 }
129 
130 template <class T> T& BList<T>::get(BIter i){
131  return nodeGet(i)->item;
132 }
133 
134 template <class T> const T& BList<T>::get(BIter i) const {
135  return nodeGet(i)->item;
136 }
137 
138 template <class T> void BList<T>::append(const T& item){
139  BIter i = end();
140 
141  insertAfter(i, item);
142 }
143 
144 template <class T> void BList<T>::insert(BIter& i, const T& item){
145  Node* c = (Node*)(BNode*)i;
146  Node* n = nodeCreate(item);
147 
148  n->next = c;
149  n->prev = c->prev;
150  c->prev->next = n;
151  c->prev = n;
152  olength++;
153  i = n;
154 }
155 
156 template <class T> void BList<T>::insertAfter(BIter& i, const T& item){
157  next(i);
158  insert(i, item);
159 }
160 
161 template <class T> void BList<T>::del(BIter& i){
162  Node* n = (Node*)(BNode*)i;
163 
164  if(olength){
165  i = n->next;
166  n->prev->next = n->next;
167  n->next->prev = n->prev;
168  delete n;
169  olength--;
170  }
171 }
172 
173 template <class T> void BList<T>::deleteLast(){
174  BIter i = end();
175 
176  del(i);
177 }
178 
179 template <class T> void BList<T>::deleteFirst(){
180  BIter i = begin();
181  del(i);
182 }
183 
184 template <class T> void BList<T>::push(const T& item){
185  append(item);
186 }
187 
188 template <class T> T BList<T>::pop(){
189  T t = rear();
190 
191  deleteLast();
192  return t;
193 }
194 
195 template <class T> void BList<T>::queueAdd(const T& i){
196  append(i);
197 }
198 
199 template <class T> T BList<T>::queueGet(){
200  T t = front();
201 
202  deleteFirst();
203  return t;
204 }
205 
206 template <class T> void BList<T>::append(const BList<T>& l){
207  BIter i;
208 
209  for(l.start(i); !l.isEnd(i); l.next(i)){
210  append(l.get(i));
211  }
212 }
213 
214 template <class T> int BList<T>::has(const T& v) const {
215  BIter i;
216 
217  for(start(i); !isEnd(i); next(i)){
218  if(get(i) == v)
219  return 1;
220  }
221  return 0;
222 }
223 
224 template <class T> void BList<T>::swap(BIter i1, BIter i2){
225  BNode* n1 = (BNode*)i1;
226  BNode* n2 = (BNode*)i2;
227  BNode* n1p = n1->prev;
228  BNode* n1n = n1->next;
229  BNode* n2p = n2->prev;
230  BNode* n2n = n2->next;
231 
232  if(n1->next == n2){
233  n1p->next = n2;
234  n2n->prev = n1;
235 
236  n1->prev = n2;
237  n2->prev = n1p;
238  n1->next = n2n;
239  n2->next = n1;
240  }
241  else if(n1->prev == n2){
242  n2p->next = n1;
243  n1n->prev = n2;
244 
245  n1->prev = n2p;
246  n2->prev = n1;
247  n1->next = n2;
248  n2->next = n1n;
249  }
250  else {
251  n1p->next = n2;
252  n1n->prev = n2;
253  n2p->next = n1;
254  n2n->prev = n1;
255 
256  n1->prev = n2p;
257  n2->prev = n1p;
258  n1->next = n2n;
259  n2->next = n1n;
260  }
261 }
262 
263 template <class T> void BList<T>::sort(){
264  BIter i;
265  BIter s;
266  int n = number();
267  int c;
268 
269  while(n){
270  for(c = n - 1, i = begin(); c > 0; c--, next(i)){
271  s = i;
272  next(s);
273  if(get(i) > get(s)){
274  swap(i, s);
275  i = s;
276  }
277  }
278  n--;
279  }
280 }
281 
282 template <class T> void BList<T>::sort(SortFunc func){
283  BIter i;
284  BIter s;
285  int n = number();
286  int c;
287 
288  while(n){
289  for(c = n - 1, i = begin(); c > 0; c--, next(i)){
290  s = i;
291  next(s);
292  if(func(get(i), get(s)) > 0){
293  swap(i, s);
294  i = s;
295  }
296  }
297  n--;
298  }
299 }
300 
301 template <class T> T& BList<T>::operator[](BIter i){
302  return get(i);
303 }
304 
305 template <class T> const T& BList<T>::operator[](const BIter& i) const {
306  return get(i);
307 }
308 
309 template <class T> T& BList<T>::operator[](int i){
310  BIter ii;
311 
312  if((ii = goTo(i))){
313  return get(ii);
314  }
315  else {
316  fprintf(stderr, "BList over range\n");
317  exit(1);
318  }
319 }
320 
321 template <class T> const T& BList<T>::operator[](int i) const {
322  BIter ii;
323 
324  if((ii = goTo(i))){
325  return get(ii);
326  }
327  else {
328  fprintf(stderr, "BList over range\n");
329  exit(1);
330  }
331 }
332 
333 template <class T> BList<T>& BList<T>::operator=(const BList<T>& l){
334  BIter i;
335 
336  if(this != &l){
337  clear();
338  for(l.start(i); !l.isEnd(i); l.next(i)){
339  append(l[i]);
340  }
341  }
342 
343  return *this;
344 }
345 
346 template <class T> BList<T> BList<T>::operator+(const BList<T>& l) const {
347  BList<T> rl = *this;
348  BIter i;
349 
350  for(l.start(i); !l.isEnd(i); l.next(i)){
351  rl.append(l[i]);
352  }
353  return rl;
354 }
355 
356 template <class T> typename BList<T>::Node* BList<T>::nodeGet(BIter i){
357  return (Node*)(BNode*)i;
358 }
359 
360 template <class T> const typename BList<T>::Node* BList<T>::nodeGet(BIter i) const{
361  return (Node*)(BNode*)i;
362 }
363 
364 template <class T> typename BList<T>::Node* BList<T>::nodeCreate(const T& item){
365  return new Node(item);
366 }
367 template <class T> typename BList<T>::Node* BList<T>::nodeCreate(){
368  Node* n;
369 
370  n = (Node*)new char [ sizeof(Node) ];
371  // WARNING: This is not ideal. However only used for the list start/end Node where the object is not valid anyway.
372  memset((void*)n, 0, sizeof(Node));
373  return n;
374 }
BInt16 number
The error number.
Definition: BoapMc1.h:0
Iterator for BLists.
Definition: BList.h:20
A BList internal Node.
Definition: BList.h:34
Template based list class.
Definition: BList.h:31
void next(BIter &i) const
Iterator for next item in list.
Definition: BList_func.h:60
BIter goTo(int pos) const
Iterator for pos item in list.
Definition: BList_func.h:76
virtual void del(BIter &i)
Delete specified item.
Definition: BList_func.h:161
T & front()
Get first item in list.
Definition: BList_func.h:122
int has(const T &i) const
Checks if the item is in the list.
Definition: BList_func.h:214
BList< T > operator+(const BList< T > &l) const
Definition: BList_func.h:346
unsigned int size() const
Number of items in list.
Definition: BList_func.h:99
void deleteFirst()
Delete fisrt item.
Definition: BList_func.h:179
BList()
Definition: BList_func.h:23
void push(const T &i)
Push item onto list.
Definition: BList_func.h:184
T & rear()
Get last item in list.
Definition: BList_func.h:126
void sort()
Sort list based on get(i) values.
Definition: BList_func.h:263
int isEnd(BIter &i) const
True if iterator refers to last item.
Definition: BList_func.h:109
int position(BIter i)
Postition in list item with iterator i.
Definition: BList_func.h:84
void append(const T &item)
Append item to list.
Definition: BList_func.h:138
virtual void insert(BIter &i, const T &item)
Insert item before item.
Definition: BList_func.h:144
virtual Node * nodeGet(BIter i)
Definition: BList_func.h:356
int isStart(BIter &i) const
True if iterator refers to first item.
Definition: BList_func.h:103
T & get(BIter i)
Get item specified by iterator in list.
Definition: BList_func.h:130
BList< T > & operator=(const BList< T > &l)
Definition: BList_func.h:333
void prev(BIter &i)
Iterator for previous item in list.
Definition: BList_func.h:68
virtual void clear()
Clear the list.
Definition: BList_func.h:115
BIter begin() const
Iterator for start of list.
Definition: BList_func.h:47
T & operator[](int i)
Definition: BList_func.h:309
T pop()
Pop item from list deleteing item.
Definition: BList_func.h:188
void start(BIter &i) const
Iterator to start of list.
Definition: BList_func.h:43
void swap(BIter i1, BIter i2)
Swap two items in list.
Definition: BList_func.h:224
BIter end() const
Iterator for end of list.
Definition: BList_func.h:51
virtual ~BList()
Definition: BList_func.h:38
void insertAfter(BIter &i, const T &item)
Insert item after item.
Definition: BList_func.h:156
unsigned int number() const
Number of items in list.
Definition: BList_func.h:95
void deleteLast()
Delete last item.
Definition: BList_func.h:173
void queueAdd(const T &i)
Add item to end of list.
Definition: BList_func.h:195
T queueGet()
Get item from front of list deleteing item.
Definition: BList_func.h:199
A BList entry's node.
Definition: BList.h:12
BNode * next
Definition: BList.h:15
BNode * prev
Definition: BList.h:16