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


// container ordered on key, with fixed size array
// no repeated elements
// with students, using TYPE
typedef
struct student { int ID;
                  char* name;
                  char* surname;
}
TYPE;

struct IKeyContainer {
      int maxSize;
      int nElements;
      TYPE* start;   // 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 = (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].ID == value.ID){
         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.ID <= p->start[index].ID) 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.ID < p->start[index].ID) 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 search(struct IKeyContainer* p, TYPE value){
    // compute index =  position where  element is (similar to compute position, but exact match)
    int index =0;
    for( ; index < p->nElements  ; index++){
           if (value.ID == p->start[index].ID) {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 printType(TYPE t){
    // for student
    printf(" %d, %s, %s ", t.ID, t.name, t.surname);

}


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

      }

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

  TYPE st1 = {1234, "mario", "rossi"};
  TYPE st2 = {001, "jian", "wang"};
  TYPE st3 = {9989, "yu", "fei"};
 TYPE st4 = {0, "", ""};

  writeKeyContainer(s1, st1 );
  writeKeyContainer(s1, st2 );
  writeKeyContainer(s1, st3 );

     printIntKeyContainer(s1);  // jian, mario, yu

     int found = 0;
     TYPE value = readKeyContainer(s1, st3, &found);
     printf("found %d\n", found);
     found = 0;
     value = readKeyContainer(s1, st4, &found);
     printf("found %d\n", found);



     freeIntKeyContainer(s1);

  system("PAUSE");
  return 0;
}