/* -----------------------------------------------------------------------------
Copyright 2021 Kevin P. Barry

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
----------------------------------------------------------------------------- */

// Author: Kevin P. Barry [ta0kira@gmail.com]

// Provides basic balanced BST functionality to custom containers.
//
// Params:
// - #n: The type of node to be managed.
// - #k: The key type used by #n.
// - #v: The value type used by #n.
// - #r: A read-only subset of the functionality of #n.
//
// Notes:
// - This is not meant for direct use: It is only exposed in this library to
//   allow other container authors to extend BST functionality by augmenting the
//   data stored along with each node. This allows the augmented data to rely on
//   where the node is within the tree.
// - #r should not expose any functionality of #n that can alter the integrity
//   of the tree. It is provided as a filter for the return of getRoot() so that
//   a container can implement custom functionality using the tree's structure
//   without risking modification of the tree.
concrete AutoBinaryTree<|#n,#k,#v|#r> {
  refines Container
  #n defines  KVFactory<#k,#v>
  #n requires BalancedTreeNode<#n,#k,#v>
  #k defines  LessThan<#k>
  #r allows   #n

  // Create a new tree.
  @type new () -> (#self)

  // Get the root of the tree.
  @value getRoot () -> (optional #r)

  // Get the value associated with the key.
  @value get (#k) -> (optional #v)

  // Set the value associated with the key.
  //
  // Notes:
  // - updateNode() will be called on every affected node, starting with the
  //   deepest node. It might be called an arbitrary number of times per node.
  @value set (#k,#v) -> ()

  // Remove the node associated with the key.
  //
  // Notes:
  // - updateNode() will be called on every affected node, starting with the
  //   deepest node. It might be called an arbitrary number of times per node.
  @value remove (#k) -> ()
}

// An interface for reading the state of a BST node.
//
// Notes:
// - This is intended for internal use in BST-based categories.
@value interface BinaryTreeNode<|#k,#v> {
  getLower  () -> (optional #self)
  getHigher () -> (optional #self)
  getKey    () -> (#k)
  getValue  () -> (#v)
  getHeight () -> (Int)
}

// An interface for managing the state of a BST node.
//
// Notes:
// - This is intended for internal use in BST-based categories.
@value interface BalancedTreeNode<#n|#k,#v|> {
  refines BinaryTreeNode<#k,#v>

  // Set the lower child of the node.
  //
  // Notes:
  // - The key for the child is strictly less-than this node's key.
  // - updateNode() will be called separately to update the node's state.
  setLower (optional #n) -> ()

  // Set the higher child of the node.
  //
  // Notes:
  // - The key for the child is strictly greater-than this node's key.
  // - updateNode() will be called separately to update the node's state.
  setHigher (optional #n) -> ()

  // Set the value associated with the node.
  setValue (#v) -> ()

  // Update the state of the node, given its position in the tree.
  //
  // Notes:
  // - This should update the height of the subtree that starts with this node;
  //   otherwise, the tree might not remain balanced.
  // - Also update any other node state that depends on the node's position
  //   within the tree.
  // - This can be called an arbitrary number of times at any time; therefore,
  //   it must always be idempotent.
  updateNode () -> ()
}

// Provides forward iteration of the nodes in a BST.
//
// Notes:
// - This is intended for internal use in BST-based categories.
concrete ForwardTreeOrder<|#k,#v> {
  refines Order<KeyValue<#k,#v>>

  @category create<#k,#v> (optional BinaryTreeNode<#k,#v>) -> (optional ForwardTreeOrder<#k,#v>)

  @category seek<#k,#v>
    #k defines LessThan<#k>
  (#k,optional BinaryTreeNode<#k,#v>) -> (optional ForwardTreeOrder<#k,#v>)
}

// Provides reverse iteration of the nodes in a BST.
//
// Notes:
// - This is intended for internal use in BST-based categories.
concrete ReverseTreeOrder<|#k,#v> {
  refines Order<KeyValue<#k,#v>>

  @category create<#k,#v> (optional BinaryTreeNode<#k,#v>) -> (optional ReverseTreeOrder<#k,#v>)

  @category seek<#k,#v>
    #k defines LessThan<#k>
  (#k,optional BinaryTreeNode<#k,#v>) -> (optional ReverseTreeOrder<#k,#v>)
}