#include <stdlib.h>
#include<algo.h>

template <class KTYPE, class T>
int operator<(indexxpair<KTYPE, T> a, indexxpair<KTYPE, T> b)
{
  if(a.key < b.key)
    return 1;
  else
    return 0;
}

template <class KTYPE, class T, int M>
indexx<KTYPE, T, M>::indexx()
{
  size = 0;
  maxsize = M;
  cursor = 0;
}

template <class KTYPE, class T, int M>
int indexx<KTYPE, T, M>::insert(KTYPE k, T * dp)
{
  if (size < maxsize)
  {
    int i=size;
    int first = findfirst(k);
    for( i; i>first; i--)
    {
      pairs[i] = pairs[i-1];
    }
    pairs[i].key = k;
    pairs[i].dataptr = dp;
    size++;
    return 1;
  }
  return 0;
}

template <class KTYPE, class T, int M>
int indexx<KTYPE, T, M>::remove(KTYPE k)
{
  int first;
  first = findfirst(k);
  if (first < 0 || first >= size || pairs[first].key != k)
    return 0;
  else
  {
    for (int i=first; i<(size-1); i++)
      pairs[i] = pairs[i+1];
    size--;
    return 1;
  }
}

template <class KTYPE, class T, int M>
int indexx<KTYPE, T, M>::findfirst(KTYPE k)
{
  indexxpair<KTYPE, T> temp;
  temp.key = k;
  indexxpair<KTYPE, T> * p = lower_bound(pairs, pairs+size, temp);
  if(p!=NULL)
    return(p-pairs);
  else
    return(-1);
}

template <class KTYPE, class T, int M>
T * indexx<KTYPE, T, M>::lookup(KTYPE k)
{
  int first = findfirst(k);
  cursor = first;
  if (first < 0 || first >= size || pairs[first].key != k)
    return NULL;
  else
    return pairs[first].dataptr;
}

template <class KTYPE, class T, int M>
T * indexx<KTYPE, T, M>::next(KTYPE k)
{
  if (cursor < size && pairs[++cursor].key == k)
    return pairs[cursor].dataptr;
  else
    return NULL;
}