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

#include    "rwtptrorderedvector.h"
#include    "subcloneTTemplate.h"


class templatesSortedByName : public RWTPtrOrderedVector<subcloneTTemplate> {
public:

   
   static int cmp2( const subcloneTTemplate** ppSub1, 
                    const subcloneTTemplate** ppSub2 ) {
      
      if ( (*ppSub1)->soTemplateName_ < (*ppSub2)->soTemplateName_ )
         return( -1 );
      else if ( (*ppSub2)->soTemplateName_ < (*ppSub1)->soTemplateName_ )
         return( 1 );
      else {
         return( 0 );
      }
   }


   void resort2() {
      void* pArray = (void*) data();
      size_t nNumberOfElementsInArray = entries();
      size_t nSizeOfAnElement = sizeof( subcloneTTemplate* );

      qsort( pArray, nNumberOfElementsInArray, nSizeOfAnElement,
             ( ( int(*) ( const void*, const void*) ) cmp2 ));

      
      if ( ! bIsSorted2() ) {
         PANIC_OST( ost ) << "templatesSortedByName::resort2 didn't work" << 
            endl << ends;
         throw ProgramLogicError( ost.str().c_str() );
      }

   }


   bool bIsSorted2() {
      
      int nNumberOfEntries = entries();
      bool bSorted = true;
      if ( nNumberOfEntries >=2 ) {
         for( int nElement = 0; 
              nElement <= nNumberOfEntries - 2;
              ++nElement ) {
            if (
                (operator[]( nElement + 1 ))->soTemplateName_ <
                (operator[]( nElement ) )->soTemplateName_ ) {
               bSorted = false;
               cerr << "Elements " << nElement << " with value " <<
                  (operator[]( nElement ))->soTemplateName_ <<
                  " and " << nElement + 1 << " with value " <<
                  (operator[]( nElement + 1 ))->soTemplateName_ <<
                  " are out of order " << endl;
            }
         }
      }
      return( bSorted );
   }


   // code borrowed from mbt_ptr_sorted_vector.h
   inline int nFindIndexOfMatchOrSuccessor2( const RWCString& soTemplate ) 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])->soTemplateName_ == soTemplate ) {
            return nTestIndex;  // exact match
         }
         else if ( soTemplate < ((*this)[nTestIndex])->soTemplateName_ ) {
            // .  .  .  +  .  .  .  .  . (+ 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 int nFindFirstOccurrenceOfMatch( const RWCString& soTemplate ) {


      int nMatchIndex = nFindIndexOfMatchOrSuccessor2( soTemplate );

      // case in which there is no match at all, so no point in backing up
      // to the first match.

      if ( nMatchIndex == RW_NPOS )
         return( nMatchIndex );


      // case in which the template is not in the list so the successor is
      // returned

      if ( ( operator[]( nMatchIndex ) )->soTemplateName_ != soTemplate )
         return( RW_NPOS );


      // if reached here, soTemplate is in the list, but may be there
      // multiple times


      // already at beginning, so no point backing up

      if ( nMatchIndex == 0 )
         return( nMatchIndex );

      
      int nBackupIndex = nMatchIndex - 1;
      while( nBackupIndex >= 0 && 
          ( operator[]( nBackupIndex ) )->soTemplateName_ == soTemplate ) {
         --nBackupIndex;
      }

      if ( nBackupIndex < 0 )
         nBackupIndex = 0;

      if ( ( operator[]( nBackupIndex ) )->soTemplateName_ != soTemplate )
         ++nBackupIndex;

      assert( ( operator[]( nBackupIndex ) )->soTemplateName_ == soTemplate );

      return( nBackupIndex );
   }

};

#endif