include/AD/contain/dlist.h

   1 #ifndef doubly_linked_lists_h
   2 #define doubly_linked_lists_h
   3
   4 #include <AD/generic/generic.h>
   5
   6 //////////////////////////////////////////////////////////////////////////////
   7 //  Linked node structure; this class is be made visible to the
   8 //  client.  Notice that the link structure is made hidden to the user
   9 //  for safety.
  10 //////////////////////////////////////////////////////////////////////////////
  11 template <class T> class DLinkList;
  12 template <class T>
  13    class DNode {
  14       ////////////////////////////////////////////////////////////////////////
  15       // Members
  16       ////////////////////////////////////////////////////////////////////////
  17       T      element;
  18       DNode * _prev, * _next;
  19       friend class DLinkList<T>;
  20       inline DNode * set_prev(DNode * p) { _prev = p; }
  21       inline DNode * set_next(DNode * n) { _next = n; }
  22    public:
  23       ////////////////////////////////////////////////////////////////////////
  24       // Public operations.
  25       ////////////////////////////////////////////////////////////////////////
  26       inline DNode(const T& e, DNode * p = 0, DNode * n = 0)
  27           : element(e), _prev(p), _next(n) {}
  28       inline DNode * prev() const      { return _prev; }
  29       inline DNode * next() const      { return _next; }
  30       inline const T& value() const    { return element; }
  31       inline       T& value()          { return element; }
  32    };
  33
  34
  35 //////////////////////////////////////////////////////////////////////////////
  36 //
  37 //  Doubly linked lists template.
  38 //  This class implements a double linked list datatype.
  39 //  The list nodes can be manipulated directly using the link/unlink methods,
  40 //  while the insert/remove methods provide an encapsulated interface to
  41 //  the list.
  42 //
  43 //////////////////////////////////////////////////////////////////////////////
  44 template <class T>
  45    class DLinkList {
  46    public:
  47       ////////////////////////////////////////////////////////////////////////
  48       //  Type equivalences.
  49       ////////////////////////////////////////////////////////////////////////
  50       typedef T          Element; // element type
  51       typedef DNode<T> * Ix;      // index type
  52
  53       ////////////////////////////////////////////////////////////////////////
  54       //  Data members
  55       ////////////////////////////////////////////////////////////////////////
  56       int        count;          // number of elements in list
  57       DNode<T> * front, * back;  // link to first and last element
  58
  59    public:
  60
  61       ////////////////////////////////////////////////////////////////////////
  62       //  Constructors and destructor
  63       ////////////////////////////////////////////////////////////////////////
  64       DLinkList();
  65       DLinkList(const DLinkList&);
  66      ~DLinkList();
  67
  68       ////////////////////////////////////////////////////////////////////////
  69       //  Assignment
  70       ////////////////////////////////////////////////////////////////////////
  71       DLinkList& operator = (const DLinkList&);
  72
  73       ////////////////////////////////////////////////////////////////////////
  74       //  Selectors
  75       ////////////////////////////////////////////////////////////////////////
  76       inline int  size     () const { return count; }
  77       inline Bool is_empty () const { return front == 0; }
  78
  79       ////////////////////////////////////////////////////////////////////////
  80       //  Iterators
  81       ////////////////////////////////////////////////////////////////////////
  82       inline DNode<T> * first()                  const { return front; }
  83       inline DNode<T> * last ()                  const { return back; }
  84       inline DNode<T> * next (DNode<T> * i)      const { return i->next(); }
  85       inline DNode<T> * prev (DNode<T> * i)      const { return i->prev(); }
  86       inline const T& operator () (DNode<T> * i) const { return i->value(); }
  87       inline       T& operator () (DNode<T> * i)       { return i->value(); }
  88
  89       ////////////////////////////////////////////////////////////////////////
  90       //  Mutators.
  91       //    Two interfaces are provided:
  92       //    (1) insert/delete
  93       ////////////////////////////////////////////////////////////////////////
  94              DLinkList& clear            ();
  95
  96       inline DLinkList& insert_before    (DNode<T> *, const T&);
  97       inline DLinkList& insert_after     (DNode<T> *, const T&);
  98       inline DLinkList& insert_to_front  (const T& e);
  99       inline DLinkList& insert_to_back   (const T& e);
 100       inline DLinkList& remove           (DNode<T> *);
 101       inline DLinkList& remove_from_front();
 102       inline DLinkList& remove_from_back ();
 103
 104       inline DNode<T> *  unlink           (DNode<T> *);
 105       inline DNode<T> *  unlink_from_front();
 106       inline DNode<T> *  unlink_from_back ();
 107       inline DLinkList& link_to_front     (DNode<T> *);
 108       inline DLinkList& link_to_back      (DNode<T> *);
 109       inline DLinkList& link_before       (DNode<T> *, DNode<T> *);
 110       inline DLinkList& link_after        (DNode<T> *, DNode<T> *);
 111
 112       ////////////////////////////////////////////////////////////////////////
 113       //  Short hands.
 114       ////////////////////////////////////////////////////////////////////////
 115       inline DLinkList& operator ,  (const T& e)   { return insert_to_back(e); }
 116       inline DLinkList& operator ,  (DNode<T> * n) { return link_to_back(n); }
 117       inline DLinkList& operator += (const T& e)   { return insert_to_back(e); }
 118       inline DLinkList& operator += (DNode<T> * n) { return link_to_back(n); }
 119       inline DLinkList& operator =  (const T& e)   { clear(); return insert_to_back(e); }
 120       inline DLinkList& operator =  (DNode<T> * n) { clear(); return link_to_back(n); }
 121    };
 122
 123 //////////////////////////////////////////////////////////////////////////////
 124 //  Implementation of the template methods.
 125 //////////////////////////////////////////////////////////////////////////////
 126
 127 //////////////////////////////////////////////////////////////////////////////
 128 //  Constructors and destructors
 129 //////////////////////////////////////////////////////////////////////////////
 130 template <class T>
 131    DLinkList<T>::DLinkList() : count(0), front(0), back(0) {}
 132 template <class T>
 133    DLinkList<T>::DLinkList(const DLinkList<T>& l)
 134       : count(0), front(0), back(0) { *this = l; }
 135 template <class T>
 136    DLinkList<T>::~DLinkList() { clear(); }
 137
 138 //////////////////////////////////////////////////////////////////////////////
 139 //  Assignment
 140 //////////////////////////////////////////////////////////////////////////////
 141 template <class T>
 142    DLinkList<T>& DLinkList<T>::operator = (const DLinkList<T>& list)
 143    {  if (this != &list) {
 144          clear();
 145          for(DNode<T> * n = list.first(); n; n = list.next(n))
 146             insert_to_back(n->value());
 147          count += list.size();
 148       }
 149       return *this;
 150    }
 151
 152 //////////////////////////////////////////////////////////////////////////////
 153 //  Emptying the list and frees all nodes.
 154 //////////////////////////////////////////////////////////////////////////////
 155 template <class T>
 156    DLinkList<T>& DLinkList<T>::clear()
 157    {  DLinkList<T>::Ix l;
 158       while (l = unlink_from_front()) delete l;
 159       count = 0;
 160       back = front = 0;
 161       return *this;
 162    }
 163
 164 //////////////////////////////////////////////////////////////////////////////
 165 //  Insert an element to the front of the list.
 166 //////////////////////////////////////////////////////////////////////////////
 167 template <class T>
 168    inline DLinkList<T>& DLinkList<T>::insert_to_front  (const T& e)
 169    {  // Make ``e'' the head of the list
 170       DNode<T> * n = new DNode<T>(e,0,front);
 171       if (front) front->set_prev(n);
 172       else back = n;
 173       front = n; count++;
 174       return *this;
 175    }
 176
 177 //////////////////////////////////////////////////////////////////////////////
 178 //  Insert an element to the back of the list.
 179 //////////////////////////////////////////////////////////////////////////////
 180 template <class T>
 181    DLinkList<T>& DLinkList<T>::insert_to_back(const T& e)
 182    {  // Make ``e'' the tail of the list
 183       DNode<T> * n = new DNode<T>(e,back,0);
 184       if (back) back->set_next(n);
 185       else front = n;
 186       back = n; count++;
 187       return *this;
 188    }
 189
 190 //////////////////////////////////////////////////////////////////////////////
 191 //  Insert an element 'e' before position ``pos''.
 192 //  Preconditions:
 193 //     ``pos'' must be non-null and on the list.
 194 //////////////////////////////////////////////////////////////////////////////
 195 template <class T>
 196    DLinkList<T>& DLinkList<T>::insert_before (DNode<T> * pos, const T& e)
 197    {  // Insert a new element before position ``pos''.
 198       // ``pos'' must be non-null.
 199       if (pos) {
 200          DNode<T> * n = new DNode<T>(e,pos->prev(),pos);
 201          pos->set_next(n);
 202          if (pos == front) front = n;
 203          count++;
 204       }
 205       return *this;
 206    }
 207
 208 //////////////////////////////////////////////////////////////////////////////
 209 //  Insert an element 'e' after position ``pos''.
 210 //  Preconditions:
 211 //     ``pos'' must be non-null and on the list.
 212 //////////////////////////////////////////////////////////////////////////////
 213 template <class T>
 214    DLinkList<T>& DLinkList<T>::insert_after (DNode<T> * pos, const T& e)
 215    {  // Insert a new element after position ``pos''.
 216       // ``pos'' must be non-null.
 217       if (pos) {
 218          DNode<T> * n = new DNode<T>(e,pos,pos->next());
 219          pos->set_prev(n);
 220          if (pos == back) back = n;
 221          count++;
 222       }
 223       return *this;
 224    }
 225
 226 //////////////////////////////////////////////////////////////////////////////
 227 //  Delete a node from a list.
 228 //  Precondition:
 229 //     The node ``n'' must be on the list.
 230 //////////////////////////////////////////////////////////////////////////////
 231 template <class T>
 232    inline DLinkList<T>& DLinkList<T>::remove (DNode<T> * n)
 233    {  if (n) {
 234          if (n == front) front = n->next();
 235          if (n == back)  back  = n->prev();
 236          if (n->prev()) n->prev()->set_next(n->next());
 237          if (n->next()) n->next()->set_prev(n->prev());
 238          count--;
 239          delete n;
 240       }
 241       return *this;
 242    }
 243
 244 //////////////////////////////////////////////////////////////////////////////
 245 //  Delete a node from the front of the list.
 246 //////////////////////////////////////////////////////////////////////////////
 247 template <class T>
 248    inline DLinkList<T>& DLinkList<T>::remove_from_front()
 249    {  DNode<T> * n = front;
 250       if (n) {
 251          front = n->next();
 252          if (n == back)  back = n->prev();
 253          if (n->next()) n->next()->set_prev(n->prev());
 254          count--;
 255          delete n;
 256       }
 257       return *this;
 258    }
 259
 260 //////////////////////////////////////////////////////////////////////////////
 261 //  Delete a node from the back of the list.
 262 //////////////////////////////////////////////////////////////////////////////
 263 template <class T>
 264    inline DLinkList<T>& DLinkList<T>::remove_from_back()
 265    {  DNode<T> * n = back;
 266       if (n) {
 267          back = n->prev();
 268          if (n == front)  front = n->next();
 269          if (n->prev()) n->prev()->set_next(n->next());
 270          count--;
 271          delete n;
 272       }
 273       return *this;
 274    }
 275
 276 //////////////////////////////////////////////////////////////////////////////
 277 //  Unlink a node ``n'' from a list.
 278 //  Precondition:
 279 //     Node ``n'' must be on the list.
 280 //////////////////////////////////////////////////////////////////////////////
 281 template <class T>
 282    DNode<T> * DLinkList<T>::unlink(DNode<T> * n)
 283    {  if (n) {
 284          if (n == front) front = n->next();
 285          if (n == back)  back  = n->prev();
 286          if (n->prev()) n->prev()->set_next(n->next());
 287          if (n->next()) n->next()->set_prev(n->prev());
 288          count--;
 289       }
 290       return n;
 291    }
 292
 293 //////////////////////////////////////////////////////////////////////////////
 294 //  Unlink a node from the front of the list.
 295 //////////////////////////////////////////////////////////////////////////////
 296 template <class T>
 297    DNode<T> * DLinkList<T>::unlink_from_front()
 298    {  DNode<T> * n = front;
 299       if (n) {
 300          count--;
 301          if (front = n->next())
 302             front->set_prev(0);
 303          else
 304             back = 0;
 305       }
 306       return n;
 307    }
 308
 309 //////////////////////////////////////////////////////////////////////////////
 310 //  Unlink a node from the back of the list.
 311 //////////////////////////////////////////////////////////////////////////////
 312 template <class T>
 313    DNode<T> * DLinkList<T>::unlink_from_back ()
 314    {
 315       DNode<T> * n = back;
 316       if (n) {
 317          count--;
 318          if (back = n->prev())
 319             back->set_next(0);
 320          else
 321             front = 0;
 322       }
 323       return n;
 324    }
 325
 326 //////////////////////////////////////////////////////////////////////////////
 327 //  Linking operations.
 328 //////////////////////////////////////////////////////////////////////////////
 329
 330 //////////////////////////////////////////////////////////////////////////////
 331 //  Link ``n'' to front of list.
 332 //  Node ``n'' must not be already on any list.
 333 //////////////////////////////////////////////////////////////////////////////
 334 template <class T>
 335    inline DLinkList<T>& DLinkList<T>::link_to_front(DNode<T> * n)
 336    {  if (n) {
 337          n->set_next(front);
 338          n->set_prev(0);
 339          if (front)
 340             front->set_prev(n);
 341          else
 342             front = n;
 343          count++;
 344       }
 345       return *this;
 346    }
 347
 348 //////////////////////////////////////////////////////////////////////////////
 349 //  Link ``n'' to end of list.
 350 //  Preconditions:
 351 //     Node ``n'' must not be already on any list.
 352 //////////////////////////////////////////////////////////////////////////////
 353 template <class T>
 354    inline DLinkList<T>& DLinkList<T>::link_to_back(DNode<T> * n)
 355    {  if (n) {
 356          n->set_next(0);
 357          n->set_prev(back);
 358          if (back)
 359             back->set_next(n);
 360          else
 361             back = n;
 362          count++;
 363       }
 364       return *this;
 365    }
 366
 367 //////////////////////////////////////////////////////////////////////////////
 368 //  Link node ``n'' before ``pos''.
 369 //  Preconditions:
 370 //     Node ``pos'' must be somewhere on the list.
 371 //     Node ``n'' must not be already on any list.
 372 //////////////////////////////////////////////////////////////////////////////
 373 template <class T>
 374    inline DLinkList<T>& DLinkList<T>::link_before (DNode<T> * pos, DNode<T> * n)
 375    {
 376       if (n) {
 377          if (pos) {
 378             if (pos == front) front = n;
 379             n->set_next(pos->next());
 380             n->set_prev(pos);
 381             pos->set_next(n);
 382             count++;
 383          } else {
 384             link_to_front(n);
 385          }
 386       }
 387       return *this;
 388    }
 389
 390 //////////////////////////////////////////////////////////////////////////////
 391 //  Link node ``n'' after ``pos''.
 392 //  Preconditions:
 393 //     Node ``pos'' must be somewhere on the list.
 394 //     Node ``n'' must not be already on any list.
 395 //////////////////////////////////////////////////////////////////////////////
 396 template <class T>
 397    inline DLinkList<T>& DLinkList<T>::link_after (DNode<T> * pos, DNode<T> * n)
 398    {
 399       if (n) {
 400          if (pos) {
 401             if (pos == back) back = n;
 402             n->set_prev(pos->prev());
 403             n->set_next(pos);
 404             pos->set_prev(n);
 405             count++;
 406          } else {
 407             link_to_back(n);
 408          }
 409       }
 410       return *this;
 411    }
 412
 413 #endif