/*****************************************************************************
#   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 MBTVALORDEREDVECTOROFINT_DEFINED
#define MBTVALORDEREDVECTOROFINT_DEFINED

#include    "rwtvalorderedvector.h"
#include    <stdlib.h>

// This class is an array of integers, which allows the concatenation of
// 2 of these arrays

class mbtValOrderedVectorOfInt : public RWTValOrderedVector<int> {
public:

   mbtValOrderedVectorOfInt( const size_t nInitialSize = 64 ) : 
      RWTValOrderedVector<int>( nInitialSize ) {}


   static int cmp( const int* pInt1, const int* pInt2 ) {
      if ( *pInt1 < *pInt2 )
         return( -1 );
      else if ( *pInt1 == *pInt2 )
         return( 0 );
      else
         return( 1 );
   }


   void resort() {
      void* pArray = (void*) pArray_;
      size_t nNumberOfElements = entries();
      size_t nSizeOfAnElement = sizeof( int );
      
      qsort( pArray, nNumberOfElements, nSizeOfAnElement,
             ( ( int(*) ( const void*, const void*) ) cmp ) );

      if ( !bIsSorted() ) {
         THROW_ERROR( "mbtValOrderedVectorOfInt::resort didn't work" );
      }
   };

   bool bIsSorted() {

      int nNumberOfEntries = entries();
      bool bSorted = true;

      if ( nNumberOfEntries >= 2 ) {
         for( int nElement = 0; nElement <= nNumberOfEntries - 2; 
              ++nElement ) {
            
            if ( operator[]( nElement + 1 ) <
                 operator[]( nElement ) ) {
               bSorted = false;
               cout << "Elements " << nElement << " and " << nElement + 1 <<
                  " are out of order " << endl;
            }

         }
      }

      return( bSorted );
   }



   int nFindIndexOfMatchOrPredecessor( const int nMatch ) const {

      if ( isEmpty() ) 
         return( RW_NPOS );

      // region A
      // ----------- nMinIndex
      // region B
      // ----------- nTestIndex
      // region C
      // ----------- nTooLargeIndex 
      // region D

      // an index becomes nTooLargeIndex if it is greater than nMatch
      // an index becomes nMinIndex if it is less than nMatch

      if ( nMatch < operator[]( 0 ) )
         return( RW_NPOS );

      int nMinIndex = 0;
      int nTooBigIndex = length() - 1;

      if ( operator[]( nTooBigIndex ) <= nMatch )
         return( nTooBigIndex );

      // if reached here, nMatch < operator[]( nTooBigIndex )
      // and operator[](0) <= nMatch
      // Thus nTooBigIndex != 0  and the correct index is somewhere
      // less than nTooBigIndex and correct index >= 0 so 
      // correct index >= 0.
      // Thus bisect this range over and over, making it smaller
      // and smaller until it is 0.

      while( true ) {
         if ( nTooBigIndex - nMinIndex <= 1 )
            return( nMinIndex );
         else {
            int nTestIndex = ( nTooBigIndex + nMinIndex ) / 2;
            if ( nMatch < operator[]( nTestIndex ) )
               nTooBigIndex = nTestIndex;
            else
               nMinIndex = nTestIndex;
         }
      }
   }


   // written June 2010
   int nFindIndexOfMatchOrSuccessor( const int nMatch ) const {
      
      if ( isEmpty() )
         return RW_NPOS;

      // this label doesn't apply yet
      int nMaxIndex = length() - 1;
      if ( operator[]( nMaxIndex ) < nMatch ) {
         return RW_NPOS;
      }

      // nMaxIndex is really the max index

      if ( nMatch <= operator[]( 0 ) ) {
         return 0;
      }

      // if reach here, operator[]( 0 ) < nMatch so 0 is too small
      int nTooSmallIndex = 0;

      while( true ) {
         if ( nMaxIndex - nTooSmallIndex <= 1 )
            return nMaxIndex;
         else {
            int nTestIndex = ( nTooSmallIndex + nMaxIndex ) / 2;
            if ( operator[]( nTestIndex ) < nMatch ) {
               nTooSmallIndex = nTestIndex;
            }
            else {
               nMaxIndex = nTestIndex;
            }
         }
      } // while
   }


            
};




mbtValOrderedVectorOfInt operator+( const mbtValOrderedVectorOfInt& a1, 
                                const mbtValOrderedVectorOfInt& a2 );




#endif