/*

EGYPT Toolkit for Statistical Machine Translation
Written by Yaser Al-Onaizan, Jan Curin, Michael Jahr, Kevin Knight, John Lafferty, Dan Melamed, David Purdy, Franz Och, Noah Smith, and David Yarowsky.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 
USA.

*/
/*--
Vector: checked vector implementation

Franz Josef Och (30/07/99)
--*/
#ifndef ARRAY_H_DEFINED
#define ARRAY_H_DEFINED
#include "mystl.h"
#include <algorithm>
#include <string>
#include <utility>
#include <functional>
#include <cassert>


#ifdef NDEBUG

#include <vector>
#define Vector vector
template<class T> ostream& operator<<(ostream&o, const Vector<T>&a)
{
  o << "Vector(" << a.size() << "){ ";
  for(unsigned int iii=0;iii<a.size();iii++)
    o << " " << iii<< ": " << a[iii]<<" ;";
  return o << "}\n";
}

#else

#define ARRAY_DEBUG
#define memo_del(a, b)
#define memo_new(a)

template<class T> class Vector
{
 private:
  T *p;                  	
  int realSize;
  int maxWritten;

  void copy(T *a, const T *b, int n);
  void copy(T *a, T *b, int n);
  void _expand();
		
 public:
  Vector() 
    : p(0), realSize(0), maxWritten(-1)
    {
#ifdef VERY_ARRAY_DEBUG
      cout << "MAKE ARRAY: " << this<<" "<<(void*)p << '\n';
#endif
    }
  Vector(const Vector<T> &x)
    : p(new T[x.maxWritten+1]), realSize(x.maxWritten+1), maxWritten(x.maxWritten)
    {
      memo_new(p);
      copy(p, x.p, realSize);
#ifdef VERY_ARRAY_DEBUG
      cout << "MAKE ARRAY copy: " << this << " " << realSize <<" "<<(void*)p<< '\n';
#endif
    }
  explicit Vector(int n)
    : p(new T[n]), realSize(n), maxWritten(n-1)
    {
      memo_new(p);
#ifdef VERY_ARRAY_DEBUG
      cout << "MAKE ARRAY with parameter n: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
    }
  Vector(int n, const T&_init)
    : p(new T[n]), realSize(n), maxWritten(n-1)
    {
      memo_new(p);
      for(int iii=0;iii<n;iii++)p[iii]=_init;
#ifdef VERY_ARRAY_DEBUG
      cout << "MAKE ARRAY with parameter n and init: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
    }
  
  ~Vector() 
    { 
#ifdef VERY_ARRAY_DEBUG
      cout << "FREE ARRAY: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
      delete [] p;
      memo_del(p, 1);
#ifndef NDEBUG
      p=0;realSize=-1;maxWritten=-1;
#endif
    }
  
  Vector<T>& operator=(const Vector<T>&x)
    {
      if( this!= &x )
	{
#ifdef VERY_ARRAY_DEBUG
	  cout << "FREE ARRAY because of operator=: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif	
	  delete [] p;
	  memo_del(p, 1);
	  realSize = x.maxWritten+1;
	  maxWritten = x.maxWritten;
	  p = new T[realSize]; 
	  memo_new(p);
	  copy(p, x.p, realSize);
#ifdef VERY_ARRAY_DEBUG
	  cout << "NEW ARRAY because of operator=: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
	}
      return *this;
    }
  
  Vector<T>& operator=(Vector<T>&x)
    {
      if( this!= &x )
	{
#ifdef VERY_ARRAY_DEBUG
	  cout << "FREE ARRAY because of operator=: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
	  delete [] p;
	  memo_del(p, 1);
	  realSize = x.maxWritten+1;
	  maxWritten = x.maxWritten;
	  p = new T[realSize]; 
	  memo_new(p);
	  copy(p, x.p, realSize);
#ifdef VERY_ARRAY_DEBUG
	  cout << "NEW ARRAY because of operator=: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
	}
      return *this;
    }
  
  void allowAccess(int n) 
    { 
      while( realSize<=n )
	_expand(); 
      maxWritten=max(maxWritten, n);
      assert( maxWritten<realSize );
    }
  void resize(int n)
    {
      while( realSize<n ) 
	_expand(); 
      maxWritten=n-1;
    }
  void clear()
    {
      resize(0);
    }
  void reserve(int n)
    {
      int maxOld=maxWritten;
      resize(n);
      maxWritten=maxOld;
    }
  void sort(int until=-1)
    {
      if( until== -1 ) until=size();
      std::sort(p, p+until);
    }
  void invsort(int until=-1)
    {
      if( until== -1 ) until=size();
      std::sort(p, p+until, greater<T>());      
    }
  void init(int n, const T&_init)
    {
#ifdef VERY_ARRAY_DEBUG
      cout << "FREE ARRAY because of init: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
      delete []p;
      memo_del(p, 1);
      p=new T[n];
      memo_new(p);
      realSize=n;
      maxWritten=n-1;
      for(int iii=0;iii<n;iii++)p[iii]=_init;
#ifdef VERY_ARRAY_DEBUG
      cout << "NEW ARRAY because of init: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
    }
  inline unsigned int size() const
    {assert( maxWritten<realSize );
    return maxWritten+1;}
  inline int low() const
    { return 0; }
  inline int high() const
    { return maxWritten; }
  int findMax() const;
  int findMin() const;
  void errorAccess(int n) const;
  inline T*getPointerToData(){return p;}
  inline T*begin(){return p;}
  inline T*end(){return p+maxWritten+1;}
  inline T& operator[](int n)
    { 
#ifndef NDEBUG
      if( n<0 || n>maxWritten )
	errorAccess(n);
#endif
      return p[n];
    }
  inline const T& operator[](int n) const 
    { 
#ifndef NDEBUG
      if(n<0 || n>maxWritten )
	errorAccess(n);
#endif
      return p[n]; 
    }
  inline const T& get(int n) const 
    { 
#ifndef NDEBUG
      if(n<0 || n>maxWritten )
	errorAccess(n);
#endif      
      return p[n]; 
    }
  const T&top(int n=0) const
    {return (*this)[maxWritten-n];}
  T&top(int n=0)
    {return (*this)[maxWritten-n];}
  const T&back(int n=0) const
    {return (*this)[maxWritten-n];}
  T&back(int n=0)
    {return (*this)[maxWritten-n];}
  T&push_back(const T&x)
    {     
      allowAccess(maxWritten+1);
      (*this)[maxWritten]=x;
      return top();
    }
  bool writeTo(ostream&out) const
    {
      out << "Vector ";
      out << size() << " ";
      //out << a << '\n';
      for(int iv=0;iv<=maxWritten;iv++)
	{
	  writeOb(out, (*this)[iv]);
	  out << '\n';
	}
      return 1;
    }
  bool readFrom(istream&in)
    {
      string s;
      if( !in )
	{
	  cerr << "ERROR(Vector): file cannot be opened.\n";
	  return 0;
	}
      in >> s;
      if( !(s=="Vector") )
	{
	  cerr << "ERROR(Vector): Vector!='"<<s<<"'\n";
	  return 0;
	}
      int biggest;
      in >> biggest;
      //in >> a;
      resize(biggest);
      for(int iv=0;iv<size();iv++)
	{
	  readOb(in, (*this)[iv]);
	}
      return 1;
    }
};

template<class T> bool operator==(const Vector<T> &x, const Vector<T> &y)
{
  if( &x == &y )
    return 1;
  else
    {
      if( y.size()!=x.size() )
	return 0;
      else
	{
	  for(unsigned int iii=0;iii<x.size();iii++)
	    if( !(x[iii]==y[iii]) )
	      return 0;
	  return 1;
	}
    }
}
template<class T> bool operator!=(const Vector<T> &x, const Vector<T> &y)
{
  return !(x==y);
}

template<class T> bool operator<(const Vector<T> &x, const Vector<T> &y)
{
  if( &x == &y )
    return 0;
  else
    {
      if( y.size()<x.size() )
	return !(y<x);
      for(int iii=0;iii<x.size();iii++)
	{
	  assert( iii!=y.size() );
	  if( x[iii]<y[iii] )
	    return 1;
	  else if( y[iii]<x[iii] )
	    return 0;
	}
      return x.size()!=y.size();//??
    }
}


template<class T> void Vector<T>:: errorAccess(int n) const
{
  cerr 	<< "ERROR: Access to array element " << n 
	<< " (" << maxWritten << ", " << realSize << ", " << (void*)p << ")\n";
  cout <<  "ERROR: Access to array element " << n 
       << " (" << maxWritten << ", " << realSize << ", " << (void*)p << ")\n";
  assert(0);
#ifndef DEBUG
  abort();
#endif
}

template<class T> ostream& operator<<(ostream&o, const Vector<T>&a)
{
  o << "Vector(" << a.size() << "){ ";
  for(unsigned int iii=0;iii<a.size();iii++)
    o << " " << iii<< ": " << a[iii]<<" ;";
  return o << "}\n";
}

template<class T> istream& operator>>(istream&in, Vector<T>&)
{return in;}

template<class T> int Hash(const Vector<T>&a)
{
  int n=0;
  for(int iii=0;iii<a.size();iii++)
    n+=Hash(a[iii])*(iii+1);
  return n+a.size()*47;
}
template<class T> void Vector<T>::copy(T *aa, const T *bb, int n)
{
  for(int iii=0;iii<n;iii++)
    aa[iii]=bb[iii];
}
template<class T> void Vector<T>::copy(T *aa, T *bb, int n)
{
  for(int iii=0;iii<n;iii++)
    aa[iii]=bb[iii];
}

template<class T> void Vector<T>::_expand()
{
#ifdef VERY_ARRAY_DEBUG
  cout << "FREE ARRAY because of _expand: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
  T *oldp=p;
  int oldsize=realSize;
  realSize=realSize*2+1;
  p=new T[realSize];
  memo_new(p);
  copy(p, oldp, oldsize);
  delete [] oldp;
  memo_del(oldp, 1);
#ifdef VERY_ARRAY_DEBUG
  cout << "NEW ARRAY because of _expand: " << this << " " << realSize<<" "<<(void*)p << '\n';
#endif			
}

template<class T> int Vector<T>::findMax() const
{
  if( size()==0 )
    return -1;
  else
    {
      int maxPos=0;
      for(int iii=1;iii<size();iii++)
	if( (*this)[maxPos]<(*this)[iii] )
	  maxPos=iii;
      return maxPos;
    }
}
template<class T> int Vector<T>::findMin() const
{
  if( size()==0 )
    return -1;
  else
    {
      int minPos=0;
      for(int iii=1;iii<size();iii++)
	if( (*this)[iii]<(*this)[minPos] )
	  minPos=iii;
      return minPos;
    }
}

#endif

#endif