sclass HuffmanTree is BitIO {
  settable Node root;
  
  /*
  algebraic Node {
    constructor Branch {
      settable Node zero;
      settable Node one;
    }
    constructor Leaf {
      settable byte literal;
    }
  }
  */
  
  abstract static class Node is BitIO {}
  
  static class Branch > Node {
    settable Node zero;
    settable Node one;
    
    public void readWrite(BitHead head) {  
      head.writeBit(1);
      head.exchange(zero);
      head.exchange(one);
    }
  }
  
  static class Leaf > Node {
    settable byte literal;
    
    *() {}
    *(int literal) { literal((byte) literal); }
    
    byte get() { ret literal; }
    
    public void readWrite(BitHead head) {  
      head.writeBit(0);
      head.writeByte(literal);
    }
  }
  
  void makeRootIfEmpty {
    root ifNull = new Leaf(0);
  }
  
  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);
  }
}