1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the qt3to4 porting application of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef LIST_H

    43 #define LIST_H

    44 

    45 #include "smallobject.h"

    46 #include <QtGlobal>

    47 

    48 QT_BEGIN_NAMESPACE

    49 

    50 template <typename T>

    51 class List

    52 {

    53     struct Data

    54     {

    55         int alloc, size;

    56         T array[1];

    57     };

    58     pool *p;

    59     Data *d;

    60 

    61 public:

    62     inline List(pool *_pool) : p(_pool), d(0) { d = malloc(16); d->size = 0; d->alloc = 16; }

    63 

    64     inline List(const List &v) : d(0) { operator=(v); }

    65     inline ~List() { d = 0; }

    66     List &operator=(const List &v);

    67 

    68     bool operator==(const List &v) const;

    69     inline bool operator!=(const List &v) const { return !(*this == v); }

    70 

    71     inline int size() const { return d->size; }

    72     inline bool isEmpty() const { return d->size == 0; }

    73 

    74     inline int capacity() const { return d->alloc; }

    75     void reserve(int alloc);

    76 

    77     inline T* data() { return d->array; }

    78     inline const T* data() const { return d->array; }

    79     void clear();

    80 

    81     const T &at(int i) const;

    82     T &operator[](int i);

    83     const T &operator[](int i) const;

    84     void append(const T &t);

    85     void prepend(const T &t);

    86     void insert(int i, const T &t);

    87     void insert(int i, int n, const T &t);

    88     void replace(int i, const T &t);

    89     void remove(int i);

    90     void remove(int i, int n);

    91 

    92     List &fill(const T &t, int size = -1);

    93 

    94     int indexOf(const T &t, int from = 0) const;

    95     int lastIndexOf(const T &t, int from = -1) const;

    96     bool contains(const T &t) const;

    97     int count(const T &t) const;

    98 

    99     // STL-style

   100     typedef T* iterator;

   101     typedef const T* const_iterator;

   102     inline iterator begin() { return d->array; }

   103     inline const_iterator begin() const { return d->array; }

   104     inline iterator end() { return d->array + d->size; }

   105     inline const_iterator end() const { return d->array + d->size; }

   106     iterator insert(iterator before, int n, const T &x);

   107     inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }

   108     iterator erase(iterator begin, iterator end);

   109     inline iterator erase(iterator pos) { return erase(pos, pos+1); }

   110 

   111     // more Qt

   112     inline int count() const { return d->size; }

   113     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }

   114     inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }

   115     inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }

   116     inline const T& last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }

   117 

   118     T value(int i) const;

   119     T value(int i, const T &defaultValue) const;

   120 

   121     // STL compatibility

   122     typedef T value_type;

   123     typedef value_type* pointer;

   124     typedef const value_type* const_pointer;

   125     typedef value_type& reference;

   126     typedef const value_type& const_reference;

   127 #ifndef QT_NO_STL

   128     typedef ptrdiff_t difference_type;

   129 #else

   130     typedef int difference_type;

   131 #endif

   132     typedef iterator Iterator;

   133     typedef const_iterator ConstIterator;

   134     typedef int size_type;

   135     inline void push_back(const T &t) { append(t); }

   136     inline void push_front(const T &t) { prepend(t); }

   137     void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }

   138     void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }

   139     inline bool empty() const

   140     { return d->size == 0; }

   141     inline T& front() { return first(); }

   142     inline const_reference front() const { return first(); }

   143     inline reference back() { return last(); }

   144     inline const_reference back() const { return last(); }

   145 

   146     //comfort

   147     List &operator+=(const List &l);

   148     inline List operator+(const List &l) const

   149     { List n = *this; n += l; return n; }

   150     inline void operator+=(const T &t)

   151     { append(t); }

   152     inline List &operator<< (const T &t)

   153     { append(t); return *this; }

   154 

   155 private:

   156     Data *malloc(int alloc);

   157 };

   158 

   159 template <typename T>

   160 inline void List<T>::clear()

   161 { d->size = 0; }

   162 

   163 template <typename T>

   164 inline const T &List<T>::at(int i) const

   165 { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::at", "index out of range");

   166   return d->array[i]; }

   167 template <typename T>

   168 inline const T &List<T>::operator[](int i) const

   169 { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");

   170   return d->array[i]; }

   171 template <typename T>

   172 inline T &List<T>::operator[](int i)

   173 { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");

   174   return d->array[i]; }

   175 template <typename T>

   176 inline void List<T>::insert(int i, const T &t)

   177 { Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");

   178   insert(begin()+i, 1, t); }

   179 template <typename T>

   180 inline void List<T>::insert(int i, int n, const T &t)

   181 { Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");

   182   insert(begin() + i, n, t); }

   183 template <typename T>

   184 inline void List<T>::remove(int i, int n)

   185 { Q_ASSERT_X(i >= 0 && i + n <= d->size, "List<T>::remove", "index out of range");

   186   erase(begin() + i, begin() + i + n); }

   187 template <typename T>

   188 inline void List<T>::remove(int i)

   189 { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::remove", "index out of range");

   190   erase(begin() + i, begin() + i + 1); }

   191 template <typename T>

   192 inline void List<T>::prepend(const T &t)

   193 { insert(begin(), 1, t); }

   194 template <typename T>

   195 inline void List<T>::replace(int i, const T &t)

   196 { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::replace", "index out of range");

   197   data()[i] = t; }

   198 

   199 template <typename T>

   200 List<T> &List<T>::operator=(const List<T> &v)

   201 {

   202     p = v.p;

   203     d = malloc(v.d->alloc);

   204     memcpy(d, v.d, sizeof(Data) + (v.d->size - 1) * sizeof(T));

   205     return *this;

   206 }

   207 

   208 template <typename T>

   209 inline typename List<T>::Data *List<T>::malloc(int alloc)

   210 {

   211     return static_cast<Data *>(p->allocate(sizeof(Data) + (alloc - 1) * sizeof(T)));

   212 }

   213 

   214 template <typename T>

   215 void List<T>::reserve(int alloc)

   216 {

   217     if (alloc <= d->alloc)

   218         return;

   219     alloc <<= 2;

   220     d = static_cast<Data *>(p->reallocate(d, sizeof(Data) + d->alloc * sizeof(T),

   221                                           sizeof(Data) + (alloc - 1) * sizeof(T)));

   222     d->alloc = alloc;

   223 }

   224 

   225 template<typename T>

   226 T List<T>::value(int i) const

   227 {

   228     if(i < 0 || i >= d->size) {

   229         return T();

   230     }

   231     return d->array[i];

   232 }

   233 template<typename T>

   234 T List<T>::value(int i, const T& defaultValue) const

   235 {

   236     return ((i < 0 || i >= d->size) ? defaultValue : d->array[i]);

   237 }

   238 

   239 template <typename T>

   240 void List<T>::append(const T &t)

   241 {

   242     reserve(d->size + 1);

   243     d->array[d->size++] = t;

   244 }

   245 

   246 

   247 template <typename T>

   248 typename List<T>::iterator List<T>::insert(iterator before, size_type n, const T& t)

   249 {

   250     int p = before - d->array;

   251     if (n != 0) {

   252         reserve(d->size + n);

   253         T *b = d->array+p;

   254         T *i = b+n;

   255         memmove(i, b, (d->size-p)*sizeof(T));

   256         while (i != b)

   257             *(--i) = t;

   258     }

   259     d->size += n;

   260     return d->array+p;

   261 }

   262 

   263 template <typename T>

   264 typename List<T>::iterator List<T>::erase(iterator begin, iterator end)

   265 {

   266     int f = begin - d->array;

   267     int l = end - d->array;

   268     int n = l - f;

   269     memmove(d->array + f, d->array + l, (d->size-l)*sizeof(T));

   270     d->size -= n;

   271     return d->array + f;

   272 }

   273 

   274 template <typename T>

   275 bool List<T>::operator==(const List<T> &v) const

   276 {

   277     if (d->size != v.d->size)

   278         return false;

   279     T* b = d->array;

   280     T* i = b + d->size;

   281     T* j = v.d->array + d->size;

   282     while (i != b)

   283         if (!(*--i == *--j))

   284             return false;

   285     return true;

   286 }

   287 

   288 template <typename T>

   289 List<T> &List<T>::fill(const T &t, int size)

   290 {

   291     resize(size < 0 ? d->size : size);

   292     if (d->size) {

   293         T* i = d->array + d->size;

   294         T* b = d->array;

   295         while (i != b)

   296             *--i = t;

   297     }

   298     return *this;

   299 }

   300 

   301 template <typename T>

   302 List<T> &List<T>::operator+=(const List &l)

   303 {

   304     int newSize = d->size + l.d->size;

   305     reserve(newSize);

   306 

   307     T *w = d->array + newSize;

   308     T *i = l.d->array + l.d->size;

   309     T *b = l.d->array;

   310     while (i != b)

   311         *--w = *--i;

   312     d->size = newSize;

   313     return *this;

   314 }

   315 

   316 template <typename T>

   317 int List<T>::indexOf(const T &t, int from) const

   318 {

   319     if (from < 0)

   320         from = qMax(from + d->size, 0);

   321     if (from < d->size) {

   322         T* n = d->array + from - 1;

   323         T* e = d->array + d->size;

   324         while (++n != e)

   325             if (*n == t)

   326                 return n - d->array;

   327     }

   328     return -1;

   329 }

   330 

   331 template <typename T>

   332 int List<T>::lastIndexOf(const T &t, int from) const

   333 {

   334     if (from < 0)

   335         from += d->size;

   336     else if (from >= d->size)

   337         from = d->size-1;

   338     if (from >= 0) {

   339         T* b = d->array;

   340         T* n = d->array + from + 1;

   341         while (n != b) {

   342             if (*--n == t)

   343                 return n - b;

   344         }

   345     }

   346     return -1;

   347 }

   348 

   349 template <typename T>

   350 bool List<T>::contains(const T &t) const

   351 {

   352     T* b = d->array;

   353     T* i = d->array + d->size;

   354     while (i != b)

   355         if (*--i == t)

   356             return true;

   357     return false;

   358 }

   359 

   360 template <typename T>

   361 int List<T>::count(const T &t) const

   362 {

   363     int c = 0;

   364     T* b = d->array;

   365     T* i = d->array + d->size;

   366     while (i != b)

   367         if (*--i == t)

   368             ++c;

   369     return c;

   370 }

   371 

   372 QT_END_NAMESPACE

   373 

   374 #endif // LIST_H