home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / DLList.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  5KB  |  140 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19.  
  20. #ifndef _DLList_h
  21. #ifdef __GNUG__
  22. //#pragma interface
  23. #endif
  24. #define _DLList_h 1
  25.  
  26. #undef OK
  27.  
  28. #include <Pix.h>
  29.  
  30. struct BaseDLNode {
  31.     BaseDLNode *bk;
  32.     BaseDLNode *fd;
  33.     void *item() {return (void*)(this+1);} //Return ((DLNode<T>*)this)->hd
  34. };
  35.  
  36. template<class T>
  37. class DLNode : public BaseDLNode
  38. {
  39.   public:
  40.     T hd;
  41.     DLNode() { }
  42.     DLNode(const T& h, DLNode* p = 0, DLNode* n = 0)
  43.         : hd(h) { bk = p; fd = n; }
  44.     ~DLNode() { }
  45. };
  46.  
  47. class BaseDLList {
  48.   protected:
  49.     BaseDLNode *h;
  50.  
  51.     BaseDLList() { h = 0; }
  52.     void copy(const BaseDLList&);
  53.     BaseDLList& operator= (const BaseDLList& a);
  54.     virtual void delete_node(BaseDLNode*node) = 0;
  55.     virtual BaseDLNode* copy_node(const void* datum) = 0;
  56.     virtual void copy_item(void *dst, void *src) = 0;
  57.     virtual ~BaseDLList() { }
  58.  
  59.     Pix                   prepend(const void*);
  60.     Pix                   append(const void*);
  61.     Pix ins_after(Pix p, const void *datum);
  62.     Pix ins_before(Pix p, const void *datum);
  63.     void remove_front(void *dst);
  64.     void remove_rear(void *dst);
  65.     void join(BaseDLList&);
  66.  
  67.   public:
  68.     int                   empty() const { return h == 0; }
  69.     int                   length() const;
  70.     void                  clear();
  71.     void                  error(const char* msg) const;
  72.     int                   owns(Pix p) const;
  73.     int                   OK() const;
  74.     void                  del(Pix& p, int dir = 1);
  75.     void                  del_after(Pix& p);
  76.     void                  del_front();
  77.     void                  del_rear();
  78. };
  79.  
  80. template <class T>
  81. class DLList : public BaseDLList {
  82.     //friend class          <T>DLListTrav;
  83.  
  84.     virtual void delete_node(BaseDLNode *node) { delete (DLNode<T>*)node; }
  85.     virtual BaseDLNode* copy_node(const void *datum)
  86.     { return new DLNode<T>(*(const T*)datum); }
  87.     virtual void copy_item(void *dst, void *src) { *(T*)dst = *(T*)src; }
  88.  
  89.   public:
  90.     DLList() : BaseDLList() { }
  91.     DLList(const DLList<T>& a) : BaseDLList() { copy(a); }
  92.  
  93.     DLList<T>&            operator = (const DLList<T>& a)
  94.     { BaseDLList::operator=((const BaseDLList&) a); return *this; }
  95.     virtual ~DLList() { clear(); }
  96.  
  97.     Pix prepend(const T& item) {return BaseDLList::prepend(&item);}
  98.     Pix append(const T& item) {return BaseDLList::append(&item);}
  99.  
  100.     void join(DLList<T>& a) { BaseDLList::join(a); }
  101.  
  102.     T& front() {
  103.     if (h == 0) error("front: empty list");
  104.     return ((DLNode<T>*)h)->hd; }
  105.     T& rear() {
  106.     if (h == 0) error("rear: empty list");
  107.     return ((DLNode<T>*)h->bk)->hd;
  108.     }
  109.     const T& front() const {
  110.     if (h == 0) error("front: empty list");
  111.     return ((DLNode<T>*)h)->hd; }
  112.     const T& rear() const {
  113.     if (h == 0) error("rear: empty list");
  114.     return ((DLNode<T>*)h->bk)->hd;
  115.     }
  116.     T remove_front() { T dst; BaseDLList::remove_front(&dst); return dst; }
  117.     T remove_rear() { T dst; BaseDLList::remove_rear(&dst); return dst; }
  118.  
  119.     T&                  operator () (Pix p) {
  120.     if (p == 0) error("null Pix");
  121.     return ((DLNode<T>*)p)->hd;
  122.     }
  123.     const T&              operator () (Pix p) const {
  124.     if (p == 0) error("null Pix");
  125.     return ((DLNode<T>*)p)->hd;
  126.     }
  127.     Pix                   first() const { return Pix(h); }
  128.     Pix                   last()  const { return (h == 0) ? 0 : Pix(h->bk); }
  129.     void                  next(Pix& p) const
  130.     { p = (p == 0 || p == h->bk)? 0 : Pix(((DLNode<T>*)p)->fd); }
  131.     void                  prev(Pix& p) const
  132.     { p = (p == 0 || p == h)? 0 : Pix(((DLNode<T>*)p)->bk); }
  133.     Pix ins_after(Pix p, const T& item)
  134.       {return BaseDLList::ins_after(p, &item); }
  135.     Pix ins_before(Pix p, const T& item)
  136.       {return BaseDLList::ins_before(p, &item);}
  137. };
  138.  
  139. #endif
  140.