samples/richedit/kbList.h

   1 /*-*- c++ -*-********************************************************
   2  * kbList.h : a double linked list                                  *
   3  *                                                                  *
   4  * (C) 1998-1999 by Karsten Ballüder (karsten@phy.hw.ac.uk)         *
   5  *                                                                  *
   6  * $Id$
   7  *
   8  *******************************************************************/
   9
  10
  11
  12 #ifndef   KBLIST_H
  13 #   define   KBLIST_H
  14
  15 #ifndef   NULL
  16 #   define   NULL   0
  17 #endif
  18
  19 /**@name Double linked list implementation. */
  20 //@{
  21
  22 /** kbListNode is a class used by kbList. It represents a single
  23     element in the list. It is not intended for general use outside
  24     kbList functions.
  25 */
  26 struct kbListNode
  27 {
  28    /// pointer to next node or NULL
  29    struct kbListNode *next;
  30    /// pointer to previous node or NULL
  31    struct kbListNode *prev;
  32    /// pointer to the actual data
  33    void *element;
  34    /** Constructor - it automatically links the node into the list, if
  35        the iprev, inext parameters are given.
  36        @param ielement pointer to the data for this node (i.e. the data itself)
  37        @param iprev if not NULL, use this as previous element in list
  38        @param inext if not NULL, use this as next element in list
  39    */
  40    kbListNode( void *ielement,
  41                kbListNode *iprev = NULL,
  42                kbListNode *inext = NULL);
  43    /// Destructor.
  44    ~kbListNode();
  45 };
  46
  47 /** The main list class, handling void pointers as data.
  48   */
  49
  50 class kbList
  51 {
  52 public:
  53    /// An iterator class for kbList, just like for the STL classes.
  54    class iterator
  55    {
  56    protected:
  57       /// the node to which this iterator points
  58       kbListNode *node;
  59       friend class kbList;
  60          public:
  61       /** Constructor.
  62           @param n if not NULL, the node to which to point
  63       */
  64       iterator(kbListNode *n = NULL);
  65       /** Dereference operator.
  66           @return the data pointer of the node belonging to this
  67           iterator
  68       */
  69       void * operator*();
  70
  71       /** This operator allows us to write if(i). It is <em>not</em> a
  72           dereference operator and the result is always useless apart
  73           from its logical value!
  74       */
  75       operator void*() const { return node == NULL ? (void*)0 : (void*)(-1); }
  76
  77
  78       /** Increment operator - prefix, goes to next node in list.
  79           @return itself
  80       */
  81       iterator & operator++();
  82
  83       /** Decrement operator - prefix, goes to previous node in list.
  84           @return itself
  85       */
  86       iterator & operator--();
  87
  88       /** Increment operator - prefix, goes to next node in list.
  89           @return itself
  90       */
  91       iterator & operator++(int); //postfix
  92
  93       /** Decrement operator - prefix, goes to previous node in list.
  94           @return itself
  95       */
  96       iterator & operator--(int); //postfix
  97
  98       /** Comparison operator.
  99           @return true if not equal.
 100       */
 101       bool operator !=(iterator const &) const;
 102
 103       /* Comparison operator.
 104          @return true if equal
 105       */
 106       bool operator ==(iterator const &) const;
 107
 108       /** Returns a pointer to the node associated with this iterator.
 109           This function is not for general use and should be
 110           protected. However, if protected, it cannot be called from
 111           derived classes' iterators. (Is this a bug in gcc/egcs?)
 112           @return the node pointer
 113       */
 114       inline kbListNode * Node(void) const
 115          { return node; }
 116    };
 117
 118    /** Constructor.
 119        @param ownsEntriesFlag if true, the list owns the entries and
 120        will issue a delete on each of them when deleting them. If
 121        false, the entries themselves will not get deleted. Do not use
 122        this with array types!
 123    */
 124    kbList(bool ownsEntriesFlag = true);
 125
 126    /** Destructor.
 127        If entries are owned, they will all get deleted from here.
 128    */
 129    ~kbList();
 130
 131    /** Tell list whether it owns objects. If owned, they can be
 132        deleted by list. See the constructor for more details.
 133        @param ownsflag if true, list will own entries
 134    */
 135    void ownsObjects(bool ownsflag)
 136       { ownsEntries = ownsflag; }
 137
 138    /** Query whether list owns entries.
 139        @return true if list owns entries
 140    */
 141    bool ownsObjects(void)
 142       { return ownsEntries; }
 143
 144    // This must be protected to disallow insertion of wrong elements.
 145 protected:
 146    /** Add an entry at the end of the list.
 147        @param element pointer to data
 148    */
 149    void push_back(void *element);
 150
 151    /** Add an entry at the head of the list.
 152        @param element pointer to data
 153    */
 154    void push_front(void *element);
 155
 156    /** Insert an element into the list.
 157        @param i an iterator pointing to the element, before which the new one should be inserted
 158        @param element the element data
 159    */
 160    void insert(iterator & i, void *element);
 161
 162 public:
 163    /** Get element from end of the list and delete it.
 164        NOTE: In this case the element's data will not get deleted by
 165        the list. It is the responsibility of the caller to free it.
 166        @return the element data
 167    */
 168    void * pop_back(void);
 169
 170    /** Get element from head of the list and delete it.
 171        NOTE: In this case the element's data will not get deleted by
 172        the list. It is the responsibility of the caller to free it.
 173        @return the element data
 174    */
 175    void * pop_front(void);
 176
 177    /** Remove an element from the list _without_ deleting the object.
 178        @param  i iterator pointing to the element to be deleted
 179        @return the value of the element just removed
 180    */
 181    void *remove(iterator& i) { void *p = *i; doErase(i); return p; }
 182
 183    /** Erase an element, move iterator to following element.
 184        @param i iterator pointing to the element to be deleted
 185    */
 186    void erase(iterator & i) { deleteContent(i); doErase(i); }
 187
 188    /* Get head of list.
 189       @return iterator pointing to head of list
 190    */
 191    iterator begin(void) const;
 192
 193    /* Get end of list.
 194    @return iterator pointing after the end of the list. This is an
 195    invalid iterator which cannot be dereferenced or decremented. It is
 196    only of use in comparisons. NOTE: this is different from STL!
 197    @see tail
 198    */
 199    iterator end(void) const;
 200
 201    /* Get last element in list.
 202       @return iterator pointing to the last element in the list.
 203       @see end
 204    */
 205    iterator tail(void) const;
 206
 207    /* Get the number of elements in the list.
 208       @return number of elements in the list
 209    */
 210    unsigned size(void) const;
 211
 212    /* Query whether list is empty.
 213       @return true if list is empty
 214    */
 215    inline bool empty(void) const
 216       { return first == NULL ; }
 217
 218 protected:
 219    /// if true, list owns entries
 220    bool        ownsEntries;
 221    /// pointer to first element in list
 222    kbListNode *first;
 223    /// pointer to last element in list
 224    kbListNode *last;
 225 protected:
 226    /** Erase an element, move iterator to following element.
 227        @param i iterator pointing to the element to be deleted
 228    */
 229    void doErase(iterator & i);
 230
 231    /** Deletes the actual content if ownsflag is set.
 232        param iterator i
 233    */
 234    inline void deleteContent(iterator i)
 235    {
 236       iterator *i_ptr = &i;
 237       if(ownsEntries) delete i_ptr;
 238    }
 239
 240
 241 private:
 242    /// forbid copy construction
 243    kbList(kbList const &foo);
 244    /// forbid assignments
 245    kbList& operator=(const kbList& foo);
 246 };
 247
 248 /// just for backward compatibility, will be removed soon
 249 typedef kbList::iterator kbListIterator;
 250 /// cast an iterator to a pointer, compatibility only to be removed
 251 #define   kbListICast(type, iterator)   ((type *)*iterator)
 252 /// cast an iterator to a const pointer, compatibility only to be removed
 253 #define   kbListIcCast(type, iterator)   ((type const *)*iterator)
 254
 255 /** Macro to define a kbList with a given name, having elements of
 256     pointer to the given type. I.e. KBLIST_DEFINE(Int,int) would
 257     create a kbListInt type holding int pointers.
 258 */
 259 #define   KBLIST_DEFINE(name,type)   \
 260 class name : public kbList \
 261 { \
 262 public: \
 263    class iterator : public kbList::iterator \
 264    { \
 265    protected: \
 266       inline iterator(kbList::iterator const & i) \
 267          { node = i.Node(); } \
 268       friend class name; \
 269    public: \
 270       inline iterator(kbListNode *n = NULL) \
 271          : kbList::iterator(n) {} \
 272       inline type * operator*() \
 273          /* the cast is needed for MS VC++ 5.0 */ \
 274          { return (type *)((kbList::iterator *)this)->operator*() ; } \
 275    }; \
 276    inline name(bool ownsEntriesFlag = true) \
 277       : kbList(ownsEntriesFlag) {} \
 278    \
 279    inline type *pop_back(void) \
 280       { return (type *) kbList::pop_back(); } \
 281    \
 282    inline type *pop_front(void) \
 283       { return (type *) kbList::pop_front(); } \
 284    inline void push_back(type *element) \
 285       { kbList::push_back( (void *) element); } \
 286    void push_front(type *element) \
 287       { kbList::push_front( (void *) element); } \
 288    void insert(iterator & i, void *element) \
 289       { kbList::insert( i, (void *) element); } \
 290    type *remove(iterator& i) \
 291       { return (type *)kbList::remove(i); } \
 292    inline void erase(iterator & i) \
 293       { deleteContent(i); doErase(i); } \
 294    \
 295    inline iterator begin(void) const \
 296       { return kbList::begin(); } \
 297    \
 298    inline iterator end(void) const \
 299       { return kbList::end(); } \
 300    \
 301    inline iterator tail(void) const \
 302       { return kbList::tail(); } \
 303    ~name() \
 304    { \
 305       kbListNode *next; \
 306       while ( first != NULL ) \
 307       { \
 308          next = first->next; \
 309          if(ownsEntries) \
 310             delete (type *)first->element; \
 311          delete first; \
 312          first = next; \
 313       } \
 314    } \
 315 protected: \
 316    inline void deleteContent(iterator i) \
 317       { if(ownsEntries) delete *i; } \
 318 }
 319
 320 #ifdef   MCONFIG_H
 321 /// define the most commonly used list type once:
 322 KBLIST_DEFINE(kbStringList, String);
 323 #endif
 324 //@}
 325
 326 #endif // KBLIST_H