list_node.pony

class ListNode[A]
  """
  A node in a list.
  """
  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 (_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 (_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.
    """
    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