#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#define MIN(a,b) (((a)<(b))?(a):(b))
#define NULL (void *)0

struct dictionary{
  int value;
  int count;
  struct dictionary* next;
};
typedef struct dictionary item;

static item* push(int v,int c,item* curr){
  item* head = malloc(sizeof(item));
  head->value = v;
  head->count = c;
  head->next = curr;
  return head;
}

static item* hash(item* head,int index){
  item* iterator = head;
  while(iterator){
    if(iterator->value == index){
      return iterator;
    }
    iterator = iterator->next;
  }

  return NULL;
}



static int scores(int src[],int tgt[],int ax,int ay){
  int i,j;
  int scores[ax+2][ay+2];
  item *head = NULL;
  int INF = ax + ay;
  scores[0][0] = INF;

  /* handle blank strings */
  if(ax == 0){
    return ay;
  }else if(ay == 0){
   return ax;
  }


  /* setup scoring matrix */
  for(i=0;i<=ax;i++){
    scores[i+1][1] = i;
    scores[i+1][0] = INF;

    if(hash(head,src[i]) == NULL){
      head = push(src[i],0,head);
    }
  }
  for(j=0;j<=ay;j++){
    scores[1][j+1] = j;
    scores[0][j+1] = INF;

    if(hash(head,tgt[j]) == NULL){
      head = push(tgt[j],0,head);
    }
  }


  /* work loop */
  int db,i1,j1;
  for(i=1;i<=ax;i++){
    db = 0;
    for(j=1;j<=ay;j++){
      i1 = hash(head,tgt[j-1])->count;
      j1 = db;

      if(src[i-1] == tgt[j-1]){
        scores[i+1][j+1] = scores[i][j];
        db = j;
      }else{
        scores[i+1][j+1] = MIN(scores[i][j], MIN(scores[i+1][j], scores[i][j+1])) + 1;
      }

      scores[i+1][j+1] = MIN(scores[i+1][j+1], scores[i1][j1] + i - i1 - 1 + j - j1);
    }

    hash(head,src[i-1])->count = i;
  }

  return scores[ax+1][ay+1];
}

int cxs_edistance (AV* arraySource, AV* arrayTarget) {

    /* Skip down to next comment chunk, not using this yet */
    /* This is left to clarify what we're solving          */

    int i,j;
    int lenSource = av_len(arraySource)+1;
    int lenTarget = av_len(arrayTarget)+1;
    int arrSource [ lenSource ];
    int arrTarget [ lenTarget ];
    int lenSource2 = 0;
    int lenTarget2 = 0;

    for (i=0; i < lenSource; i++) {
        SV** elem = av_fetch(arraySource, i, 0);
        int retval = SvNV(*elem);

        if (elem != NULL) {
            arrSource[ i ] = retval;
             lenSource2++;
        }
    }
    for (j=0; j < lenTarget; j++) {
        SV** elem = av_fetch(arrayTarget, j, 0);
        int retval = SvNV(*elem);

        if (elem != NULL) {
            arrTarget[ j ] = retval;
             lenTarget2++;
        }
    }
    //return scores(arrSource,arrTarget,lenSource2,lenTarget2);


    /* For testing purposes, we use known values                    */
    /* Ok, perl, here are values that compile with cc and return 1 */

    int arrSourcex[4];
    int arrTargetx[4];

    arrSourcex[0] = 1;
    arrSourcex[1] = 2;
    arrSourcex[2] = 3;
    arrSourcex[3] = 4;

    arrTargetx[0] = 1;
    arrTargetx[1] = 3;
    arrTargetx[2] = 2;
    arrTargetx[3] = 4;


    int lenSourcex2 = 4;
    int lenTargetx2 = 4;

    // *should* return 1, instead it craps out
    //
    // If you remove this function, compile as C, and run main,
    //  it succesfully returns the correct value

    return scores(arrSourcex,arrTargetx,lenSourcex2,lenTargetx2);
}

int main(void) {
    // Same code as cxs_distance
    // Left for ease of compiling outside of perl

    int arrSourcex[4];
    int arrTargetx[4];

    arrSourcex[0] = 1;
    arrSourcex[1] = 2;
    arrSourcex[2] = 3;
    arrSourcex[3] = 4;

    arrTargetx[0] = 1;
    arrTargetx[1] = 3;
    arrTargetx[2] = 2;
    arrTargetx[3] = 4;


    int lenSourcex2 = 4;
    int lenTargetx2 = 4;

    return scores(arrSourcex,arrTargetx,lenSourcex2,lenTargetx2);
}

MODULE = Text::Levenshtein::Damerau::XS PACKAGE = Text::Levenshtein::Damerau::XS

PROTOTYPES: DISABLE

int
cxs_edistance (arraySource, arrayTarget)
    AV *    arraySource
    AV *    arrayTarget