/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package svgconverter;

import java.util.*;

/**
 *
 * @author Pap
 */
public class HuffCode<T>{
    public class Entry{
        T   value;
        int cnt;
        Entry   child0 = null;
        Entry   child1 = null;
        Entry   parent = null;
    }

    Vector<Entry> entries = new Vector<Entry>();
    Vector<Entry> rawEntries = new Vector<Entry>();

    public void AddEntry(T value, int cnt) {
        Entry e = new Entry();
        e.cnt = cnt;
        e.value = value;
        this.entries.add(e);
    }

    public void CalculateTree() {
        for(int i = 0; i < this.entries.size(); i++)
            this.rawEntries.add(this.entries.get(i));
        while(this.entries.size() != 1) {
            // lookup lowest freq trees
            LinkedList<Entry> ee = new LinkedList<Entry>();
            for(int t = 0; t < 2; t++) {
                Entry best = null;
                for(int i = 0; i < this.entries.size(); i++) {
                    Entry e = this.entries.get(i);
                    if((best == null) || (e.cnt <= best.cnt)) {
                        best = e;
                    }
                }
                this.entries.remove(best);
                ee.add(best);
            }
            Entry ne = new Entry();
            ne.child0 = ee.get(0);
            ne.child1 = ee.get(1);
            ne.child0.parent = ne;
            ne.child1.parent = ne;
            ne.cnt = ne.child0.cnt + ne.child1.cnt;
            this.entries.add(ne);
        }
    }

    public LinkedList<Boolean> getPath(T value) {
        LinkedList<Boolean> res = new LinkedList<Boolean>();
        Entry e = null;
        for(int i = 0; i < this.rawEntries.size(); i++)
            if(this.rawEntries.get(i).value.equals(value)) {
                e = this.rawEntries.get(i);
                break;
            }
        while(e.parent != null) {
            if(e.parent.child0 == e)
                res.addFirst(Boolean.FALSE);
            else
                res.addFirst(Boolean.TRUE);
            e = e.parent;
        }
        return res;
    }
}
