list_node.pony

class ListNode[A]
  """
  A node in a doubly linked list.

  See Pony [collections.List](https://stdlib.ponylang.io/collections-List/)
  class for usage examples.

  Each node contains four fields: two link fields (references to the previous and
  to the next node in the sequence of nodes), one data field, and the reference to
  the List in which it resides.

  As you would expect functions are provided to create a ListNode, update a
  ListNode's contained item, and pop the item from the ListNode.

  Additional functions are provided to operate on a ListNode as part of a Linked
  List. These provide for prepending, appending, removal, and safe traversal in
  both directions.  The Ponylang
  [collections.List](https://stdlib.ponylang.io/collections-List/) class is the
  correct way to create these. _Do not attempt to create a Linked List using only
  ListNodes._

  ## Example program
  The functions which are illustrated below are only those which operate on an
  individual ListNode.

  It outputs:

    My node has the item value: My Node item
    My node has the updated item value: My updated Node item
    Popped the item from the ListNode
    The ListNode has no (None) item.

  ```pony
    use "collections"
    actor Main
      new create(env:Env) =>

        // Create a new ListNode of type String
        let my_list_node = ListNode[String]("My Node item")
        try 
          env.out.print("My node has the item value: "
                        + my_list_node.apply()?) // My Node item
        end

        // Update the item contained in the ListNode
        try
          my_list_node.update("My updated Node item")?
          env.out.print("My node has the updated item value: "
                        + my_list_node.apply()?) // My updated Node item
        end
        // Pop the item from the ListNode
        try
          my_list_node.pop()?
          env.out.print("Popped the item from the ListNode")
          my_list_node.apply()? // This will error as the item is now None
        else
          env.out.print("The ListNode has no (None) item.")
        end
  ```
  """
  var _item: (A | None)
  var _list: (List[A] | None) = None
  var _prev: (ListNode[A] | None) = None
  var _next: (ListNode[A] | None) = None

  new create(item: (A | None) = None) =>
    """
    Create a node. Initially, it is not in any list.
    """
    _item = consume item

  fun apply(): this->A ? =>
    """
    Return the item, if we have one, otherwise raise an error.
    """
    _item as this->A

  fun ref update(value: (A | None)): A^ ? =>
    """
    Replace the item and return the previous one. Raise an error if we have no
    previous value.
    """
    (_item = consume value) as A^

  fun ref pop(): A^ ? =>
    """
    Remove the item from the node, if we have one, otherwise raise an error.
    """
    (_item = None) as A^

  fun ref prepend(that: ListNode[A]): Bool =>
    """
    Prepend a node to this one. If `that` is already in a list, it is removed
    before it is prepended. Returns true if `that` was removed from another
    list.
    If the ListNode is not contained within a List the prepend will fail.
    """
    if (_prev is that) or (this is that) then
      return false
    end

    var in_list = false

    match _list
    | let list': List[A] =>
      in_list = that._list isnt None
      that.remove()

      match _prev
      | let  prev': ListNode[A] =>
        prev'._next = that
      else
        list'._set_head(that)
      end

      that._list = list'
      that._prev = _prev
      that._next = this
      _prev = that
      list'._increment()
    end
    in_list

  fun ref append(that: ListNode[A]): Bool =>
    """
    Append a node to this one. If `that` is already in a list, it is removed
    before it is appended. Returns true if `that` was removed from another
    list.

    If the ListNode is not contained within a List the append will fail.
    """
    if (_next is that) or (this is that) then
      return false
    end

    var in_list = false

    match _list
    | let list': List[A] =>
      in_list = that._list isnt None
      that.remove()

      match _next
      | let  next': ListNode[A] =>
        next'._prev = that
      else
        list'._set_tail(that)
      end

      that._list = list'
      that._prev = this
      that._next = _next
      _next = that
      list'._increment()
    end
    in_list

  fun ref remove() =>
    """
    Remove a node from a list.

    The ListNode must be contained within a List for this to succeed.
    """
    match _list
    | let list': List[A] =>
      match (_prev, _next)
      | (let prev': ListNode[A], let next': ListNode[A]) =>
        // We're in the middle of the list.
        prev'._next = _next
        next'._prev = _prev
        _prev = None
        _next = None
      | (let prev': ListNode[A], None) =>
        // We're the tail.
        prev'._next = None
        list'._set_tail(prev')
        _prev = None
      | (None, let next': ListNode[A]) =>
        // We're the head.
        next'._prev = None
        list'._set_head(next')
        _next = None
      | (None, None) =>
        // We're the only member
        list'._set_head(None)
        list'._set_tail(None)
      end

      list'._decrement()
      _list = None
    end

  fun has_prev(): Bool =>
    """
    Return true if there is a previous node.
    """
    _prev isnt None

  fun has_next(): Bool =>
    """
    Return true if there is a next node.
    """
    _next isnt None

  fun prev(): (this->ListNode[A] | None) =>
    """
    Return the previous node.
    """
    _prev

  fun next(): (this->ListNode[A] | None) =>
    """
    Return the next node.
    """
    _next

  fun ref _set_list(list: List[A]): ListNode[A]^ =>
    """
    Make this node the only node on the given list.
    """
    remove()
    _list = list
    this