#include <stdio.h>
#include <stdlib.h>


// container ordered on key, with fixed size array
// no repeated elements
// with TYPE elements
typedef int TYPE;

struct IKeyContainer {
      int maxSize;
      int nElements;
      TYPE* start;   // int* start

  } IKeyContainer;
  const int size =10;



struct IKeyContainer* createIntOrderedKeyContainer() {
        struct IKeyContainer* p;
        p = (struct IKeyContainer*) malloc(sizeof(struct IKeyContainer));
        if (p == NULL) {printf("error in malloc createOrderedKeyContainer\n");  }
        p->maxSize = size;
        p->start = (TYPE*) malloc(size*sizeof(TYPE));
        if (p->start == NULL) {printf("error in malloc createOrderedKeyContainer\n");   }
        int i;
        // initialize all to zero
        //     for(i=0; i< p->maxSize; i++) {
        //         p->start[i]=0;
        //     }
        p->nElements=0;
        return p;
   }


int keyContainerIsFull(struct IKeyContainer* p){
     if (p->nElements >= p->maxSize) return 1;
     else return 0;
}

void insert(struct IKeyContainer* p, int index, TYPE value){
     // if element already exists overwrite
     if (p->start[index] == value){
         p->start[ index] = value; return;
     }

        // shift elements down by one
    int i;
    i = p->nElements-1;
    while( i >= index) {
            p->start[i+1] = p->start[i];
            i--;
     }

     // write element
     p->start[ index] = value;
     p->nElements++;
}

int computePositionBinarySearch(){
   // TO DO
}

int computePosition(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  element to be inserted
    int index =0;

    for( ; index < p->nElements  ; index++){
           if (value <= p->start[index]) break;
    }
    return index;


        // time analysis
          // if no elements, constant
        // if n elements,
         //   best case first element, constant
         //   worst case, until n
         //   average case linear with n/2


    // time analysis: on avereage linear with N/2
}
int computePositionNotOptimal(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  elelemnt to be inserted
    int index =0;
    int goodPosition;
    for( ; index < p->nElements ; index++){
           if (value < p->start[index]) goodPosition =index;
    }
    return goodPosition;

       // time analysis: always linear with N
      }

void writeKeyContainer(struct IKeyContainer* p, TYPE value){
     if (  keyContainerIsFull(p) ) {printf("OrdContainer full \n"); return; }

     int index = computePosition(p, value);
     insert(p, index, value);
/*
    write at beginning
          computePosition()  --> constant
        insert --> shift N elements --> linear with N
            overall N
   write at end
          computePosition()  --> linear with N
          insert --> constant (no shift)
            overall N
   write in middle
          computePosition()  --> linear with N/2
          insert --> linear with N/2
            overall N
*/
   }

int binarySearch(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  element is (similar to compute position, but exact match)
    // returns the position of value if found, -1 if not found
    int middle;  // local variables
    int top =0; int bottom = p->nElements-1;
    int lenght = p->nElements;
    middle = top + lenght/2;
    printf(" middle = %d\n", middle);
    for(;   top < bottom;){
         printf(" middle = %d top %d  bottom %d\n", middle, top, bottom);
         if (value < p->start[middle]) //search in upper part of container
             {
                 // top = top;
                 bottom = middle;
                 lenght = lenght/2;
                 middle = top + lenght;
             }
         else if (value >  p->start[middle]) // search in lower part of container
            {
                top = middle+1;
                //bottom = bottom;
                 lenght = lenght/2;
                 middle = top + lenght;
            }
            else // element found
              {  return middle;}
    }
    return -1;

      // time analysis
      // best case: one iteration (element is in middle)
      // worst case: ln2(n)
}

int binSearchR(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  element is (similar to compute position, but exact match)
    // returns the position of value if found, -1 if not found

    if (p->start[index] < value) {
        binSearchR(p,  value)
        }
        else {
        }
        else {  found}
    }

    int middle;  // local variables
    int top =0; int bottom = p->nElements-1;
    int lenght = p->nElements;
    //middle = (bottom - top)/2;
    middle = top + lenght/2;
    printf(" middle = %d\n", middle);
    for(;   top < bottom;){
         printf(" middle = %d top %d  bottom %d\n", middle, top, bottom);
         if (value < p->start[middle]) //search in upper part of container
             {
                 // top = top;
                 bottom = middle;
                 lenght = lenght/2;
                 middle = top + lenght;
                 //middle += (bottom -top)/2;
             }
         else if (value >  p->start[middle]) // seacrh in lower part of container
            {
                top = middle+1;
                //bottom = bottom;
                //middle = top + (bottom -top)/2;
                 lenght = lenght/2;
                 middle = top + lenght;
            }
            else // element found
              {  return middle;}
    }
    return -1;

      // time analysis
      // best case: one iteration (element is in middle)
      // worst case: ln2(n)
}
int search(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  element is (similar to compute position, but exact match)
    // returns the position of value if found, -1 if not found
    int index =0;
    for( ; index < p->nElements  ; index++){
           if (value == p->start[index]) {return index;}
    }
    return -1;
        // time analysis
          // if no elements, constant
        // if n elements,
         //   best case first element, constant
         //   worst case, until n
         //   average case linear with n/2


    // time analysis: on avereage linear with N/2
}

TYPE readKeyContainer(struct IKeyContainer* p, TYPE value, int* found){
      // search element, return value and found notFound
      int index = search(p, value);
      if (index == -1) {  *found = 0;}
      else {  *found = 1;}
      return value;
   }

TYPE readCancelKeyContainer(struct IKeyContainer* p, TYPE value){
   }

void  freeIntKeyContainer (struct IKeyContainer* p){
       free(p->start);
       free(p);
      }


void printIntKeyContainer(struct IKeyContainer* p){
     int index ;
      printf("printing ordered container %p\n", p);
      for(index=0; index< p->nElements; index++)
      printf("%d, ",  p->start[index]);
      printf("end %p\n", p);

      }

   struct IKeyContainer * s1;
int main(int argc, char *argv[])
{
    struct IKeyContainer * s1;
    s1 = createIntOrderedKeyContainer();
     //printIntKeyContainer(s1);

  writeKeyContainer(s1, 20);
      writeKeyContainer(s1, 20);
     printIntKeyContainer(s1);
     writeKeyContainer(s1, 10);
      printIntKeyContainer(s1);
     writeKeyContainer(s1, 40);
      printIntKeyContainer(s1);

     writeKeyContainer(s1, 0);
      writeKeyContainer(s1, 33);
       writeKeyContainer(s1, -22);
        writeKeyContainer(s1, 17);
      printIntKeyContainer(s1);

      int value =-23;
      int index = binarySearch(s1, value);
      printf("index of  %d is %d\n", value , index);
  /*   int found = 0;
     int value = readKeyContainer(s1, 40, &found);
     printf("found %d\n", found);
     found = 0;
     value = readKeyContainer(s1, 919, &found);
     printf("found %d\n", found);
     /*
     writeKeyContainer(s1, 20);
     printIntKeyContainer(s1);
     writeKeyContainer(s1, 10);
      printIntKeyContainer(s1);
     writeKeyContainer(s1, 2);
      printIntKeyContainer(s1);   // 2, 10, 20

*/
 //    freeIntKeyContainer(s1);



  system("PAUSE");
  return 0;
}