/*****************************************************************************
#   Copyright (C) 1994-2008 by David Gordon.
#   All rights reserved.                           
#                                                                           
#   This software is part of a beta-test version of the Consed/Autofinish
#   package.  It should not be redistributed or
#   used for any commercial purpose, including commercially funded
#   sequencing, without written permission from the author and the
#   University of Washington.
#   
#   This software is provided ``AS IS'' and any express or implied
#   warranties, including, but not limited to, the implied warranties of
#   merchantability and fitness for a particular purpose, are disclaimed.
#   In no event shall the authors or the University of Washington be
#   liable for any direct, indirect, incidental, special, exemplary, or
#   consequential damages (including, but not limited to, procurement of
#   substitute goods or services; loss of use, data, or profits; or
#   business interruption) however caused and on any theory of liability,
#   whether in contract, strict liability, or tort (including negligence
#   or otherwise) arising in any way out of the use of this software, even
#   if advised of the possibility of such damage.
#
#   Building Consed from source is error prone and not simple which is
#   why I provide executables.  Due to time limitations I cannot
#   provide any assistance in building Consed.  Even if you do not
#   modify the source, you may introduce errors due to using a
#   different version of the compiler, a different version of motif,
#   different versions of other libraries than I used, etc.  For this
#   reason, if you discover Consed bugs, I can only offer help with
#   those bugs if you first reproduce those bugs with an executable
#   provided by me--not an executable you have built.
# 
#   Modifying Consed is also difficult.  Although Consed is modular,
#   some modules are used by many other modules.  Thus making a change
#   in one place can have unforeseen effects on many other features.
#   It may takes months for you to notice these other side-effects
#   which may not seen connected at all.  It is not feasable for me to
#   provide help with modifying Consed sources because of the
#   potentially huge amount of time involved.
#
#*****************************************************************************/
#ifndef rwtptrorderedvector_included
#define rwtptrorderedvector_included

#include    "mbt_exception.h"
#include    "rwdefs.h"
#include    <cstdlib>
using namespace std;
#include    "soEmptyString.h"



const int nInitialRWTPtrOrderedVectorCapacity = 0;



template <class TP>
class RWTPtrOrderedVector {
public:
   int nCurrentLength_;
   int nMaxLength_;
   TP** ppArray_;
   RWCString soName_;
public:
   RWTPtrOrderedVector(
	size_t nCapacity = nInitialRWTPtrOrderedVectorCapacity,
	const RWCString& soName = soEmptyString ) :
     nMaxLength_( nCapacity ),
     soName_( soName ) {

      if ( nMaxLength_ > 0 ) {
         ppArray_ = (TP**) malloc( nMaxLength_ * sizeof( TP* ) );

         if ( !ppArray_ ) {
            PANIC_OST( ost ) << 
               "in RWTPtrOrderedVector ctor. failed to malloc memory for " <<
               nCapacity << " objects" << ends;
            throw RWInternalError( ost.str().c_str() );
         }
      }
      else
         ppArray_ = (TP**) 0;

      nCurrentLength_ = 0;
   }
   

   RWTPtrOrderedVector( const RWTPtrOrderedVector& aArray );
   

   ~RWTPtrOrderedVector() {
      free( (void*) ppArray_ );
   }

   inline void append( TP* pVal ) {
      if ( nCurrentLength_ + 1 > nMaxLength_ )
         resize( (size_t) ( ( nMaxLength_ + 1 ) * nDefaultArrayResizeIncrement ) );

      ppArray_[ nCurrentLength_ ] = pVal;
      ++nCurrentLength_;
   }


   bool bContains( TP* pVal ) {
      if ( index( pVal ) == RW_NPOS )
         return( false );
      else
         return( true );
   }


   void clear() {
      nCurrentLength_ = 0;
   }

   void clearAndDestroy() {
      for( int n = nCurrentLength_ - 1; n >= 0; --n )
         delete ppArray_[n];

      nCurrentLength_ = 0;
   }

   TP** data() { return ppArray_; }


   int entries() const { return nCurrentLength_; }


   void increaseMaxLengthIfNecessary( const size_t nExtraRoomNeeded ) {
      int nNewMaxLength = nExtraRoomNeeded + nCurrentLength_;

      if ( nNewMaxLength > nMaxLength_ ) {
         resize( nNewMaxLength );
      }
   }


   int index( const TP* pVal );

   int indexByPointers( const TP* pVal );

   inline void insert( TP* pVal ) {
      append( pVal );
   }


   inline void insertAt( const size_t nInsertBeforeIndex, TP* pVal ) {
      
      // I'm allowing an insert at nCurrentLength_, just after the
      // end of the array
      if ( nInsertBeforeIndex > nCurrentLength_ ) {
         PANIC_OST( ost ) << "In RWTPtrOrderedVector::insertAt( " <<
            nInsertBeforeIndex << 
            " ... index out of bounds since nCurrentLength_ = " <<
            nCurrentLength_ << ends;

         throw RWInternalError( ost.str().c_str() );
      }
      

      if ( nCurrentLength_ + 1 > nMaxLength_ )
         resize( (size_t) ( ( nMaxLength_ + 1 ) * nDefaultArrayResizeIncrement ) );
      
      for( register size_t nIndex = nCurrentLength_; 
           nIndex > nInsertBeforeIndex;
           --nIndex ) 
         ppArray_[ nIndex ] = ppArray_[ nIndex - 1 ];

      ++nCurrentLength_;
      ppArray_[ nInsertBeforeIndex ] = pVal;
   }


   inline bool isEmpty() const { 
      if ( nCurrentLength_ == 0 )
         return true;
      else 
         return false;
   }


   // this does not behave like the Rogue Wave function, which
   // throws an exception if the array is empty.

   TP* last() const {
      if ( nCurrentLength_ == 0 )
         return( 0 );
      else
         return( ppArray_[ nCurrentLength_ - 1 ] );
   }


   int length() const { return nCurrentLength_; }


   int nGetMaxIndex() const { return ( (int) nCurrentLength_ ) - 1; }


   inline TP*& operator[]( const size_t nIndex ) {

      if ( nIndex >= nCurrentLength_ ) {
         PANIC_OST( ost ) << "In RWTPtrOrderedVector::operator[]( " <<
            nIndex << " ). index out of bounds since nCurrentLength_ = " <<
            nCurrentLength_ << " array name = " << soName_ << ends;
         throw RWInternalError( ost.str().c_str() );
      }

      return( ppArray_[ nIndex ] );
   }

   inline TP* operator[]( const size_t nIndex ) const {
   
      if ( nIndex >= nCurrentLength_ ) {
         PANIC_OST( ost ) << "In RWTPtrOrderedVector::operator[]( " <<
            nIndex << " ). index out of bounds since nCurrentLength_ = " <<
            nCurrentLength_ << " array name = " << soName_ << ends;

         throw RWInternalError( ost.str().c_str() );
      }

      return( ppArray_[ nIndex ] );
   }

   inline TP*& operator()( const size_t nIndex ) {
      return( ppArray_[ nIndex ] );
   }

   RWTPtrOrderedVector<TP>& operator=( const RWTPtrOrderedVector& aArray ) {
      clear();
      // + 1 is just to handle null arrays
      resize( aArray.nCurrentLength_ + 1 );

      nCurrentLength_ = aArray.nCurrentLength_;
      for( int n = 0; n < nCurrentLength_; ++n )
         ppArray_[n] = aArray.ppArray_[n];

      return( *this );
   }

   // not tested
   RWTPtrOrderedVector<TP>& operator+=( const RWTPtrOrderedVector& aArray ) {

      // + 1 to handle both arrays being null
      resize( nCurrentLength_ + aArray.nCurrentLength_ + 1 );

      for( int n = 0; n < aArray.length(); ++n ) {
         insert( aArray[n] );
      }
      return( *this );
   }

   inline TP* remove( const TP* pVal ) {

      size_t nFoundIndex = index( pVal );

      if ( nFoundIndex == RW_NPOS )
         return( 0 );
      
      TP* pTemp = ppArray_[ nFoundIndex ];

      // shift the rest of the array left to fill in where the 
      // element was removed
      for( int nIndex = nFoundIndex; nIndex < nCurrentLength_ - 1; ++nIndex )
         ppArray_[ nIndex ] = ppArray_[ nIndex + 1 ];

      --nCurrentLength_;
            

      return( pTemp );
   }


   inline TP* removeAt( const size_t nIndex ) {
      if ( nIndex >= nCurrentLength_ ) {
         PANIC_OST( ost ) << "RWTPtrOrderedVector::removeAt( " <<
            nIndex << " ) is out of bounds for array with nCurrentLength_ = " <<
            nCurrentLength_ << ends;

         throw RWInternalError( ost.str().c_str() );
      }

      TP* pTemp = ppArray_[ nIndex ];

      for( int n = nIndex; n < nCurrentLength_ - 1; ++n )
         ppArray_[ n ] = ppArray_[ n + 1 ];

      --nCurrentLength_;
      
      return( pTemp );
   }


   TP* removeLast();

   void resize( const size_t nNewSize ) {

      if ( nCurrentLength_ > nNewSize ) {
         PANIC_OST( ost ) << "RWTPtrOrderedVector::resize( " <<
            nNewSize << 
            " ) has new size out of bounds since nCurrentLength_ = " <<
            nCurrentLength_ << " soName_ = " << soName_ << ends;
         throw RWInternalError( ost.str().c_str() );
      }

      ppArray_ = (TP**) realloc( ppArray_, nNewSize * sizeof( TP* ) );
      if ( !ppArray_ && nNewSize ) {
         PANIC_OST( ost ) << "RWTPtrOrderedVector::resize( " <<
            nNewSize << 
            " ).  realloc could not get enough memory" << ends;
         throw RWInternalError( ost.str().c_str() );
      }

      nMaxLength_ = nNewSize;
   }


   void resizeIfNecessary( const size_t nNewSize ) {
      
      if ( nNewSize <= nMaxLength_ )
         return;

      resize( nNewSize );
   }


   void reverseElementOrder() {
      for( int nIndex = 0; nIndex < nCurrentLength_ / 2; ++nIndex ) {
         TP* pTPTemp = ppArray_[ nIndex ];
         ppArray_[ nIndex ] = ppArray_[ nCurrentLength_ - nIndex - 1 ];
         ppArray_[ nCurrentLength_ - nIndex - 1 ] = pTPTemp;
      }
   }

};


#ifdef INLINE_RWTPTRORDEREDVECTOR

#include    "rwtptrorderedvector_inc.cpp"

#endif


#endif