#include <assert.h>
#include <stdio.h>
#include "piece-table.h"

/*
 * We probably should have a pool of pieces and go using them and deleting them
 * from there instead of malloc/free but we are lazy
 */
static void print_string(char *str, size_t size) {
    size_t i;
    printf("\"");
    for ( i=0; i < size; i++) {
        printf("%c", str[i]);
    }
    printf("\"");
}

void print_piece_table (piece_table *pt) {
    piece *cur;
    printf("piece_table {");
    printf("\n\toriginal: "); print_string(pt->orig.content, pt->orig.size);
    printf("\n\tadd: "); print_string(pt->add.content, pt->add.used);
    printf("\n\tlength: %ld", pt->length);
    printf("\n\tpieces: ");
    for ( cur = pt->sentinel->next; cur != pt->sentinel; cur = cur->next ) {
        printf("\n\t\ttext: "); print_string(cur->start, cur->length);
    }
    printf("\n\t cached_offset: %ld", pt->cached_offset);
    printf("\n\t cached (piece-text):");
        print_string(pt->cached->start, pt->cached->length);
    printf("\n}\n");
}

static piece *make_piece() {
    return malloc(sizeof(piece));
}

static piece *make_piece_list() {
    /* Makes a sentinel connected to itself in a ring*/
    piece *p = make_piece();
    p->next = p;
    p->prev = p;
    p->length = 0;
    p->start  = NULL;
    return p;
}

void init_piece_table(piece_table *pt, char *orig) {
    piece *pc;

    init_growable_buffer(&pt->add);
    init_fixed_buffer(&pt->orig, orig);

    pt->length = pt->orig.size;

    pt->sentinel = make_piece_list();

    pc = make_piece();
    pc->start = pt->orig.content;
    pc->length = pt->orig.size;
    pc->prev = pt->sentinel;
    pc->next = pt->sentinel;

    pt->sentinel->next = pc;
    pt->sentinel->prev = pc;

    pt->cached_offset = 0;
    pt->cached = pc;
}


static void free_piece_list(piece *p) {
    piece *cur, *next;
    assert(p != NULL);
    for ( cur = p->next; cur != p; cur = next ) {
        next = cur->next;
        free(cur);
    }
    free(cur);
}

void free_piece_table(piece_table *pt) {
    free_growable_buffer(&pt->add);
    free_piece_list(pt->sentinel);
    pt->sentinel = NULL;
    pt->cached = NULL;
    pt->cached_offset = 0;
    pt->length = 0;
}


static void find_piece_by_pos(piece_table *pt, size_t pos) {
    piece *cur;
    assert(pos < pt->length);
    if ( pos >= pt->cached_offset ) {
        /* Search forward */
        for ( cur = pt->cached; ; cur = cur->next ) {
            if ( pt->cached_offset + cur->length > pos ) {
                pt->cached = cur;
                assert(pt->cached != pt->sentinel);
                return;
            }
            pt->cached_offset += cur->length;
        }
    } else {
        /* Search backwards */
        for ( cur = pt->cached->prev; ; cur = cur->prev ) {
            pt->cached_offset -= cur->length;
            if ( pt->cached_offset < pos ) {
                pt->cached = cur;
                assert(pt->cached != pt->sentinel);
                return;
            }
        }
    }
}

char index_piece_table(piece_table *pt, size_t pos) {
    assert(pos < pt->length);
    find_piece_by_pos(pt, pos);
    return pt->cached->start[pos - pt->cached_offset];
}


static piece *split_piece(piece *p, size_t pos) {
    /* Returns the first piece */
    piece *second;
    assert(pos < p->length);
    assert(p->start != NULL); /* Not a sentinel piece */
    assert(p->start != 0);    /* Not an empty piece (they should not exist) */
    if ( pos == 0 ) {
        return p->prev;
    }
    second = make_piece();
    second->length = p->length - pos;
    p->length = pos;
    second->next = p->next;
    p->next = second;
    second->prev = p;
    second->start = p->start + pos;
    return p;
}

void insert_piece_table(piece_table *pt, size_t pos, char *in, size_t in_len) {
    piece *start, *end, *new;

    assert( pos <= pt->length );
    assert( in_len > 0 );

    append_growable_buffer(&pt->add, in, in_len);

    if ( pos == 0 ) {
        start = pt->sentinel;
    } else if ( pos == pt->length ) {
        start = pt->sentinel->prev;
        pt->cached_offset = pt->length - start->length;
        pt->cached = start;
    } else {
        find_piece_by_pos(pt, pos);
        start = split_piece(pt->cached, pos - pt->cached_offset);
    }
    end = start->next;

    /* Update cache;
     * If we insert before our cached piece, the offset is not up-to-date
     * anymore.
     */
    if ( pt->cached_offset >= pos ) {
        pt->cached = pt->cached->prev;
        pt->cached_offset -= pt->cached->length;
    }

    /* Optimization!
     * Add in the end of the buffer, and the end of the piece: enlarge
     */
    if ( pt->add.used != 0 &&
         pt->cached_offset + start->length == pos &&
         pt->add.content + pt->add.used ==
            start->start + start->length + in_len ) {
        pt->length += in_len;
        start->length += in_len;
        return;
    }
    /* Make a new piece and insert it */
    new = make_piece();
    new->start = pt->add.content + pt->add.used - in_len;
    new->length = in_len;

    start->next = new;
    new->prev = start;
    new->next = end;
    end->prev = new;
    pt->length += in_len;
}

void delete_piece_table(piece_table *pt, size_t pos, size_t len) {
    piece *cur, *next, *start, *end;
    size_t off_start;
    assert( pos + len <= pt->length );
    assert( len > 0 );

    if ( pos == 0 ) {
        start = pt->sentinel;
        off_start = 0;
    } else {
        find_piece_by_pos(pt, pos);
        off_start = pt->cached_offset;
        start = split_piece(pt->cached, pos - pt->cached_offset);
    }

    if ( pos + len == pt->length ) {
        end = pt->sentinel;
    } else {
        find_piece_by_pos(pt, pos + len);
        end = split_piece(pt->cached, pos + len - pt->cached_offset)->next;
    }

    /* Update cache to before the start */
    if ( pt->cached_offset >= pos ) {
        pt->cached = start;
        pt->cached_offset = off_start;
    }

    /* Free unneeded pieces */
    for ( cur = start->next; cur != end ; cur = next ) {
        next = cur->next;
        free(cur);
    }

    start->next = end;
    end->prev = start;
    pt->length -= len;
}