// Common/Vector.h

#ifndef __COMMON_VECTOR_H
#define __COMMON_VECTOR_H

#include "Defs.h"

class CBaseRecordVector
{
  void MoveItems(int destIndex, int srcIndex);
protected:
  int _capacity;
  int _size;
  void *_items;
  size_t _itemSize;
  
  void ReserveOnePosition();
  void InsertOneItem(int index);
  void TestIndexAndCorrectNum(int index, int &num) const
    { if (index + num > _size) num = _size - index; }
public:
  CBaseRecordVector(size_t itemSize): _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
  virtual ~CBaseRecordVector();
  void ClearAndFree();
  int Size() const { return _size; }
  bool IsEmpty() const { return (_size == 0); }
  void Reserve(int newCapacity);
  void ReserveDown();
  virtual void Delete(int index, int num = 1);
  void Clear();
  void DeleteFrom(int index);
  void DeleteBack();
};

template <class T>
class CRecordVector: public CBaseRecordVector
{
public:
  CRecordVector(): CBaseRecordVector(sizeof(T)){};
  CRecordVector(const CRecordVector &v): CBaseRecordVector(sizeof(T)) { *this = v; }
  CRecordVector& operator=(const CRecordVector &v)
  {
    Clear();
    return (*this += v);
  }
  CRecordVector& operator+=(const CRecordVector &v)
  {
    int size = v.Size();
    Reserve(Size() + size);
    for (int i = 0; i < size; i++)
      Add(v[i]);
    return *this;
  }
  int Add(T item)
  {
    ReserveOnePosition();
    ((T *)_items)[_size] = item;
    return _size++;
  }
  void Insert(int index, T item)
  {
    InsertOneItem(index);
    ((T *)_items)[index] = item;
  }
  // T* GetPointer() const { return (T*)_items; }
  // operator const T *() const { return _items; };
  const T& operator[](int index) const { return ((T *)_items)[index]; }
  T& operator[](int index) { return ((T *)_items)[index]; }
  const T& Front() const { return operator[](0); }
  T& Front() { return operator[](0); }
  const T& Back() const { return operator[](_size - 1); }
  T& Back() { return operator[](_size - 1); }

  void Swap(int i, int j)
  {
    T temp = operator[](i);
    operator[](i) = operator[](j);
    operator[](j) = temp;
  }

  int FindInSorted(const T& item, int left, int right) const
  {
    while (left != right)
    {
      int mid = (left + right) / 2;
      const T& midValue = (*this)[mid];
      if (item == midValue)
        return mid;
      if (item < midValue)
        right = mid;
      else
        left = mid + 1;
    }
    return -1;
  }

  int FindInSorted(const T& item) const
  {
    int left = 0, right = Size();
    while (left != right)
    {
      int mid = (left + right) / 2;
      const T& midValue = (*this)[mid];
      if (item == midValue)
        return mid;
      if (item < midValue)
        right = mid;
      else
        left = mid + 1;
    }
    return -1;
  }

  int AddToUniqueSorted(const T& item)
  {
    int left = 0, right = Size();
    while (left != right)
    {
      int mid = (left + right) / 2;
      const T& midValue = (*this)[mid];
      if (item == midValue)
        return mid;
      if (item < midValue)
        right = mid;
      else
        left = mid + 1;
    }
    Insert(right, item);
    return right;
  }

  static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param)
  {
    T temp = p[k];
    for (;;)
    {
      int s = (k << 1);
      if (s > size)
        break;
      if (s < size && compare(p + s + 1, p + s, param) > 0)
        s++;
      if (compare(&temp, p + s, param) >= 0)
        break;
      p[k] = p[s];
      k = s;
    }
    p[k] = temp;
  }

  void Sort(int (*compare)(const T*, const T*, void *), void *param)
  {
    int size = _size;
    if (size <= 1)
      return;
    T* p = (&Front()) - 1;
    {
      int i = size / 2;
      do
        SortRefDown(p, i, size, compare, param);
      while (--i != 0);
    }
    do
    {
      T temp = p[size];
      p[size--] = p[1];
      p[1] = temp;
      SortRefDown(p, 1, size, compare, param);
    }
    while (size > 1);
  }
};

typedef CRecordVector<int> CIntVector;
typedef CRecordVector<unsigned int> CUIntVector;
typedef CRecordVector<bool> CBoolVector;
typedef CRecordVector<unsigned char> CByteVector;
typedef CRecordVector<void *> CPointerVector;

template <class T>
class CObjectVector: public CPointerVector
{
public:
  CObjectVector() {};
  ~CObjectVector() { Clear(); };
  CObjectVector(const CObjectVector &v): CPointerVector() { *this = v; }
  CObjectVector& operator=(const CObjectVector &v)
  {
    Clear();
    return (*this += v);
  }
  CObjectVector& operator+=(const CObjectVector &v)
  {
    int size = v.Size();
    Reserve(Size() + size);
    for (int i = 0; i < size; i++)
      Add(v[i]);
    return *this;
  }
  const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
  T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
  T& Front() { return operator[](0); }
  const T& Front() const { return operator[](0); }
  T& Back() { return operator[](_size - 1); }
  const T& Back() const { return operator[](_size - 1); }
  int Add(const T& item) { return CPointerVector::Add(new T(item)); }
  void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); }
  virtual void Delete(int index, int num = 1)
  {
    TestIndexAndCorrectNum(index, num);
    for (int i = 0; i < num; i++)
      delete (T *)(((void **)_items)[index + i]);
    CPointerVector::Delete(index, num);
  }
  int Find(const T& item) const
  {
    for (int i = 0; i < Size(); i++)
      if (item == (*this)[i])
        return i;
    return -1;
  }
  int FindInSorted(const T& item) const
  {
    int left = 0, right = Size();
    while (left != right)
    {
      int mid = (left + right) / 2;
      const T& midValue = (*this)[mid];
      if (item == midValue)
        return mid;
      if (item < midValue)
        right = mid;
      else
        left = mid + 1;
    }
    return -1;
  }
  int AddToSorted(const T& item)
  {
    int left = 0, right = Size();
    while (left != right)
    {
      int mid = (left + right) / 2;
      const T& midValue = (*this)[mid];
      if (item == midValue)
      {
        right = mid + 1;
        break;
      }
      if (item < midValue)
        right = mid;
      else
        left = mid + 1;
    }
    Insert(right, item);
    return right;
  }

  void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
    { CPointerVector::Sort(compare, param); }

  static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
    { return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
  void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
};

#endif