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