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


#include    "rwtptrorderedvector.h"


template <class TP>
class RWTPtrSortedVector : public RWTPtrOrderedVector<TP> {
public:
   RWTPtrSortedVector( 
           size_t nCapacity = nInitialRWTPtrOrderedVectorCapacity ) 
      : 
      RWTPtrOrderedVector<TP>( nCapacity ) {}

#ifdef USE_USING_IN_PUBLIC_TEMPLATE_CLASSES
   using RWTPtrOrderedVector<TP>::nCurrentLength_;
   using RWTPtrOrderedVector<TP>::isEmpty;
   using RWTPtrOrderedVector<TP>::nCurrentLength_;
   using RWTPtrOrderedVector<TP>::length;
   using RWTPtrOrderedVector<TP>::ppArray_;
   using RWTPtrOrderedVector<TP>::data;
   using RWTPtrOrderedVector<TP>::entries;
   using RWTPtrOrderedVector<TP>::operator[];
#endif


   bool bContains( const TP* pVal ) const {
      // we want to use the fast index in this class, not 
      // the slow one in RWTPtrOrderedVector
      if ( RWTPtrSortedVector::index( pVal ) == RW_NPOS )
         return( false );
      else
         return( true );
   }



   void insert( TP* pVal ) {
      
      int nInsertBeforeIndex = nFindIndexOfMatchOrSuccessor( pVal );

      if ( nInsertBeforeIndex == RW_NPOS )
         nInsertBeforeIndex = nCurrentLength_;

      insertAt( nInsertBeforeIndex, pVal );
   }

   // note:  this has now been tested and currently is used for finding
   // which reads are not at the start of a template
   int nFindIndexOfMatchOrSuccessor( const TP* pTMatch) const {
      
      // return immediately if empty
      if ( isEmpty() ) 
         return RW_NPOS;

      int nRangeStart = 0;
      int nRangeEnd = length() - 1;

      while( true ) {

         int nRangeLen = nRangeEnd - nRangeStart + 1;
         int nTestIndex = ( nRangeLen / 2 ) + nRangeStart;

         if ( *( (*this)[nTestIndex]) == *pTMatch ) {
            return nTestIndex;  // exact match
         }
         else if ( *pTMatch < *((*this)[nTestIndex]) ) {
            // .  .  .  +  .  .  .  .  . (+ is nTestIndex)
            //         * (pTMatch)
            // This is first case

            //    + . . . . .
            //  * (pTMatch)
            // This is second case

            if ( ( nRangeLen == 1 ) || ( nTestIndex == 0 ) ) {
               return( nTestIndex );
            }
            else {
               // .  .  .  .  +  .  .  (+ is nTestIndex)
               //      * (pTMatch)
               // So overshot.
               nRangeEnd = nTestIndex - 1;
            }
         }
         else { 
            // *((*this)[nTestIndex])  < *pTMatch


            // case of nRangeLen == 1

            // .  l  u(+) .
            //           *

            // l is nRangeStart
            // u is nRangeEnd
            // + is nTestIndex
            // * is pTMatch

            
            if ( nRangeLen == 1 || nTestIndex == nRangeEnd) {

               if ( nTestIndex == ( length() - 1 ) ) {
               // .  .  .  +
               //            * (pTMatch)
               // In this case, there is no match or successor
                  return RW_NPOS;
               }
               else {
                  // .  .  .  .  +  .  .  .
                  //               * (pTMatch)
                  // In this case, we want the "." after the "+"

                  return( nTestIndex + 1);
               }
            }
            else 
            // normal case:  

            // .  .  +  .  .  .  .
            //               * (pTMatch)
               nRangeStart = nTestIndex + 1;
         }
      } //  while( true )
   }
         

   inline size_t index( const TP* pVal ) const {

      int nIndex = nFindIndexOfMatchOrSuccessor( pVal );

      if ( nIndex != RW_NPOS ) {
         if (! (  *(ppArray_[ nIndex ]) == *pVal ) )
            nIndex = RW_NPOS;
      }

      return( nIndex );
   }

   TP* find( const TP* pVal ) const {
      
      int nIndex = index( pVal );
      if ( nIndex == RW_NPOS ) 
         return( 0 );
      else
         return( ppArray_[ nIndex ] );
   }


   //
   // finds the element equal to the passed value, or it's immediate
   // predecessor in the sort order if match not found.
   // returns RW_POS if array empty or no values <= passed val exist
   //
   
   // cases:
   //     (passed value) < (all elements in array)    passes RW_POS
   //     (all elements in array) < (passed value)    returns index
   //           of last element in array
   //      == some element, returns index of that element
   //      passed value is between some values, returns the index of the
   //           element just below that value

   int nFindIndexOfMatchOrPredecessor(const TP* pTMatch) const {

      // return immediately if empty
      if (this->isEmpty()) { return RW_NPOS; }

      // the array is cut up into increasingly smaller sections
      // for the first comparison, the range is the entire array.
      int nRangeStart = 0;
      int nRangeEnd = this->length() - 1;

      // repeat until found
      while (true) {
         // what is the size of the current range
         int nRangeLen = nRangeEnd - nRangeStart + 1;

         // test the middle of the range - odd/even doesn't matter
         int nTestIndex = (nRangeLen / 2) + nRangeStart;
         
         if (*((*this)[nTestIndex]) == *pTMatch) {
            return nTestIndex;         // exact match
         }
         else if ( *pTMatch < *((*this)[nTestIndex]) ) {
            if (nRangeLen == 1) { 
               if (nTestIndex > 0) { 
                  return nTestIndex-1; // one before this one is best
               }
               else {
                  return RW_NPOS; // sorry.
               }
            }

            nRangeEnd = nTestIndex - 1;  // overshot.  look lower.
         }
         else {
            if ((nRangeLen == 1) || (nTestIndex == nRangeEnd)) { 
               return nTestIndex; 
            }  // best available

            nRangeStart = nTestIndex + 1; // undershot.  look higher.
         }
      }  // while true
   }



   TP* findMatchOrPredecessor(const TP* pTMatch) const {
      // use above version for search
      int nRetIndex = nFindIndexOfMatchOrPredecessor(pTMatch);

      // cannot have multiple returns in inline on HP (sigh)
      TP* tTemp;

      // return null or pointer to found object
      if (nRetIndex == RW_NPOS) 
        tTemp = 0;
      else 
        tTemp = (*this)[nRetIndex];

      return tTemp;
   }



   void resort();
   static int cmp( const TP** ppT1, const TP** ppT2 );
   bool bIsSorted();
   
};







#endif