1 /*! \file kbool/include/kbool/_dl_itr.cpp
2 \brief Double Linked list with Iterators on list
3 \author Klaas Holwerda
4
5 Copyright: 2001-2004 (C) Klaas Holwerda
6
7 Licence: see kboollicense.txt
8
9 RCS-ID: $Id: _dl_itr.cpp,v 1.1 2005/05/24 19:13:35 titato Exp $
10 */
11
12 #ifdef __GNUG__
13 #pragma implementation
14 #endif
15
16 #ifdef __UNIX__
17 #include "kbool/include/_dl_itr.h"
18 #endif
19
20 //=======================================================================
21 // implementation class DL_Node
22 //=======================================================================
23 /*! \class DL_Node
24 * This class is used in the class DL_List to contain the items of the list. This can be a
25 * pointer to an object or the object itself. The class contains a next and a previous pointer
26 * to connect the nodes in the list. \n
27 * class Dtype | Object stored at the node
28 */
29
30
31
32 /*!
33 Construct a node for a list object
34 \param it Item the node will contain
35 */
36 template <class Dtype>
DL_Node(Dtype it)37 DL_Node<Dtype>::DL_Node(Dtype it) // + init nodeitem
38 :_item(it)
39 {}
40
41 /*!
42 Template constructor no contents
43 Construct a node for a list object
44 */
45 template <class Dtype>
DL_Node()46 DL_Node<Dtype>::DL_Node()
47 :_item(0)
48 {}
49
50 /*!
51 Destruct a node object
52 */
53 template <class Dtype>
~DL_Node()54 DL_Node<Dtype>::~DL_Node()
55 {
56 }
57
58
59 //=======================================================================
60 // implementation class DL_List
61 //=======================================================================
62 /*! \class DL_List
63 * class is the base class for implementing a double linked list. The Root node marks the begining and end of the list. The
64 * lists consists of nodes double linked with a next and previous pointer DL_Node The nodes are cyclic connected to the root
65 * node. The list is meant to be used with an iterator class, to traverse the nodes. More then 1 iterator can be attached to the
66 * list. The list keeps track of the number of iterators that are attached to it. Depending on this certain operations are allowed
67 * are not. For instance a node can only be deleted if there is only one iterator attached to the list.
68 * class | Dtype | Object contaning List Nodes
69 */
70
71 /*!
72 Construct a node object
73 \par Example:
74 How to construct a list of type integer:
75 \code
76 DL_List<int> * a_list = new DL_List<int>();
77 \endcode
78 */
79 template <class Dtype>
DL_List()80 DL_List<Dtype>::DL_List()
81 :_nbitems(0), _iterlevel(0)
82 {
83 _root = new DL_Node<Dtype>();
84 _root->_next=_root;
85 _root->_prev=_root;
86 }
87
88
89 /*!
90 //Destruct a list object
91 \par Example:
92 How to construct a list of type integer:
93 \code
94 DL_List<int> * a_list = new DL_List<int>(); # declaration and allocation
95 delete a_list; #delete it (must have no iterators attached to it)
96 \endcode
97 */
98 template <class Dtype>
~DL_List()99 DL_List<Dtype>::~DL_List()
100 {
101 if (_iterlevel != 0)
102 throw Bool_Engine_Error("DL_List::~DL_List()\n_iterlevel > 0 ","list error", 0, 1);
103
104 remove_all(false);
105 delete _root;
106 _root=0;_nbitems=0; //reset memory used (no lost pointers)
107 }
108
109 /*!
110 Error report for list error inside DL_List class
111 the error function is used internally in the list class to report errors,
112 the function will generate a message based on the error code.
113 Then an exeption will be generated using the global booleng class instance. \n
114 tcarg: class | Dtype | item object in list
115 \par Example
116 to call error from inside an DL_List class
117 \code
118 Error("remove_all",ITER_GT_O);
119 \endcode
120 \param function string that generated this error
121 \param error code to generate a message for
122 */
123 template <class Dtype>
Error(const char * function,Lerror a_error)124 void DL_List<Dtype>::Error(const char* function,Lerror a_error)
125 {
126 char buf[100];
127 strcpy(buf,"DL_List<Dtype>::");
128 strcat(buf,function);
129 switch (a_error)
130 {
131 case NO_MES: strcat(buf,""); break;
132 case EMPTY: strcat(buf,"list is empty"); break;
133 case ITER_GT_0: strcat(buf,"more then zero iter"); break;
134 case NO_LIST: strcat(buf,"no list attached"); break;
135 case SAME_LIST: strcat(buf,"same list not allowed"); break;
136 case AC_ITER_LIST_OTHER: strcat(buf,"iter not allowed on other list"); break;
137 default: strcat(buf,"unhandled error"); break;
138 }
139
140 throw Bool_Engine_Error(buf,"list error", 0, 1);
141 }
142
143 /*!
144 is list empty (contains items or not)? \n
145 class | Dtype | item object in list
146 \return returns true is list is empty else false
147 \par Example
148 too see if list is empty
149 \code
150 DL_List<int> _intlist; #create a list of integers
151
152 if (_intlist.Empty())
153
154 cout << "empty";
155 \endcode
156 */
157 template <class Dtype>
empty()158 bool DL_List<Dtype>::empty()
159 {
160 return(bool)(_nbitems==0);
161 }
162
163 /*!
164 number of items in list \n
165 class | Dtype | item object in list
166 \return return number of items in the list
167 \par Example
168 too see if list contains only one object
169 \code
170 DL_List <int> _intlist; #create a list of integers
171
172 if (_intlist.count() == 1)
173
174 cout << "one object in list";
175 \endcode
176 */
177 template <class Dtype>
count()178 int DL_List<Dtype>::count()
179 {
180 return _nbitems;
181 }
182
183 /*!
184 remove all objects from the list\n
185 class | Dtype | item object in list
186 \note
187 The objects itself are not deleted, only removed from the list.
188 The user is responsible for memory management.
189
190 \note
191 The iterator level must be zero to be able to use this function,
192 else an error will be generated
193
194 \note
195 Use this function if an iterator is not needed to do more complex things.
196 This will save time, since the iterator does not have to be created.
197 \par Example
198 too insert integer a and b into list and remove_all directly
199 \code
200 DL_List<int> _intlist; #create a list of integers
201 int a=123;
202
203 int b=345;
204
205 _intlist.insbegin(a);
206
207 _intlist.insbegin(b);
208
209 _intlist.remove_all();
210 \endcode
211 */
212 template <class Dtype>
remove_all(bool deleteObject)213 void DL_List<Dtype>::remove_all( bool deleteObject )
214 {
215 if (_iterlevel > 0 )
216 Error("remove_all()",ITER_GT_0);
217
218 Dtype* obj;
219
220 DL_Node<Dtype> *node;
221 for (int i=0; i<_nbitems; i++)
222 {
223 node = _root->_next;
224 _root->_next = node->_next;
225 if ( deleteObject == true )
226 {
227 obj=(Dtype*)(node->_item);
228 delete obj;
229 }
230 delete node;
231 }
232 _nbitems=0;_iterlevel=0; //reset memory used (no lost pointers)
233 _root->_prev=_root;
234 }
235
236 /*!
237 remove the object at the begin of the list (head).
238 \note
239 The object itself is not deleted, only removed from the list.
240 The user is responsible for memory management.
241
242 \note
243 The iterator level must be zero to be able to use this function, else an error will be generated
244
245 \note
246 The list must contain objects, else an error will be generated.
247
248 \note
249 Use this function if an iterator is not needed to do more complex things. This will save time, since the iterator does not
250 have to be created.
251
252 \par Example:
253 too insert integer a at begin of list and remove it directly.
254 \code
255 DL_List<int> _intlist; #create a list of integers
256
257 int a=123;
258
259 _intlist.insbegin(a)
260
261 _intlist.removehead();
262
263 \endcode
264 */
265 template <class Dtype>
removehead()266 void DL_List<Dtype>::removehead()
267 {
268 if (_iterlevel > 0 )
269 Error("removehead()",ITER_GT_0);
270 if(_nbitems==0)
271 Error("removehead()",EMPTY);
272
273 DL_Node<Dtype>* node=_root->_next;
274
275 node->_prev->_next = node->_next; // update forward link
276 node->_next->_prev = node->_prev; // update backward link
277
278 _nbitems--;
279 delete node; // delete list node
280 }
281
282
283 /*!
284 remove the object at the begin of the list (head).
285
286 \note
287 - The object itself is not deleted, only removed from the list.
288 The user is responsible for memory management.
289 - The iterator level must be zero to be able to use this function,
290 else an error will be generated
291 - The list must contain objects, else an error will be generated.
292 - Use this function if an iterator is not needed to do more complex things.
293 This will save time, since the iterator does not have to be created.
294
295 \par Example:
296 too insert integer a at end of list and remove it directly.
297 \code
298 DL_List<int> _intlist; #create a list of integers
299
300 int a=123;
301
302 _intlist.insend(a)
303
304 _intlist.removetail();
305
306 \endcode
307 */
308 template <class Dtype>
removetail()309 void DL_List<Dtype>::removetail()
310 {
311 if (_iterlevel > 0)
312 Error("removetail()",ITER_GT_0);
313 if (_nbitems==0)
314 Error("removehead()",EMPTY);
315
316 DL_Node<Dtype>* node=_root->_prev;
317
318 node->_prev->_next = node->_next; // update forward link
319 node->_next->_prev = node->_prev; // update backward link
320
321 _nbitems--;
322 delete node; // delete list node
323 }
324
325 /*!
326 insert the object given at the end of the list, after tail
327 \note
328 The iterator level must be zero to be able to use this function,
329 else an error will be generated
330
331 \note
332 Use this function if an iterator is not needed to do more complex things.
333 This will save time, since the iterator does not have to be created.
334 \par Example:
335 too insert integer a at end of list
336 \code
337 DL_List<int> _intlist; #create a list of integers
338
339 int a=123;
340
341 _intlist.insend(a)
342 \endcode
343 \param newitem an object for which the template list was generated
344 */
345 template <class Dtype>
insend(Dtype newitem)346 DL_Node<Dtype>* DL_List<Dtype>::insend(Dtype newitem)
347 {
348 if (_iterlevel > 0)
349 Error("insend()",ITER_GT_0);
350
351 DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);
352
353 newnode ->_next = _root;
354 newnode ->_prev = _root->_prev;
355 _root->_prev->_next = newnode;
356 _root->_prev = newnode;
357
358 _nbitems++;
359
360 return newnode;
361 }
362
363 /*!
364 insert the object given at the begin of the list, before head
365 \note
366 The iterator level must be zero to be able to use this function,
367 else an error will be generated
368
369 \note
370 Use this function if an iterator is not needed to do more complex things.
371 This will save time, since the iterator does not have to be created.
372
373 \par Example:
374 too insert integer a at begin of list
375 \code
376 DL_List<int> _intlist; #create a list of integers
377
378 int a=123;
379
380 _intlist.insbegin(a)
381 \endcode
382 \param newitem an object for which the template list was generated
383 */
384 template <class Dtype>
insbegin(Dtype newitem)385 DL_Node<Dtype>* DL_List<Dtype>::insbegin(Dtype newitem)
386 {
387 if (_iterlevel > 0)
388 Error("insbegin()",ITER_GT_0);
389
390 DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);
391
392 newnode ->_prev = _root;
393 newnode ->_next = _root->_next;
394 _root->_next->_prev = newnode;
395 _root->_next = newnode;
396
397 _nbitems++;
398 return newnode;
399 }
400
401 /*!
402 get head item
403 \return returns the object at the head of the list.
404 \par Example:
405 too insert integer a and b into list and make c be the value of b
406 which is at head of list|
407 \code
408 DL_List<int> _intlist; #create a list of integers
409
410 int a=123;
411
412 int b=345;
413
414 int c;
415
416 _intlist.insbegin(a)
417
418 _intlist.insbegin(b)
419 c=_intlist.headitem()
420 \endcode
421 */
422 template <class Dtype>
headitem()423 Dtype DL_List<Dtype>::headitem()
424 {
425 return _root->_next->_item;
426 }
427
428 /*!
429 get tail item
430 \return returns the object at the tail/end of the list.
431 \par Example:
432 too insert integer a and b into list and make c be the value of b which
433 is at the tail of list
434 \code
435 DL_List<int> _intlist; #create a list of integers
436
437 int a=123;
438
439 int b=345;
440
441 int c;
442 _intlist.insbegin(a)
443 _intlist.insbegin(b)
444
445 c=_intlist.headitem()
446 \endcode
447 */
448 template <class Dtype>
tailitem()449 Dtype DL_List<Dtype>::tailitem()
450 {
451 return _root->_prev->_item;
452 }
453
454 /*!
455 * \note
456 The iterator level must be zero to be able to use this function, else an error will be generated
457
458 * \note The list may not be the same list as this list
459 * \param otherlist the list to take the items from
460 */
461 template <class Dtype>
takeover(DL_List<Dtype> * otherlist)462 void DL_List<Dtype>::takeover(DL_List<Dtype>* otherlist)
463 {
464 if (otherlist==0)
465 Error("takeover(DL_List*)",NO_LIST);
466 // no iterators allowed on otherlist
467 if (otherlist->_iterlevel > 0)
468 Error("takeover(DL_List*)",AC_ITER_LIST_OTHER);
469 // otherlist not this list
470 else if (otherlist == this)
471 Error("takeover(DL_List*)",SAME_LIST);
472
473 if (otherlist->_nbitems == 0)
474 return;
475
476 //link other list into this list at the end
477 _root->_prev->_next=otherlist->_root->_next;
478 otherlist->_root->_next->_prev=_root->_prev;
479 otherlist->_root->_prev->_next=_root;
480 _root->_prev=otherlist->_root->_prev;
481
482 //empty other list
483 _nbitems+=otherlist->_nbitems;
484 otherlist->_nbitems=0;
485 otherlist->_root->_next=otherlist->_root;
486 otherlist->_root->_prev=otherlist->_root;
487 }
488
489 //=======================================================================
490 // implementation class DL_Iter
491 //=======================================================================
492 /*! \class DL_Iter
493 template iterator for any list/node type\n
494 This class is the base class to attach/instantiate an iterator on a double linked list. \n
495 DL_List The iterator is used to traverse and perform functions on the nodes of a list. \n
496 More then 1 iterator can be attached to a list. The list keeps track of the
497 number of iterators that are attached to it. \n
498 Depending on this certain operations are allowed are not. For instance a node can
499 only be deleted if there is only one iterator attached to the list. \n
500 class | Dtype | Object for traversing a DL_List of the same Dtype
501 // \par Example
502 to insert integer a and b into list and remove_all directly using an iterator
503 \code
504 DL_List<int>* a_list = new DL_List<int>(); // declaration and allocation
505
506 int a=123;
507
508 int b=345;
509
510 {
511
512 DL_Iter<int>* a_listiter=new DL_Iter<int>(a_list);
513
514 a_listiter->insbegin(a)
515
516 a_listiter->insbegin(b)
517
518 a_listiter->remove_all()
519
520 } //to destruct the iterator before the list is deleted
521
522 delete a_list; #delete it (must have no iterators attached to it)
523 \endcode
524 */
525
526 /*!
527 Error report for list error inside DL_Iter class
528 the error function is used internally in the iterator class to report errors,
529 the function will generate a message based on the error code.
530 Then an exception will be generated using the global booleng class instance.|
531 \par Example
532 to call error from inside an DL_List class|
533 \code
534 Error("remove_all",ITER_GT_O);
535 \endcode
536 \param function: function string that generated this error
537 \param a_error: error code to generate a message for
538 */
539 template <class Dtype>
Error(const char * function,Lerror a_error)540 void DL_Iter<Dtype>::Error(const char* function,Lerror a_error)
541 {
542 char buf[100];
543 strcpy(buf,"DL_Iter<Dtype>::");
544 strcat(buf,function);
545 switch (a_error)
546 {
547 case NO_MES: strcat(buf,""); break;
548 case NO_LIST: strcat(buf,"no list attached"); break;
549 case NO_LIST_OTHER: strcat(buf,"no list on other iter"); break;
550 case AC_ITER_LIST_OTHER: strcat(buf,"iter not allowed on other list"); break;
551 case SAME_LIST: strcat(buf,"same list not allowed"); break;
552 case NOT_SAME_LIST: strcat(buf,"must be same list"); break;
553 case ITER_GT_1: strcat(buf,"more then one iter"); break;
554 case ITER_HITROOT: strcat(buf,"iter at root"); break;
555 case NO_ITEM: strcat(buf,"no item at current"); break;
556 case NO_NEXT: strcat(buf,"no next after current"); break;
557 case NO_PREV: strcat(buf,"no prev before current"); break;
558 case EMPTY: strcat(buf,"list is empty"); break;
559 case NOT_ALLOW: strcat(buf,"not allowed"); break;
560 case ITER_NEG: strcat(buf,"to much iters deleted"); break;
561 default: strcat(buf,"unhandled error"); break;
562 }
563 throw Bool_Engine_Error(buf,"list error", 0, 1);
564 }
565
566 /*!
567 Construct an iterator object for a given list of type Dtype \n
568 tcarg: class | Dtype | list item object
569 \par Example
570 How to construct a list of type integer and an iterator for it:
571 \code
572 DL_List<int>* IntegerList;
573 IntegerList = new DL_List<int>();
574 DL_Iter<int>* a_listiter=new DL_Iter<int>(IntegerList);
575 \endcode
576 \param newlist: list for the iterator
577 */
578 template <class Dtype>
DL_Iter(DL_List<Dtype> * newlist)579 DL_Iter<Dtype>:: DL_Iter(DL_List<Dtype>* newlist)
580 :_list(newlist), _current(RT)
581 {
582 _list->_iterlevel++; // add 1 to DL_Iters on list
583 }
584
585 /*!
586 This constructs an iterator for a list using an other iterator on the same list,
587 The new iterator will be pointing to the same list item as the other iterator.\n
588 tcarg: class | Dtype | list item object
589 \par Example
590 How to construct a list of type integer and a second iterator for it:|
591 \code
592 DL_List<int>* IntegerList;
593
594 IntegerList = new DL_List<int>();
595
596 DL_Iter<int>* a_listiter=new DL_Iter<int>(IntegerList);
597
598 DL_Iter<int>* a_secondlistiter=new DL_Iter<int>(a_listiter);
599 \endcode
600 \param otheriter other iterator on same list
601 */
602 template <class Dtype>
DL_Iter(DL_Iter * otheriter)603 DL_Iter<Dtype>:: DL_Iter(DL_Iter* otheriter)
604 {
605 if (otheriter->_current==0)
606 Error("DL_Iter(otheriter)",NO_LIST_OTHER);
607 _list=otheriter->_list;
608 _list->_iterlevel++; // add 1 to DL_Iters on List
609 _current=otheriter->_current;
610 }
611
612 /*!
613 This constructs an iterator for a list of a given type, the list does not have to exist.
614 Later on when a list is constructed,the iterator can be attached to it.
615 This way an iterator to a specific list can be made static to a class, and can be used
616 for several lists at the same time. \n
617 tcarg: class | Dtype | list item object
618
619 \par Example
620 How to construct an iterator, without having a list first.
621 This constructs an iterator for a list of the given type, but the list thus not yet exist.
622 \code
623 DL_Iter<int>* a_iter=new DL_Iter<int>();
624
625 DL_List<int>* IntegerList;
626
627 IntegerList = new DL_List<int>();
628
629 a_iter.Attach(IntegerList);
630
631 a_iter.insend(123);
632
633 a_iter.Detach();
634 \endcode
635 */
636 template <class Dtype>
DL_Iter()637 DL_Iter<Dtype>:: DL_Iter()
638 :_list(0), _current(0)
639 {
640 }
641
642 /*!
643 destruct an iterator for a list of a given type.
644 */
645 template <class Dtype>
~DL_Iter()646 DL_Iter<Dtype>::~DL_Iter()
647 {
648 if (_current==0)
649 return;
650 _list->_iterlevel--; // decrease iterators
651 if (_list->_iterlevel < 0)
652 Error("~DL_Iter()",ITER_NEG);
653 }
654
655 /*!
656 This attaches an iterator to a list of a given type, the list must exist.
657 This way an iterator to a specific list can be made
658 static to a class, and can be used for several lists at the same time.\n
659 !tcarg: class | Dtype | list item object
660 \par Example
661 How to construct an iterator, without having a list first, and attach an iterator later:|
662 \code
663 DL_Iter<int>* a_iter=new DL_Iter<int>();
664
665 DL_List<int>* IntegerList;
666
667 IntegerList = new DL_List<int>();
668
669 a_iter.Attach(IntegerList);
670
671 a_iter.insend(123);
672
673 a_iter.Detach();
674 \endcode
675 \param newlist the list to attached the iterator to
676 */
677 template <class Dtype>
Attach(DL_List<Dtype> * newlist)678 void DL_Iter<Dtype>::Attach(DL_List<Dtype>* newlist)
679 {
680 if (_current!=0)
681 Error("Attach(list)",NOT_ALLOW);
682 _list=newlist;
683 _current=HD;
684 _list->_iterlevel++; // add 1 to DL_Iters on list
685 }
686
687 /*!
688 This detaches an iterator from a list of a given type, the list must exist.
689 This way an iterator to a specific list can be made static to a class,
690 and can be used for several lists at the same time. \n
691 !tcarg: class | Dtype | list item object
692 \par Example:
693 How to construct an iterator, without having a list first, and attach an iterator later:
694 \code
695 DL_Iter<int>* a_iter=new DL_Iter<int>();
696
697 DL_List<int>* IntegerList;
698
699 IntegerList = new DL_List<int>();
700
701 a_iter.Attach(IntegerList);
702
703 a_iter.insend(123);
704
705 a_iter.Detach();
706 \endcode
707 \param newlist: the list to attached the iterator to
708 */
709 template <class Dtype>
Detach()710 void DL_Iter<Dtype>::Detach()
711 {
712 if (_current==0)
713 Error("Attach()",NO_LIST);
714 _list->_iterlevel--; // subtract 1 from DL_Iters on list
715 _list=0;
716 _current=0;
717 }
718
719 /*
720 // copy pointers to items from other list
721 template <class Dtype> void DL_Iter<Dtype>::merge(DL_List<Dtype>* otherlist)
722 {
723 DL_Node* node=otherlist->HD; //can be 0 if empty
724 for(int i=0; i<otherlist->NB; i++)
725 {
726 insend(node->new_item); // insert item at end
727 node=node->_next; // next item of otherlist
728 }
729 }
730 */
731 /*
732 //call Dtype::mfp for each item
733 template <class Dtype>
734 void DL_Iter<Dtype>::foreach_mf(void (Dtype::*mfp)())
735 {
736 DL_Node<Dtype>* node=HD; //can be 0 if empty
737 for(int i=0; i< NB; i++)
738 {
739 ((node->_item).*mfp)();
740 node=node->_next;
741 }
742 }
743 */
744
745
746 /*! call given function for each item*/
747 template <class Dtype>
foreach_f(void (* fp)(Dtype n))748 void DL_Iter<Dtype>::foreach_f(void (*fp) (Dtype n) )
749 {
750 DL_Node<Dtype>* node=HD; //can be 0 if empty
751 for(int i=0; i< NB; i++)
752 {
753 fp (node->_item);
754 node=node->_next;
755 }
756 }
757
758
759 /*!
760 to move all objects in a list to the list of the iterator.
761 \note
762 The iterator level must be one to be able to use this function,
763 else an error will be generated
764
765 \note
766 The list may not be the same list as the iterator list
767 \par Example
768 to take over all items in _intlist|
769 \code
770 DL_List<int> _intlist; #create a list of integers
771
772 DL_List<int> _intlist2; #create a list of integers
773
774 int a=123;
775
776 DL_Iter<int>* a_listiter2=new DL_Iter<int>(&_intlist2);
777
778 _intlist->insend(a) // insert at end
779
780 a_listiter2->takeover(_intlist)
781 \endcode
782 \param otherlist the list to take the items from
783 */
784 template <class Dtype>
takeover(DL_List<Dtype> * otherlist)785 void DL_Iter<Dtype>::takeover(DL_List<Dtype>* otherlist)
786 {
787 if (_current==0)
788 Error("takeover(DL_List*)",NO_LIST);
789 // no iterators allowed on otherlist
790 if (otherlist->_iterlevel > 0)
791 Error("takeover(DL_List*)",AC_ITER_LIST_OTHER);
792 // otherlist not this list
793 else if (otherlist == _list)
794 Error("takeover(DL_List*)",SAME_LIST);
795
796 if (otherlist->_nbitems == 0)
797 return;
798
799 //link other list into this list at the end
800 TL->_next=otherlist->_root->_next;
801 otherlist->_root->_next->_prev=TL;
802 otherlist->_root->_prev->_next=RT;
803 TL=otherlist->_root->_prev;
804
805 //empty other list
806 NB+=otherlist->_nbitems;
807 otherlist->_nbitems=0;
808 otherlist->_root->_next=otherlist->_root;
809 otherlist->_root->_prev=otherlist->_root;
810 }
811
812
813 /*!
814 to move all objects in a list (using iterator of that list) to the list of the iterator.
815 \note
816 The iterator level for both iterators must be one to be able to use this function,
817
818 \note
819 else an error will be generated
820
821 \note
822 The list may not be the same list as the iterator list
823
824 \par Example
825 to take over all items in a_listiter1 it's list|
826 \code
827 DL_List<int> _intlist; #create a list of integers
828
829 DL_List<int> _intlist2; #create a list of integers
830
831 int a=123;
832
833 DL_Iter<int>* a_listiter1=new DL_Iter<int>(&_intlist);
834
835 DL_Iter<int>* a_listiter2=new DL_Iter<int>(&_intlist2);
836
837 a_listiter1->insend(a) // insert at end
838
839 a_listiter2->takeover(a_listiter1)
840 \\!to move all objects in a list (using iterator of that list) to the list of the iterator
841 \endcode
842 \param otheriter: the iterator to take the items from
843 */
844 template <class Dtype>
takeover(DL_Iter * otheriter)845 void DL_Iter<Dtype>::takeover(DL_Iter* otheriter)
846 {
847 if (otheriter->_current==0)
848 Error(" DL_Iter",NO_LIST_OTHER);
849 if (_current==0)
850 Error(" DL_Iter",NO_LIST);
851
852 // only one iterator allowed on other list?
853 if (otheriter->_list->_iterlevel > 1)
854 Error("takeover(DL_Iter*)",AC_ITER_LIST_OTHER);
855 // otherlist not this list?
856 else if (otheriter->_list == _list)
857 Error("takeover(DL_Iter*)",SAME_LIST);
858
859 if (otheriter->NB == 0)
860 return;
861
862 //link other list into this list at the end
863 TL->_next=otheriter->HD;
864 otheriter->HD->_prev=TL;
865 otheriter->TL->_next=RT;
866 TL=otheriter->TL;
867
868 //empty other iter & list
869 NB+=otheriter->NB;
870 otheriter->NB=0;
871 otheriter->HD=otheriter->RT;
872 otheriter->TL=otheriter->RT;
873 otheriter->_current=otheriter->RT;
874 }
875
876 /*!
877 to move maxcount objects in a list (using iterator of that list)
878 to the list of the iterator.
879 \note The iterator level for both iterators must be one to be able to use this function,
880 else an error will be generated
881
882 \note The list may not be the same list as the iterator list
883
884 \note If less then maxcount objects are available in the source iterator,
885 all of them are taken and no error will accur
886
887 \par Example
888 to take over 1 item from a_listiter1 it's list
889 \code
890 DL_List<int> _intlist; #create a list of integers
891
892 DL_List<int> _intlist2; #create a list of integers
893
894 int a=123;
895
896 DL_Iter<int>* a_listiter1=new DL_Iter<int>(&_intlist);
897
898 DL_Iter<int>* a_listiter2=new DL_Iter<int>(&_intlist2);
899
900 a_listiter1->insend(a) // insert at end
901
902 a_listiter2->takeover(a_listiter1,1);
903 //! to move maxcount objects in a list (using iterator of that list) to the list of the iterator
904 \endcode
905 \param otheriter the iterator to take the items from
906 \param maxcount maximum number of objects to take over
907 */
908 template <class Dtype>
takeover(DL_Iter * otheriter,int maxcount)909 void DL_Iter<Dtype>::takeover(DL_Iter* otheriter, int maxcount)
910 {
911 if (otheriter->_current==0)
912 Error("takeover(DL_Iter*,int)",NO_LIST_OTHER);
913 if (_current==0)
914 Error("takeover(DL_Iter*,int)",NO_LIST);
915
916 if (otheriter->_list->_iterlevel > 1)
917 Error("takeover(DL_Iter*,int)",AC_ITER_LIST_OTHER);
918 else if (otheriter->_list == _list)
919 Error("takeover(DL_Iter*,int)",SAME_LIST);
920
921 if (maxcount<0)
922 Error("takeover(DL_Iter*,int), maxcount < 0",NO_MES);
923
924 if (otheriter->NB == 0)
925 return;
926
927
928 if (otheriter->NB <= maxcount)
929 { //take it all
930 //link other list into this list at the end
931 TL->_next=otheriter->HD;
932 otheriter->HD->_prev=TL;
933 otheriter->TL->_next=RT;
934 TL=otheriter->TL;
935
936 //empty other iter & list
937 NB+=otheriter->NB;
938 otheriter->NB=0;
939 otheriter->HD=otheriter->RT;
940 otheriter->TL=otheriter->RT;
941 otheriter->_current=otheriter->RT;
942 }
943 else
944 { //take maxcount elements from otheriter
945 //set cursor in otherlist to element maxcount
946 DL_Node<Dtype>* node;
947
948 if (NB/2 < maxcount)
949 { // this is faster (1st half)
950 node=otheriter->HD;
951 for(int i=1; i<maxcount; i++)
952 node=node->_next;
953 }
954 else
955 { // no, this is faster (2nd half)
956 node=otheriter->TL;
957 for(int i=NB; i>maxcount+1; i--)
958 node=node->_prev;
959 }
960
961 // link this->tail to other->head
962 if (NB>0)
963 {
964 TL->_next=otheriter->HD;
965 otheriter->HD->_prev=TL;
966 }
967 else // target is empty
968 {
969 HD=otheriter->HD;
970 otheriter->HD->_prev=RT;
971 }
972
973 // set other root to node-> next (after last to copy)
974 otheriter->HD=node->_next;
975 otheriter->HD->_prev=otheriter->RT;
976
977 // set this->tail to other->item()->prev (last element to be copied)
978 TL=node;
979 node->_next=RT;
980
981 // still need to update element counter
982 NB+=maxcount;
983
984 // update other list
985 otheriter->NB-=maxcount;
986 otheriter->_current=otheriter->HD; // other->current is moved to this!
987 }
988 }
989
990
991 /*!
992 put the iterator root object before the current iterator position in the list.
993 The current object will become the new head of the list.
994 \note The iterator level must be one to be able to use this function,
995 else an error will be generated
996
997 \par Example
998 move the root object to make the new head the old tail object|
999 \code
1000 DL_List <int> _intlist; #create a list of integers
1001 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1002
1003 a_listiter->insend(1234);
1004 a_listiter->insend(2345);
1005 a_listiter->insend(3456);
1006 a_listiter->totail();
1007 a_listiter->reset_head();
1008 a_listiter->tohead(); //the new head will be at object 3456
1009 \endcode
1010 */
1011 template <class Dtype>
reset_head()1012 void DL_Iter<Dtype>::reset_head()
1013 {
1014 if (_current==0)
1015 Error("reset_head()",NO_LIST);
1016 if (_list->_iterlevel > 1 )
1017 Error("reset_head()",ITER_GT_1);
1018
1019 if(_current==RT)
1020 Error("reset head()",ITER_HITROOT);
1021
1022 //link out RT
1023 HD->_prev=TL;
1024 TL->_next=HD;
1025
1026 //link in RT before current
1027 HD=_current;
1028 TL=_current->_prev;
1029
1030 TL->_next=RT;
1031 HD->_prev=RT;
1032 }
1033
1034 /*!
1035 put the iterator root object after the current iterator position in the list.
1036 The current object will become the new tail of the list.
1037 \note
1038 The iterator level must be one to be able to use this function,
1039 else an error will be generated
1040 \par Example
1041 move the root object to make the new tail the old head object
1042 \code
1043 DL_List <int> _intlist; #create a list of integers
1044 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1045
1046 a_listiter->insend(1234);
1047 a_listiter->insend(2345);
1048 a_listiter->insend(3456);
1049 a_listiter->tohead();
1050 a_listiter->reset_tail();
1051 a_listiter->totail(); //the new tail will be at object 1234
1052 \endcode
1053 */
1054 template <class Dtype>
reset_tail()1055 void DL_Iter<Dtype>::reset_tail()
1056 {
1057 if (_current==0)
1058 Error("reset_tail()",NO_LIST);
1059 if (_list->_iterlevel > 1 )
1060 Error("reset_tail()",ITER_GT_1);
1061
1062 if(_current==RT)
1063 Error("reset head()",ITER_HITROOT);
1064
1065 //link out RT
1066 HD->_prev=TL;
1067 TL->_next=HD;
1068
1069 //link in RT after current
1070 TL=_current;
1071 HD=_current->_next;
1072
1073 HD->_prev=RT;
1074 TL->_next=RT;
1075 }
1076
1077 /*!
1078 is list empty (contains items or not)?
1079 \return returns true is list is empty else false
1080 \par exmaple:
1081 too see if list is empty
1082 \code
1083 DL_List<int> _intlist; #create a list of integers
1084 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1085
1086 if (a_listiter->Empty())
1087 cout << "empty"
1088 \endcode
1089 */
1090 template <class Dtype>
empty()1091 bool DL_Iter<Dtype>::empty()
1092 {
1093 if (_current==0)
1094 Error("empty()",NO_LIST);
1095
1096 return(bool)(NB==0);
1097 }
1098
1099 /*!
1100 is the iterator at the root of the list.
1101 \note Traversing the list in a certain direction using a while loop,
1102 the end can be tested with this function.
1103 \return returns true if the iterator is at the root of the list (after the last/tail/head object), else false.
1104 \par example:
1105 to traverse in both directions|
1106 \code
1107 DL_List <int> _intlist; #create a list of integers
1108 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1109
1110 a_listiter->tohead();
1111 //traverse forwards
1112 while ( ! a_listiter->hitroot())
1113 {
1114 cout << "The item =" << a_listiter->item();
1115 a_listiter++; //goto next object
1116 }
1117
1118 a_listiter->totail();
1119 //traverse backwards
1120 while ( ! a_listiter->hitroot())
1121 {
1122 cout << "The item =" << a_listiter->item();
1123 a_listiter--; //goto next object
1124 }
1125 \endcode
1126 */
1127 template <class Dtype>
hitroot()1128 bool DL_Iter<Dtype>::hitroot()
1129 {
1130 if (_current==0)
1131 Error("hitroot()",NO_LIST);
1132
1133 return(bool)(_current == RT);
1134 }
1135
1136 /*!
1137 is the iterator at the head of the list.
1138 \return returns true if the iterator is at the head object of the list, else false.
1139 \par exmaple:
1140 too see the object at the head
1141 \code
1142 DL_List <int> _intlist; #create a list of integers
1143 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1144
1145 a_listiter->tohead();
1146 if (a_listiter->athead())
1147 cout << "at the head The item =" << a_listiter->item();
1148 \endcode
1149 */
1150 template <class Dtype>
athead()1151 bool DL_Iter<Dtype>::athead()
1152 {
1153 if (_current==0)
1154 Error("athead()",NO_LIST);
1155
1156 return(bool)(_current == HD);
1157 }
1158
1159 /*!
1160 is the iterator at the tail of the list.
1161 \return returns true if the iterator is at the tail object of the list,
1162 else false.
1163 \par Example
1164 too see the object at the tail|
1165 \code
1166 DL_List <int> _intlist; #create a list of integers
1167 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1168
1169 a_listiter->totail();
1170 if (a_listiter->attail())
1171 cout << "at the tail The item =" << a_listiter->item();
1172 \endcode
1173 */
1174 template <class Dtype>
attail()1175 bool DL_Iter<Dtype>::attail()
1176 {
1177 if (_current==0)
1178 Error("attail()",NO_LIST);
1179
1180 return(bool)(_current == TL);
1181 }
1182
1183 /*!
1184 does the iterator/list contain the given object
1185 \return returns true if the iterator/list contains the given object in the list, else false.
1186 \par Example
1187 too see if the object is already in the list
1188 \code
1189 DL_List <int> _intlist; #create a list of integers
1190 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1191 a_listiter->insend(1234);
1192
1193 if (a_listiter->has(1234))
1194 cout << "yes it does";
1195 \endcode
1196 \param otheritem item to search for
1197 */
1198 template <class Dtype>
has(Dtype otheritem)1199 bool DL_Iter<Dtype>::has(Dtype otheritem)
1200 {
1201 if (_current==0)
1202 Error("has()",NO_LIST);
1203
1204 DL_Node<Dtype>* node=HD; //can be 0 if empty
1205 for(int i=0; i<NB; i++)
1206 { if (node->_item == otheritem)
1207 return true;
1208 node=node->_next;
1209 }
1210 return false;
1211 }
1212
1213 /*!
1214 number of items in list
1215 \return number of items in the list
1216 \par Example:
1217 to see if a list contains only one object
1218 \code
1219 DL_List <int> _intlist; #create a list of integers
1220 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1221 if (a_listiter->count() == 1)
1222 cout << "one object in list";
1223 \endcode
1224 */
1225 template <class Dtype>
count()1226 int DL_Iter<Dtype>::count()
1227 {
1228 if (_current==0)
1229 Error("count()",NO_LIST);
1230
1231 return NB;
1232 }
1233
1234 /*!
1235 go to first item, if list is empty goto hite
1236 \par Example
1237 set iterator to head of list
1238 \code
1239 DL_List <int> _intlist; #create a list of integers
1240 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1241
1242 a_listiter->insend(1234);
1243 a_listiter->tohead();
1244 \endcode
1245 */
1246 template <class Dtype>
tohead()1247 void DL_Iter<Dtype>::tohead()
1248 {
1249 if (_current==0)
1250 Error("tohead()",NO_LIST);
1251
1252 _current=HD;
1253 }
1254
1255 /*!
1256 go to last item, if list is empty goto hite
1257 \par Example
1258 set iterator to tail of list
1259 \code
1260 DL_List <int> _intlist; #create a list of integers
1261 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1262
1263 a_listiter->insend(1234);
1264 a_listiter->totail();
1265 \endcode
1266 */
1267 template <class Dtype>
totail()1268 void DL_Iter<Dtype>::totail()
1269 {
1270 if (_current==0)
1271 Error("totail()",NO_LIST);
1272
1273 _current=TL;
1274 }
1275
1276 /*!
1277 set the iterator position to the root (empty dummy) object in the list.
1278 \par Example
1279 set iterator to root of list and iterate
1280 \code
1281 DL_List <int> _intlist; #create a list of integers
1282 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1283
1284 a_listiter->insend(1234);
1285 a_listiter->toroot();
1286 while (a_listiter->iterate())
1287 cout << a_listiter->item();
1288 \endcode
1289 */
1290 template <class Dtype>
toroot()1291 void DL_Iter<Dtype>::toroot()
1292 {
1293 if (_current==0)
1294 Error("toroot()",NO_LIST);
1295
1296 _current=RT;
1297 }
1298
1299 /*!
1300 set the iterator position to next object in the list ( can be the root also)(prefix).
1301 \par Example
1302 how to iterate backwards
1303 \code
1304 DL_List <int> _intlist; //create a list of integers
1305 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1306
1307 a_listiter->insend(1234);
1308 a_listiter->tohead();
1309 while (!a_listiter->hitroot())
1310 {
1311 cout << a_listiter->item();
1312 _listiter++;
1313 }
1314 \endcode
1315 */
1316 template <class Dtype>
operator ++(void)1317 void DL_Iter<Dtype>::operator++(void)
1318 {
1319 if (_current==0)
1320 Error("operator++()",NO_LIST);
1321
1322 _current=_current->_next;
1323 }
1324
1325 /*!
1326 set the iterator position to next object in the list ( can be the root also)(prefix).
1327 \par Example
1328 how to iterate backwards
1329 \code
1330 DL_List <int> _intlist; //create a list of integers
1331 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1332
1333 a_listiter->insend(1234);
1334 a_listiter->tohead();
1335 while (!a_listiter->hitroot())
1336 {
1337 cout << a_listiter->item();
1338 ++_listiter;
1339 }
1340 \endcode
1341 */
1342 template <class Dtype>
operator ++(int)1343 void DL_Iter<Dtype>::operator++(int)
1344 {
1345 if (_current==0)
1346 Error("operator++(int)",NO_LIST);
1347
1348 _current=_current->_next;
1349 }
1350
1351
1352 /*!
1353 set the iterator position to previous object in the list ( can be the root also)(prefix).
1354 \par Example
1355 how to iterate backwards
1356 \code
1357 DL_List <int> _intlist; //create a list of integers
1358 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1359
1360 a_listiter->insend(1234);
1361 a_listiter->totail();
1362 while (!a_listiter->hitroot())
1363 {
1364 cout << a_listiter->item();
1365 _listiter--;
1366 }
1367 \endcode
1368 */
1369 template <class Dtype>
operator --(void)1370 void DL_Iter<Dtype>::operator--(void)
1371 {
1372 if (_current==0)
1373 Error("operator++()",NO_LIST);
1374
1375 _current=_current->_prev;
1376 }
1377
1378
1379 /*!
1380 set the iterator position to previous object in the list ( can be the root also)(prefix).
1381 \par Example
1382 how to iterate backwards
1383 \code
1384 DL_List <int> _intlist; //create a list of integers
1385 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1386
1387 a_listiter->insend(1234);
1388 a_listiter->totail();
1389 while (!a_listiter->hitroot())
1390 {
1391 cout << a_listiter->item();
1392 --_listiter;
1393 }
1394 \endcode
1395 */
1396 template <class Dtype>
operator --(int)1397 void DL_Iter<Dtype>::operator--(int)
1398 {
1399 if (_current==0)
1400 Error("operator++(int)",NO_LIST);
1401
1402 _current=_current->_prev;
1403 }
1404
1405
1406 /*!
1407 set the iterator position n objects in the next direction ( can be the root also).
1408 \par Example:
1409 how to set iterator 2 items forward
1410 \code
1411 DL_List <int> _intlist; #create a list of integers
1412 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1413 a_listiter->insend(1234);
1414 a_listiter->tohead();
1415 a_listiter>>2;//at root now
1416 \endcode
1417 \param n go n places forward
1418 */
1419 template <class Dtype>
operator >>(int n)1420 void DL_Iter<Dtype>::operator>>(int n)
1421 {
1422 if (_current==0)
1423 Error("operator>>()",NO_LIST);
1424
1425 for(int i=0; i<n; i++)
1426 _current=_current->_next;
1427 }
1428
1429
1430 /*!
1431 set the iterator position n objects in the previous direction ( can be the root also).
1432 \par Example:
1433 how to set iterator 2 items backwards
1434 \code
1435 DL_List <int> _intlist; #create a list of integers
1436 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1437 a_listiter->insend(1234);
1438 a_listiter->totail();
1439 a_listiter<<2;//at root now
1440 \endcode
1441 \param n go n places back
1442 */
1443 template <class Dtype>
operator <<(int n)1444 void DL_Iter<Dtype>::operator<<(int n)
1445 {
1446 if (_current==0)
1447 Error("operator<<()",NO_LIST);
1448
1449 for(int i=0; i<n; i++)
1450 _current=_current->_prev;
1451 }
1452
1453
1454 /*!
1455 put the iterator at the position of the given object in the list.
1456 \return returns true if the object was in the list, else false
1457 \par Example:
1458 goto element 2345
1459 \code
1460 DL_List <int> _intlist; #create a list of integers
1461 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1462
1463 a_listiter->insend(1234);
1464 a_listiter->insend(2345);
1465 a_listiter->insend(3456);
1466
1467 a_listiter->toitem(2345); template <class Dtype>
1468 \endcode
1469 */
1470 template <class Dtype>
toitem(Dtype item)1471 bool DL_Iter<Dtype>::toitem(Dtype item)
1472 {
1473 if (_current==0)
1474 Error("toitem(item)",NO_LIST);
1475 DL_Node<Dtype>* node=HD; //can be 0 if empty
1476 for(int i=0; i<NB; i++)
1477 { if (node->_item == item)
1478 {
1479 _current = node;
1480 return true;
1481 }
1482 node=node->_next;
1483 }
1484 return false;
1485 }
1486
1487 /*!
1488 put the iterator at the same position as the given iterator in the list.
1489 \par Example:
1490 goto element 2345 and let a_listiter2 point to the same position
1491 \code
1492 DL_List <int> _intlist; #create a list of integers
1493 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1494 DL_Iter<int>* a_listiter2=new DL_Iter<int>(&_intlist);
1495
1496 a_listiter->insend(1234);
1497 a_listiter->insend(2345);
1498 a_listiter->insend(3456);
1499 a_listiter->toitem(2345);
1500 a_listiter2->toiter(a_listiter2);
1501 \endcode
1502 \param otheriter other iterator to let this iterator point to.
1503 */
1504 template <class Dtype>
toiter(DL_Iter * otheriter)1505 void DL_Iter<Dtype>::toiter(DL_Iter *otheriter)
1506 {
1507 if (otheriter->_current==0)
1508 Error("toiter(otheriter)",NO_LIST);
1509 // both iters must have the same list
1510 if (_list != otheriter->_list)
1511 Error("toiter(otheriter)",NOT_SAME_LIST);
1512
1513 _current = otheriter->_current;
1514 }
1515
1516
1517 /*!
1518 put the iterator at the position of the given object in the list.
1519 \note DO NOT use this function. Normally you will not be able to address the nodes in a list.
1520 \return returns true if the node was in the list, else false
1521 \param othernode a node to let this iterator point to.
1522 */
1523 template <class Dtype>
tonode(DL_Node<Dtype> * othernode)1524 bool DL_Iter<Dtype>::tonode(DL_Node<Dtype> *othernode)
1525 {
1526 DL_Node<Dtype>* node=HD; //can be 0 if empty //node is a temporary cursor
1527 for(int i=0; i<NB; i++)
1528 { if (node == othernode)
1529 {
1530 _current = othernode;
1531 return true;
1532 }
1533 node=node->_next;
1534 }
1535 return false;
1536 }
1537
1538 /*!
1539 advance the iterator one position in the next direction in the list.
1540 \return returns true if not at the end/root of the list else false.
1541
1542 \note This function combines iteration and testing for the end of
1543 the list in one.
1544
1545 \note Therefore we do not have to advance the iterator ourselves.
1546
1547 \note
1548 The iterator is first put to the next object, before testing for the end of the list. |
1549 This is why we need to start at the root element in general usage.
1550
1551 \par Example
1552 iterate through all the items in a list
1553 \code
1554 DL_List <int> _intlist; #create a list of integers
1555 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1556
1557 a_listiter->insend(1234);
1558 a_listiter->insend(2345);
1559 a_listiter->insend(3456);
1560 a_listiter->tobegin(2345);
1561
1562 while (a_listiter->iterate())
1563 { cout << a_listiter->item(); }
1564 \endcode
1565 */
1566 template <class Dtype>
iterate(void)1567 bool DL_Iter<Dtype>::iterate(void)
1568 {
1569 if (_current==0)
1570 Error("iterate()",NO_LIST);
1571
1572 _current=_current->_next;
1573 if (_current==RT)
1574 return false;
1575 return true;
1576 }
1577
1578 /*!
1579 To get the item at the current iterator position
1580 \return returns the object where the iterator is pointing to at the moment.
1581 \note
1582 If the iterator is at the root of the list an error will be generated,
1583 since there is no item there.
1584 \par Example:
1585 get the element at the head of the list|
1586 \code
1587 DL_List <int> _intlist; //create a list of integers
1588 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1589
1590 a_listiter->insend(1234);
1591 a_listiter->tohead();
1592 int theitem=a_listiter->item();
1593 \endcode
1594 */
1595 template <class Dtype>
item()1596 Dtype DL_Iter<Dtype>::item()
1597 {
1598 if (_current==0)
1599 Error("item()",NO_LIST);
1600 if (_current==RT)
1601 Error("item()",NO_ITEM);
1602
1603 return _current->_item;
1604 }
1605
1606 //! get the node at iterater position
1607 template <class Dtype>
node()1608 DL_Node<Dtype>* DL_Iter<Dtype>::node()
1609 {
1610 if (_current==0)
1611 Error("item()",NO_LIST);
1612 if (_current==RT)
1613 Error("item()",NO_ITEM);
1614
1615 return _current;
1616 }
1617
1618 /*!
1619 set the iterator position to next object in the list ( can be the root also).
1620 \note Use this function inside a new class derived from DL_Iter.
1621 */
1622 template <class Dtype>
next()1623 void DL_Iter<Dtype>::next()
1624 {
1625 if (_current==0)
1626 Error("item()",NO_LIST);
1627
1628 _current=_current->_next;
1629 }
1630
1631
1632 /*!
1633 set the iterator position to next object in the list, if this would be the root object,
1634 then set the iterator at the head object
1635 \par Example
1636 cycle the list twice
1637 \code
1638 DL_List <int> _intlist; #create a list of integers
1639 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1640
1641 a_listiter->insend(1234);
1642 a_listiter->insend(2345);
1643 a_listiter->tohead();
1644
1645 int count=2*a_listiter->count();
1646 while (count)
1647 {
1648 cout << a_listiter->item();
1649 next_wrap();
1650 count--;
1651 }
1652 \endcode
1653 */
1654 template <class Dtype>
next_wrap()1655 void DL_Iter<Dtype>::next_wrap()
1656 {
1657 if (_current==0)
1658 Error("item()",NO_LIST);
1659
1660 _current=_current->_next;
1661 if (_current==RT)
1662 _current=_current->_next;
1663 }
1664
1665
1666 /*!
1667 set the iterator position to previous object in the list ( can be the root also).
1668 \note Use this function inside a new class derived from DL_Iter.
1669 */
1670 template <class Dtype>
prev()1671 void DL_Iter<Dtype>::prev()
1672 {
1673 if (_current==0)
1674 Error("item()",NO_LIST);
1675
1676 _current=_current->_prev;
1677 }
1678
1679 /*!
1680 set the iterator position to previous object in the list, if this would be the root object,
1681 then set the iterator at the tail object
1682 \par Example
1683 cycle the list twice
1684 \code
1685 DL_List <int> _intlist; #create a list of integers
1686 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1687
1688 a_listiter->insend(1234);
1689 a_listiter->insend(2345);
1690 a_listiter->totail();
1691
1692 int count=2*a_listiter->count();
1693 while (count)
1694 {
1695 cout << a_listiter->item();
1696 prev_wrap();
1697 count--;
1698 }
1699 \endcode
1700 */
1701 template <class Dtype>
prev_wrap()1702 void DL_Iter<Dtype>::prev_wrap()
1703 {
1704 if (_current==0)
1705 Error("item()",NO_LIST);
1706
1707 _current=_current->_prev;
1708 if (_current==RT)
1709 _current=_current->_prev;
1710 }
1711
1712 template <class Dtype>
remove_all()1713 void DL_Iter<Dtype>::remove_all()
1714 {
1715 if (_current==0)
1716 Error("remove_all()",NO_LIST);
1717 if (_list->_iterlevel > 1 )
1718 Error("remove_all()",ITER_GT_1);
1719
1720 _list->_iterlevel--;
1721 _list->remove_all();
1722 _list->_iterlevel++;
1723 _current=RT;
1724 }
1725
1726 /*!
1727 remove object at current iterator position from the list.
1728 \note The object itself is not deleted, only removed from the list. The user is responsible for memory management.
1729
1730 \note The iterator level must be one to be able to use this function, else an error will be generated
1731
1732 \note The list must contain an object at the current iterator position, else an error will be generated.
1733 \par Example:
1734 to insert integer a at begin of list and remove it directly
1735 \code
1736 DL_List<int> _intlist; #create a list of integers
1737
1738 int a=123;
1739
1740 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1741
1742 a_listiter->insbegin(a);
1743
1744 a_listiter->tohead();
1745
1746 a_listiter->remove();
1747 \endcode
1748 */
1749 template <class Dtype>
remove()1750 void DL_Iter<Dtype>::remove()
1751 {
1752 if (_current==0)
1753 Error("remove()",NO_LIST);
1754 if (_list->_iterlevel > 1 )
1755 Error("remove()",ITER_GT_1);
1756 if (_current==RT)
1757 Error("remove()",ITER_HITROOT);
1758
1759 DL_Node<Dtype>* node=_current;
1760
1761 _current=_current->_next;
1762
1763 node->_prev->_next = node->_next; // update forward link
1764 node->_next->_prev = node->_prev; // update backward link
1765
1766 NB--;
1767 delete node; // delete list node
1768 }
1769
1770 /*!
1771 remove the object at the begin of the list using an iterator
1772 \note The object itself is not deleted, only removed from the list. The user is responsible for memory management.
1773
1774 \note The iterator level must be one to be able to use this function, else an error will be generated
1775
1776 \note The list must contain objects, else an error will be generated.
1777
1778 \note Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
1779 \par Example:
1780 to insert integer a at begin of list and remove it directly|
1781 \code
1782 DL_List<int> _intlist; #create a list of integers
1783
1784 int a=123;
1785
1786 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1787
1788 a_listiter->insbegin(a);
1789 a_listiter->removehead();
1790 \endcode
1791 */
1792 template <class Dtype>
removehead()1793 void DL_Iter<Dtype>::removehead()
1794 {
1795 if (_current==0)
1796 Error("removehead()",NO_LIST);
1797 if (_list->_iterlevel > 1 )
1798 Error("removehead()",ITER_GT_1);
1799 if(NB==0)
1800 Error("removehead()",EMPTY);
1801
1802 if (_current==HD)
1803 _current=_current->_next;
1804
1805 _list->_iterlevel--;
1806 _list->removehead();
1807 _list->_iterlevel++;
1808 }
1809
1810
1811 /*!
1812 //remove the object at the end of the list using an iterator
1813 \note The object itself is not deleted, only removed from the list. The user is responsible for memory management.
1814
1815 \note The iterator level must be one to be able to use this function, else an error will be generated
1816
1817 \note The list must contain objects, else an error will be generated.
1818
1819 \note Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
1820 \par Example:
1821 to insert integer a at end of list and remove it directly
1822 \code
1823 DL_List<int> _intlist; #create a list of integers
1824
1825 int a=123;
1826
1827 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1828
1829 a_listiter->insend(a);
1830 a_listiter->removetail();
1831 \endcode
1832 */
1833 template <class Dtype>
removetail()1834 void DL_Iter<Dtype>::removetail()
1835 {
1836 if (_current==0)
1837 Error("removetail()",NO_LIST);
1838 if (_list->_iterlevel > 1 )
1839 Error("removetail()",ITER_GT_1);
1840 if (NB==0)
1841 Error("removehead()",EMPTY);
1842
1843 if (_current==TL)
1844 _current=_current->_prev;
1845
1846 _list->_iterlevel--;
1847 _list->removetail();
1848 _list->_iterlevel++;
1849
1850 }
1851
1852 /*!
1853 insert the object given at the end of the list
1854
1855 \note The iterator level must be one to be able to use this function, else an error will be generated
1856
1857 \note Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
1858 \par Example:
1859 to insert integer a at end of list|
1860 \code
1861 DL_List<int> _intlist; #create a list of integers
1862
1863 int a=123;
1864
1865 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1866
1867 a_listiter->insend(a);
1868 \endcode
1869 */
1870 template <class Dtype>
insend(Dtype newitem)1871 DL_Node<Dtype>* DL_Iter<Dtype>::insend(Dtype newitem)
1872 {
1873 if (_current==0)
1874 Error("insend()",NO_LIST);
1875 if (_list->_iterlevel > 1)
1876 Error("insend()",ITER_GT_1);
1877
1878 _list->_iterlevel--;
1879 DL_Node<Dtype>* ret = _list->insend(newitem);
1880 _list->_iterlevel++;
1881 return ret;
1882 }
1883
1884
1885 /*!
1886 insert the object given at the begin of the list
1887 \note The iterator level must be one to be able to use this function, else an error will be generated
1888
1889 \note Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
1890
1891 \par Example:
1892 to insert integer a at begin of list|
1893 \code
1894 DL_List<int> _intlist; #create a list of integers
1895
1896 int a=123;
1897
1898 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1899
1900 a_listiter->insbegin(a);
1901 \endcode
1902 \param newitem an object for which the template list/iterator was generated
1903 */
1904 template <class Dtype>
insbegin(Dtype newitem)1905 DL_Node<Dtype>* DL_Iter<Dtype>::insbegin(Dtype newitem)
1906 {
1907 if (_current==0)
1908 Error("insbegin()",NO_LIST);
1909 if (_list->_iterlevel > 1)
1910 Error("insbegin()",ITER_GT_1);
1911
1912 _list->_iterlevel--;
1913 DL_Node<Dtype>* ret = _list->insbegin(newitem);
1914 _list->_iterlevel++;
1915 return ret;
1916 }
1917
1918 /*!
1919 //insert the object given before the current position of the iterator in list
1920 \note The iterator level must be one to be able to use this function, else an error will be generated
1921 \par Example:
1922 to insert integer before the iterator position in the list|
1923 \code
1924 DL_List<int> _intlist; #create a list of integers
1925
1926 int a=123;
1927
1928 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1929 a_listiter->totail();
1930 a_listiter->insbefore(a); // insert before tail
1931 \endcode
1932 \param newitem an object for which the template list/iterator was generated
1933 */
1934 template <class Dtype>
insbefore(Dtype newitem)1935 DL_Node<Dtype>* DL_Iter<Dtype>::insbefore(Dtype newitem)
1936 {
1937 if (_current==0)
1938 Error("insbefore()",NO_LIST);
1939 if (_list->_iterlevel > 1)
1940 Error("insbefore()",ITER_GT_1);
1941
1942 DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);
1943
1944 newnode ->_next = _current;
1945 _current->_prev->_next = newnode;
1946 newnode ->_prev = _current->_prev;
1947 _current->_prev = newnode;
1948
1949 NB++;
1950 return newnode;
1951 }
1952
1953
1954 /*!
1955 insert the object given after the current position of the iterator in list
1956 \note The iterator level must be one to be able to use this function, else an error will be generated
1957 \par Example: to insert integer after the iterator position in the list|
1958 \code
1959 DL_List<int> _intlist; #create a list of integers
1960
1961 int a=123;
1962
1963 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
1964 a_listiter->tohead();
1965 a_listiter->insafter(a); // insert after head
1966 \endcode
1967 \param newitem an object for which the template list/iterator was generated
1968 */
1969 template <class Dtype>
insafter(Dtype newitem)1970 DL_Node<Dtype>* DL_Iter<Dtype>::insafter(Dtype newitem)
1971 {
1972 if (_current==0)
1973 Error("insafter()",NO_LIST);
1974 if (_list->_iterlevel > 1)
1975 Error("insafter()",ITER_GT_1);
1976
1977 DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);
1978
1979 newnode ->_next = _current->_next;
1980 newnode ->_prev = _current;
1981 _current->_next->_prev = newnode;
1982 _current->_next = newnode;
1983
1984 NB++;
1985 return newnode;
1986 }
1987
1988 /*!
1989 sort all items in the list according to the compare function.
1990 when items need to be swapped to reach the right order the swap function will be called also.
1991 \note There are no restrictions on the internal decision in the compare function when to return -1,0,1.
1992
1993 \note The swap function can be used to change items when they are swapped.
1994 fcmp (function, fcmp)
1995 \verbatim
1996
1997 Declaration: int (*fcmp) (Dtype,Dtype)
1998
1999 compare function pointer, the function takes two objects in the list. It must return -1, 0, 1, to sort the list in upgoing
2000 order the function should return:
2001
2002 -1 is returned if the first object is bigger then the second.
2003 0 is returned if the objects are equal.
2004 1 is returned if the first object is smaller then the second.
2005
2006 To sort the list in downgoing order:
2007
2008 1 is returned if the first object is bigger then the second.
2009 0 is returned if the objects are equal.
2010 -1 is returned if the first object is smaller then the second.
2011
2012 fswap (function, fswap)
2013
2014 Declaration: void (*fswap) (Dtype,Dtype)
2015
2016 swap function pointer, the function takes two objects in the list. It will be called when the objects are swapped to
2017 reach the right order. If it is NULL, it will not be called.
2018 \endverbatim
2019 \par Example: sort the list in upgoing order using cocktailsort and the function numbersorter|
2020 \code
2021 int numbersorter(int a,int b)
2022 {
2023 if(a < b) return(1);
2024 else
2025 if(a == b) return(0);
2026 return(-1);
2027 }
2028
2029 DL_List <int> _intlist; #create a list of integers
2030 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
2031
2032 a_listiter->insend(2345);
2033 a_listiter->insend(3456);
2034 a_listiter->insend(1234);
2035 a_listiter->cocktailsort(numbersorter,NULL);
2036 \endcode
2037 \param fcmp sortfunction
2038 \param fswap swapfunction
2039 */
2040 template <class Dtype>
cocktailsort(int (* fcmp)(Dtype,Dtype),bool (* fswap)(Dtype,Dtype))2041 int DL_Iter<Dtype>::cocktailsort(int (*fcmp) (Dtype, Dtype), bool (*fswap)(Dtype, Dtype))
2042 {
2043 if (_current==0)
2044 Error("cocktailsort()",NO_LIST);
2045 if (NB <= 1)
2046 return 0;
2047
2048 DL_Node<Dtype>* cursor;
2049 Dtype swap;
2050
2051 int swapResult = 0;
2052
2053 // boven/ondergrens setten
2054 DL_Node<Dtype> *bg = TL, *bgold = TL;
2055 DL_Node<Dtype> *og = HD, *ogold = HD;
2056
2057 bool swapped = true;
2058
2059 // while swaping is done & lowerborder upperborder don't touch
2060 while (swapped && (og!=bg))
2061 {
2062 swapped = false;
2063
2064 // BUBBELSLAG lowerborder--->> upperborder
2065 cursor=og;
2066 while(!(cursor == bgold))
2067 {
2068 // (current.next < current)?
2069 if( fcmp(cursor->_next->_item, cursor->_item)==1)
2070 {
2071 // user function
2072 if ( fswap != NULL )
2073 if ( fswap(cursor->_item, cursor->_next->_item) )
2074 swapResult++;
2075 // update swap-flag en upperborder
2076 swapped = true;
2077 bg = cursor;
2078 // swap the items of the nodes
2079 swap = cursor->_item;
2080 cursor->_item = cursor->_next->_item;
2081 cursor->_next->_item = swap;
2082 }
2083 cursor=cursor->_next;
2084 }// end bubbelslag
2085 bgold = bg;
2086
2087 // BRICKSLAG lowerborder <<---upperborder
2088 cursor=bg;
2089 while(!(cursor == ogold))
2090 {
2091 // (current < current.next)?
2092 if( fcmp(cursor->_item, cursor->_prev->_item)==1)
2093 {
2094 // user function
2095 if ( fswap != NULL )
2096 if ( fswap(cursor->_item, cursor->_prev->_item) )
2097 swapResult++;
2098 // update swap-flag and lowerborder
2099 swapped = true;
2100 og = cursor;
2101 // swap de items van de nodes
2102 swap = cursor->_item;
2103 cursor->_item = cursor->_prev->_item;
2104 cursor->_prev->_item = swap;
2105 }
2106 cursor=cursor->_prev;
2107 }// end brickslag
2108 ogold = og;
2109 }// end while(ongesorteerd)
2110
2111 return swapResult;
2112 }
2113
2114 /*!
2115 sort all items in the list according to the compare function.
2116
2117 \note
2118 There are no restrictions on the internal decision in the compare function when to return -1,0,1.
2119
2120 \note
2121 For the mergesort function the objects will be swapped when the return value is -1.
2122
2123 \note
2124 \verbatim
2125
2126 fcmp (function, fcmp)
2127
2128 Declaration: int (*fcmp) (Dtype,Dtype)
2129
2130 compare function pointer, the function takes two objects in the list. It must return -1, 0, 1, to sort the list in upgoing
2131 order the function should return:
2132
2133 -1 is returned if the first object is bigger then the second.
2134 0 is returned if the objects are equal.
2135 1 is returned if the first object is smaller then the second.
2136
2137 To sort the list in downgoing order:
2138
2139 1 is returned if the first object is bigger then the second.
2140 0 is returned if the objects are equal.
2141 -1 is returned if the first object is smaller then the second.
2142 \endverbatim
2143
2144 !tcarg: class | Dtype | list item object
2145 \par example
2146 sort the list in upgoing order using mergesort and the function numbersorter|
2147 \code
2148 int numbersorter(int a,int b)
2149 {
2150 if(a < b) return(1);
2151 else
2152 if(a == b) return(0);
2153 return(-1);
2154 }
2155
2156 DL_List <int> _intlist; #create a list of integers
2157 DL_Iter<int>* a_listiter=new DL_Iter<int>(&_intlist);
2158
2159 a_listiter->insend(2345);
2160 a_listiter->insend(3456);
2161 a_listiter->insend(1234);
2162 a_listiter->mergesort(numbersorter);
2163 \endcode
2164 */
2165 template <class Dtype>
mergesort(int (* fcmp)(Dtype,Dtype))2166 void DL_Iter<Dtype>::mergesort(int (*fcmp) (Dtype, Dtype))
2167 {
2168 if (_current==0)
2169 Error("mergesort()",NO_LIST);
2170 mergesort_rec(fcmp, RT, NB);
2171 }
2172
2173
2174 template <class Dtype>
mergesort_rec(int (* fcmp)(Dtype,Dtype),DL_Node<Dtype> * RT1,int n1)2175 void DL_Iter<Dtype>::mergesort_rec(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1, int n1)
2176 {
2177 if (n1 > 1) //one element left then stop
2178 {
2179 DL_Node<Dtype> RT2;
2180 int n2;
2181
2182 RT2._prev=RT1->_prev;
2183 RT2._next=RT1->_next;
2184 // goto middle
2185 n2=n1;n1>>=1;n2-=n1;
2186 for (int i=0; i <n1;i++)
2187 RT2._next=RT2._next->_next;
2188
2189 //RT2 is at half
2190 RT1->_prev->_next=&RT2;
2191 RT2._prev=RT1->_prev;
2192 RT1->_prev=RT2._next->_prev;
2193 RT2._next->_prev->_next=RT1;
2194
2195 mergesort_rec(fcmp,RT1,n1);
2196 mergesort_rec(fcmp,&RT2,n2);
2197 mergetwo(fcmp,RT1,&RT2);
2198 }
2199 }
2200
2201 template <class Dtype>
mergetwo(int (* fcmp)(Dtype,Dtype),DL_Node<Dtype> * RT1,DL_Node<Dtype> * RT2)2202 void DL_Iter<Dtype>::mergetwo(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1,DL_Node<Dtype> *RT2)
2203 {
2204 DL_Node<Dtype> *c,*a,*b;
2205 a=RT1->_next;b=RT2->_next;
2206 c=RT1;
2207 do
2208 {
2209 if (fcmp(a->_item , b->_item) > -1)
2210 { c->_next=a;a->_prev=c;c=a;a=a->_next;}
2211 else
2212 { c->_next=b;b->_prev=c;c=b;b=b->_next;}
2213 if (a == RT1)
2214 { c->_next=
2215 b;b->_prev=c; //connect list b to the list made sofar
2216 RT1->_prev=RT2->_prev;
2217 RT1->_prev->_next=RT1;
2218 break;
2219 }
2220 if (b == RT2)
2221 { c->_next=a;a->_prev=c; //connect list a to the list made sofar
2222 break;
2223 }
2224 }
2225 while (true);
2226 }
2227
2228
2229 //=======================================================================
2230 // implementation class DL_StackIter
2231 //=======================================================================
2232 /*! \class DL_StackIter
2233 * template class DL_StackIter class for stack iterator on DL_List
2234 * template stack iterator for any list/node type \n
2235 * This class is the base class to attach/instantiate a stack iterator on a double linked list
2236 * DL_List. The stack iterator is used to push and pop objects
2237 * to and from the beginning of a list.
2238 * class | Dtype | Object for traversing a DL_List of the same Dtype
2239 *\par Example
2240 How to work with a stack iterator for a list of type integer \n
2241 to push a and b, pop a into list and remove_all directly using a stack iterator
2242 *
2243 *\code DL_List<int>* a_list = new DL_List<int>();# declaration and allocation
2244 *
2245 * int a=123;
2246 *
2247 * int b=345;
2248 *
2249 * {
2250 *
2251 * DL_StackIter<int>* a_listiter=new DL_StackIter<int>(a_list);
2252 *
2253 * a_listiter->push(a)
2254 *
2255 * a_listiter->push(b)
2256 *
2257 * a_listiter->pop()
2258 *
2259 * a_listiter->remove_all()
2260 *
2261 * } //to destruct the iterator before the list is deleted
2262 *
2263 * delete a_list; #delete it (must have no iterators attached to it)
2264 *\endcode
2265 */
2266
2267 // constructor
2268 template <class Dtype>
DL_StackIter(DL_List<Dtype> * newlist)2269 DL_StackIter<Dtype>::DL_StackIter(DL_List<Dtype> *newlist)
2270 :DL_Iter<Dtype>(newlist) // initialiseer BaseIter
2271 {}
2272
2273
2274 // destructor
2275 template <class Dtype>
~DL_StackIter()2276 DL_StackIter<Dtype>::~DL_StackIter()
2277 {
2278 }
2279
2280 // plaats nieuw item op stack
2281 template <class Dtype>
push(Dtype newitem)2282 void DL_StackIter<Dtype>::push(Dtype newitem)
2283 {
2284 DL_Iter<Dtype>::insbegin(newitem);
2285 }
2286 // remove current item
2287 template <class Dtype>
remove_all()2288 void DL_StackIter<Dtype>::remove_all()
2289 {
2290 DL_Iter<Dtype>::remove_all();
2291 }
2292
2293 // is stack leeg?
2294 template <class Dtype>
empty()2295 bool DL_StackIter<Dtype>::empty()
2296 {
2297 return DL_Iter<Dtype>::empty();
2298 }
2299
2300 // aantal items op stack
2301 template <class Dtype>
count()2302 int DL_StackIter<Dtype>::count()
2303 {
2304 return DL_Iter<Dtype>::count();
2305 }
2306
2307 // haal bovenste item van stack
2308 template <class Dtype>
pop()2309 Dtype DL_StackIter<Dtype>::pop()
2310 {
2311 if(DL_Iter<Dtype>::empty())
2312 this->Error("pop()",EMPTY);
2313
2314 DL_Iter<Dtype>::tohead();
2315 Dtype temp = DL_Iter<Dtype>::item();
2316 DL_Iter<Dtype>::removehead();
2317 return temp;
2318 }
2319
2320 //=======================================================================
2321 // implementation class DL_SortIter
2322 //=======================================================================
2323 /*! \class DL_SortIter
2324 * template class DL_SortIter
2325 * class for sort iterator on DL_List
2326 * template sort iterator for any list/node type
2327 * This class is a derived class to attach/instantiate a sorted iterator on a double linked list
2328 * DL_List. The iterator is used to insert items in sorted order into a list.
2329 //!tcarg: class | Dtype | Object for traversing a DL_List of the same Dtype
2330 */
2331
2332 // constructor
2333 template <class DType>
DL_SortIter(DL_List<DType> * nw_list,int (* new_func)(DType,DType))2334 DL_SortIter<DType>::DL_SortIter(DL_List<DType>* nw_list, int (*new_func)(DType ,DType ))
2335 :DL_Iter<DType>(nw_list), comparef(new_func)
2336 {}
2337
2338 // destructor
2339 template <class DType>
~DL_SortIter()2340 DL_SortIter<DType>::~DL_SortIter()
2341 {}
2342
2343 // general function to insert item
2344 template <class DType>
insert(DType new_item)2345 void DL_SortIter<DType>::insert(DType new_item)
2346 {
2347 DL_Node<DType>* cursor=this->_current; //can be 0 if empty //node is a temporary cursor
2348
2349 // if list is empty directly insert
2350 if (DL_Iter<DType>::empty())
2351 {
2352 DL_Iter<DType>::insend(new_item);
2353 }
2354 else
2355 {
2356 // put new item left of item
2357 DL_Iter<DType>::tohead();
2358 while(!DL_Iter<DType>::hitroot())
2359 {
2360 if (!(*comparef)(DL_Iter<DType>::item(), new_item))
2361 break;
2362 DL_Iter<DType>::next();
2363 }
2364
2365 //if at root
2366 DL_Iter<DType>::insbefore(new_item);
2367 }
2368
2369 this->_current=cursor; //set to old cursor position
2370 }
2371
2372 template <class DType>
sortitererror()2373 void DL_SortIter<DType>::sortitererror()
2374 {
2375 this->Error("sortiter()",NOT_ALLOW);
2376 }
2377
2378
2379