vector.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

template <class T>
vector<T>::vector(Size_type n, const T& value)
   : xCapacity(0), xSize(0), data(0)
{
  reserve(n);
  xSize = n;
  for (size_type i = 0; i < n; i++)
#ifdef PLACEMENT_NEW
    new (data+i) T(value);
#else
    data[i] = new T(value);
#endif
}


template <class T>
vector<T>::vector(const vector<T>& x): xCapacity(0), xSize(0), data(0)
{
  reserve (x.xSize);
  xSize = x.xSize;
  for (size_type i = 0; i < xSize; i++)
#ifdef PLACEMENT_NEW
    new (data+i) T(x.data[i]);
#else
    data[i] = new T(*(x.data[i]));
#endif
}

template <class T>
vector<T>::vector(Const_iterator first,
               Const_iterator last)
    : xCapacity(0), xSize(0), data(0)
{
  ValidRange (first, last, first.container);
  reserve (last - first);
  xSize = last - first;
  for (size_type i = 0; i < xSize; i++)
#ifdef PLACEMENT_NEW
    new (data+i) T(first.position[i]);
#else
    data[i] = new T(AT(first.position+i));
#endif
}

template <class T>
vector<T>::~vector()
{
#ifdef PLACEMENT_NEW
  for (size_type i = 0; i < xSize; i++)
    (data+i)->~T();
  free (data);
#else
  for (size_type i = 0; i < xSize; i++)
    delete data[i];
  delete [] data;
#endif
}


// Copying

template <class T>
vector<T>& vector<T>::operator=(const vector<T>& x)
{
  if (this != &x)
    {
      if (xSize > x.xSize)
        erase(begin()+x.xSize, end());
      reserve (x.xSize);
      unsigned i;
#ifdef PLACEMENT_NEW
      for (i = xSize; i < x.xSize; i++)
        initialize(data+i);
#endif
      for (i = 0; i < x.xSize; i++)
#ifdef PLACEMENT_NEW
        data[i] = x.data[i];
#else
        if (i >= xSize)
          data[i] = new T(*(x.data[i]));
        else
          *(data[i]) = *(x.data[i]);
#endif
      xSize = x.xSize;
    }
  return *this;
}

template <class T>
void vector<T>::swap(vector<T>& x)
{
  {
    size_type tmp = xCapacity;
    xCapacity = x.xCapacity;
    x.xCapacity = tmp;

    tmp = xSize;
    xSize = x.xSize;
    x.xSize = tmp;
  }
  {
    VTYPE* tmp = data;
    data = x.data;
    x.data = tmp;
  }
}

// Iterators

template <class T>
Iterator vector<T>::begin()
{
  return iterator(this, (const VTYPE*)data);
}

template <class T>
Const_iterator vector<T>::begin() const
{
  return iterator((vector<T>*)this, (const VTYPE*)data);
}


template <class T>
Iterator vector<T>::end()
{
  return iterator(this, (const VTYPE*)data + xSize);
}

template <class T>
Const_iterator vector<T>::end() const
{
  return iterator((vector<T>*)this, (const VTYPE*)data + xSize);
}


// Size and capacity
template <class T>
Size_type vector<T>::size() const
{
  return xSize;
}

template <class T>
Size_type vector<T>::max_size() const
{
  return INT_MAX / (sizeof(T3) - sizeof(T2));
}

template <class T>
Size_type vector<T>::capacity() const
{
  return xCapacity;
}


template <class T>
bool vector<T>::empty() const
{
  return (xSize == 0);
}


#ifdef __TCPLUSPLUS__
template <class T>
void destroy (T* ptr)
{
  ptr->~T();
}
#endif

template <class T>
void vector<T>::reserve(Size_type n)
{
  assert (n <= max_size());
  if (n > xCapacity)
    {
      int k = 4;
      if (n <= max_size()/2)
        while (k < n)  k *= 2;
      else
        k = max_size();
#ifdef PLACEMENT_NEW
      T* newData = (T*)malloc(k * (sizeof(T3) - sizeof(T2)));
      for (int i = 0; i < xSize; i++)
        {
         new (newData+i) T (data[i]);
         (data+i)->~T();
        }
      if (data != 0)
        free (data);
#else
      ArrayElement* newData = new ArrayElement[k];
      for (int i = 0; i < xSize; i++)
        newData[i] = data[i];
      delete [] data;
#endif
      data = newData;
      xCapacity = k;
    }
}


// Access

template <class T>
T& vector<T>::operator[](Size_type n)
{
  assert (n >= 0 && n < xSize);
  return AT(data+n);
}

template <class T>
const T& vector<T>::operator[](Size_type n) const
{
  assert (n >= 0 && n < xSize);
  return AT(data+n);
}

template <class T>
T& vector<T>::front()
{
  assert (xSize > 0);
  return AT(data);
}

template <class T>
const T& vector<T>::front() const
{
  assert (xSize > 0);
  return AT(data);
}


template <class T>
T& vector<T>::back()
{
  assert (xSize > 0);
  return AT(data+xSize-1);
}

template <class T>
const T& vector<T>::back() const
{
  assert (xSize > 0);
  return AT(data+xSize-1);
}



// Insertion
template <class T>
void vector<T>::push_back(const T& x)
{
  assert (xSize < max_size());
  reserve (xSize+1);
#ifdef PLACEMENT_NEW
  new (data+xSize) T(x);
#else
  data[xSize] = new T(x);
#endif
  xSize++;
}

template <class T>
Iterator vector<T>::insert(Iterator position,
                        const T& x)
{
  assert (xSize < max_size());
  ValidIterator (position, 0);
  size_type pos = (VTYPE*)(position.position) - (VTYPE*)data;
  reserve (xSize+1);
#ifdef PLACEMENT_NEW
  initialize(data+xSize);
#endif
  for (size_type p = xSize; p != pos; p--)
    data[p] = data[p-1];
#ifdef PLACEMENT_NEW
  data[pos] = x;
#else
  data[pos] = new T(x);
#endif
  xSize++;
  return position;
}

template <class T>
void vector<T>::insert (Iterator position,
                     Const_iterator first,
                     Const_iterator last)
{
  size_type n = last - first;
  assert ((unsigned long)(xSize + n) < max_size());
  ValidIterator (position, 0);
  ValidRange (first, last, first.container);

  size_type pos = (VTYPE*)(position.position) - (VTYPE*)data;
  reserve (xSize + n);
#ifdef PLACEMENT_NEW
  {
   for (int i = 0; i < n; i++)
     initialize(data+xSize+i);
  }
#endif
  {
   for (size_type p = xSize; p != pos; p--)
     data[p+n-1] = data[p-1];
  }
  {
   VTYPE* p = data + pos;
   for (const_iterator q = first; q != last; q++)
     {
#ifdef PLACEMENT_NEW
       *p = *q;
#else
       *p = new T(*q);
#endif
       p++;
     }
  }
  xSize += n;
}

template <class T>
void vector<T>::insert (Iterator position,
                     Size_type n, const T& x)
{
  assert ((unsigned long)(xSize + n) < max_size());
  ValidIterator (position, 0);
  size_type pos = (VTYPE*)(position.position) - (VTYPE*)data;
  reserve (xSize + n);
#ifdef PLACEMENT_NEW
  {
   for (int i = 0; i < n; i++)
     initialize(data+xSize+i);
  }
#endif
  {
   for (size_type p = xSize; p != pos; p--)
     data[p+n-1] = data[p-1];
  }
  {
   VTYPE* p = data + pos;
   for (size_type q = 0; q < n; q++)
     {
#ifdef PLACEMENT_NEW
       *p = x;
#else
       *p = new T(x);
#endif
       p++;
     }
  }
  xSize += n;
}


// Removal
template <class T>
void vector<T>::pop_back()
{
  assert (xSize > 0);
  xSize--;
#ifdef PLACEMENT_NEW
  (data+xSize)->~T();
#else
  delete data[xSize];
#endif
}

template <class T>
void vector<T>::erase(Iterator position)
{
  assert (xSize > 0);
  ValidIterator (position, 1);

  for (iterator p = position+1; p != end(); p++)
    *(p-1) = *p;
  xSize--;
#ifdef PLACEMENT_NEW
  (data+xSize)->~T();
#else
  delete data[xSize];
#endif
}

template <class T>
void vector<T>::erase(Iterator first, Iterator last)
{
  assert (xSize >= last - first);
  ValidRange(first, last, this);
  size_type ifirst = (VTYPE*)(first.position) - (VTYPE*)data;
  size_type ilast = (VTYPE*)(last.position) - (VTYPE*)data;
#ifndef PLACEMENT_NEW
  {
   for (int i = ifirst; i < ilast; ++i)
     delete data[i];
  }
#endif
  int p = ifirst;
  for (int q = ilast; q < xSize; q++)
    {
      data[p] = data[q];
      p++;
    }
  xSize -= (last - first);
#ifdef PLACEMENT_NEW
  for (T* t = data+xSize; t != data+xSize+(last-first); t++)
    t->~T();
#endif
}


#undef Size_type
#undef Iterator
#undef Const_iterator

#endif