sclass HuffmanTree is BitIO {
  settable Node root;
  Leaf[] characterMap = new[256];
  
  settable bool debug;
  replace print with if (debug) print.
  
  /*
  algebraic type Node {
    constructor Branch(Node zero, Node one) {}
    constructor Leaf(byte literal) {}
  }
  */
  
  abstract class Node is BitIO {
    settable Branch parent;
    
    void buildSymbol(BitBuffer head, Node child) {
      parent?.buildSymbol(head, this);
    }
    
    abstract Leaf readSymbol(BitHead head);
  }
  
  class Branch > Node {
    gettable Node zero;
    gettable Node one;
    
    meta-for zero also as one {
      selfType zero(Node zero) {
        this.zero = zero;
        zero.parent = this;
        this;
      }
    }
    
    public void readWrite(BitHead head) {  
      head.exchangeBit(1);
      head.exchange(zero, -> zero(readNode(head)));
      head.exchange(one, -> one(readNode(head)));
    }
    
    void buildSymbol(BitBuffer head, Node child) {
      head.add(child == one);
      super.buildSymbol(head, child);
    }
    
    Leaf readSymbol(BitHead head) {
      bool bit = head.readBit();
      print("Read bit " + bit);
      ret (bit ? one : zero).readSymbol(head);
    }
  }
  
  class Leaf > Node {
    gettable byte literal;
    
    *() {}
    *(int literal) { literal((byte) literal); }
    
    byte get() { ret literal; }
    
    selfType literal(byte b) {
      literal = b;
      fillCharacterMap();
      this;
    }
    
    public void readWrite(BitHead head) {  
      head.exchangeBit(0);
      head.exchangeByte(literal, l1 literal);
      print(this);
    }
    
    void fillCharacterMap {
      characterMap[ubyteToInt(literal)] = this;
    }
    
    Leaf readSymbol(BitHead head) {
      print("Reached symbol " + this);
      this;
    }
    
    toString { 
      ret "Literal " + byteToHex(literal);
    }
  }
  
  void makeRootIfEmpty {
    root ifNull = new Leaf(0);
  }
  
  Node readNode(BitHead head) {
    bool type = head.peekBit();
    Node node = type ? new Branch : new Leaf;
    print(type ? "Branch" : "Leaf");
    node.readWrite(head);
    ret node;
  }
  
  public void readWrite(BitHead head) {
    if (head.writeMode()) {
      makeRootIfEmpty();
      root.readWrite(head);
    }
    
    if (head.readMode())
      root = readNode(head);
  }
  
  toString {
    makeRootIfEmpty();
    new LS out;
    new StringBuilder symbol;
    
    embedded void toString_collect(Node node) {
      if (node cast Leaf) {
        out.add(symbol + ": " + /*ubyteToHex*/quote(codePoint(ubyteToInt(node!))));
      } else {
        cast node to Branch;
        symbol.append("0");
        toString_collect(node.zero());
        removeLast(symbol);
        symbol.append("1");
        toString_collect(node.one());
        removeLast(symbol);
      }
    }
    
    toString_collect(root);
    ret lines(out);
  }
  
  void writeCharacter aka writeSymbol(int sym, BitHead head) {
    sym &= 0xFF;
    Leaf node = characterMap[sym];
    if (node == null)
      fail("Symbol cannot be encoded: " + sym);
    new BitBuffer buffer;
    node.buildSymbol(buffer, null);
    
    // when there is only one symbol
    if (buffer.isEmpty())
      buffer.add(0);
      
    for (int i = l(buffer)-1; i >= 0; i--)
      head.writeBit(buffer.get(i));
  }
  
  int readSymbol(BitHead head) {
    if (head.isEOF()) ret -1;
    
    if (root instanceof Leaf)
      head.advanceBit(); // don't even care
      
    ret ubyteToInt(root.readSymbol(head)!);
  }
}