#ifndef LIBRARY_H
#define LIBRARY_H

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#ifndef _WIN32
#include <sys/time.h>
#else
#include <sys/timeb.h>
#endif

// A simple pair (or tuple) type 
template<class T, class U> struct Pair { T a; U b; };

// A simple equality function for primitives
// (useful as a template argument)
template<class T> inline bool eq(T a, T b) { return a == b; }

// A linked list type (nil is 0)
template<class T> struct List { T car; List<T> *cdr; };

// Construct a new cons cell
//static int consCount;
template<class T> inline List<T> *cons(T car, List<T> *cdr) {
    List<T> *ret = new List<T>;
    ret->car = car;
    ret->cdr = cdr;
    //consCount++;
    return ret;
}

template <class T> bool eq(List<T> *x, List<T> *y) {
    if(!x) return !y;
    else if(!y) return false;
    else if(!eq(x->car,y->car)) return false;
    else return eq(x->cdr,y->cdr);
}

// Find the length of a linked list
template<class T> int length(List<T> *xs) {
    int len;
    for(len=0;xs;xs=xs->cdr) len++;
    return len;
}

// Return the first n elements from the list
template<class T> List<T> *take(int n, List<T> *xs) {
    List<T> *prev, *head;
    if(!xs) return 0;
    head = prev = cons<T>(xs->car,0);
    while(--n) {
        xs = xs->cdr;
        if(!xs) break;
        prev->cdr = cons<T>(xs->car,0);
        prev = prev->cdr;
    }
    return head;
}

// Concat returns a NEW list that shares b, a is not needed after a concat
template<class T> List<T> *concat(List<T> *a, List<T> *b) {
    List<T> *prev,*head;
    if(!a) return b;
    head = prev = cons<T>(a->car,0);
    for(;;) {
        a = a->cdr;
        if(!a) break;
        prev->cdr = cons<T>(a->car,0);
        prev = prev->cdr;
    }
    prev->cdr = b;
    return head;   
}

template<class T> void deepFreeList(List<T> *xs) {
    List<T> *tmp;
    while(xs) {
        tmp = xs->cdr;
        delete xs;
        xs = tmp;
    }
}

// Generic output functions, fput(x,fp) and put(x) can be applied to any type
static inline size_t fput(char c, FILE *fp) { return fputc(c,fp); }
static inline size_t fput(const char *s, FILE *fp) { return fputs(s,fp); }
static inline size_t fput(int i, FILE *fp) { return fprintf(fp,"%d",i); }
template <class T>
size_t fput(List<T> *xs, FILE *fp) {
    for(;xs;xs=xs->cdr) if(fput(xs->car,fp)<0) return EOF;
    return 0;
}
template <class T,class U>
size_t fput(Pair<T,U> pair, FILE *fp) {
    if(putchar('(')<0) return EOF;
    if(fput(pair.a,fp)<0) return EOF;
    if(putchar(',')<0) return EOF;
    if(fput(pair.b)<0) return EOF;
    if(putchar(')')<0); return EOF;
    return 0;
}

template<class T> 
size_t put(T x) {
    if(fput(x,stdout)<0) return EOF;
    if(putchar('\n')<0) return EOF;
    return 0;
}

// Time functions
#ifdef _WIN32
struct timeval { long tv_sec; long tv_usec; };
static inline int gettimeofday(struct timeval *tv, void *ignore) {
    struct _timeb buf;
    _ftime_s(&buf);
    tv->tv_sec = buf.time;
    tv->tv_usec = buf.millitm * 1000;
    return 0;
}
#endif

static inline unsigned long timeval_diff_ms(struct timeval a, struct timeval b) {
    return (a.tv_sec - b.tv_sec)*1000 + (a.tv_usec - b.tv_usec + 500) / 1000;
}

#endif