sclass HuffmanTree is BitIO {
  gettable Node root;
  Leaf[] characterMap = new[256];
  
  /*
  algebraic Node {
    constructor Branch {
      settable Node zero;
      settable Node one;
    }
    constructor Leaf {
      settable byte literal;
    }
  }
  */
  
  abstract class Node is BitIO {
    settable Branch parent;
    
    void buildSymbol(BitBuffer head, Node child) {
      parent?.buildSymbol(head, this);
    }
  }
  
  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);
    }
  }
  
  class Leaf > Node {
    gettable byte literal;
    
    *() {}
    *(int literal) { literal((byte) literal); }
    
    byte get() { ret literal; }
    
    selfType literal(byte b) {
      literal = b;
      fillCharacterMap();
    }
    
    public void readWrite(BitHead head) {  
      head.exchangeBit(0);
      head.exchangeByte(literal, l1 literal);
    }
    
    void fillCharacterMap {
      characterMap[ubyteToInt(literal)] = this;
    }
  }
  
  void makeRootIfEmpty {
    root ifNull = new Leaf(0);
  }
  
  Node readNode(BitHead head) {
    Node node = head.peekBit() ? new Branch : new Leaf;
    node.readWrite(head);
    ret node;
  }
  
  public void readWrite(BitHead head) {
    makeRootIfEmpty();
    root.readWrite(head);
  }
  
  toString {
    makeRootIfEmpty();
    new LS out;
    new StringBuilder symbol;
    
    embedded void toString_collect(Node node) {
      if (node cast Leaf) {
        symbol.append("0");
        out.add(symbol + ": " + /*ubyteToHex*/quote(codePoint(node!)));
        removeLast(symbol);
      } else {
        cast node to Branch;
        symbol.append("1");
        toString_collect(node.zero());
        toString_collect(node.one());
        removeLast(symbol);
      }
    }
    
    toString_collect(root);
    ret lines(out);
  }
  
  selfType root(Node root) {
    this.root = root;
    makeCharacterMap();
    this;
  }
  
  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);
    for (int i = l(buffer)-1; i >= 0; i--)
      head.writeBit(buffer.get(i));
  }
}