/*
BasicHuffman.java : a program which lets you pick characters using a Huffman tree.
    Copyright 2010  Ken Takusagawa

    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 3 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, see <http://www.gnu.org/licenses/>.
*/

import java.util.*;
abstract class Node {
    public InternalNode parent;
    
    public Node(InternalNode in_parent){
        parent=in_parent;
    }
    abstract public Set<Character> charsset();
}

class LeafNode extends Node {
    public Character x;
    public LeafNode(InternalNode in_parent, char inchar){
        super(in_parent);
        x=Character.valueOf(inchar);
    }
    public String toString (){
        return x.toString();
    }
    public Set<Character> charsset(){
        Set<Character> s=new TreeSet<Character>();
        s.add(x);
        return s;
    }
}

class InternalNode extends Node {
    public Node[] children;
    public InternalNode(InternalNode in_parent){
        super(in_parent);
        children=new Node[2];
    }
    public String toString(){
        if(children[0].parent!=this)
            return "!";
        if(children[1].parent!=this)
            return "@";
        return "("+children[0].toString()+children[1].toString()+")";
    }
    public Set<Character> charsset(){
        Set<Character> x=children[0].charsset();
        x.addAll(children[1].charsset());
        return x;
    }
    public InternalNode find(Character c){
        Node n=children[0];
        if (children[1].charsset().contains(c)){
            n=children[1];
        }
        if (n instanceof InternalNode)
            return ((InternalNode)n).find(c);
        else
            return this;
    }
}

class Zippernode {
    public InternalNode current;
    private final Character initchar;
    private Map<Character,InternalNode> h;
    private Outputacceptor out;
    public Zippernode(Outputacceptor in_out){
        out=in_out;
        h=new HashMap<Character,InternalNode>();
        h.put(Character.valueOf('+'),Work.createTreeFromString("::::yz:wx:::qr:op::uv:st::::ij:gh::mn:kl:::ab:+_::ef:cd"));
        h.put(Character.valueOf('_'),Work.createTreeFromString(":::i:c:::::::+_xzqkun:a::lro:::w:::jvyf::dp:hm:t:s::geb"));
        h.put(Character.valueOf('a'),Work.createTreeFromString(":::_l:r:::u:fhm:bv::::i:k:w::z:ea::j::+oqx:dyt::::pgcsn"));
        h.put(Character.valueOf('b'),Work.createTreeFromString("::::y::b:j::::h:::+xkqd::z:fgnv_a:lo:::i:::t::m:pwcsrue"));
        h.put(Character.valueOf('c'),Work.createTreeFromString("::o::li:k:ur::he:a:::c:y:s:n::p:bm:d::f:::+xw:jz:q:vg_t"));
        h.put(Character.valueOf('d'),Work.createTreeFromString(":_::o:a:s:::::::k:::+xzqptwvgn:e:::r:ld:u:y:::bf::jhcmi"));
        h.put(Character.valueOf('e'),Work.createTreeFromString(":::n::y:fo::p::qh:b:k:::+jzu:ix:::mea:d:c::gwv::r::lts_"));
        h.put(Character.valueOf('f'),Work.createTreeFromString("::o::uai:::f:t::::c::m::::::+qzjxvhds:::gb:w:p:nkyl:re_"));
        h.put(Character.valueOf('g'),Work.createTreeFromString(":_::he::::lnuo::::g:y:t:::cb:w:::vz:k:::+xqjd::fpmsa:ir"));
        h.put(Character.valueOf('h'),Work.createTreeFromString(":e::i_:::t::uy:r:::l::p::zgvb::::f::::+jxkqcd:wh::snmoa"));
        h.put(Character.valueOf('i'),Work.createTreeFromString(":::::v::::u::h::+yw:jq:ixzkos:::mr:fe:c:g::pba:n:t::dl_"));
        h.put(Character.valueOf('j'),Work.createTreeFromString("::o:e:a::h::cp:::bv::njm:ts:_:::f:w:l:k:g:q:::+zxy:rdiu"));
        h.put(Character.valueOf('k'),Work.createTreeFromString(":_:e:i:::::r:gbo:::wh:p::c:::::+zqxvjkl:a:y:u::md:tf:sn"));
        h.put(Character.valueOf('l'),Work.createTreeFromString(":::a::u::v:cw::r:b:::h:::+qx:jzngf:s::k:mpt:yi:::dol:e_"));
        h.put(Character.valueOf('m'),Work.createTreeFromString(":::i:::::tl:::gvdc:n::f::w::x::+qz:kjhrsp:o::bm:uy:e:a_"));
        h.put(Character.valueOf('n'),Work.createTreeFromString("::::s:y::::::q::+xzbhmf:u:::wp:rjvt:d::aio:_:g::c:k:lne"));
        h.put(Character.valueOf('o'),Work.createTreeFromString("::::w::kc:b::y::::+qzjxg:m:p:iv:::sltr::u::o:d:e:ahf:_n"));
        h.put(Character.valueOf('p'),Work.createTreeFromString("::e:al::o:p:::y:::::::::+zxjqv:wkg:cb:m::nfdsu:r:_:i:ht"));
        h.put(Character.valueOf('q'),Work.createTreeFromString(":::i:a::s:we::::::::+kgh:jqf::n::yzxo:lm:::pct:r::vdb_u"));
        h.put(Character.valueOf('r'),Work.createTreeFromString("::_::ts:::::fbvkd:y:mn:e::ao:::ur::::h::::+xq:zjwpl:cgi"));
        h.put(Character.valueOf('s'),Work.createTreeFromString(":_:::iot:::a:c:::::::::+zxvjgb:qfyn:hu::s:p::k::rdw:mle"));
        h.put(Character.valueOf('t'),Work.createTreeFromString(":::e::u::cwy:sr:o:::::::f:gp:vb:::z:d:x:::+qjknmltai:h_"));
        h.put(Character.valueOf('u'),Work.createTreeFromString("::::p:i::::zx::v::w::+qjuk:ho:fyn:lr::::am:ecs:t:_::bdg"));
        h.put(Character.valueOf('v'),Work.createTreeFromString("::i:a:::::pd::u::wvlt:s:y:::::k:q::+jzgn::hxm:c::bfr_oe"));
        h.put(Character.valueOf('w'),Work.createTreeFromString("::h:::r:::::gpm::u:c:z::::+qxjvb:y:ft:w::dkl:sno::i_:ea"));
        h.put(Character.valueOf('x'),Work.createTreeFromString("::p:i::::h::f:r::::+jqg::kzd:s:nw:y:m:l:bv:u:oxe:_:t:ca"));
        h.put(Character.valueOf('y'),Work.createTreeFromString("::o::s:::cr:a:::g::k:v:::+jqxzdn:b:mw::i:t::l:u:h:yfpe_"));
        h.put(Character.valueOf('z'),Work.createTreeFromString(":e::ai:::y::w:hglo:_:z::u:::d:r:x:::+jqfmb:s:::t:vk:ncp"));
        initchar=Character.valueOf('_');
        current=h.get(initchar);
    }
    public void forward(int x){
        if(x<0 || x>1){
            //ignore
            System.err.println("out of range "+x);
        } else {
            //System.err.println("isnull"+(i!=null));
            //System.err.println("length="+i.children.length);
            Node n=current.children[x];
            if(n instanceof LeafNode){
                LeafNode l=(LeafNode)n;
                Character c=l.x;
                out.send(c);
                current=h.get(c);
            } else {
                current=(InternalNode)n;
            }
        }
    }
    public String getc(int z){
        Character[] s=current.children[z].charsset().toArray(new Character[0]);
        char[] cs=new char[s.length];
        for(int i=0;i<s.length;++i){
            cs[i]=s[i].charValue();
        }
        return new String(cs);
    }
    public String get0(){
        return getc(0)+"|"+getc(1);
    }
    public void backward(){
        if(current.parent!=null){
            current=current.parent;
        } else {
            Character curtop=out.top();
            if(curtop!=null){
                out.backspace();
                Character prev=out.top();
                if (prev==null) prev=initchar;
                current=h.get(prev);
                current=current.find(curtop);
            } else {
                current=h.get(initchar);
            }
        }
    }
}

interface Command{}
class InternalCommand implements Command {
}

class LeafCommand implements Command {
    public char x;
    public LeafCommand(char inx){
        x=inx;
    }
}

class Work{
    public static Node createTree(InternalNode parent,List<Command> cmds){
        Command c=cmds.get(0);
        cmds.remove(0);
        if(c instanceof LeafCommand){
            LeafCommand l=(LeafCommand)c;
            return (new LeafNode(parent,l.x));
        } else {
            InternalNode n=new InternalNode(parent);
            Node a=createTree(n,cmds);
            Node b=createTree(n,cmds);
            if(b.charsset().size()<a.charsset().size()){
                n.children[0]=b;
                n.children[1]=a;
            } else {
                n.children[0]=a;
                n.children[1]=b;
            }
            return n;
        }
    }
    public static Command cmake(char c) {
        if (c==':'){
            return new InternalCommand();
        } else {
            return new LeafCommand(c);
        }
    }
    public static ArrayList<Command> makecommands(String s){
        char[] cs=s.toCharArray();
        ArrayList<Command> v=new ArrayList<Command>();
        for(int i=0;i<cs.length;++i){
            v.add(cmake(cs[i]));
        }
        return v;
    }
    public static InternalNode createTreeFromString(String s){
        return (InternalNode)createTree(null,makecommands(s));
    }
}

interface Outputacceptor{
    public void send(Character c);
    public void backspace();
    public Character top();
}

class CumulativeOutput implements Outputacceptor{
    ArrayList<Character> current;
    public CumulativeOutput(){
        current=new ArrayList<Character>();
    }
    public void send(Character c){
        current.add(c);
        showstate();
    }
    private void showstate(){
        System.out.print("OUTPUT:(");
        for(Iterator<Character> p=current.iterator();p.hasNext();){
            System.out.print(p.next());
        }
        System.out.println(")");
    }
    public void backspace(){
        if(current.size()>0){
            current.remove(current.size()-1);
            showstate();
        }
    }
    public Character top(){
        if(current.size()>0){
            return(current.get(current.size()-1));
        } else {
            return null;
        }
    }
}
    

public class BasicHuffman{
    public static void main(String[] argv){
        //Node n=Work.createTree(null,Work.makecommands(":a:bc"));
        //System.out.println(n);
        System.out.println("Enter 1 or 2 to select the branch of the tree, or 0 to backspace:");
        Zippernode z=new Zippernode(new CumulativeOutput());
        Scanner s=new Scanner(System.in);
        System.out.println("STATE="+z.get0()+".");
        while(s.hasNext()){
            int i=s.nextInt();
            if(i<=0){
                z.backward();
                System.out.println("STATE="+z.get0()+".");
            } else if(i<=2){
                z.forward(i-1);
                System.out.println("STATE="+z.get0()+".");
            } else {
                System.out.println("ignored "+i);
            }
        }
    }
}