qtools/qglist.h

   1 /****************************************************************************
   2 **
   3 **
   4 ** Definition of QGList and QGListIterator classes
   5 **
   6 ** Created : 920624
   7 **
   8 ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
   9 **
  10 ** This file is part of the tools module of the Qt GUI Toolkit.
  11 **
  12 ** This file may be distributed under the terms of the Q Public License
  13 ** as defined by Trolltech AS of Norway and appearing in the file
  14 ** LICENSE.QPL included in the packaging of this file.
  15 **
  16 ** This file may be distributed and/or modified under the terms of the
  17 ** GNU General Public License version 2 as published by the Free Software
  18 ** Foundation and appearing in the file LICENSE.GPL included in the
  19 ** packaging of this file.
  20 **
  21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
  22 ** licenses may use this file in accordance with the Qt Commercial License
  23 ** Agreement provided with the Software.
  24 **
  25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27 **
  28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
  29 **   information about Qt Commercial License Agreements.
  30 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
  31 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
  32 **
  33 ** Contact info@trolltech.com if any conditions of this licensing are
  34 ** not clear to you.
  35 **
  36 **********************************************************************/
  37
  38 #ifndef QGLIST_H
  39 #define QGLIST_H
  40
  41 #ifndef QT_H
  42 #include "qcollection.h"
  43 #endif // QT_H
  44
  45
  46 /*****************************************************************************
  47   QLNode class (internal doubly linked list node)
  48  *****************************************************************************/
  49
  50 class Q_EXPORT QLNode
  51 {
  52 friend class QGList;
  53 friend class QGListIterator;
  54 public:
  55     QCollection::Item getData() { return data; }
  56 private:
  57     QCollection::Item data;
  58     QLNode *prev;
  59     QLNode *next;
  60     QLNode( QCollection::Item d ) { data = d; }
  61 };
  62
  63
  64 /*****************************************************************************
  65   QGList class
  66  *****************************************************************************/
  67
  68 class Q_EXPORT QGList : public QCollection      // doubly linked generic list
  69 {
  70 friend class QGListIterator;
  71 friend class QGVector;                          // needed by QGVector::toList
  72 public:
  73     uint  count() const;                        // return number of nodes
  74
  75 #ifndef QT_NO_DATASTREAM
  76     QDataStream &read( QDataStream & );         // read list from stream
  77     QDataStream &write( QDataStream & ) const;  // write list to stream
  78 #endif
  79 protected:
  80     QGList();                                   // create empty list
  81     QGList( const QGList & );                   // make copy of other list
  82     virtual ~QGList();
  83
  84     QGList &operator=( const QGList & );        // assign from other list
  85     bool operator==( const QGList& ) const;
  86
  87     void inSort( QCollection::Item );           // add item sorted in list
  88     void append( QCollection::Item );           // add item at end of list
  89     bool insertAt( uint index, QCollection::Item ); // add item at i'th position
  90     void relinkNode( QLNode * );                // relink as first item
  91     bool removeNode( QLNode * );                // remove node
  92     bool remove( QCollection::Item = 0 );       // remove item (0=current)
  93     bool removeRef( QCollection::Item = 0 );    // remove item (0=current)
  94     bool removeFirst();                         // remove first item
  95     bool removeLast();                          // remove last item
  96     bool removeAt( uint index );                // remove item at i'th position
  97     QCollection::Item takeNode( QLNode * );     // take out node
  98     QCollection::Item take();                   // take out current item
  99     QCollection::Item takeAt( uint index );     // take out item at i'th pos
 100     QCollection::Item takeFirst();              // take out first item
 101     QCollection::Item takeLast();               // take out last item
 102
 103     void sort();                        // sort all items;
 104     void clear();                       // remove all items
 105
 106     int  findRef( QCollection::Item, bool = TRUE ); // find exact item in list
 107     int  find( QCollection::Item, bool = TRUE ); // find equal item in list
 108
 109     uint containsRef( QCollection::Item ) const; // get number of exact matches
 110     uint contains( QCollection::Item )  const;  // get number of equal matches
 111
 112     QCollection::Item at( uint index );         // access item at i'th pos
 113     int   at() const;                           // get current index
 114     QLNode *currentNode() const;                // get current node
 115
 116     QCollection::Item get() const;              // get current item
 117
 118     QCollection::Item cfirst() const;   // get ptr to first list item
 119     QCollection::Item clast()  const;   // get ptr to last list item
 120     QCollection::Item first();          // set first item in list curr
 121     QCollection::Item last();           // set last item in list curr
 122     QCollection::Item next();           // set next item in list curr
 123     QCollection::Item prev();           // set prev item in list curr
 124
 125     void  toVector( QGVector * ) const;         // put items in vector
 126
 127     virtual int compareItems( QCollection::Item, QCollection::Item );
 128
 129 #ifndef QT_NO_DATASTREAM
 130     virtual QDataStream &read( QDataStream &, QCollection::Item & );
 131     virtual QDataStream &write( QDataStream &, QCollection::Item ) const;
 132 #endif
 133 private:
 134     void  prepend( QCollection::Item ); // add item at start of list
 135
 136     void heapSortPushDown( QCollection::Item* heap, int first, int last );
 137
 138     QLNode *firstNode;                          // first node
 139     QLNode *lastNode;                           // last node
 140     QLNode *curNode;                            // current node
 141     int     curIndex;                           // current index
 142     uint    numNodes;                           // number of nodes
 143     QGList *iterators;                          // list of iterators
 144
 145     QLNode *locate( uint );                     // get node at i'th pos
 146     QLNode *unlink();                           // unlink node
 147 };
 148
 149
 150 inline uint QGList::count() const
 151 {
 152     return numNodes;
 153 }
 154
 155 inline bool QGList::removeFirst()
 156 {
 157     first();
 158     return remove();
 159 }
 160
 161 inline bool QGList::removeLast()
 162 {
 163     last();
 164     return remove();
 165 }
 166
 167 inline int QGList::at() const
 168 {
 169     return curIndex;
 170 }
 171
 172 inline QCollection::Item QGList::at( uint index )
 173 {
 174     QLNode *n = locate( index );
 175     return n ? n->data : 0;
 176 }
 177
 178 inline QLNode *QGList::currentNode() const
 179 {
 180     return curNode;
 181 }
 182
 183 inline QCollection::Item QGList::get() const
 184 {
 185     return curNode ? curNode->data : 0;
 186 }
 187
 188 inline QCollection::Item QGList::cfirst() const
 189 {
 190     return firstNode ? firstNode->data : 0;
 191 }
 192
 193 inline QCollection::Item QGList::clast() const
 194 {
 195     return lastNode ? lastNode->data : 0;
 196 }
 197
 198
 199 /*****************************************************************************
 200   QGList stream functions
 201  *****************************************************************************/
 202
 203 #ifndef QT_NO_DATASTREAM
 204 Q_EXPORT QDataStream &operator>>( QDataStream &, QGList & );
 205 Q_EXPORT QDataStream &operator<<( QDataStream &, const QGList & );
 206 #endif
 207
 208 /*****************************************************************************
 209   QGListIterator class
 210  *****************************************************************************/
 211
 212 class Q_EXPORT QGListIterator                   // QGList iterator
 213 {
 214 friend class QGList;
 215 protected:
 216     QGListIterator( const QGList & );
 217     QGListIterator( const QGListIterator & );
 218     QGListIterator &operator=( const QGListIterator & );
 219    ~QGListIterator();
 220
 221     bool  atFirst() const;                      // test if at first item
 222     bool  atLast()  const;                      // test if at last item
 223     QCollection::Item     toFirst();                            // move to first item
 224     QCollection::Item     toLast();                             // move to last item
 225
 226     QCollection::Item     get() const;                          // get current item
 227     QCollection::Item     operator()();                         // get current and move to next
 228     QCollection::Item     operator++();                         // move to next item (prefix)
 229     QCollection::Item     operator+=(uint);                     // move n positions forward
 230     QCollection::Item     operator--();                         // move to prev item (prefix)
 231     QCollection::Item     operator-=(uint);                     // move n positions backward
 232
 233 protected:
 234     QGList *list;                               // reference to list
 235
 236 private:
 237     QLNode  *curNode;                           // current node in list
 238 };
 239
 240
 241 inline bool QGListIterator::atFirst() const
 242 {
 243     return curNode == list->firstNode;
 244 }
 245
 246 inline bool QGListIterator::atLast() const
 247 {
 248     return curNode == list->lastNode;
 249 }
 250
 251 inline QCollection::Item QGListIterator::get() const
 252 {
 253     return curNode ? curNode->data : 0;
 254 }
 255
 256
 257 #endif  // QGLIST_H