#include <stdio.h>
#define MAXSIZE 100

typedef struct {
  unsigned int size;
  int arr[MAXSIZE];
} SortedArray;

/*******************************************************************
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;

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

}

/*******************************************************************
main()--test the stuff to see what's going on.
*******************************************************************/

int main () {
  SortedArray s;

  SA_Init(&s);

  /* use the broken insert function to get stuff for testing */
  SA_Insert1(&s,8);
  SA_Insert1(&s,10);
  SA_Insert1(&s,20);
  SA_Insert1(&s,21);

  SA_Print(s);

  /* test the "working" SA_Insert function */
  SA_Insert(&s,9);

  SA_Print(s);

  return 0;
}