user/wxLayout/kbList.cpp

   1 /*-*- c++ -*-********************************************************
   2  * kbList.cc : a double linked list                                 *
   3  *                                                                  *
   4  * (C) 1998 by Karsten Ballüder (Ballueder@usa.net)                 *
   5  *                                                                  *
   6  * $Id$          *
   7  *                                                                  *
   8  * $Log$
   9  * Revision 1.2  1998/08/12 08:33:23  KB
  10  * Cursor and insert/delete work much better now, code streamlined, still
  11  * a minor problem left.
  12  *
  13  * Revision 1.6  1998/07/08 11:56:56  KB
  14  * M compiles and runs on Solaris 2.5/gcc 2.8/c-client gso
  15  *
  16  * Revision 1.5  1998/06/27 20:07:18  KB
  17  * several bug fixes for kbList
  18  * started adding my layout stuff
  19  *
  20  * Revision 1.1.1.1  1998/06/13 21:51:12  karsten
  21  * initial code
  22  *
  23  * Revision 1.4  1998/05/24 14:48:00  KB
  24  * lots of progress on Python, but cannot call functions yet
  25  * kbList fixes again?
  26  *
  27  * Revision 1.3  1998/05/18 17:48:34  KB
  28  * more list<>->kbList changes, fixes for wxXt, improved makefiles
  29  *
  30  * Revision 1.2  1998/05/14 16:39:31  VZ
  31  *
  32  * fixed SIGSEGV in ~kbList if the list is empty
  33  *
  34  * Revision 1.1  1998/05/13 19:02:11  KB
  35  * added kbList, adapted MimeTypes for it, more python, new icons
  36  *
  37  *******************************************************************/
  38
  39 #ifdef __GNUG__
  40 #   pragma implementation "kbList.h"
  41 #endif
  42
  43 #ifdef   M_BASEDIR
  44 #   include   "Mconfig.h"
  45 #endif
  46
  47 #include   "kbList.h"
  48
  49 kbListNode::kbListNode( void *ielement,
  50                         kbListNode *iprev,
  51                         kbListNode *inext)
  52 {
  53    next = inext;
  54    prev = iprev;
  55    if(prev)
  56       prev->next = this;
  57    if(next)
  58       next->prev = this;
  59    element = ielement;
  60 }
  61
  62 kbListNode::~kbListNode()
  63 {
  64    if(prev)
  65       prev->next = next;
  66    if(next)
  67       next->prev = prev;
  68 }
  69
  70
  71 kbList::iterator::iterator(kbListNode *n)
  72 {
  73    node = n;
  74 }
  75
  76 void *
  77 kbList::iterator::operator*()
  78 {
  79    return node->element;
  80 }
  81
  82 kbList::iterator &
  83 kbList::iterator::operator++()
  84 {
  85    node  = node ? node->next : NULL;
  86    return *this;
  87 }
  88
  89 kbList::iterator &
  90 kbList::iterator::operator--()
  91 {
  92    node = node ? node->prev : NULL;
  93    return *this;
  94 }
  95 kbList::iterator &
  96 kbList::iterator::operator++(int foo)
  97 {
  98    return operator++();
  99 }
 100
 101 kbList::iterator &
 102 kbList::iterator::operator--(int bar)
 103 {
 104    return operator--();
 105 }
 106
 107
 108 bool
 109 kbList::iterator::operator !=(kbList::iterator const & i) const
 110 {
 111    return node != i.node;
 112 }
 113
 114 bool
 115 kbList::iterator::operator ==(kbList::iterator const & i) const
 116 {
 117    return node == i.node;
 118 }
 119
 120 kbList::kbList(bool ownsEntriesFlag)
 121 {
 122    first = NULL;
 123    last = NULL;
 124    ownsEntries = ownsEntriesFlag;
 125 }
 126
 127 void
 128 kbList::push_back(void *element)
 129 {
 130    if(! first) // special case of empty list
 131    {
 132       first = new kbListNode(element);
 133       last = first;
 134       return;
 135    }
 136    else
 137       last = new kbListNode(element, last);
 138 }
 139
 140 void
 141 kbList::push_front(void *element)
 142 {
 143    if(! first) // special case of empty list
 144    {
 145       push_back(element);
 146       return;
 147    }
 148    else
 149       first = new kbListNode(element, NULL, first);
 150 }
 151
 152 void *
 153 kbList::pop_back(void)
 154 {
 155    iterator i;
 156    void *data;
 157    bool ownsFlagBak = ownsEntries;
 158    i = tail();
 159    data = *i;
 160    ownsEntries = false;
 161    erase(i);
 162    ownsEntries = ownsFlagBak;
 163    return data;
 164 }
 165
 166 void *
 167 kbList::pop_front(void)
 168 {
 169    iterator i;
 170    void *data;
 171    bool ownsFlagBak = ownsEntries;
 172
 173    i = begin();
 174    data = *i;
 175    ownsEntries = false;
 176    erase(i);
 177    ownsEntries = ownsFlagBak;
 178    return data;
 179
 180 }
 181
 182 void
 183 kbList::insert(kbList::iterator & i, void *element)
 184 {
 185    if(! i.Node())
 186       return;
 187    else if(i.Node() == first)
 188    {
 189       push_front(element);
 190       i = first;
 191       return;
 192    }
 193    i = kbList::iterator(new kbListNode(element, i.Node()->prev, i.Node()));
 194 }
 195
 196 void
 197 kbList::erase(kbList::iterator & i)
 198 {
 199    kbListNode
 200       *node = i.Node(),
 201       *prev, *next;
 202
 203    if(! node) // illegal iterator
 204       return;
 205
 206    prev = node->prev;
 207    next = node->next;
 208
 209    // correct first/last:
 210    if(node == first)
 211       first = node->next;
 212    if(node == last)  // don't put else here!
 213       last = node->prev;
 214
 215    // build new links:
 216    if(prev)
 217       prev->next = next;
 218    if(next)
 219       next->prev = prev;
 220
 221    // delete this node and contents:
 222    if(ownsEntries)
 223       delete *i;
 224    delete i.Node();
 225
 226    // change the iterator to next element:
 227    i = kbList::iterator(next);
 228 }
 229
 230 kbList::~kbList()
 231 {
 232    kbListNode *next;
 233
 234    while ( first != NULL )
 235    {
 236       next = first->next;
 237       if(ownsEntries)
 238          delete first->element;
 239       delete first;
 240       first = next;
 241    }
 242 }
 243
 244 kbList::iterator
 245 kbList::begin(void) const
 246 {
 247    return kbList::iterator(first);
 248 }
 249
 250 kbList::iterator
 251 kbList::tail(void) const
 252 {
 253    return kbList::iterator(last);
 254 }
 255
 256 kbList::iterator
 257 kbList::end(void) const
 258 {
 259    return kbList::iterator(NULL); // the one after the last
 260 }
 261
 262 unsigned
 263 kbList::size(void) const // inefficient
 264 {
 265    unsigned count = 0;
 266    kbList::iterator i;
 267    for(i = begin(); i != end(); i++, count++)
 268       ;
 269    return count;
 270 }
 271
 272
 273
 274
 275
 276
 277
 278 #ifdef   KBLIST_TEST
 279
 280 #include   <iostream.h>
 281
 282 KBLIST_DEFINE(kbListInt,int);
 283
 284 int main(void)
 285 {
 286    int
 287       n, *ptr;
 288    kbListInt
 289       l;
 290    kbListInt::iterator
 291       i;
 292
 293    for(n = 0; n < 10; n++)
 294    {
 295       ptr = new int;
 296       *ptr = n*n;
 297       l.push_back(ptr);
 298    }
 299
 300    i = l.begin(); // first element
 301    i++; // 2nd
 302    i++; // 3rd
 303    i++; // 4th, insert here:
 304    ptr = new int;
 305    *ptr = 4444;
 306    l.insert(i,ptr);
 307
 308    // this cannot work, because l.end() returns NULL:
 309    i = l.end(); // behind last
 310    i--;  // still behind last
 311    l.erase(i);  // doesn't do anything
 312
 313    // this works:
 314    i = l.tail(); // last element
 315    i--;
 316    --i;
 317    l.erase(i); // erase 3rd last element (49)
 318
 319    for(i = l.begin(); i != l.end(); i++)
 320       cout << *i << '\t' << *((int *)*i) << endl;
 321
 322
 323    return 0;
 324 }
 325 #endif