/* -----------------------------------------------------------------------------
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]

// Factory for creating new nodes.
@type interface NewNode<#x|> {
  newNode (#x) -> (#self)
}

// List element whose next element can be replaced.
@value interface ListNode<|#n|#x> {
  refines Order<#x>

  // Replace next with the provided element.
  //
  // Returns:
  // - optional #n: The element being replaced as next.
  //
  // Notes:
  // - This is allowed to modify the argument, e.g., set prev if applicable.
  // - This is *not* required to prevent cycles.
  setNext (optional #n) -> (optional #n)
}

// List element that supports reverse iteration.
@value interface DoubleNode<|#n|#x> {
  refines ListNode<#n, #x>

  // Return the previous element.
  prev () -> (optional #self)

  // Replace prev with the provided element.
  //
  // Returns:
  // - optional #n: The element being replaced as prev.
  //
  // Notes:
  // - This is allowed to modify the argument, e.g., set next if applicable.
  // - This is *not* required to prevent cycles.
  setPrev (optional #n) -> (optional #n)
}

// Node in a doubly-linked list.
//
// Notes:
// - This list is weak in the reverse direction. In other words, prev only
//   exists if there is another non-weak reference to it.
concrete LinkedNode<#x> {
  defines NewNode<#x>
  // Duplication happens only in the forward direction.
  refines Duplicate
  refines DoubleNode<LinkedNode<#x>, #x>

  // Create a new builder.
  @type builder () -> (ListBuilder<#x, #self>)

  // Set the value held by the node.
  @value set (#x) -> (#self)
}

// Node in a singly-linked list.
//
// Notes:
// - This is more efficient than LinkedNode, but lacks housekeeping when
//   modifying the list's structure.
concrete ForwardNode<#x> {
  defines NewNode<#x>
  refines Duplicate
  refines ListNode<ForwardNode<#x>, #x>

  // Create a new builder.
  @type builder () -> (ListBuilder<#x, #self>)

  // Set the value held by the node.
  @value set (#x) -> (#self)
}

// Builder for ListNode.
concrete ListBuilder<#x|#n> {
  refines Append<#x>
  #n defines NewNode<#x>
  #n requires ListNode<#n, #x>

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

  // Append all of the elements from the Order.
  @value appendAll (optional Order<#x>) -> (#self)

  // Build the list.
  //
  // Returns:
  // - optional #n: The head of the built list.
  // - optional #n: The tail of the built list.
  //
  // Notes:
  // - Appending new values after calling build will not invalidate the previous
  //   head/tail, but that tail will no longer be the end.
  // - Calling mutating functions (e.g., setNext, setPrev) on any of the
  //   elements between the returned head/tail will invalidate the builder.
  @value build () -> (optional #n, optional #n)
}