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


// container ordered on key, with fixed size array
// no repeated elements
struct IKeyContainer {
      int maxSize;
      int nElements;
      int* start;

  } IKeyContainer;
  const int size =5;

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 = (int*) malloc(size*sizeof(int));
        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, int 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, int 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, int 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, int 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 search(struct IKeyContainer* p, int value){
    // compute index =  position where  element is (similar to compute position, but exact match)
    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
}

int readKeyContainer(struct IKeyContainer* p, int 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;
   }

int readCancelKeyContainer(struct IKeyContainer* p, int 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);

      }

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);
      printIntKeyContainer(s1);
     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;
}