ARB
SoTl.hxx
Go to the documentation of this file.
1 #ifndef SOTL_HXX
2 #define SOTL_HXX
3 
4 // SOTL = SelfOrganising TemplateList
5 
6 /*
7  Copyright by Andrej Konkow 1996
8 
9  User has to take care by his own on calling update_pos_no, when inserting
10  elements somewhere in the middle. If elements are inserted only at the last
11  position the pos is incremented correctly. By default the first element in the list
12  has position 1.
13  no_of_members is counted and updated automatically.
14 
15  Caution:
16  This List by default is NOT a selforganizing list. This means that by default an element
17  that is being asked for is NOT put at front of the list. This only will be done while the
18  flag sotl is set to false(this is default). You can change this flag with the methods
19  sotl_list() (sets the flag true) and no_sotl_list() (sets the flag false).
20 
21  The List is created by
22  List<Typename> *instance_variable = new List<Typename>(sotl_flag);
23  ^^^^^^^
24  sotl_flag is optional.
25  For a normal double linked list
26  this flag has not to be set. For
27  a selforganizing list : true
28 
29  Afterwards the elements can be inserted.
30  The User of this list has to delete the elements which are inserted to the list by
31  its own.
32  The User has only have to work with the List class.
33 */
34 
35 #ifndef _GLIBCXX_CSTDIO
36 #include <cstdio>
37 #endif
38 #ifndef ARBTOOLS_H
39 #include <arbtools.h>
40 #endif
41 
42 typedef unsigned long positiontype;
43 
44 #define RELATION_GREATER 1
45 #define RELATION_LESS 2
46 
47 
48 template <class Type>
49 class list_elem : virtual Noncopyable {
50  positiontype pos;
51 
52 public:
56  bool isolate_list_elem(); // set next and prev links to NULp
57  // true if isolation has taken place,
58  // else false(for example if we're the
59  // only element
60 
61  Type *get_elem() { return elem; };
62  void set_elem(Type *el) { elem = el; };
63  positiontype get_pos() { return pos; };
64  void set_pos(positiontype p) { pos = p; };
65  list_elem<Type> *get_next() { return next; };
66  void set_next(list_elem<Type> *n) { next = n; };
67  list_elem<Type> *get_prev() { return prev; };
68  void set_prev(list_elem<Type> *p) { prev = p; };
69 
70  list_elem();
71  list_elem(Type *el);
72  ~list_elem();
73 };
74 
75 
76 template <class Type>
77 class List : virtual Noncopyable {
78  list_elem<Type> *first;
79  list_elem<Type> *last;
80  list_elem<Type> *last_asked_list_elem;
81  list_elem<Type> *remembered_elem;
82 
83  positiontype no_of_members;
84  bool sotl;
85 
86 
87  list_elem<Type> *get_list_elem_with_member (Type *object);
88  list_elem<Type> *get_list_elem_at_pos (positiontype pos);
89  list_elem<Type> *get_list_elem_at_pos_simple (positiontype pos);
90 public:
91  // general List functions
92 
93 
94  // only use these functions if you know what you are doing !!! BEGINNING
95  list_elem<Type> *get_first_list_elem() { return first; }; // do not use !!!
96  list_elem<Type> *get_last_list_elem() { return last; }; // do not use !!!
97  list_elem<Type> *get_current_list_elem() { return last_asked_list_elem; }; // do not use !!!
98  void remember_current() { remembered_elem = last_asked_list_elem; };
99  void set_current_ARC(list_elem<Type> *t); // ARC = and remember current
100  void set_remembered_as_current_ARC(); // ARC = and remember current
101  // only use these functions if you know what you are doing !!! END
102 
103  void sotl_list() { sotl = true; };
104  void no_sotl_list() { sotl = false; };
105  positiontype get_no_of_members() { return no_of_members; };
106 
108  positiontype insert_as_last (Type *object); // returns pos_no
111  positiontype insert (Type *object); // returns pos_no
112  Type *get_first ();
113  Type *get_last ();
114  Type *get_prev ();
115  Type *get_next ();
116 
117  void remove_member_from_list (Type *object); // object won't be deleted
118  void remove_first();
119  void remove_last();
120  List<Type> *duplicate_list (Type *object); // the list is duplicated
121  // from the element given til the end.
122  // For duplicating the whole list
123  // object = get_first(). Only the list is
124  // duplicated, not the elems. Caution:
125  // In a sotl list the asked element is put
126  // to the front. So first make a no_sotl_list()
127  // ask and duplicate the list, and then make a
128  // sotl_list() again.
129 
130  bool exchange_members (Type *ex, Type *change);
131 
132  /* following functions only make sense if our list is sorted by the address of
133  our item inserted to the list.
134  Caution:
135  The list is only sorted if it's NOT a sotl list. So take care to
136  create or set it to a no_sotl_list().
137  */
138 
139  // Comment to insert_sorted_by_address_of_object:
140  // The function returns the no_of_members in the list.
141  // By default an object(the meaning here is that one object equals another,
142  // if the address of both objects matches) can be inserted to the list
143  // several times. If there is the need to insert an object only once
144  // in the list, the flag duplicates has to be set to false.
145  // Finally the relation has to be set, by which the list is sorted.
146  // The possibilities are : RELATION_GREATER and RELATION_LESS
148  int relation=RELATION_LESS,
149  bool duplicates=true);
150 
151  // Comment to sort_list_join:
152  // if an object found in List l is found in this list it won't be inserted
153  // a second time.
154  void sort_list_join (List<Type> *l,
155  int relation=RELATION_LESS); // Lists given as parameter
156  // won't be affected
157  // Comment to sort_list_subtract:
158  // this function call only makes sense if the same element can be found
159  // in both lists. The flag relation tells the method how this list(not list l)
160  // is sorted. Both lists have to be sorted by the same relation.
162  int relation=RELATION_LESS);
163 
164 
165 
166  positiontype insert_at_pos_simple (Type *object, positiontype pos); // returns pos inserted to
167  // doesn't refer to get_pos()
169 
170  /*
171  Following functions only make sense if the user takes care of the list as
172  a numbered list.
173  */
174  // Comment to insert_at_pos :
175  // user does not have to call update_pos_no after insert_at_pos()
176  positiontype insert_at_pos (Type *object, positiontype pos); // returns pos inserted to
179  bool remove_pos_from_list (positiontype pos); // element won't be deleted
180  bool exchange_positions (positiontype ex, positiontype change); // exchange elems in list
181  void update_pos_no(list_elem<Type> *elem, positiontype nr); // updates no from
182  // the given elem with nr til last
183  void update_pos_no(); // updates pos number from first to last
184 
185  List(bool so=false);
186  ~List();
187 };
188 
189 // ------------------
190 // list_elem
191 
192 template <class Type> inline list_elem<Type>::list_elem() {
193  pos = 0;
194  next = NULp;
195  prev = NULp;
196  elem = NULp;
197 }
198 
199 template <class Type> inline list_elem<Type>::list_elem(Type *el) {
200  pos = 0;
201  next = NULp;
202  prev = NULp;
203  elem = el;
204 }
205 
206 template <class Type> inline list_elem<Type>::~list_elem() {
207  isolate_list_elem();
208 }
209 
210 template <class Type> inline bool list_elem<Type>::isolate_list_elem() {
211  if (prev && next) { // somewhere in the middle
212  prev->next = next;
213  next->prev = prev;
214  next = NULp;
215  prev = NULp;
216  }
217  else if (prev) { // we're the last
218  prev->next = NULp;
219  prev = NULp;
220  }
221  else if (next) { // we're the first
222  next->prev = NULp;
223  next = NULp;
224  }
225  else {
226  return false;
227  }
228  return true;
229 }
230 
231 // -------------
232 // List
233 
234 template <class Type> inline List<Type>::List(bool so) {
235  first = last = last_asked_list_elem = remembered_elem = NULp;
236  no_of_members = 0;
237  sotl = so;
238 }
239 
240 template <class Type> inline List<Type>::~List() {
241  list_elem<Type> *elem, *help;
242 
243  elem = first;
244  while (elem) { // delete every object in list
245  help = elem->next;
246  delete elem;
247  elem = help;
248  }
249 }
250 
251 template <class Type> inline void List<Type>::set_current_ARC(list_elem<Type> *t) { // ARC = and remember current
252  remembered_elem = last_asked_list_elem;
253  last_asked_list_elem = t;
254 }
255 
256 template <class Type> inline void List<Type>::set_remembered_as_current_ARC() { // ARC = and remember current
257  list_elem<Type> *mark;
258 
259  mark = last_asked_list_elem;
260  last_asked_list_elem = remembered_elem;
261  remembered_elem = mark;
262 }
263 
264 template <class Type> inline list_elem<Type> *List<Type>::get_list_elem_with_member(Type *object) {
265  list_elem<Type> *loc_elem;
266 
267  loc_elem = first;
268  while (loc_elem && loc_elem->elem!=object) {
269  loc_elem = loc_elem->next;
270  }
271 
272  return loc_elem;
273 }
274 
275 template <class Type> inline list_elem<Type> *List<Type>::get_list_elem_at_pos(positiontype pos) {
276  list_elem<Type> *elem;
277 
278  if (pos < 1 || pos > no_of_members)
279  return NULp;
280 
281  if (! last_asked_list_elem) {
282  if (pos > no_of_members/2) {
283  elem = last;
284  while (elem && elem->get_pos() != pos)
285  elem = elem->get_prev();
286  }
287  else {
288  elem = first;
289  while (elem && elem->get_pos() != pos)
290  elem = elem->next;
291  }
292  }
293  else {
294  elem = last_asked_list_elem;
295 
296  if (pos >= last_asked_list_elem->get_pos()) {
297  while (elem && elem->get_pos() != pos)
298  elem = elem->next;
299  }
300  else { // pos < last_asked_list_elem->pos
301  while (elem && elem->get_pos() != pos)
302  elem = elem->get_prev();
303  }
304  }
305 
306  return elem;
307 }
308 
309 template <class Type> inline list_elem<Type> *List<Type>::get_list_elem_at_pos_simple(positiontype pos) {
310  list_elem<Type> *elem;
311  positiontype counter = 1;
312 
313  if (pos < 1 || pos > no_of_members)
314  return NULp;
315 
316  if (pos > no_of_members/2) {
317  elem = last;
318  counter = no_of_members;
319  while (elem && counter != pos) {
320  elem = elem->get_prev();
321  counter --;
322  }
323  }
324  else {
325  elem = first;
326  while (elem && counter != pos) {
327  elem = elem->next;
328  counter ++;
329  }
330  }
331 
332  return elem;
333 }
334 
335 template <class Type> inline Type *List<Type>::get_first() {
336  if (first) {
337  last_asked_list_elem = first;
338  return first->elem;
339  }
340  else
341  return NULp;
342 }
343 
344 template <class Type> inline Type *List<Type>::get_last() {
345  if (last && ! sotl) { // behavior of a normal linked list
346  last_asked_list_elem = last;
347  return last->elem;
348  }
349  else if (last && sotl) {
350  last_asked_list_elem = last->get_prev();
351  insert_as_first(last->elem);
352  remove_last();
353  return first->elem;
354  }
355  else
356  return NULp;
357 }
358 
359 template <class Type> inline Type *List<Type>::get_prev() {
360  Type *result = NULp;
361  list_elem<Type> *mark_prev;
362 
363  if (last_asked_list_elem) {
364 
365  if (!sotl) { // behavior of a normal linked list
366  last_asked_list_elem = last_asked_list_elem->get_prev();
367 
368  if (last_asked_list_elem)
369  result = last_asked_list_elem->elem;
370  }
371  else if (sotl) {
372  if (last_asked_list_elem) {
373  result = last_asked_list_elem->elem;
374  mark_prev = last_asked_list_elem->get_prev();
375 
376  remove_member_from_list(result);
377  insert_as_first(result);
378  last_asked_list_elem = mark_prev;
379  }
380  }
381  }
382  return result;
383 }
384 
385 template <class Type> inline Type *List<Type>::get_next() {
386  Type *result = NULp;
387  list_elem<Type> *mark_next;
388 
389  if (last_asked_list_elem) {
390 
391  if (!sotl) { // behavior of a normal linked list
392  last_asked_list_elem = last_asked_list_elem->next;
393 
394  if (last_asked_list_elem)
395  result = last_asked_list_elem->elem;
396  }
397  else if (sotl) {
398  if (last_asked_list_elem) {
399  result = last_asked_list_elem->elem;
400  mark_next = last_asked_list_elem->next;
401 
402  remove_member_from_list(result);
403  insert_as_first(result);
404  last_asked_list_elem = mark_next;
405  }
406  }
407  }
408 
409  return result;
410 }
411 
412 
413 template <class Type> inline positiontype List<Type>::insert_as_first(Type *object) {
415 
416  if (! first) { // create first element in list
417  first = new list_elem<Type>(object);
418  first->set_pos(1);
419  last = first;
420  }
421  else {
422  help = new list_elem<Type>(object);
423  help->set_pos(1); // update by USER !!!
424  help->set_next(first);
425  first->set_prev(help);
426  first = help;
427  }
428 
429  no_of_members ++;
430  return 1;
431 }
432 
433 template <class Type> inline positiontype List<Type>::insert_as_last(Type *object) {
435 
436  if (! first) { // create first element in list
437  first = new list_elem<Type>(object);
438  first->set_pos(1);
439  last = first;
440  }
441  else {
442  help = new list_elem<Type>(object);
443  help->set_pos(no_of_members+1);
444  help->set_prev(last);
445  last->set_next(help);
446  last = help;
447  }
448 
449  no_of_members ++;
450  return no_of_members;
451 }
452 
453 template <class Type> inline positiontype List<Type>::insert_after_current(Type *object) {
455  positiontype result = 0;
456 
457  if (last_asked_list_elem) {
458 
459  if (!last_asked_list_elem->get_next()) {
460  result = insert_as_last(object);
461  }
462  else {
463  help = new list_elem<Type>(object);
464  help->set_pos(last_asked_list_elem->get_pos() + 1);
465  help->set_prev(last_asked_list_elem);
466  help->set_next(last_asked_list_elem->get_next());
467  help->get_next()->set_prev(help);
468  last_asked_list_elem->set_next(help);
469  last_asked_list_elem = help;
470 
471  no_of_members ++;
472  result = no_of_members;
473  }
474  }
475  return result;
476 }
477 
478 template <class Type> inline positiontype List<Type>::insert_before_current(Type *object) {
480  positiontype result = 0;
481  if (last_asked_list_elem) {
482 
483  if (!last_asked_list_elem->get_prev()) {
484  result = insert_as_first(object);
485  }
486  else {
487  help = new list_elem<Type>(object);
488  help->set_pos(last_asked_list_elem->get_pos() - 1);
489  help->set_next(last_asked_list_elem);
490  help->set_prev(last_asked_list_elem->get_prev());
491  help->get_prev()->set_next(help);
492  last_asked_list_elem->set_prev(help);
493  last_asked_list_elem = help;
494 
495  no_of_members ++;
496  result = no_of_members;
497  }
498  }
499  return result;
500 }
501 
502 template <class Type> inline positiontype List<Type>::insert(Type *object) {
503  return insert_as_first(object);
504 }
505 
506 template <class Type> inline positiontype List<Type>::insert_at_pos_simple(Type *object, positiontype temp_pos) {
507  // returns pos inserted to
508  list_elem<Type> *elem,
509  *new_elem;
510 
511  if (temp_pos<=1) {
512  insert_as_first(object);
513  return 1;
514  }
515  else if (temp_pos>no_of_members) {
516  insert_as_last(object);
517  return no_of_members;
518  }
519  else {
520  elem = get_list_elem_at_pos_simple(temp_pos);
521 
522  new_elem = new list_elem<Type>;
523  new_elem->elem = object;
524  new_elem->set_pos(temp_pos);
525  new_elem->prev = elem->prev;
526  new_elem->next = elem;
527  elem->prev->next = new_elem;
528  elem->prev = new_elem;
529 
530  no_of_members ++;
531  return temp_pos;
532  }
533 }
534 
535 template <class Type> inline void List<Type>::remove_member_from_list(Type *object) {
536  list_elem<Type> *loc_elem;
537 
538  if (last_asked_list_elem && last_asked_list_elem->elem==object) {
539  if (! last_asked_list_elem->next) // we're the last
540  last = last_asked_list_elem->get_prev();
541 
542  if (! last_asked_list_elem->get_prev()) // we're the first
543  first = last_asked_list_elem->next;
544 
545  delete last_asked_list_elem;
546 
547  if (no_of_members == 1)
548  first = last = NULp;
549 
550  last_asked_list_elem = NULp;
551  }
552  else {
553  if (last_asked_list_elem &&
554  last_asked_list_elem->next &&
555  last_asked_list_elem->next->elem == object)
556  {
557  loc_elem = last_asked_list_elem->next;
558  }
559  else if (last_asked_list_elem &&
560  last_asked_list_elem->get_prev() &&
561  last_asked_list_elem->get_prev()->elem == object)
562  {
563  loc_elem = last_asked_list_elem->get_prev();
564  }
565  else {
566  loc_elem = get_list_elem_with_member(object);
567  }
568 
569  if (! loc_elem)
570  return;
571 
572  if (! loc_elem->next) // we're the last
573  last = loc_elem->get_prev();
574 
575  if (! loc_elem->get_prev()) // we're the first
576  first = loc_elem->next;
577 
578  delete loc_elem;
579  }
580 
581  no_of_members --;
582 }
583 
584 template <class Type> inline void List<Type>::remove_first() {
585  list_elem<Type> *new_first;
586 
587  if (no_of_members <= 1) { // case 0 or 1
588  delete first;
589  first = last = last_asked_list_elem = NULp;
590  no_of_members = 0;
591  }
592  else {
593  new_first = first->next;
594  delete first;
595  first = new_first;
596  no_of_members --;
597  }
598 }
599 
600 template <class Type> inline void List<Type>::remove_last() {
601  list_elem<Type> *new_last;
602 
603  if (no_of_members <= 1) { // case 0 or 1
604  delete last;
605  first = last = last_asked_list_elem = NULp;
606  no_of_members = 0;
607  }
608  else {
609  new_last = last->get_prev();
610  delete last;
611  last = new_last;
612  no_of_members --;
613  }
614 }
615 
617  int relation,
618  bool duplicates) // falls object schon vorhanden, dann
619 {
621  *l_help;
622 
623  if (! first) { // create first element in list
624  first = new list_elem<Type>(object);
625  first->set_pos(1);
626  last = first;
627  }
628  else {
629  if (relation == RELATION_GREATER) { // search for a place to insert to objects which are created later,
630  l_help = first; // have a greater address !!!
631  while (l_help && object < l_help->elem)
632  l_help = l_help->next;
633  }
634  else { // RELATION_LESS
635  l_help = last;
636  while (l_help && object < l_help->elem)
637  l_help = l_help->get_prev();
638  }
639 
640  if (l_help && object == l_help->elem && ! duplicates) // Element already is in the list
641  return no_of_members;
642 
643  help = new list_elem<Type>(object); // generate new element
644 
645  if (! l_help) { // new element in front/at end
646  if (relation == RELATION_GREATER) {
647  last->set_next(help);
648  help->set_prev(last);
649  last = help;
650  }
651  else { // RELATION_LESS
652  first->set_prev(help);
653  help->set_next(first);
654  first = help;
655  }
656  }
657  else {
658  if (relation == RELATION_GREATER) {
659  if (first == l_help)
660  first = help;
661 
662  help->set_next(l_help);
663  help->set_prev(l_help->get_prev());
664  }
665  else { // RELATION_LESS
666  if (last == l_help)
667  last = help;
668 
669  help->set_prev(l_help);
670  help->set_next(l_help->next);
671  }
672 
673  if (help->next)
674  help->next->set_prev(help);
675 
676  if (help->get_prev())
677  help->get_prev()->set_next(help);
678  }
679 
680  }
681 
682  no_of_members ++;
683 
684  return no_of_members;
685 }
686 
687 template <class Type> inline void List<Type>::sort_list_join(List<Type> *l, int relation) {
688  list_elem<Type> *this_list = first,
689  *join_list,
690  *new_elem;
691 
692  if (! l || ! l->get_no_of_members())
693  return;
694 
695  join_list = l->get_first_list_elem();
696 
697  while (this_list && join_list) {
698  if (this_list->elem == join_list->elem) {
699  this_list = this_list->next;
700  join_list = join_list->next;
701  }
702  else {
703  if ((relation == RELATION_GREATER && this_list->elem > join_list->elem) ||
704  (relation == RELATION_LESS && this_list->elem < join_list->elem))
705  {
706  this_list = this_list->next;
707  }
708  else
709  {
710  new_elem = new list_elem<Type>(join_list->elem);
711  new_elem->set_prev(this_list->get_prev());
712  new_elem->set_next(this_list);
713  this_list->set_prev(new_elem);
714 
715  if (new_elem->get_prev())
716  new_elem->get_prev()->set_next(new_elem);
717  else
718  first = new_elem;
719 
720  join_list = join_list->next;
721 
722  no_of_members ++;
723  }
724  }
725  }
726 
727  if (! join_list || (!this_list && !join_list))
728  return;
729 
730  if (!this_list) {
731  while (join_list) {
732  new_elem = new list_elem<Type>(join_list->elem);
733  new_elem->set_prev(last);
734 
735  if (last)
736  last->set_next(new_elem);
737 
738  if (!first)
739  first = new_elem;
740 
741  last = new_elem;
742  no_of_members ++;
743  join_list = join_list->next;
744  }
745  }
746 }
747 
748 template <class Type> inline void List<Type>::sort_list_subtract(List<Type> *l, int relation) {
749  list_elem<Type> *this_list = first,
750  *join_list = l->get_first_list_elem(),
751  *mark;
752 
753  while (this_list && join_list) {
754  if ((relation == RELATION_GREATER && this_list->elem > join_list->elem) ||
755  (relation == RELATION_LESS && this_list->elem < join_list->elem))
756  {
757  this_list = this_list->next;
758  }
759  else if ((relation == RELATION_GREATER && this_list->elem < join_list->elem) ||
760  (relation == RELATION_LESS && this_list->elem > join_list->elem))
761  {
762  join_list = join_list->next;
763  }
764  else if (this_list->elem == join_list->elem) { // same element => delete from this_list
765  if (this_list == first)
766  first = this_list->next;
767 
768  if (this_list == last)
769  last = this_list->get_prev();
770 
771  mark = this_list->next;
772  delete this_list;
773  this_list = mark;
774 
775  join_list = join_list->next;
776  no_of_members --;
777 
778  if (! no_of_members) {
779  last_asked_list_elem = NULp;
780  return;
781  }
782  }
783  }
784 }
785 
786 template <class Type> inline List<Type> *List<Type>::duplicate_list(Type *object) {
787  list_elem<Type> *help_l = first;
788  List<Type> *new_list = NULp;
789 
790  if (last_asked_list_elem->elem == object)
791  help_l = last_asked_list_elem;
792  else
793  help_l = get_list_elem_with_member(object);
794 
795  if (help_l)
796  new_list = new List<Type>;
797 
798  while (help_l) {
799  new_list->insert_as_last(help_l->elem);
800 
801  help_l = help_l->next;
802  }
803 
804  return new_list;
805 }
806 
807 template <class Type> inline void List<Type>::update_pos_no(list_elem<Type> *elem, positiontype nr) {
808  list_elem<Type> *mark;
809 
810  if (!elem)
811  return;
812 
813  elem->set_pos(nr++);
814  mark = elem->next;
815  while (mark) {
816  mark->set_pos(nr++);
817  mark = mark->next;
818  }
819 }
820 
821 template <class Type> inline void List<Type>::update_pos_no() {
822  update_pos_no(first, 1);
823 }
824 
825 template <class Type> inline bool List<Type>::exchange_members(Type *ex, Type *change) {
826  list_elem<Type> *one, *two;
827  bool result = false;
828  while (1) {
829  if (!ex || !change)
830  break;
831 
832  if (last_asked_list_elem && last_asked_list_elem->elem == ex)
833  one = last_asked_list_elem;
834  else
835  one = get_list_elem_with_member(ex);
836 
837  if (! one)
838  break;
839 
840  if (last_asked_list_elem && last_asked_list_elem->elem == change)
841  two = last_asked_list_elem;
842  else
843  two = get_list_elem_with_member(change);
844 
845  if (!two)
846  break;
847 
848  one->set_elem(change);
849  two->set_elem(ex);
850  result = true;
851  break;
852  }
853 
854  return result;
855 }
856 
857 template <class Type> inline bool List<Type>::exchange_positions(positiontype ex, positiontype change) {
858  list_elem<Type> *one, *two;
859  Type *dummy;
860  bool result = false;
861  while (1) {
862  if (ex < 1 || ex > no_of_members ||
863  change < 1 || change > no_of_members)
864  break;
865 
866  one = get_list_elem_at_pos(ex);
867  if (! one)
868  break;
869 
870  two = get_list_elem_at_pos(change);
871  if (!two)
872  break;
873 
874  dummy = one->elem;
875  one->elem = two->elem;
876  two->elem = dummy;
877  result = true;
878  break;
879  }
880  return result;
881 }
882 
883 template <class Type> inline positiontype List<Type>::get_pos_of_member(Type *object) {
884  list_elem<Type> *elem;
885 
886  if (!object)
887  return 0;
888 
889  if (last_asked_list_elem && last_asked_list_elem->elem == object) {
890  return last_asked_list_elem->get_pos();
891  }
892  else {
893  elem = first;
894  while (elem && elem->elem != object)
895  elem = elem->next;
896 
897  if (elem)
898  return elem->get_pos();
899  else
900  return 0;
901  }
902 }
903 
904 
905 template <class Type> inline positiontype List<Type>::insert_at_pos(Type *object, positiontype pos) {
906  // returns pos inserted to
907  list_elem<Type> *elem,
908  *new_elem;
910 
911  elem = get_list_elem_at_pos(pos);
912 
913  if (! elem) {
914  insert_as_last(object);
915  result = last->get_pos();
916  }
917  else {
918  new_elem = new list_elem<Type>(object);
919  new_elem->set_prev(elem->get_prev());
920  new_elem->set_next(elem);
921 
922  if (elem->get_prev())
923  elem->get_prev()->set_next(new_elem);
924 
925  elem->set_prev(new_elem);
926 
927  if (first == elem)
928  first = new_elem;
929 
930  update_pos_no (new_elem, pos);
931 
932  result = pos;
933  }
934  return result;
935 }
936 
937 template <class Type> inline Type *List<Type>::get_member_at_pos(positiontype pos) {
938  list_elem<Type> *elem;
939 
940  elem = get_list_elem_at_pos(pos);
941 
942  if (elem) {
943  last_asked_list_elem = elem;
944  return elem->elem;
945  }
946  else
947  return NULp;
948 }
949 
950 template <class Type> inline Type *List<Type>::get_member_at_pos_simple(positiontype pos) {
951  list_elem<Type> *elem;
952 
953  elem = get_list_elem_at_pos_simple(pos);
954 
955  if (elem) {
956  last_asked_list_elem = elem;
957  return elem->elem;
958  }
959  else
960  return NULp;
961 }
962 
963 template <class Type> inline bool List<Type>::remove_pos_from_list(positiontype pos) {
964  list_elem<Type> *loc_elem;
965  bool result = false;
966  while (1) {
967  if (pos < 1 || pos > no_of_members)
968  break;
969 
970  loc_elem = last_asked_list_elem;
971 
972  if (loc_elem && loc_elem->get_pos() == pos)
973  last_asked_list_elem = NULp;
974  else {
975  if (! (loc_elem = get_list_elem_at_pos(pos)))
976  break;
977  }
978 
979  if (last == loc_elem)
980  last = last->get_prev();
981 
982  if (first == loc_elem)
983 
984 
985  first = first->next;
986 
987  delete loc_elem;
988  no_of_members --;
989  result = true;
990  break;
991  }
992 
993  return result;
994 }
995 
996 #else
997 #error SoTl.hxx included twice
998 #endif
void set_pos(positiontype p)
Definition: SoTl.hxx:64
Type * get_elem()
Definition: SoTl.hxx:61
void set_prev(list_elem< Type > *p)
Definition: SoTl.hxx:68
string result
positiontype insert_as_last(Type *object)
Definition: SoTl.hxx:433
void sotl_list()
Definition: SoTl.hxx:103
positiontype get_pos()
Definition: SoTl.hxx:63
list_elem()
Definition: SoTl.hxx:192
positiontype insert_before_current(Type *object)
Definition: SoTl.hxx:478
void set_current_ARC(list_elem< Type > *t)
Definition: SoTl.hxx:251
#define RELATION_GREATER
Definition: SoTl.hxx:44
static void help()
list_elem< Type > * prev
Definition: SoTl.hxx:54
positiontype get_no_of_members()
Definition: SoTl.hxx:105
~list_elem()
Definition: SoTl.hxx:206
positiontype get_pos_of_member(Type *object)
Definition: SoTl.hxx:883
list_elem< Type > * get_current_list_elem()
Definition: SoTl.hxx:97
Type * get_last()
Definition: SoTl.hxx:344
positiontype insert_at_pos_simple(Type *object, positiontype pos)
Definition: SoTl.hxx:506
void remove_first()
Definition: SoTl.hxx:584
bool exchange_members(Type *ex, Type *change)
Definition: SoTl.hxx:825
void sort_list_subtract(List< Type > *l, int relation=RELATION_LESS)
Definition: SoTl.hxx:748
list_elem< Type > * get_next()
Definition: SoTl.hxx:65
Type * elem
Definition: SoTl.hxx:55
list_elem< Type > * next
Definition: SoTl.hxx:53
List(bool so=false)
Definition: SoTl.hxx:234
Type * get_next()
Definition: SoTl.hxx:385
list_elem< Type > * get_first_list_elem()
Definition: SoTl.hxx:95
List< Type > * duplicate_list(Type *object)
Definition: SoTl.hxx:786
list_elem< Type > * get_prev()
Definition: SoTl.hxx:67
Type * get_prev()
Definition: SoTl.hxx:359
positiontype insert_sorted_by_address_of_object(Type *object, int relation=RELATION_LESS, bool duplicates=true)
Definition: SoTl.hxx:616
~List()
Definition: SoTl.hxx:240
Type * get_member_at_pos(positiontype pos)
Definition: SoTl.hxx:937
list_elem< Type > * get_last_list_elem()
Definition: SoTl.hxx:96
Definition: SoTl.hxx:77
void sort_list_join(List< Type > *l, int relation=RELATION_LESS)
Definition: SoTl.hxx:687
positiontype insert_after_current(Type *object)
Definition: SoTl.hxx:453
unsigned long positiontype
Definition: SoTl.hxx:42
GB_write_int const char GB_write_autoconv_string WRITE_SKELETON(write_pointer, GBDATA *,"%p", GB_write_pointer) char *AW_awa if)(!gb_var) return strdup("")
Definition: AW_awar.cxx:166
bool remove_pos_from_list(positiontype pos)
Definition: SoTl.hxx:963
void remove_member_from_list(Type *object)
Definition: SoTl.hxx:535
void remember_current()
Definition: SoTl.hxx:98
void remove_last()
Definition: SoTl.hxx:600
positiontype insert_at_pos(Type *object, positiontype pos)
Definition: SoTl.hxx:905
Type * get_first()
Definition: SoTl.hxx:335
bool exchange_positions(positiontype ex, positiontype change)
Definition: SoTl.hxx:857
Type * get_member_at_pos_simple(positiontype pos)
Definition: SoTl.hxx:950
void set_remembered_as_current_ARC()
Definition: SoTl.hxx:256
#define NULp
Definition: cxxforward.h:97
void set_next(list_elem< Type > *n)
Definition: SoTl.hxx:66
positiontype insert(Type *object)
Definition: SoTl.hxx:502
void update_pos_no()
Definition: SoTl.hxx:821
#define RELATION_LESS
Definition: SoTl.hxx:45
void no_sotl_list()
Definition: SoTl.hxx:104
void set_elem(Type *el)
Definition: SoTl.hxx:62
bool isolate_list_elem()
Definition: SoTl.hxx:210
positiontype insert_as_first(Type *object)
Definition: SoTl.hxx:413