aapl/dlcommon.h

   1 /*
   2  *  Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 /* This header is not wrapped in ifndef becuase it is not intended to
  23  * be included by the user. */
  24
  25 #ifdef AAPL_NAMESPACE
  26 namespace Aapl {
  27 #endif
  28
  29 #if defined( DOUBLELIST_VALUE )
  30 /**
  31  * \brief Double list element for DListVal.
  32  *
  33  * DListValEl stores the type T of DListVal by value.
  34  */
  35 template <class T> struct DListValEl
  36 {
  37         /**
  38          * \brief Construct a DListValEl with a given value.
  39          *
  40          * The only constructor available initializes the value element. This
  41          * enforces that DListVal elements are never created without having their
  42          * value intialzed by the user. T's copy constructor is used to copy the
  43          * value in.
  44          */
  45         DListValEl( const T &val ) : value(val) { }
  46
  47         /**
  48          * \brief Value stored by the list element.
  49          *
  50          * Value is always copied into new list elements using the copy
  51          * constructor.
  52          */
  53         T value;
  54
  55         /**
  56          * \brief List previous pointer.
  57          *
  58          * Points to the previous item in the list. If this is the first item in
  59          * the list, then prev is NULL. If this element is not in a list then
  60          * prev is undefined.
  61          */
  62         DListValEl<T> *prev;
  63
  64         /**
  65          * \brief List next pointer.
  66          *
  67          * Points to the next item in the list. If this is the list item in the
  68          * list, then next is NULL. If this element is not in a list then next is
  69          * undefined.
  70          */
  71         DListValEl<T> *next;
  72 };
  73 #else
  74
  75 #ifndef __AAPL_DOUBLE_LIST_EL
  76 #define __AAPL_DOUBLE_LIST_EL
  77 /**
  78  * \brief Double list element properties.
  79  *
  80  * This class can be inherited to make a class suitable to be a double list
  81  * element. It simply provides the next and previous pointers. An alternative
  82  * is to put the next and previous pointers in the class directly.
  83  */
  84 template <class Element> struct DListEl
  85 {
  86         /**
  87          * \brief List previous pointer.
  88          *
  89          * Points to the previous item in the list. If this is the first item in
  90          * the list, then prev is NULL. If this element is not in a list then
  91          * prev is undefined.
  92          */
  93         Element *prev;
  94
  95         /**
  96          * \brief List next pointer.
  97          *
  98          * Points to the next item in the list. If this is the list item in the
  99          * list, then next is NULL. If this element is not in a list then next is
 100          * undefined.
 101          */
 102         Element *next;
 103 };
 104 #endif /* __AAPL_DOUBLE_LIST_EL */
 105
 106 #endif
 107
 108 /* Doubly Linked List */
 109 template <DLMEL_TEMPDEF> class DList
 110 {
 111 public:
 112         /** \brief Initialize an empty list. */
 113         DList() : head(0), tail(0), listLen(0) {}
 114
 115         /**
 116          * \brief Perform a deep copy of the list.
 117          *
 118          * The elements of the other list are duplicated and put into this list.
 119          * Elements are copied using the copy constructor.
 120          */
 121         DList(const DList &other);
 122
 123 #ifdef DOUBLELIST_VALUE
 124         /**
 125          * \brief Clear the double list contents.
 126          *
 127          * All elements are deleted.
 128          */
 129         ~DList() { empty(); }
 130
 131         /**
 132          * \brief Assign another list into this list using a deep copy.
 133          *
 134          * The elements of the other list are duplicated and put into this list.
 135          * Each list item is created using the copy constructor. If this list
 136          * contains any elements before the copy, they are deleted first.
 137          *
 138          * \returns A reference to this.
 139          */
 140         DList &operator=(const DList &other);
 141
 142         /**
 143          * \brief Transfer the contents of another list into this list.
 144          *
 145          * The elements of the other list moved in. The other list will be empty
 146          * afterwards.  If this list contains any elements before the copy, then
 147          * they are deleted.
 148          */
 149         void transfer(DList &other);
 150 #else
 151         /**
 152          * \brief Abandon all elements in the list.
 153          *
 154          * List elements are not deleted.
 155          */
 156         ~DList() {}
 157
 158         /**
 159          * \brief Perform a deep copy of the list.
 160          *
 161          * The elements of the other list are duplicated and put into this list.
 162          * Each list item is created using the copy constructor. If this list
 163          * contains any elements before the copy, they are abandoned.
 164          *
 165          * \returns A reference to this.
 166          */
 167         DList &operator=(const DList &other);
 168
 169         /**
 170          * \brief Transfer the contents of another list into this list.
 171          *
 172          * The elements of the other list moved in. The other list will be empty
 173          * afterwards.  If this list contains any elements before the copy, they
 174          * are abandoned.
 175          */
 176         void transfer(DList &other);
 177 #endif
 178
 179
 180 #ifdef DOUBLELIST_VALUE
 181         /**
 182          * \brief Make a new element and prepend it to the front of the list.
 183          *
 184          * The item is copied into the new element using the copy constructor.
 185          * Equivalent to list.addBefore(list.head, item).
 186          */
 187         void prepend(const T &item);
 188
 189         /**
 190          * \brief Make a new element and append it to the end of the list.
 191          *
 192          * The item is copied into the new element using the copy constructor.
 193          * Equivalent to list.addAfter(list.tail, item).
 194          */
 195         void append(const T &item);
 196
 197         /**
 198          * \brief Make a new element and insert it immediately after an element in
 199          * the list.
 200          *
 201          * The item is copied into the new element using the copy constructor. If
 202          * prev_el is NULL then the new element is prepended to the front of the
 203          * list. If prev_el is not already in the list then undefined behaviour
 204          * results.  Equivalent to list.addAfter(prev_el, new DListValEl(item)).
 205          */
 206         void addAfter(Element *prev_el, const T &item);
 207
 208         /**
 209          * \brief Make a new element and insert it immediately before an element
 210          * in the list.
 211          *
 212          * The item is copied into the new element using the copy construcotor. If
 213          * next_el is NULL then the new element is appended to the end of the
 214          * list.  If next_el is not already in the list then undefined behaviour
 215          * results.  Equivalent to list.addBefore(next_el, new DListValEl(item)).
 216          */
 217         void addBefore(Element *next_el, const T &item);
 218 #endif
 219
 220         /**
 221          * \brief Prepend a single element to the front of the list.
 222          *
 223          * If new_el is already an element of some list, then undefined behaviour
 224          * results. Equivalent to list.addBefore(list.head, new_el).
 225          */
 226         void prepend(Element *new_el) { addBefore(head, new_el); }
 227
 228         /**
 229          * \brief Append a single element to the end of the list.
 230          *
 231          * If new_el is alreay an element of some list, then undefined behaviour
 232          * results.  Equivalent to list.addAfter(list.tail, new_el).
 233          */
 234         void append(Element *new_el)  { addAfter(tail, new_el); }
 235
 236         /**
 237          * \brief Prepend an entire list to the beginning of this list.
 238          *
 239          * All items are moved, not copied. Afterwards, the other list is emtpy.
 240          * All items are prepended at once, so this is an O(1) operation.
 241          * Equivalent to list.addBefore(list.head, dl).
 242          */
 243         void prepend(DList &dl)       { addBefore(head, dl); }
 244
 245         /**
 246          * \brief Append an entire list to the end of the list.
 247          *
 248          * All items are moved, not copied. Afterwards, the other list is empty.
 249          * All items are appened at once, so this is an O(1) operation.
 250          * Equivalent to list.addAfter(list.tail, dl).
 251          */
 252         void append(DList &dl)        { addAfter(tail, dl); }
 253
 254         void addAfter(Element *prev_el, Element *new_el);
 255         void addBefore(Element *next_el, Element *new_el);
 256
 257         void addAfter(Element *prev_el, DList &dl);
 258         void addBefore(Element *next_el, DList &dl);
 259
 260         /**
 261          * \brief Detach the head of the list
 262          *
 263          * The element detached is not deleted. If there is no head of the list
 264          * (the list is empty) then undefined behaviour results.  Equivalent to
 265          * list.detach(list.head).
 266          *
 267          * \returns The element detached.
 268          */
 269         Element *detachFirst()        { return detach(head); }
 270
 271         /**
 272          * \brief Detach the tail of the list
 273          *
 274          * The element detached is not deleted. If there is no tail of the list
 275          * (the list is empty) then undefined behaviour results.  Equivalent to
 276          * list.detach(list.tail).
 277          *
 278          * \returns The element detached.
 279          */
 280         Element *detachLast()         { return detach(tail); }
 281
 282         /* Detaches an element from the list. Does not free any memory. */
 283         Element *detach(Element *el);
 284
 285         /**
 286          * \brief Detach and delete the first element in the list.
 287          *
 288          * If there is no first element (the list is empty) then undefined
 289          * behaviour results.  Equivalent to delete list.detach(list.head);
 290          */
 291         void removeFirst()         { delete detach( head ); }
 292
 293         /**
 294          * \brief Detach and delete the last element in the list.
 295          *
 296          * If there is no last element (the list is emtpy) then undefined
 297          * behaviour results.  Equivalent to delete list.detach(list.tail);
 298          */
 299         void removeLast()          { delete detach( tail ); }
 300
 301         /**
 302          * \brief Detach and delete an element from the list.
 303          *
 304          * If the element is not in the list, then undefined behaviour results.
 305          * Equivalent to delete list.detach(el);
 306          */
 307         void remove(Element *el)   { delete detach( el ); }
 308
 309         void empty();
 310         void abandon();
 311
 312         /** \brief The number of elements in the list. */
 313         long length() const { return listLen; }
 314
 315         /** \brief Head and tail of the linked list. */
 316         Element *head, *tail;
 317
 318         /** \brief The number of element in the list. */
 319         long listLen;
 320
 321         /* Convenience access. */
 322         long size() const           { return listLen; }
 323
 324         /* Forward this so a ref can be used. */
 325         struct Iter;
 326
 327         /* Class for setting the iterator. */
 328         struct IterFirst { IterFirst( const DList &l ) : l(l) { } const DList &l; };
 329         struct IterLast { IterLast( const DList &l ) : l(l) { } const DList &l; };
 330         struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
 331         struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
 332
 333         /**
 334          * \brief Double List Iterator.
 335          * \ingroup iterators
 336          */
 337         struct Iter
 338         {
 339                 /* Default construct. */
 340                 Iter() : ptr(0) { }
 341
 342                 /* Construct from a double list. */
 343                 Iter( const DList &dl )      : ptr(dl.head) { }
 344                 Iter( Element *el )          : ptr(el) { }
 345                 Iter( const IterFirst &dlf ) : ptr(dlf.l.head) { }
 346                 Iter( const IterLast &dll )  : ptr(dll.l.tail) { }
 347                 Iter( const IterNext &dln )  : ptr(dln.i.ptr->BASE_EL(next)) { }
 348                 Iter( const IterPrev &dlp )  : ptr(dlp.i.ptr->BASE_EL(prev)) { }
 349
 350                 /* Assign from a double list. */
 351                 Iter &operator=( const DList &dl )     { ptr = dl.head; return *this; }
 352                 Iter &operator=( Element *el )         { ptr = el; return *this; }
 353                 Iter &operator=( const IterFirst &af ) { ptr = af.l.head; return *this; }
 354                 Iter &operator=( const IterLast &al )  { ptr = al.l.tail; return *this; }
 355                 Iter &operator=( const IterNext &an )  { ptr = an.i.ptr->BASE_EL(next); return *this; }
 356                 Iter &operator=( const IterPrev &ap )  { ptr = ap.i.ptr->BASE_EL(prev); return *this; }
 357
 358                 /** \brief Less than end? */
 359                 bool lte() const    { return ptr != 0; }
 360
 361                 /** \brief At end? */
 362                 bool end() const    { return ptr == 0; }
 363
 364                 /** \brief Greater than beginning? */
 365                 bool gtb() const { return ptr != 0; }
 366
 367                 /** \brief At beginning? */
 368                 bool beg() const { return ptr == 0; }
 369
 370                 /** \brief At first element? */
 371                 bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }
 372
 373                 /** \brief At last element? */
 374                 bool last() const  { return ptr && ptr->BASE_EL(next) == 0; }
 375
 376                 /** \brief Implicit cast to Element*. */
 377                 operator Element*() const   { return ptr; }
 378
 379                 /** \brief Dereference operator returns Element&. */
 380                 Element &operator *() const { return *ptr; }
 381
 382                 /** \brief Arrow operator returns Element*. */
 383                 Element *operator->() const { return ptr; }
 384
 385                 /** \brief Move to next item. */
 386                 inline Element *operator++()      { return ptr = ptr->BASE_EL(next); }
 387
 388                 /** \brief Move to next item. */
 389                 inline Element *increment()       { return ptr = ptr->BASE_EL(next); }
 390
 391                 /** \brief Move to next item. */
 392                 inline Element *operator++(int);
 393
 394                 /** \brief Move to previous item. */
 395                 inline Element *operator--()      { return ptr = ptr->BASE_EL(prev); }
 396
 397                 /** \brief Move to previous item. */
 398                 inline Element *decrement()       { return ptr = ptr->BASE_EL(prev); }
 399
 400                 /** \brief Move to previous item. */
 401                 inline Element *operator--(int);
 402
 403                 /** \brief Return the next item. Does not modify this. */
 404                 inline IterNext next() const { return IterNext(*this); }
 405
 406                 /** \brief Return the prev item. Does not modify this. */
 407                 inline IterPrev prev() const { return IterPrev(*this); }
 408
 409                 /** \brief The iterator is simply a pointer. */
 410                 Element *ptr;
 411         };
 412
 413         /** \brief Return first element. */
 414         IterFirst first()  { return IterFirst(*this); }
 415
 416         /** \brief Return last element. */
 417         IterLast last()    { return IterLast(*this); }
 418 };
 419
 420 /* Copy constructor, does a deep copy of other. */
 421 template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE>::
 422                 DList(const DList<DLMEL_TEMPUSE> &other) :
 423                         head(0), tail(0), listLen(0)
 424 {
 425         Element *el = other.head;
 426         while( el != 0 ) {
 427                 append( new Element(*el) );
 428                 el = el->BASE_EL(next);
 429         }
 430 }
 431
 432 #ifdef DOUBLELIST_VALUE
 433
 434 /* Assignement operator does deep copy. */
 435 template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
 436                 operator=(const DList &other)
 437 {
 438         /* Free the old list. The value list assumes items were allocated on the
 439          * heap by itself. */
 440         empty();
 441
 442         Element *el = other.head;
 443         while( el != 0 ) {
 444                 append( new Element(*el) );
 445                 el = el->BASE_EL(next);
 446         }
 447         return *this;
 448 }
 449
 450 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 451                 transfer(DList &other)
 452 {
 453         /* Free the old list. The value list assumes items were allocated on the
 454          * heap by itself. */
 455         empty();
 456
 457         head = other.head;
 458         tail = other.tail;
 459         listLen = other.listLen;
 460
 461         other.abandon();
 462 }
 463
 464 #else
 465
 466 /* Assignement operator does deep copy. */
 467 template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
 468                 operator=(const DList &other)
 469 {
 470         Element *el = other.head;
 471         while( el != 0 ) {
 472                 append( new Element(*el) );
 473                 el = el->BASE_EL(next);
 474         }
 475         return *this;
 476 }
 477
 478 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 479                 transfer(DList &other)
 480 {
 481         head = other.head;
 482         tail = other.tail;
 483         listLen = other.listLen;
 484
 485         other.abandon();
 486 }
 487
 488 #endif
 489
 490 #ifdef DOUBLELIST_VALUE
 491
 492 /* Prepend a new item. Inlining this bloats the caller with new overhead. */
 493 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 494                 prepend(const T &item)
 495 {
 496         addBefore(head, new Element(item));
 497 }
 498
 499 /* Append a new item. Inlining this bloats the caller with the new overhead. */
 500 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 501                 append(const T &item)
 502 {
 503         addAfter(tail, new Element(item));
 504 }
 505
 506 /* Add a new item after a prev element. Inlining this bloats the caller with
 507  * the new overhead. */
 508 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 509                 addAfter(Element *prev_el, const T &item)
 510 {
 511         addAfter(prev_el, new Element(item));
 512 }
 513
 514 /* Add a new item before a next element. Inlining this bloats the caller with
 515  * the new overhead. */
 516 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 517                 addBefore(Element *next_el, const T &item)
 518 {
 519         addBefore(next_el, new Element(item));
 520 }
 521
 522 #endif
 523
 524 /*
 525  * The larger iterator operators.
 526  */
 527
 528 /* Postfix ++ */
 529 template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
 530                 operator++(int)
 531 {
 532         Element *rtn = ptr;
 533         ptr = ptr->BASE_EL(next);
 534         return rtn;
 535 }
 536
 537 /* Postfix -- */
 538 template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
 539                 operator--(int)
 540 {
 541         Element *rtn = ptr;
 542         ptr = ptr->BASE_EL(prev);
 543         return rtn;
 544 }
 545
 546 /**
 547  * \brief Insert an element immediately after an element in the list.
 548  *
 549  * If prev_el is NULL then new_el is prepended to the front of the list. If
 550  * prev_el is not in the list or if new_el is already in a list, then
 551  * undefined behaviour results.
 552  */
 553 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 554                 addAfter(Element *prev_el, Element *new_el)
 555 {
 556         /* Set the previous pointer of new_el to prev_el. We do
 557          * this regardless of the state of the list. */
 558         new_el->BASE_EL(prev) = prev_el;
 559
 560         /* Set forward pointers. */
 561         if (prev_el == 0) {
 562                 /* There was no prev_el, we are inserting at the head. */
 563                 new_el->BASE_EL(next) = head;
 564                 head = new_el;
 565         }
 566         else {
 567                 /* There was a prev_el, we can access previous next. */
 568                 new_el->BASE_EL(next) = prev_el->BASE_EL(next);
 569                 prev_el->BASE_EL(next) = new_el;
 570         }
 571
 572         /* Set reverse pointers. */
 573         if (new_el->BASE_EL(next) == 0) {
 574                 /* There is no next element. Set the tail pointer. */
 575                 tail = new_el;
 576         }
 577         else {
 578                 /* There is a next element. Set it's prev pointer. */
 579                 new_el->BASE_EL(next)->BASE_EL(prev) = new_el;
 580         }
 581
 582         /* Update list length. */
 583         listLen++;
 584 }
 585
 586 /**
 587  * \brief Insert an element immediatly before an element in the list.
 588  *
 589  * If next_el is NULL then new_el is appended to the end of the list. If
 590  * next_el is not in the list or if new_el is already in a list, then
 591  * undefined behaviour results.
 592  */
 593 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 594                 addBefore(Element *next_el, Element *new_el)
 595 {
 596         /* Set the next pointer of the new element to next_el. We do
 597          * this regardless of the state of the list. */
 598         new_el->BASE_EL(next) = next_el;
 599
 600         /* Set reverse pointers. */
 601         if (next_el == 0) {
 602                 /* There is no next elememnt. We are inserting at the tail. */
 603                 new_el->BASE_EL(prev) = tail;
 604                 tail = new_el;
 605         }
 606         else {
 607                 /* There is a next element and we can access next's previous. */
 608                 new_el->BASE_EL(prev) = next_el->BASE_EL(prev);
 609                 next_el->BASE_EL(prev) = new_el;
 610         }
 611
 612         /* Set forward pointers. */
 613         if (new_el->BASE_EL(prev) == 0) {
 614                 /* There is no previous element. Set the head pointer.*/
 615                 head = new_el;
 616         }
 617         else {
 618                 /* There is a previous element, set it's next pointer to new_el. */
 619                 new_el->BASE_EL(prev)->BASE_EL(next) = new_el;
 620         }
 621
 622         /* Update list length. */
 623         listLen++;
 624 }
 625
 626 /**
 627  * \brief Insert an entire list immediatly after an element in this list.
 628  *
 629  * Elements are moved, not copied. Afterwards, the other list is empty. If
 630  * prev_el is NULL then the elements are prepended to the front of the list.
 631  * If prev_el is not in the list then undefined behaviour results. All
 632  * elements are inserted into the list at once, so this is an O(1) operation.
 633  */
 634 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 635                 addAfter( Element *prev_el, DList<DLMEL_TEMPUSE> &dl )
 636 {
 637         /* Do not bother if dl has no elements. */
 638         if ( dl.listLen == 0 )
 639                 return;
 640
 641         /* Set the previous pointer of dl.head to prev_el. We do
 642          * this regardless of the state of the list. */
 643         dl.head->BASE_EL(prev) = prev_el;
 644
 645         /* Set forward pointers. */
 646         if (prev_el == 0) {
 647                 /* There was no prev_el, we are inserting at the head. */
 648                 dl.tail->BASE_EL(next) = head;
 649                 head = dl.head;
 650         }
 651         else {
 652                 /* There was a prev_el, we can access previous next. */
 653                 dl.tail->BASE_EL(next) = prev_el->BASE_EL(next);
 654                 prev_el->BASE_EL(next) = dl.head;
 655         }
 656
 657         /* Set reverse pointers. */
 658         if (dl.tail->BASE_EL(next) == 0) {
 659                 /* There is no next element. Set the tail pointer. */
 660                 tail = dl.tail;
 661         }
 662         else {
 663                 /* There is a next element. Set it's prev pointer. */
 664                 dl.tail->BASE_EL(next)->BASE_EL(prev) = dl.tail;
 665         }
 666
 667         /* Update the list length. */
 668         listLen += dl.listLen;
 669
 670         /* Empty out dl. */
 671         dl.head = dl.tail = 0;
 672         dl.listLen = 0;
 673 }
 674
 675 /**
 676  * \brief Insert an entire list immediately before an element in this list.
 677  *
 678  * Elements are moved, not copied. Afterwards, the other list is empty. If
 679  * next_el is NULL then the elements are appended to the end of the list. If
 680  * next_el is not in the list then undefined behaviour results. All elements
 681  * are inserted at once, so this is an O(1) operation.
 682  */
 683 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
 684                 addBefore( Element *next_el, DList<DLMEL_TEMPUSE> &dl )
 685 {
 686         /* Do not bother if dl has no elements. */
 687         if ( dl.listLen == 0 )
 688                 return;
 689
 690         /* Set the next pointer of dl.tail to next_el. We do
 691          * this regardless of the state of the list. */
 692         dl.tail->BASE_EL(next) = next_el;
 693
 694         /* Set reverse pointers. */
 695         if (next_el == 0) {
 696                 /* There is no next elememnt. We are inserting at the tail. */
 697                 dl.head->BASE_EL(prev) = tail;
 698                 tail = dl.tail;
 699         }
 700         else {
 701                 /* There is a next element and we can access next's previous. */
 702                 dl.head->BASE_EL(prev) = next_el->BASE_EL(prev);
 703                 next_el->BASE_EL(prev) = dl.tail;
 704         }
 705
 706         /* Set forward pointers. */
 707         if (dl.head->BASE_EL(prev) == 0) {
 708                 /* There is no previous element. Set the head pointer.*/
 709                 head = dl.head;
 710         }
 711         else {
 712                 /* There is a previous element, set it's next pointer to new_el. */
 713                 dl.head->BASE_EL(prev)->BASE_EL(next) = dl.head;
 714         }
 715
 716         /* Update list length. */
 717         listLen += dl.listLen;
 718
 719         /* Empty out dl. */
 720         dl.head = dl.tail = 0;
 721         dl.listLen = 0;
 722 }
 723
 724
 725 /**
 726  * \brief Detach an element from the list.
 727  *
 728  * The element is not deleted. If the element is not in the list, then
 729  * undefined behaviour results.
 730  *
 731  * \returns The element detached.
 732  */
 733 template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::
 734                 detach(Element *el)
 735 {
 736         /* Set forward pointers to skip over el. */
 737         if (el->BASE_EL(prev) == 0)
 738                 head = el->BASE_EL(next);
 739         else {
 740                 el->BASE_EL(prev)->BASE_EL(next) =
 741                                 el->BASE_EL(next);
 742         }
 743
 744         /* Set reverse pointers to skip over el. */
 745         if (el->BASE_EL(next) == 0)
 746                 tail = el->BASE_EL(prev);
 747         else {
 748                 el->BASE_EL(next)->BASE_EL(prev) =
 749                                 el->BASE_EL(prev);
 750         }
 751
 752         /* Update List length and return element we detached. */
 753         listLen--;
 754         return el;
 755 }
 756
 757 /**
 758  * \brief Clear the list by deleting all elements.
 759  *
 760  * Each item in the list is deleted. The list is reset to its initial state.
 761  */
 762 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::empty()
 763 {
 764         Element *nextToGo = 0, *cur = head;
 765
 766         while (cur != 0)
 767         {
 768                 nextToGo = cur->BASE_EL(next);
 769                 delete cur;
 770                 cur = nextToGo;
 771         }
 772         head = tail = 0;
 773         listLen = 0;
 774 }
 775
 776 /**
 777  * \brief Clear the list by forgetting all elements.
 778  *
 779  * All elements are abandoned, not deleted. The list is reset to it's initial
 780  * state.
 781  */
 782 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::abandon()
 783 {
 784         head = tail = 0;
 785         listLen = 0;
 786 }
 787
 788 #ifdef AAPL_NAMESPACE
 789 }
 790 #endif