/****************************************************************************

**

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

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

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

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

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

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

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

**

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

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

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

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#ifndef LIST_H

#define LIST_H

#include "smallobject.h"

#include <QtGlobal>

QT_BEGIN_NAMESPACE

template <typename T>

class List

{

    struct Data

    {

        int alloc, size;

        T array[1];

    };

    pool *p;

    Data *d;

public:

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

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

    inline ~List() { d = 0; }

    List &operator=(const List &v);

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

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

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

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

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

    void reserve(int alloc);

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

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

    void clear();

    const T &at(int i) const;

    T &operator[](int i);

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

    void append(const T &t);

    void prepend(const T &t);

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

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

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

    void remove(int i);

    void remove(int i, int n);

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

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

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

    bool contains(const T &t) const;

    int count(const T &t) const;

    // STL-style

    typedef T* iterator;

    typedef const T* const_iterator;

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

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

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

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

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

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

    iterator erase(iterator begin, iterator end);

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

    // more Qt

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

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

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

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

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

    T value(int i) const;

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

    // STL compatibility

    typedef T value_type;

    typedef value_type* pointer;

    typedef const value_type* const_pointer;

    typedef value_type& reference;

    typedef const value_type& const_reference;

#ifndef QT_NO_STL

    typedef ptrdiff_t difference_type;

#else

    typedef int difference_type;

#endif

    typedef iterator Iterator;

    typedef const_iterator ConstIterator;

    typedef int size_type;

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

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

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

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

    inline bool empty() const

    { return d->size == 0; }

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

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

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

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

    //comfort

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

    inline List operator+(const List &l) const

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

    inline void operator+=(const T &t)

    { append(t); }

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

    { append(t); return *this; }

private:

    Data *malloc(int alloc);

};

template <typename T>

inline void List<T>::clear()

{ d->size = 0; }

template <typename T>

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

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

  return d->array[i]; }

template <typename T>

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

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

  return d->array[i]; }

template <typename T>

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

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

  return d->array[i]; }

template <typename T>

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

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

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

template <typename T>

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

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

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

template <typename T>

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

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

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

template <typename T>

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

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

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

template <typename T>

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

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

template <typename T>

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

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

  data()[i] = t; }

template <typename T>

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

{

    p = v.p;

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

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

    return *this;

}

template <typename T>

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

{

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

}

template <typename T>

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

{

    if (alloc <= d->alloc)

        return;

    alloc <<= 2;

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

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

    d->alloc = alloc;

}

template<typename T>

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

{

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

        return T();

    }

    return d->array[i];

}

template<typename T>

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

{

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

}

template <typename T>

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

{

    reserve(d->size + 1);

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

}

template <typename T>

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

{

    int p = before - d->array;

    if (n != 0) {

        reserve(d->size + n);

        T *b = d->array+p;

        T *i = b+n;

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

        while (i != b)

            *(--i) = t;

    }

    d->size += n;

    return d->array+p;

}

template <typename T>

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

{

    int f = begin - d->array;

    int l = end - d->array;

    int n = l - f;

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

    d->size -= n;

    return d->array + f;

}

template <typename T>

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

{

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

        return false;

    T* b = d->array;

    T* i = b + d->size;

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

    while (i != b)

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

            return false;

    return true;

}

template <typename T>

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

{

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

    if (d->size) {

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

        T* b = d->array;

        while (i != b)

            *--i = t;

    }

    return *this;

}

template <typename T>

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

{

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

    reserve(newSize);

    T *w = d->array + newSize;

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

    T *b = l.d->array;

    while (i != b)

        *--w = *--i;

    d->size = newSize;

    return *this;

}

template <typename T>

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

{

    if (from < 0)

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

    if (from < d->size) {

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

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

        while (++n != e)

            if (*n == t)

                return n - d->array;

    }

    return -1;

}

template <typename T>

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

{

    if (from < 0)

        from += d->size;

    else if (from >= d->size)

        from = d->size-1;

    if (from >= 0) {

        T* b = d->array;

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

        while (n != b) {

            if (*--n == t)

                return n - b;

        }

    }

    return -1;

}

template <typename T>

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

{

    T* b = d->array;

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

    while (i != b)

        if (*--i == t)

            return true;

    return false;

}

template <typename T>

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

{

    int c = 0;

    T* b = d->array;

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

    while (i != b)

        if (*--i == t)

            ++c;

    return c;

}

QT_END_NAMESPACE

#endif // LIST_H