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