// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Michael Dineen (Los Alamos National Laboratory)

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#ifndef _DyArray_c
#define _DyArray_c

#include <iostream.h>
#include <memory.h>

#include "LINK/basic/stdfuncs.h"
#include "LINK/basic/bstream.h"


// ---------------------------------------------------------------------

// dtor
//
template< class T >
UnArray<T>::~UnArray()
{
   //cerr << "aad: " << (void*) array << ' ' << (void*) this << nl;
   if (array) delete [] array;
   array = 0;
}


// copy all ops from <a> into self
//
template< class T >
void UnArray<T>::copy( const T *a, int length )
{
   if ( length == 0 ) return;

   if ( simpleType( (*this)[0] ) )
   {
      memcpy( baseAddr(), a, length*sizeof(T) );
   }
   else
   {
      for ( int i=0; i<length; i++ )
         array[i] = (T) a[i];
   }
}


// Allocate the array and set the allocated size.
// This is a virtual function.
// Setting allocSize means nothing for Array (always==_size).
//
template< class T >
void UnArray<T>::allocate( int size )
{
   assert( size >= 0 );

   if ( size != 0 )
      array = new T[ size ];
   else
      array = 0;

   //cerr << "aa===" << size << ' ' << (void*) array << ' ' << (void*) this << nl;

   setSize( size );
}


// Allocate the array and set the allocated size.
// Copy n items from the old array to the new.
// Delete the old array.
// This is a virtual function.
// Setting allocSize means nothing for Array (always==_size).
//
template< class T >
void UnArray<T>::reallocate( int newSize, int keepNum )
{
//cerr << "array reallocate" << nl;

   assert( newSize >= 0 && keepNum >= 0 );
   assert( keepNum <= size() ); // can't keep more than it has

   if ( allocSize() == newSize ) return; // do nothing

   setSize( newSize );

   T* oldArray = array;

   if ( newSize != 0 )
      array = new T[ newSize ];
   else
      array = 0;

   //cerr << "ar===" << newSize << ' ' << array  << nl;

   int copyMax = min( keepNum, newSize );
   copy( oldArray, copyMax );

   if ( oldArray ) delete [] oldArray;
}


//----------------------------------------------------------------



// reallocate the array, copy old to new
//
template< class T >
void UnArray<T>::resize( int newSize )
{
   assert( newSize >= 0 );

   reallocate( newSize, min( size(), newSize ) );
}


// reallocate the array, do not copy old ops into new
//
template< class T >
void UnArray<T>::resizeNoCopy( int newSize )
{
   assert( newSize >= 0 );

   reallocate( newSize, 0 );
}


// resize, filling new area with fill
//
template< class T >
void UnArray<T>::resize( int newSize, const T& fill )
{
   int oldSize = _size;

   resize( newSize );

   for ( int i=oldSize; i<_size; i++ )
      array[i] = (T) fill;
}


// Constructors, copying  -----------------------------------------

template< class T >
UnArray<T>::UnArray( int size )
{
   assert( size>=0 );
   allocate( size );
   //cerr << "array int ctor" << nl;
}


template< class T >
UnArray<T>::UnArray( const UnArray<T>& a )
{
   allocate( a.size() );
   copy( (T*) a.baseAddr(), a.size() );
   //cerr << "array copy ctor" << nl;
}


// copy, with extra
//
template< class T >
UnArray<T>::UnArray( const UnArray<T>& a, int extra )
{
   assert( a.size() + extra >= 0 );

   allocate( a.size() + extra );
   copy( (T*) a.baseAddr(), a.size() );
}

// assignment
//
template< class T >
UnArray<T>& UnArray<T>::operator=( const UnArray<T>& a )
{
   if ( this != &a ) // beware of s=s
   {
      reallocate( a.size(), 0 );
      copy( (T*) a.baseAddr(), a.size() );
   }

   return *this;
}


template< class T >
Bool UnArray<T>::operator==( const UnArray<T>& a ) const
{
   if ( size() != a.size() ) return FALSE;
   for ( int i = 0; i < size(); i++ )
      if ( ! ( (*this)[i] == a[i] ) ) return FALSE;
   return TRUE;
}

template< class T >
void UnArray<T>::fill(const T &fill)
{
   for (int i=0; i<_size; i++) array[i] = (T) fill;
}


/*
 * Reverse a subrange of an array.
 */
template< class T >
void UnArray<T>::reverse( int i, int j )
 {
    int k;
    assert( i>=0 && i<_size && j>=0 && j<_size && i <= j);

    if (j-i == 0) return;

    UnArray<T> rev(j-i+1);

//    cerr << "rev size " << rev.size() << nl;

    for (k=0; k < rev.size(); k++) rev.array[k]=array[k+i];

    for (k=0; k < rev.size(); k++) array[j-k]=rev.array[k];
 }


/*
 * Rotate array Left a few times.
 */
template< class T >
void UnArray<T>::rotateLeft( int num )
 {
    int k;
    assert( num>=0 && num<_size );

    if (num == 0) return;

    UnArray<T> rot(_size);

    for (k=0; k < _size; k++) rot[k]=array[(k+num) % _size];
    //
    for (k=0; k < _size; k++) array[k]=rot[k];
 }

/*
 * Rotate array Right a few times.
 */
template< class T >
void UnArray<T>::rotateRight( int num )
 {
    int k;
    assert( num>=0 && num<_size );

    if (num == 0) return;

    UnArray<T> rot(_size);

    for (k=0; k < _size; k++) rot[k]=array[(k+_size-num) % _size];
    //
    for (k=0; k < _size; k++) array[k]=rot[k];
 }

/*
 * Try to find the index of an array element.
 */
template< class T >
int UnArray<T>::index( const T &elm ) const
 {
  int idx=0;
 
  // Some objects don't have operator()!= defined.
  //
  while ( idx < size() ) if (array[idx] == elm) return idx; else idx++;
  //while ( idx < size() && array[idx] != elm ) idx++;

  return idx;
 }


template< class T >
void UnArray<T>::shiftAndResizeLeft( int index, int num )
{
   assert( num >= 0 ); //assert( index <= num );
   
   assert( num <= size() );

   if (num == 0) return;

   int sz = size();
   for (int k=index; k < sz-num; k++) put( k, array[k+num] );
   resize( sz - num );
}

template< class T >
void UnArray<T>::shiftLeft( int index, int num )
{
   assert( num >= 0 ); //assert( index <= num );
   
   assert( num <= size() );

   if (num == 0) return;

   int sz = size();
   for (int k=index; k < sz-num; k++) put( k, array[k+num] );
   //resize( sz - num );
}

template< class T >
void UnArray<T>::shiftAndResizeRight( int index, int num )
{
   if (num == 0) return;

   resize( size() + num );

   for (int k=size()-num-1; k >= index; k--) put( k+num, array[k] );
}


// copy memory into array
//
template< class T >
void UnArray<T>::binaryInsert( int index, char* buffer, int length )
{
   assert( (char*) offsetAddr( index ) + length <= (char*) offsetAddr(size()) );
   memcpy( offsetAddr( index ), buffer, length );
}

// append an array
//
template< class T >
void UnArray<T>::append( const UnArray<T> &a )
{
   int n = size();
   
   extend(a.size());

   for (int j=0; j<a.size(); j++) array[j+n]=a[j];
}

// subtrack items from an array
//
template< class T >
void UnArray<T>::minus( const UnArray<T> &a )
{
   for (int i=0; i<size(); i++)
    for (int j=0; j<a.size(); j++)
     {
       if (array[i]==a[j]) 
         {
           swap(i,size()-1);
           shrink(1);
           i--;
           break;
         }         
     } 
}

//----------------------------------------------------------
//       ---------------- DyArray ----------------
//----------------------------------------------------------

/*
 * Maximum amount to over allocate by. (to do later)
 */
//#define _DyArrayGrowMax_ 16


// Allocate the array and set the allocated size.
// This is a virtual function.
//
template< class T >
void DyArray<T>::allocate( int size )
{
   assert( size >= 0 );

   if ( size != 0 )
      array = new T[ size ];
   else
      array = 0;

   //cerr << "da===" << size << ' ' << (void*) array << ' ' << (void*) this << nl;

   _allocSize = size;

   setSize( size );
}


// Allocate the array and set the allocated size.
// Copy n items from the old array to the new.
// Delete the old array.
// This is a virtual function.
// Setting allocSize means nothing for Array (always==_size).
//
template< class T >
void DyArray<T>::reallocate( int newSize, int keepNum )
{
   //cerr << "dyarray reallocate " << array << nl;

   assert( newSize >= 0 );
   assert( keepNum <= size() ); // can't keep more than it has

   setSize( newSize );

   if ( allocSize() >= newSize ) return;
   //cerr << "   realloc needed" << nl;

   T* oldArray = array;

   // we know newSize > 0, because it's > allocSize
   //
   array = new T[ newSize ];

   //cerr << "dr===" << newSize << ' ' <<(void*)array<< ' ' << (void*) this<<nl;

   int copyMax = min( keepNum, newSize );
   copy( oldArray, copyMax );
 
   _allocSize = newSize;

   if ( oldArray ) delete [] oldArray;
}


template< class T >
void DyArray<T>::resizeAndOverAllocate( int newSize, int extraSize )
{
   assert( newSize >= 0 );
   assert( extraSize >= 0 );

   // check if realloc is needed
   //
   if ( allocSize() < newSize )
   {
      //reallocate( newSize + extraSize, min( size(), newSize ) );
      //
      // since newSize >= allocSize() >= size()
      //
      reallocate( newSize + extraSize, size() ); 
   }

   setSize( newSize );

}

template< class T >
void DyArray<T>::resizeNoCopyAndOverAllocate( int newSize, int extraSize )
{
   assert( newSize >= 0 );
   assert( extraSize >= 0 );

   // check if realloc is needed
   //
   if ( allocSize() < newSize )
   {
      reallocate( newSize + extraSize, 0 );
   }

   setSize( newSize );

}


// Constructors, copying  -----------------------------------------

template< class T >
DyArray<T>::DyArray( int size, int moreSpace )
{
   assert( size >= 0 );
   allocate( size + moreSpace );
   setSize( size );
}


template< class T >
DyArray<T>::DyArray( const UnArray<T>& a )
{
   allocate( a.size() );
   copy( (T*) a.baseAddr(), a.size() );
}


template< class T >
DyArray<T>::DyArray( const DyArray<T>& a )
{
   allocate( a.size() );
   copy( (T*) a.baseAddr(), a.size() );
}


template< class T >
DyArray<T>::DyArray( const UnArray<T>& a, int extra )
{
   assert( a.size() + extra >= 0 );

   allocate( a.size() + extra );
   copy( (T*) a.baseAddr(), a.size() );
}


template< class T >
DyArray<T>& DyArray<T>::operator=( const UnArray<T>& a )
{ 
  UnArray<T>::operator=( a ); 
  _allocSize = size(); 
  return *this; 
}


template< class T >
DyArray<T>& DyArray<T>::operator=( const DyArray<T>& a )
{ 
  UnArray<T>::operator=( a ); 
  _allocSize = size(); 
  return *this; 
}

// -------------------------------------------------------------------
//  	I/O stuff ...
// -------------------------------------------------------------------


template< class T >
ostream& operator<<( ostream& o, const UnArray<T>& A )
{
   o << '[';
   if ( A.size() > 0 ) o << A[0];
 
   for ( int i = 1; i < A.size(); i++ ) o << ',' << A[i];
   o << ']';
 
   return o;
}

template< class T >
istream& operator>>( istream& in, UnArray<T>& A )
{
   int n=A.length();
   int i=0;

   char c=0;

   while (c!='[') in >> c;
   in >> c;
   if (c==']') { A.resize(0); return in; }
   in.putback(c);

   while (i<n)
    {
      in >> A[i++];
      in >> c;

      if (c==']') { A.resize(i); return in; }
      assert(c==',');
    }

   T item;
   //
   while (c!=']')
    {
     in >> item;

     A.append(item);

     in >> c;			
     assert(c==']' || c==',');
    }
 
   return in;
}

template<class T>
bostream& operator<<( bostream& s, const UnArray<T>& A )       
{                                                           
      int z = A.size();                                       
      s << z;                                                
      for ( int i = 0; i < z; i++ ) s << A[i];              
      return s;                                            
}                                                      

template<class T>
bistream& operator>>( bistream& s, UnArray<T>& A )      
{                                                    
      int z;                                           
      s >> z;                                         
      assert( z >= 0 );                              
      A.allocate( z );                              
      A.setSize( z );                              
      for ( int i = 0; i < z; i++ ) s >> A[i];    
      return s;                                  
}



template< class T >
bostream& operator<<( bostream& o, const DyArray<T>& A )
{ return o << (UnArray<T>&) A; }

template< class T >
bistream& operator>>( bistream& o, DyArray<T>& A )
{ return o >> (UnArray<T>&) A; }

#ifdef __GNUC__ 	/* g++2.6 doesn't use base class */
template< class T >
ostream& operator<<( ostream& o, const DyArray<T>& A )
{ return o << (UnArray<T>&) A; }
#endif

#endif