/***********************************************************************
*
* Copyright (c) 2012-2016 Barbara Geller
* Copyright (c) 2012-2016 Ansel Sermersheim
* Copyright (c) 2012-2014 Digia Plc and/or its subsidiary(-ies).
* Copyright (c) 2008-2012 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
*
* This file is part of CopperSpice.
*
* CopperSpice is free software: you can redistribute it and/or 
* modify it under the terms of the GNU Lesser General Public License
* version 2.1 as published by the Free Software Foundation.
*
* CopperSpice is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with CopperSpice.  If not, see 
* <http://www.gnu.org/licenses/>.
*
***********************************************************************/

#ifndef QLIST_H
#define QLIST_H

#include <qalgorithms.h>
#include <qrefcount.h>

#include <iterator>
#include <list>
#include <iterator>
#include <initializer_list>

#include <exception>
#include <stdexcept>
#include <new>
#include <limits.h>
#include <string.h>

#ifdef Q_CC_CLANG
#include <sstream>
#endif

QT_BEGIN_NAMESPACE

template <typename T>
class QVector;

template <typename T>
class QSet;

struct Q_CORE_EXPORT QListData {
   struct Data {
      QtPrivate::RefCount ref;
      int alloc, begin, end;
      uint sharable : 1;
      void *array[1];
   };
   enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };

   Data *detach(int alloc);
   Data *detach_grow(int *i, int n);
   Data *detach();  // remove in 5.0
   Data *detach2(); // remove in 5.0
   Data *detach3(); // remove in 5.0
   void realloc(int alloc);

   static Data *sharedNull();

   Data *d;
   void **erase(void **xi);
   void **append(int n);
   void **append();
   void **append(const QListData &l);
   void **append2(const QListData &l); // remove in 5.0
   void **prepend();
   void **insert(int i);
   void remove(int i);
   void remove(int i, int n);
   void move(int from, int to);

   inline int size() const {
      return d->end - d->begin;
   }
   inline bool isEmpty() const {
      return d->end  == d->begin;
   }
   inline void **at(int i) const {
      return d->array + d->begin + i;
   }
   inline void **begin() const {
      return d->array + d->begin;
   }
   inline void **end() const {
      return d->array + d->end;
   }
};

template <typename T>
class QList
{
   struct Node {
      void *v;
      Q_INLINE_TEMPLATE T &t() {
         return *reinterpret_cast<T *>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic
                                       ? v : this);
      }

   };

   union {
      QListData p;
      QListData::Data *d;
   };

 public:
   QList() : d( QListData::sharedNull() ) { }

   inline QList(const QList<T> &l) : d(l.d) {
      d->ref.ref();
      if (!d->sharable) {
         detach_helper();
      }
   }
   ~QList();
   QList<T> &operator=(const QList<T> &l);

   inline QList &operator=(QList && other) {
      qSwap(d, other.d);
      return *this;
   }

   inline void swap(QList<T> &other) {
      qSwap(d, other.d);
   }


   QList(std::initializer_list<T> args) : d( QListData::sharedNull() ) {
      qCopy(args.begin(), args.end(), std::back_inserter(*this));
   }

   bool operator==(const QList<T> &l) const;
   inline bool operator!=(const QList<T> &l) const {
      return !(*this == l);
   }

   typedef int size_type;
   typedef T value_type;
   typedef value_type *pointer;
   typedef const value_type *const_pointer;
   typedef value_type &reference;
   typedef const value_type &const_reference;
   typedef qptrdiff difference_type;

   inline int size() const {
      return p.size();
   }

   inline void detach() {
      if (d->ref.isShared()) {
         detach_helper();
      }
   }

   inline void detachShared() {
      // The "this->" qualification is needed for GCCE.
      if (d->ref.isShared() && this->d != QListData::sharedNull()) {
         detach_helper();
      }
   }

   inline bool isDetached() const {
      return ! d->ref.isShared();
   }
   inline void setSharable(bool sharable) {
      if (!sharable) {
         detach();
      }
      if ( d != QListData::sharedNull() ) {
         d->sharable = sharable;
      }
   }
   inline bool isSharedWith(const QList<T> &other) const {
      return d == other.d;
   }

   inline bool isEmpty() const {
      return p.isEmpty();
   }

   void clear();

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

   void reserve(int size);
   void append(const T &t);
   void append(const QList<T> &t);
   void prepend(const T &t);
   void insert(int i, const T &t);
   void replace(int i, const T &t);
   void removeAt(int i);
   int removeAll(const T &t);
   bool removeOne(const T &t);
   T takeAt(int i);
   T takeFirst();
   T takeLast();
   void move(int from, int to);
   void swap(int i, int j);
   int indexOf(const T &t, int from = 0) const;
   difference_type lastIndexOf(const T &t, int from = -1) const;
   QBool contains(const T &t) const;
   int count(const T &t) const;

   class const_iterator;

   class iterator
   {
    public:
      Node *i;
      typedef std::random_access_iterator_tag  iterator_category;
      typedef qptrdiff difference_type;
      typedef T value_type;
      typedef T *pointer;
      typedef T &reference;

      inline iterator() : i(0) {}
      inline iterator(Node *n) : i(n) {}
      inline iterator(const iterator &o): i(o.i) {}
      inline T &operator*() const {
         return i->t();
      }
      inline T *operator->() const {
         return &i->t();
      }
      inline T &operator[](int j) const {
         return i[j].t();
      }
      inline bool operator==(const iterator &o) const {
         return i == o.i;
      }
      inline bool operator!=(const iterator &o) const {
         return i != o.i;
      }
      inline bool operator<(const iterator &other) const {
         return i < other.i;
      }
      inline bool operator<=(const iterator &other) const {
         return i <= other.i;
      }
      inline bool operator>(const iterator &other) const {
         return i > other.i;
      }
      inline bool operator>=(const iterator &other) const {
         return i >= other.i;
      }
#ifndef QT_STRICT_ITERATORS
      inline bool operator==(const const_iterator &o) const {
         return i == o.i;
      }
      inline bool operator!=(const const_iterator &o) const {
         return i != o.i;
      }
      inline bool operator<(const const_iterator &other) const {
         return i < other.i;
      }
      inline bool operator<=(const const_iterator &other) const {
         return i <= other.i;
      }
      inline bool operator>(const const_iterator &other) const {
         return i > other.i;
      }
      inline bool operator>=(const const_iterator &other) const {
         return i >= other.i;
      }
#endif
      inline iterator &operator++() {
         ++i;
         return *this;
      }
      inline iterator operator++(int) {
         Node *n = i;
         ++i;
         return n;
      }
      inline iterator &operator--() {
         i--;
         return *this;
      }
      inline iterator operator--(int) {
         Node *n = i;
         i--;
         return n;
      }
      inline iterator &operator+=(int j) {
         i += j;
         return *this;
      }
      inline iterator &operator-=(int j) {
         i -= j;
         return *this;
      }
      inline iterator operator+(int j) const {
         return iterator(i + j);
      }
      inline iterator operator-(int j) const {
         return iterator(i - j);
      }
      inline int operator-(iterator j) const {
         return int(i - j.i);
      }
   };
   friend class iterator;

   class const_iterator
   {
    public:
      Node *i;
      typedef std::random_access_iterator_tag  iterator_category;
      typedef qptrdiff difference_type;
      typedef T value_type;
      typedef const T *pointer;
      typedef const T &reference;

      inline const_iterator() : i(0) {}
      inline const_iterator(Node *n) : i(n) {}
      inline const_iterator(const const_iterator &o): i(o.i) {}
#ifdef QT_STRICT_ITERATORS
      inline explicit const_iterator(const iterator &o): i(o.i) {}
#else
      inline const_iterator(const iterator &o): i(o.i) {}
#endif
      inline const T &operator*() const {
         return i->t();
      }
      inline const T *operator->() const {
         return &i->t();
      }
      inline const T &operator[](int j) const {
         return i[j].t();
      }
      inline bool operator==(const const_iterator &o) const {
         return i == o.i;
      }
      inline bool operator!=(const const_iterator &o) const {
         return i != o.i;
      }
      inline bool operator<(const const_iterator &other) const {
         return i < other.i;
      }
      inline bool operator<=(const const_iterator &other) const {
         return i <= other.i;
      }
      inline bool operator>(const const_iterator &other) const {
         return i > other.i;
      }
      inline bool operator>=(const const_iterator &other) const {
         return i >= other.i;
      }
      inline const_iterator &operator++() {
         ++i;
         return *this;
      }
      inline const_iterator operator++(int) {
         Node *n = i;
         ++i;
         return n;
      }
      inline const_iterator &operator--() {
         i--;
         return *this;
      }
      inline const_iterator operator--(int) {
         Node *n = i;
         i--;
         return n;
      }
      inline const_iterator &operator+=(int j) {
         i += j;
         return *this;
      }
      inline const_iterator &operator-=(int j) {
         i -= j;
         return *this;
      }
      inline const_iterator operator+(int j) const {
         return const_iterator(i + j);
      }
      inline const_iterator operator-(int j) const {
         return const_iterator(i - j);
      }
      inline difference_type operator-(const_iterator j) const {
         return i - j.i;
      }
   };
   friend class const_iterator;

   // stl style
   inline iterator begin() {
      detach();
      return reinterpret_cast<Node *>(p.begin());
   }
   inline const_iterator begin() const {
      return reinterpret_cast<Node *>(p.begin());
   }
   inline const_iterator cbegin() const {
      return reinterpret_cast<Node *>(p.begin());
   }
   inline const_iterator constBegin() const {
      return reinterpret_cast<Node *>(p.begin());
   }
   inline iterator end() {
      detach();
      return reinterpret_cast<Node *>(p.end());
   }
   inline const_iterator end() const {
      return reinterpret_cast<Node *>(p.end());
   }
   inline const_iterator cend() const {
      return reinterpret_cast<Node *>(p.end());
   }
   inline const_iterator constEnd() const {
      return reinterpret_cast<Node *>(p.end());
   }
   iterator insert(iterator before, const T &t);
   iterator erase(iterator pos);
   iterator erase(iterator first, iterator last);

   // more Qt
   typedef iterator Iterator;
   typedef const_iterator ConstIterator;
   inline int count() const {
      return p.size();
   }
   inline int length() const {
      return p.size();   // Same as count()
   }
   inline T &first() {
      Q_ASSERT(!isEmpty());
      return *begin();
   }
   inline const T &first() const {
      Q_ASSERT(!isEmpty());
      return at(0);
   }
   T &last() {
      Q_ASSERT(!isEmpty());
      return *(--end());
   }
   const T &last() const {
      Q_ASSERT(!isEmpty());
      return at(count() - 1);
   }
   inline void removeFirst() {
      Q_ASSERT(!isEmpty());
      erase(begin());
   }
   inline void removeLast() {
      Q_ASSERT(!isEmpty());
      erase(--end());
   }
   inline bool startsWith(const T &t) const {
      return !isEmpty() && first() == t;
   }
   inline bool endsWith(const T &t) const {
      return !isEmpty() && last() == t;
   }
   QList<T> mid(int pos, int length = -1) const;

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

   // stl compatibility
   inline void push_back(const T &t) {
      append(t);
   }
   inline void push_front(const T &t) {
      prepend(t);
   }
   inline T &front() {
      return first();
   }
   inline const T &front() const {
      return first();
   }
   inline T &back() {
      return last();
   }
   inline const T &back() const {
      return last();
   }
   inline void pop_front() {
      removeFirst();
   }
   inline void pop_back() {
      removeLast();
   }
   inline bool empty() const {
      return isEmpty();
   }
   // comfort
   QList<T> &operator+=(const QList<T> &l);
   inline QList<T> operator+(const QList<T> &l) const {
      QList n = *this;
      n += l;
      return n;
   }

   inline QList<T> &operator+=(const T &t) {
      append(t);
      return *this;
   }

   inline QList<T> &operator<< (const T &t) {
      append(t);
      return *this;
   }

   inline QList<T> &operator<<(const QList<T> &l) {
      *this += l;
      return *this;
   }

   QVector<T> toVector() const;
   QSet<T> toSet() const;

   static QList<T> fromVector(const QVector<T> &vector);
   static QList<T> fromSet(const QSet<T> &set);

   static inline QList<T> fromStdList(const std::list<T> &list) {
      QList<T> tmp;
      qCopy(list.begin(), list.end(), std::back_inserter(tmp));
      return tmp;
   }
   inline std::list<T> toStdList() const {
      std::list<T> tmp;
      qCopy(constBegin(), constEnd(), std::back_inserter(tmp));
      return tmp;
   }

 private:
   Node *detach_helper_grow(int i, int n);
   void detach_helper(int alloc);
   void detach_helper();
   void free(QListData::Data *d);

   void node_construct(Node *n, const T &t);
   void node_destruct(Node *n);
   void node_copy(Node *from, Node *to, Node *src);
   void node_destruct(Node *from, Node *to);
};

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t)
{
   if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
      n->v = new T(t);
   } else if (QTypeInfo<T>::isComplex) {
      new (n) T(t);
   }
#if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__)
   // This violates pointer aliasing rules, but it is known to be safe (and silent)
   // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which
   // set the same define are assumed to be safe.
   else {
      *reinterpret_cast<T *>(n) = t;
   }
#else
   // This is always safe, but penaltizes unoptimized builds a lot.
   else {
      ::memcpy(n, &t, sizeof(T));
   }
#endif
}

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n)
{
   if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
      delete reinterpret_cast<T *>(n->v);
   } else if (QTypeInfo<T>::isComplex) {
      reinterpret_cast<T *>(n)->~T();
   }
}

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src)
{
   Node *current = from;
   if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
      QT_TRY {
         while (current != to)
         {
            current->v = new T(*reinterpret_cast<T *>(src->v));
            ++current;
            ++src;
         }
      } QT_CATCH(...) {
         while (current-- != from) {
            delete reinterpret_cast<T *>(current->v);
         }
         QT_RETHROW;
      }

   } else if (QTypeInfo<T>::isComplex) {
      QT_TRY {
         while (current != to)
         {
            new (current) T(*reinterpret_cast<T *>(src));
            ++current;
            ++src;
         }
      } QT_CATCH(...) {
         while (current-- != from) {
            (reinterpret_cast<T *>(current))->~T();
         }
         QT_RETHROW;
      }
   } else {
      if (src != from && to - from > 0) {
         memcpy(from, src, (to - from) * sizeof(Node *));
      }
   }
}

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to)
{
   if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)
      while (from != to) {
         --to, delete reinterpret_cast<T *>(to->v);
      }
   else if (QTypeInfo<T>::isComplex)
      while (from != to) {
         --to, reinterpret_cast<T *>(to)->~T();
      }
}

template <typename T>
Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l)
{
   if (d != l.d) {
      QListData::Data *o = l.d;
      o->ref.ref();

      if (!d->ref.deref()) {
         free(d);
      }

      d = o;
      if (!d->sharable) {
         detach_helper();
      }
   }

   return *this;
}

template <typename T>
inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t)
{
   int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin()));
   Node *n = reinterpret_cast<Node *>(p.insert(iBefore));

   QT_TRY {
      node_construct(n, t);
   } QT_CATCH(...) {
      p.remove(iBefore);
      QT_RETHROW;
   }

   return n;
}

template <typename T>
inline typename QList<T>::iterator QList<T>::erase(iterator it)
{
   node_destruct(it.i);
   return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void **>(it.i)));
}

template <typename T>
inline const T &QList<T>::at(int i) const
{
   if (i < 0 || i >= p.size()) {

#ifdef Q_CC_CLANG

      std::stringstream temp;
      temp << "QList<T>::at() Index is out of Range. (Index is " << i << ", Size is " << p.size() << ")";

      std::string msg = temp.str();

#else
      std::string msg = "QList<T>::at() Index is out of Range. (Index is " + std::to_string(i) +
                        ", Size is " + std::to_string(p.size()) + ")";
#endif

      throw std::logic_error(msg);
   }

   return reinterpret_cast<Node *>(p.at(i))->t();
}

template <typename T>
inline const T &QList<T>::operator[](int i) const
{
   if (i < 0 || i >= p.size()) {

#ifdef Q_CC_CLANG

      std::stringstream temp;
      temp << "QList<T>::operator[] Index is out of Range. (Index is " << i << ", Size is " << p.size() << ")";

      std::string msg = temp.str();

#else
      std::string msg = "QList<T>::operator[] Index is out of Range. (Index is " + std::to_string(i) +
                        ", Size is " + std::to_string(p.size()) + ")";
#endif

      throw std::logic_error(msg);
   }

   return reinterpret_cast<Node *>(p.at(i))->t();
}

template <typename T>
inline T &QList<T>::operator[](int i)
{
   if (i < 0 || i >= p.size()) {

#ifdef Q_CC_CLANG

      std::stringstream temp;
      temp << "QList<T>::operator[] Index is out of Range. (Index is " << i << ", Size is " << p.size() << ")";

      std::string msg = temp.str();

#else
      std::string msg = "QList<T>::operator[] Index is out of Range. (Index is " + std::to_string(i) +
                        ", Size is " + std::to_string(p.size()) + ")";
#endif

      throw std::logic_error(msg);
   }

   detach();
   return reinterpret_cast<Node *>(p.at(i))->t();
}

template <typename T>
inline void QList<T>::removeAt(int i)
{
   if ( i >= 0 && i < p.size()) {
      detach();
      node_destruct(reinterpret_cast<Node *>(p.at(i)));
      p.remove(i);
   }
}

template <typename T>
inline T QList<T>::takeAt(int i)
{
   if (i < 0 || i >= p.size()) {

#ifdef Q_CC_CLANG

      std::stringstream temp;
      temp << "QList<T>::takeAt() Index is out of Range. (Index is " << i << ", Size is " << p.size() << ")";

      std::string msg = temp.str();

#else
      std::string msg = "QList<T>::takeAt() Index is out of Range. (Index is " + std::to_string(i) +
                        ", Size is " + std::to_string(p.size()) + ")";
#endif

      throw std::logic_error(msg);
   }

   detach();
   Node *n = reinterpret_cast<Node *>(p.at(i));
   T t = n->t();
   node_destruct(n);
   p.remove(i);

   return t;
}

template <typename T>
inline T QList<T>::takeFirst()
{
   T t = first();
   removeFirst();
   return t;
}

template <typename T>
inline T QList<T>::takeLast()
{
   T t = last();
   removeLast();
   return t;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc)
{
   if (d->alloc < alloc) {
      if (d->ref.isShared()) {
         detach_helper(alloc);
      } else {
         p.realloc(alloc);
      }
   }
}

template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
{
   if (d->ref.isShared()) {
      Node *n = detach_helper_grow(INT_MAX, 1);

      QT_TRY {
         node_construct(n, t);

      } QT_CATCH(...) {
         --d->end;
         QT_RETHROW;
      }

   } else {
      if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.append());
         QT_TRY {
            node_construct(n, t);
         } QT_CATCH(...) {
            --d->end;
            QT_RETHROW;
         }
      } else {
         Node *n, copy;
         node_construct(&copy, t); // t might be a reference to an object in the array
         QT_TRY {
            n = reinterpret_cast<Node *>(p.append());;
         } QT_CATCH(...) {
            node_destruct(&copy);
            QT_RETHROW;
         }
         *n = copy;
      }
   }
}

template <typename T>
inline void QList<T>::prepend(const T &t)
{
   if (d->ref.isShared()) {
      Node *n = detach_helper_grow(0, 1);
      QT_TRY {
         node_construct(n, t);
      } QT_CATCH(...) {
         ++d->begin;
         QT_RETHROW;
      }
   } else {
      if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.prepend());
         QT_TRY {
            node_construct(n, t);
         } QT_CATCH(...) {
            ++d->begin;
            QT_RETHROW;
         }
      } else {
         Node *n, copy;
         node_construct(&copy, t); // t might be a reference to an object in the array
         QT_TRY {
            n = reinterpret_cast<Node *>(p.prepend());;
         } QT_CATCH(...) {
            node_destruct(&copy);
            QT_RETHROW;
         }
         *n = copy;
      }
   }
}

template <typename T>
inline void QList<T>::insert(int i, const T &t)
{
   if (d->ref.isShared()) {
      Node *n = detach_helper_grow(i, 1);
      QT_TRY {
         node_construct(n, t);
      } QT_CATCH(...) {
         p.remove(i);
         QT_RETHROW;
      }
   } else {
      if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
         Node *n = reinterpret_cast<Node *>(p.insert(i));
         QT_TRY {
            node_construct(n, t);
         } QT_CATCH(...) {
            p.remove(i);
            QT_RETHROW;
         }
      } else {
         Node *n, copy;
         node_construct(&copy, t); // t might be a reference to an object in the array
         QT_TRY {
            n = reinterpret_cast<Node *>(p.insert(i));;
         } QT_CATCH(...) {
            node_destruct(&copy);
            QT_RETHROW;
         }
         *n = copy;
      }
   }
}

template <typename T>
inline void QList<T>::replace(int i, const T &t)
{
   Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range");
   detach();
   reinterpret_cast<Node *>(p.at(i))->t() = t;
}

template <typename T>
inline void QList<T>::swap(int i, int j)
{
   Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(),
              "QList<T>::swap", "index out of range");
   detach();
   void *t = d->array[d->begin + i];
   d->array[d->begin + i] = d->array[d->begin + j];
   d->array[d->begin + j] = t;
}

template <typename T>
inline void QList<T>::move(int from, int to)
{
   Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(),
              "QList<T>::move", "index out of range");
   detach();
   p.move(from, to);
}

template<typename T>
Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const
{
   if (alength < 0 || pos + alength > size()) {
      alength = size() - pos;
   }
   if (pos == 0 && alength == size()) {
      return *this;
   }
   QList<T> cpy;
   if (alength <= 0) {
      return cpy;
   }
   cpy.reserve(alength);
   cpy.d->end = alength;
   QT_TRY {
      cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()),
      reinterpret_cast<Node *>(cpy.p.end()),
      reinterpret_cast<Node *>(p.begin() + pos));
   } QT_CATCH(...) {
      // restore the old end
      cpy.d->end = 0;
      QT_RETHROW;
   }
   return cpy;
}

template<typename T>
Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const
{
   if (i < 0 || i >= p.size()) {
      return T();
   }
   return reinterpret_cast<Node *>(p.at(i))->t();
}

template<typename T>
Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T &defaultValue) const
{
   return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t());
}

template <typename T>
Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c)
{
   Node *n = reinterpret_cast<Node *>(p.begin());
   QListData::Data *x = p.detach_grow(&i, c);
   QT_TRY {
      node_copy(reinterpret_cast<Node *>(p.begin()),
      reinterpret_cast<Node *>(p.begin() + i), n);
   } QT_CATCH(...) {
      qFree(d);
      d = x;
      QT_RETHROW;
   }
   QT_TRY {
      node_copy(reinterpret_cast<Node *>(p.begin() + i + c),
      reinterpret_cast<Node *>(p.end()), n + i);
   } QT_CATCH(...) {
      node_destruct(reinterpret_cast<Node *>(p.begin()),
                    reinterpret_cast<Node *>(p.begin() + i));
      qFree(d);
      d = x;
      QT_RETHROW;
   }

   if (!x->ref.deref()) {
      free(x);
   }

   return reinterpret_cast<Node *>(p.begin() + i);
}

template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc)
{
   Node *n = reinterpret_cast<Node *>(p.begin());
   QListData::Data *x = p.detach(alloc);
   QT_TRY {
      node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
   } QT_CATCH(...) {
      qFree(d);
      d = x;
      QT_RETHROW;
   }

   if (!x->ref.deref()) {
      free(x);
   }
}

template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
{
   detach_helper(d->alloc);
}

template <typename T>
Q_OUTOFLINE_TEMPLATE QList<T>::~QList()
{
   if (!d->ref.deref()) {
      free(d);
   }
}

template <typename T>
Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
{
   if (p.size() != l.p.size()) {
      return false;
   }
   if (d == l.d) {
      return true;
   }
   Node *i = reinterpret_cast<Node *>(p.end());
   Node *b = reinterpret_cast<Node *>(p.begin());
   Node *li = reinterpret_cast<Node *>(l.p.end());
   while (i != b) {
      --i;
      --li;
      if (!(i->t() == li->t())) {
         return false;
      }
   }
   return true;
}

// ### Qt5/rename freeData() to avoid confusion with std::free()
template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::free(QListData::Data *data)
{
   node_destruct(reinterpret_cast<Node *>(data->array + data->begin),
                 reinterpret_cast<Node *>(data->array + data->end));
   qFree(data);
}


template <typename T>
Q_OUTOFLINE_TEMPLATE void QList<T>::clear()
{
   *this = QList<T>();
}

template <typename T>
Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t)
{
   int index = indexOf(_t);
   if (index == -1) {
      return 0;
   }

   const T t = _t;
   detach();

   Node *i = reinterpret_cast<Node *>(p.at(index));
   Node *e = reinterpret_cast<Node *>(p.end());
   Node *n = i;
   node_destruct(i);
   while (++i != e) {
      if (i->t() == t) {
         node_destruct(i);
      } else {
         *n++ = *i;
      }
   }

   difference_type removedCount = e - n;
   d->end -= removedCount;
   return removedCount;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t)
{
   int index = indexOf(_t);
   if (index != -1) {
      removeAt(index);
      return true;
   }
   return false;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst,
      typename QList<T>::iterator alast)
{
   for (Node *n = afirst.i; n < alast.i; ++n) {
      node_destruct(n);
   }
   int idx = afirst - begin();
   p.remove(idx, alast - afirst);
   return begin() + idx;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l)
{
   if (!l.isEmpty()) {
      if (isEmpty()) {
         *this = l;
      } else {
         Node *n = (d->ref.isShared())
                   ? detach_helper_grow(INT_MAX, l.size())
                   : reinterpret_cast<Node *>(p.append2(l.p));
         QT_TRY {
            node_copy(n, reinterpret_cast<Node *>(p.end()),
            reinterpret_cast<Node *>(l.p.begin()));
         } QT_CATCH(...) {
            // restore the old end
            d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
            QT_RETHROW;
         }
      }
   }
   return *this;
}

template <typename T>
inline void QList<T>::append(const QList<T> &t)
{
   *this += t;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const
{
   if (from < 0) {
      from = qMax(from + p.size(), 0);
   }
   if (from < p.size()) {
      Node *n = reinterpret_cast<Node *>(p.at(from - 1));
      Node *e = reinterpret_cast<Node *>(p.end());
      while (++n != e)
         if (n->t() == t) {
            return int(n - reinterpret_cast<Node *>(p.begin()));
         }
   }
   return -1;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE typename QList<T>::difference_type QList<T>::lastIndexOf(const T &t, int from) const
{
   if (from < 0) {
      from += p.size();
   } else if (from >= p.size()) {
      from = p.size() - 1;
   }
   if (from >= 0) {
      Node *b = reinterpret_cast<Node *>(p.begin());
      Node *n = reinterpret_cast<Node *>(p.at(from + 1));
      while (n-- != b) {
         if (n->t() == t) {
            return n - b;
         }
      }
   }
   return -1;
}

template <typename T>
Q_OUTOFLINE_TEMPLATE QBool QList<T>::contains(const T &t) const
{
   Node *b = reinterpret_cast<Node *>(p.begin());
   Node *i = reinterpret_cast<Node *>(p.end());
   while (i-- != b)
      if (i->t() == t) {
         return QBool(true);
      }
   return QBool(false);
}

template <typename T>
Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const
{
   int c = 0;
   Node *b = reinterpret_cast<Node *>(p.begin());
   Node *i = reinterpret_cast<Node *>(p.end());
   while (i-- != b)
      if (i->t() == t) {
         ++c;
      }
   return c;
}


template <class T>
class QListIterator
{ 
   typedef typename QList<T>::const_iterator const_iterator;
   QList<T> c;
   const_iterator i;
   
   public:
      inline QListIterator(const QList<T> &container)
         : c(container), i(c.constBegin()) {}
   
      inline QListIterator &operator=(const QList<T> &container)
         { c = container; i = c.constBegin(); return *this; }
      
      inline void toFront() { i = c.constBegin(); } 
      inline void toBack() { i = c.constEnd(); } 
      inline bool hasNext() const { return i != c.constEnd(); } 
      inline const T &next() { return *i++; } 
      inline const T &peekNext() const { return *i; } 
      inline bool hasPrevious() const { return i != c.constBegin(); } 
      inline const T &previous() { return *--i; } 
      inline const T &peekPrevious() const { const_iterator p = i; return *--p; } 
      
      inline bool findNext(const T &t)  { 
         while (i != c.constEnd()) {
            if (*i++ == t) {
               return true; 
            }
         }
         return false;           
      }
      
      inline bool findPrevious(const T &t)   { 
         while (i != c.constBegin()) {
            if (*(--i) == t)  {
               return true; 
            }
         }  
         return false;                 
      }
};

template <class T>
class QMutableListIterator
{ 
   typedef typename QList<T>::iterator iterator;
   typedef typename QList<T>::const_iterator const_iterator;
   QList<T> *c;
   iterator i, n;
   inline bool item_exists() const { return const_iterator(n) != c->constEnd(); } 
   
   public:
      inline QMutableListIterator(QList<T> &container)
         : c(&container)
      { c->setSharable(false); i = c->begin(); n = c->end(); } 
      
      inline ~QMutableListIterator()
         { c->setSharable(true); }

      inline QMutableListIterator &operator=(QList<T> &container)
         { c->setSharable(true); c = &container; c->setSharable(false);

      i = c->begin(); n = c->end(); return *this; }
      inline void toFront() { i = c->begin(); n = c->end(); }
      inline void toBack() { i = c->end(); n = i; }
      inline bool hasNext() const { return c->constEnd() != const_iterator(i); }
      inline T &next() { n = i++; return *n; }
      inline T &peekNext() const { return *i; }
      inline bool hasPrevious() const { return c->constBegin() != const_iterator(i); }
      inline T &previous() { n = --i; return *n; }
      inline T &peekPrevious() const { iterator p = i; return *--p; }

      inline void remove()
         { if (c->constEnd() != const_iterator(n)) { i = c->erase(n); n = c->end(); } }

      inline void setValue(const T &t) const { if (c->constEnd() != const_iterator(n)) *n = t; }
      inline T &value() { Q_ASSERT(item_exists()); return *n; }
      inline const T &value() const { Q_ASSERT(item_exists()); return *n; }
      inline void insert(const T &t) { n = i = c->insert(i, t); ++i; } 

      inline bool findNext(const T &t) 
         { while (c->constEnd() != const_iterator(n = i)) if (*i++ == t) return true; return false; } 

      inline bool findPrevious(const T &t) 
         { while (c->constBegin() != const_iterator(i)) if (*(n = --i) == t) return true; 

      n = c->end(); return false;  } 
};

QT_END_NAMESPACE

#endif // QLIST_H
