/*
 *  PSX-Tools Bundle Pack
 *  Copyright (C) 2002 Nicolas "Pixel" Noble
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include "generic.h"
#include "Handle.h"

class thingtree : public Base {
  public:
    static void addstring(const String, long);
    static long look(const String);
    static void destroy();
  private:
      thingtree();
      thingtree(char, bool, thingtree *, long);
      ~thingtree();
    char thischar;
    bool terminal;
    thingtree * father, * child, * brother;
    long thingentry;
    static thingtree * root;
};

thingtree * thingtree::root = 0;

thingtree::thingtree(char gchar, bool gterm, thingtree * gfather, long gthingentry) : thischar(gchar), terminal(gterm), thingentry(gthingentry) {
    if (!gfather) {
	if (!root) {
	    root = new thingtree();
	}
	father = root;
    } else {
	father = gfather;	
    }
    brother = father->child;
    father->child = this;
}

thingtree::thingtree() : thischar(0), terminal(false), father(0), child(0), brother(0) { }

long thingtree::look(const String s) {
    long currentthing = -1;
    thingtree * ptr = root;
    int i;
    
    if (!ptr) {
	printm(M_ERROR, "Error: thingtree not initialised\n");
	exit(-1);
    }
    
    for (i = 0; s[i]; i++) {
//	printm(M_INFO, "Looking for '%c'\n", *p);
	for (ptr = ptr->child; ptr; ptr = ptr->brother) {
//	    printm(M_INFO, "Looking in %p: %c\n", ptr, ptr->thischar);
	    if (ptr->thischar == s[i]) {
		if (ptr->terminal) {
		    currentthing = ptr->thingentry;
		}
		break;
	    }
	}
	if (!ptr) {
//	    printm(M_INFO, "Not found.\n");
	    break;
	}
    }
    
    if (currentthing == -1) {
	printm(M_ERROR, "Error, can't find any entry for string '" + s + "'\n");
    }
    
    return currentthing;
}

void thingtree::addstring(const String s, long thingentry) {
    thingtree * ptr, * fptr;
    int i;
    
    if (!root) {
	root = new thingtree();
    }
    
//    printm(M_INFO, "Creating new thingtree entry: %li='%s'\n", thingentry, s);
    
    ptr = root;
    for (i = 0; s[i]; i++) {
	fptr = ptr;
//	printm(M_INFO, "Finding entry for '%c'\n", *p);
	for (ptr = ptr->child; ptr; ptr = ptr->brother) {
//	    printm(M_INFO, "Browsing childs: %p = %c\n", ptr, ptr->thischar);
	    if (ptr->thischar == s[i])
		break;
	}
	
	if (!ptr) {
//	    printm(M_INFO, "Creating new branch for %c\n", *p);
	    ptr = new thingtree(s[i], s[i + 1] == 0, fptr, thingentry);
//	    printm(M_INFO, "Created branch %p\n", ptr);
	} else {
	    if (s[i + 1] == 0) {
		ptr->terminal = true;
		ptr->thingentry = thingentry;
	    }
	}
    }
}

void thingtree::destroy() {
    delete root;
    root = 0;
}

thingtree::~thingtree() {
    if (father->child == this)
	father->child = brother;
    
    while (child)
	delete child;
}

String things[256];

char * dte_text;
char dte_flags[256 * 256];
long dte_counters[256 * 256];
long dte_entries[256];
char alloweds[256];
long dte_usage[256];

long dte_most;
long dte_counter;
long dte_text_size;
int dte_size;
long gain;
long nb_dte = 0;
long tnb_dte = 0;

void dte_reset(void) {
    memset(dte_counters, 0, 0x40000);
    dte_most = 0;
    dte_counter = 0;
}

void build_dte(void) {
    int i;
    Uint16 t, t2;
    unsigned short p = 0;
    
    for (i = 0; i < dte_text_size; i++) {
	t = *((Uint16 *) (dte_text + i));
	t2 = *((Uint16 *) (dte_text + i + 1));
	if (t == p) {
	    p = 0;
	    continue;
	}
	p = t;
	if (!dte_flags[t]) {
//	if ((!dte_flags[t]) && (dte_flags[t2] != 3)) {
	    if ((dte_counters[t]++) == 0) {
		nb_dte++;
	    }
	    if (dte_counters[t] > dte_counter) {
		dte_most = t;
		dte_counter = dte_counters[t];
	    }
//	} else if (dte_flags[t] == 3) {
//	    i++;
	}
    }
}

void push_entry(long entry) {
    int i;
    char t[3], c1, c2;
    t[2] = 0;
    
    c1 = dte_most & 0xff;
    c2 = dte_most >> 8;
    t[0] = things[c1][0];
    t[1] = things[c2][0];

    for (i = 0; i < 256; i++) {
	if (!dte_entries[i]) {
	    dte_entries[i] = entry;
	    things[i] = strdup(t);
	    thingtree::addstring(t, i);
	    break;
	}
    }
}

void dte_compress() {
    int i, j;
    char c1, c2;
    
    for (i = 0; i < 256; i++) {
	for (j = 0; j < 256; j++) {
	    dte_flags[i * 256 + j] = alloweds[i] ? alloweds[j] ? 0 : 1 : 1;
	}
    }
    
    gain = 0;
    
    printm(M_STATUS, "Going for it: dte_size = %i\n", dte_size);
    for (i = 0; i < dte_size; i++) {
	dte_reset();
	build_dte();
	if (!tnb_dte)
	    tnb_dte = nb_dte;
	c1 = dte_most & 0xff;
	c2 = dte_most >> 8;
	c1 = things[c1][0];
	c2 = things[c2][0];
	printm(M_INFO, "Entry #%i, most count: %li, couple = 0x%04x = (%c %c)\n", i, dte_counter, (int) dte_most, c1, c2);
	dte_flags[dte_most] = 3;
	gain += dte_counter;
	push_entry(dte_most);
    }
    
    printm(M_STATUS, "Estimated gain: %li bytes, new file size = %li\n", gain, dte_text_size - gain);
}

void read_thingy(Handle * f) {
    String line, st, thing;
    long code;
    int i;
    
    dte_size = 0;
    
    for (i = 0; i < 256; i++) {
	dte_entries[i] = -1;
    }
    
    while (1) {
	line = "0x";
	*f >> st;
	if (st.strlen()) {
	    line += st.extract(0, 1);
	    code = line.to_int();
	    thing = st.extract(3);
	    switch (thing.strlen()) {
	    case 0:
		dte_size++;
		dte_entries[code] = 0;
		break;
	    case 1:
		alloweds[code] = 1;
	    default:
		things[code] = thing;
		thingtree::addstring(thing, code);
	    }
	}
    }
}

void read_thingy_file(Handle * f) {
    String line, trans;
    long code;
    int ptr = 0, i, c;
    
    for (i = 0; i < 256; i++) {
	dte_usage[i] = 0;
    }
    
    while (1) {
	*f >> line;
	if (!line.strlen())
	    continue;
	i = 0;
	while (line[i]) {
	    if (line[i] == '<') {
		if ((c = line.strchr('>', i)) < 0) {
		    printm(M_ERROR, "Error in file: '<' not closed.\n");
		    exit(-1);
		}
		i++;
		if (c == 2) {
		    trans = "0x" + line.extract(i, 2);
		    code = line.to_int();
		    dte_text[ptr++] = code;
		    printm(M_BARE, "0x%02x-", code);
		} else {
		    printm(M_BARE, "Unknow " + trans.extract(2) + "-");
		}
		i += c;
	    } else {
		if ((code = thingtree::look(line.extract(i))) == -1)
		    exit(-1);
		dte_text[ptr++] = code;
		i += things[code].strlen();
		printm(M_BARE, things[code] + "-");
		dte_usage[code]++;
	    }
	}
	printm(M_BARE, "\n");
    }
    
    dte_text[ptr] = dte_text[ptr + 1] = dte_text[ptr + 2] = dte_text[ptr + 3] = 0;
    dte_text_size = ptr;
}