///////    File: OrdededSeq.C    ///////
#include "OrderedSeq.h"

// enter puts new element at end of array and
// invalidates ordered flag
int OrderedSeq::enter(void* any)
{   int i = append(any);         // virtual append
    if ( i != -1 ) sorted(0);    // append failed if i == -1
    return(i);
}

// binary search returns index of desired entry
int OrderedSeq::index(void* key)
{     if ( ! sorted() ) sort();
      int low = 0, high = length()-1, mid, test;
      while (low <= high)
      {   mid = (high + low)/2;
          test = cmp(key, mid);
          if ( test == 0 )
               return( mid );
          else if ( test > 0 )
               low = mid + 1;
          else high = mid - 1;
      }
      return(-1);   // entry not found
}

// basic sorting using quicksort
void OrderedSeq::sort()
{    if ( sorted() ) return;
     quicksort(0, length()-1);
     sorted(1);
}

Uint OrderedSeq::partition(int l, int r)
{ register int i=l, j=r;
     swap((i+j)/2, r);                        // pivot moved to r
     while (i < j)
     {  while (cmp(i, r) <= 0 && i < j) i++;  // virtual cmp  
        while (j > i && cmp(j, r) >= 0) j--;  // virtual cmp  
        if (i < j) swap(i++,j);               // virtual swap 
     }
     if (i != r) swap(i,r);                   // virtual swap 
     return(i);
}

void OrderedSeq::quicksort(int l, int r)
{    if ( l >= r || l < 0 )
         return;
     int k = partition(l, r);
     quicksort(l, k-1);
     quicksort(k+1, r);  
}