#include <stdio.h>
#include "sortedlist.h"

/*******************************************************************
Basic SortedArray access functions
*******************************************************************/

/* print out the contents of "s", for debugging */
void SA_Print ( SortedArray s ) {
  int i;
  
  for ( i=0; i<s.size; i++ ) {
    printf("%i ", s.arr[i]);
  }
  printf(" [%i]\n", s.size);
}

/* return the item from position "pos" in "s" */
int SA_Index( SortedArray s, unsigned int pos ) {
  return s.arr[pos];
}


/*******************************************************************
Searching in a SortedArray--three attempts
*******************************************************************/

/* find the position of "val" in "s"; MAXSIZE+1 if it's not there. */
unsigned int SA_Search1( SortedArray s, int val ) {
  int i;

  for( i=0;  i<s.size; i++ ) {
    if ( s.arr[i] == val ) {
      return i;
    }
  }

  return MAXSIZE+1;
}

/* second try at SA_Search--stops the search when it gets to a value larger */
/* than the thing its looking for. */
unsigned int SA_Search2( SortedArray s, int val ) {
  int i;

  for( i=0;  i<s.size; i++ ) {
    if ( s.arr[i] == val ) {
      return i;
    }
    if ( s.arr[i] > val ) {
      return MAXSIZE+1;
    }
  }

  return MAXSIZE+1;
}

/* a binary search version--much faster. */
unsigned int SA_Search( SortedArray s, int val ) {
  unsigned int left, right, mid;

  left = 0;
  right = s.size - 1;

  do {
    mid = (left + right) / 2;

    printf ("search1: %u %u %u\n", left, mid, right);
    if ( s.arr[mid] == val ) {
      return mid;
    } else if ( s.arr[mid] < val ) {
      left = mid + 1;
    } else { /* s.arr[mid] > val */ 
      right = mid - 1;
    }
    printf ("search2: %u %u %u\n", left, mid, right);

  } while (left <= right);

  return MAXSIZE+1;
}

/*******************************************************************
Changing a SortedArray--Init, Insert, Delete
*******************************************************************/

/* Initialize the data structure */
void SA_Init ( SortedArray *p ) {
  p->size = 0;
}



/* Put val into the array at the end. (aka. not the right spot) */
void SA_Insert1 ( SortedArray *p, int val ) {
  p->arr[ p->size ] = val;  
  p->size ++;
}


/* Put val into the array in the right spot. */
void SA_Insert ( SortedArray *p, int val ) {
  int i;

  if ( p->size == MAXSIZE ) {
    printf("Can insert--SortedArray already full.\n");
    return;
  }

  i = p->size - 1;
  while ( p->arr[i] > val && i>=0 ) {
    p->arr[i+1] = p->arr[i];
    i--;
  }
  
  p->arr[i+1] = val;

  p->size ++;

}