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