/* An interface for updating a key-value index.
 */
@value interface KVWriter<#k,#v|> {
  // #self below always means the type of value that the function is being
  // called from. For example, the type of foo.remove(key) is the same type as
  // foo is.

  set (#k,#v) -> (#self)
  remove (#k) -> (#self)
}

/* An interface for looking up values from a key-value index.
 */
@value interface KVReader<#k|#v> {
  get (#k) -> (optional #v)
}

/* An AVL implementation of KVWriter and KVReader.
 */
concrete Tree<#k,#v> {
  refines KVWriter<#k,#v>
  refines KVReader<#k,#v>
  #k defines LessThan<#k>

  // Creates a new Tree, e.g., Tree.new().
  @type new () -> (Tree<#k,#v>)

  // Since set and remove return #self, their implementations in Tree must
  // return Tree<#k,#v>.
}