vector.h

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

#ifndef VECTOR_H
#define VECTOR_H
//
//  vector class, copyright 1996, S Zeil, Old Dominion Univ.
//                derived from draft ANSI/ISO C++ standard
//       Permission is granted to copy, distribute and prepare
//       derivative works without charge provided only that
//       this copyright notice is retained.
//
//  This is a "light" version of the standard vector class,
//  designed for use with the variety of compilers currently
//  in use at ODU, including gcc/g++ 2.6.8, Borland Turbo C/C++
//  4.5 (Windows), and Borland Turbo C/C++ 3.1 (MSDOS).
//

#include <algae/config.h>
#include <algae/assert.h>
#include <algae/stdlib.h>

#include <limits.h>

#ifdef PLACEMENT_NEW
#include <new.h>
#define VTYPE T
#define AT(p) *(p)
#ifdef __TCPLUSPLUS__
#include <alloc.h>
#endif
#else
#define VTYPE T*
#define AT(p) *(*(p))
#endif

template <class T>
class vector;

template <class T>
class vector_iterator;


template <class T>
class vector_const_iterator
{
protected:
  const vector<T>* container;
  const VTYPE* position;
  friend class vector<T>;

  vector_const_iterator (const vector<T>* c, const VTYPE* p)
    : container(c), position(p) {}
  friend class vector_iterator<T>;

public:
  vector_const_iterator(): container(0), position(0) {}

  const T& operator*() const  {assert (container != 0); return AT(position);}

  vector_const_iterator& operator++ () // prefix
    {assert ((container != 0)
	     && ((VTYPE*)position < container->data+container->xSize));
     position++;
     return *this;}

  vector_const_iterator operator++ (int)  // postfix: int argument is ignored
    {assert ((container != 0)
	     && ((VTYPE*)position < container->data+container->xSize));
     position++;
     return vector_const_iterator<T>(container, position-1);}

  vector_const_iterator& operator-- () // prefix
    {assert ((container != 0)
	     && ((VTYPE*)position >= container->data));
     position--;
     return *this;}

  vector_const_iterator operator-- (int)  // postfix: int argument is ignored
    {assert ((container != 0)
	     && ((VTYPE*)position >= container->data));
     position--;
     return vector_const_iterator<T>(container, position+1);}

  vector_const_iterator operator+ (unsigned long n) const
    {
      assert (container != 0);
      return vector_const_iterator<T>(container, position+n);
    }
  vector_const_iterator operator- (unsigned long n) const
    {
      assert (container != 0);
      return vector_const_iterator<T>(container, position-n);
    }
  unsigned long operator- (const vector_const_iterator& i) const
    {
      assert ((container != 0) && (container == i.container) 
	      && (position >= i.position));
      return position - i.position;
    }
  bool operator== (const vector_const_iterator& i) const
    {
      assert ((container != 0) && (container == i.container));
      return (position == i.position);
    }
  bool operator!= (const vector_const_iterator& i) const
    {
      assert ((container != 0) && (container == i.container));
      return (position != i.position);
    }
};

template <class T>
class vector_iterator:  public vector_const_iterator<T>
{
private:
  vector_iterator (const vector<T>* c, const VTYPE* p)
    : vector_const_iterator<T>(c,p) {}
  friend class vector<T>;

public:
  vector_iterator(): vector_const_iterator<T>() {}

  T& operator*() const  {return (T&)(AT(position));}

  vector_iterator& operator++ () // prefix
    {assert ((container != 0)
	     && ((VTYPE*)position < container->data+container->xSize));
     position++;
     return *this;}

  vector_iterator operator++ (int)  // postfix: int argument is ignored
    {assert ((container != 0)
	     && ((VTYPE*)position < container->data+container->xSize));
     position++;
     return vector_iterator<T>(container, position-1);}

  vector_iterator& operator-- () // prefix
    {assert ((container != 0)
	     && ((VTYPE*)position >= container->data));
     position--;
     return *this;}

  vector_iterator operator-- (int)  // postfix: int argument is ignored
    {assert ((container != 0)
	     && ((VTYPE*)position >= container->data));
     position--;
     return vector_iterator<T>(container, position+1);}

  vector_iterator operator+ (unsigned long n) const
    {
      assert (container != 0);
      return vector_iterator<T>(container, position+n);
    }
  vector_iterator operator- (unsigned long n) const
    {
      assert (container != 0);
      return vector_iterator<T>(container, position-n);
    }

  unsigned long operator- (const vector_iterator& i) const
    {
      assert ((container != 0) && (container == i.container) 
	      && (position >= i.position));
      return position - i.position;
    }
};




template  <class T>
class vector {
public:
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef T& reference;
  typedef const T& const_reference;
  #define Size_type unsigned int
  typedef Size_type size_type;
  typedef int difference_type;
  #define Iterator vector_iterator<T>
  typedef Iterator iterator;
  #define Const_iterator vector_const_iterator<T>
  typedef Const_iterator const_iterator;

private:
  size_type xSize;
  size_type xCapacity;
  typedef VTYPE ArrayElement;
  VTYPE* data;


  friend class iterator;
  friend class const_iterator;

public:
// Constructors & Destructors

  vector();
  //post: size() == 0

  vector(Size_type n, const T& value =T());
  //  vector v(n, t);
  //post: size() == n &&  ((0 <= i < n) => (v[i] == t))

  vector(const vector& x);
  //  vector v(x);
  //post: v == x

  vector(const_iterator first,
         const_iterator last);
  //  vector v (f, l);
  //post:  (v.size() == l-f) &&
  //       for (p = first; p != last; p++)
  //          *p == v[p-first]

  ~vector();


// Copying

  vector& operator=(const vector& x);
  //  v = x;
  //post:  v == x

  void swap(vector& x);
  //  v = v0;  x = x0;  v.swap(x);
  //post:  v == x0 && x == v0 && ((v0 == x0) == (v == x))

// Iterators

  iterator begin();
  const_iterator begin() const;
  //inv: v.size() > 0  =>  *(v.begin()) == v[0]


  iterator end();
  const_iterator end() const;
  //inv: v.size() > 0  =>  *(v.end()-1) == v[v.size()-1]


// Size and capacity
  size_type size() const;
  size_type max_size() const;
  size_type capacity() const;

  //inv: capacity() <= max_size()
  //inv: size() <= capacity()

  bool empty() const;
  //inv: v.empty() == (v.size() == 0)

  void reserve(Size_type n);
  //pre: n <= max_size()
  //post:  capacity() >= n


// Access

  T& operator[](Size_type n);
  const T& operator[](Size_type n) const;
  //pre: n >= 0 && n < size()

  T& front();
  const T& front() const;
  //pre: size() > 0

  //inv: v.front() == v[0]

  T& back();
  const T& back() const;
  //pre: size() > 0

  //inv: v.back() == v[size()-1]


// Insertion
  void push_back(const T& x);
  //pre: size() < max_size()
  // v0 = v; v.push_back (x);
  //post: v.size() == v0.size()+1
  //      && v.back() == x
  //      && for (i = 0; i < v0.size(); i++)
  //            v0[i] == v[i]

  iterator insert(Iterator position,
                  const T& x);
  //pre: size() < max_size()
  // v0 = v; k = p - v.begin(); v.insert (p, x);
  //post: v.size() == v0.size()+1
  //      && for (i = 0; i < k; i++)
  //            v0[i] == v[i]
  //      && v[k] == x
  //      && for (i = k+1; i < v0.size(); i++)
  //            v0[i] == v[i+1]

  void insert (Iterator position,
               Const_iterator first,
               Const_iterator last);
  //pre: size() + last - first <= max_size()
  // v0 = v; k = p - v.begin(); v.insert (p, f, l);
  //post: v.size() == v0.size()+l-f
  //      && for (i = 0; i < k; i++)
  //            v0[i] == v[i]
  //      && for (i = k; i < k+l-f; i++)
  //            v[i] == *(f+i-k)
  //      && for (i = k+l-f; i < v0.size(); i++)
  //            v0[i] == v[i+l-f]

  void insert (Iterator position,
               Size_type n, const T& x);
  //pre: size() + n <= max_size()
  // v0 = v; k = p - v.begin(); v.insert (p, n x);
  //post: v.size() == v0.size()+n
  //      && for (i = 0; i < k; i++)
  //            v0[i] == v[i]
  //      && for (i = k; i < k+n; i++)
  //            v[i] == x
  //      && for (i = k+n; i < v0.size(); i++)
  //            v0[i] == v[i+n]


// Removal
  void pop_back();
  //pre: size() > 0
  // v0 = v; v.pop_back ();
  //post: v.size() == v0.size()-1
  //      && for (i = 0; i < v.size(); i++)
  //            v0[i] == v[i]

  void erase(Iterator position);
  //pre: size() > 0
  // v0 = v; k = p - v.begin(); v.erase (p);
  //post: v.size() == v0.size()11
  //      && for (i = 0; i < k; i++)
  //            v0[i] == v[i]
  //      && for (i = k+1; i < v.size(); i++)
  //            v0[i] == v[i-1]

  void erase(Iterator first, Iterator last);
  //pre: size() >= last - first
  // v0 = v; k = f - begin(); n = l - f; v.erase (f, l);
  //post: v.size() == v0.size()-n
  //      && for (i = 0; i < k; i++)
  //            v0[i] == v[i]
  //      && for (i = k; i < v.size(); i++)
  //            v0[i+n] == v[i]


private:

  struct T2 {T t1; T t2;};
  struct T3 {T t1; T t2; T t3;};

  void initialize (T*);
};




template <class T>
bool operator== (const vector<T>& left,
		 const vector<T>& right)
{
  if (left.size() == right.size())
    {
      for (int i = 0; i < left.size(); i++)
	if (!(left[i] == right[i]))
	  return false;
      return true;
    }
  else
    return false;
}

template <class T>
bool operator< (const vector<T>& left,
		const vector<T>& right)
{
  vector<T>::size_type sz = left.size();
  if (sz > right.size())
    sz = right.size();

  for (int i = 0; i < sz; i++)
    if (left[i] < right[i])
      return true;
    else if (right[i] < left[i])
      return false;
  return (left.size() < right.size());
}


///////////////////////////////////////////////
#define ValidIterator(p, d) assert(p.container == this \
                                   && (VTYPE*)(p.position) >= (VTYPE*)data \
                                   && (VTYPE*)(p.position) <= (VTYPE*)data + xSize - d)
#define ValidRange(f, l, c) assert(f.container == l.container && \
                                   f.container == c);\
                            assert (c != 0); \
                            assert ((VTYPE*)(f.position) >= (VTYPE*)(c->data));\
                            assert (f.position <= l.position);\
                            assert ((VTYPE*)(l.position) <= (VTYPE*)(c->data)+c->xSize)


// Constructors & Destructors

template <class T>
vector<T>::vector(): xCapacity(0), xSize(0), data(0)
{
  reserve(4);
}


template <class T>
void vector<T>::initialize (T* address)
{
#ifdef PLACEMENT_NEW
  // Force construction of element at address
  new (address) T();
#endif
}