Generic List

# With UEFN version 41.00, we can now implement parametric classes with variable members.
 
# The code below provides a parametric list implementation.
 
# As we know, in Verse, adding or removing elements from an array triggers the allocation of a 
# new modified array. When the number of elements is small, the overhead may be acceptable. 
# For larger arrays, however, it can become significant for such a seemingly trivial operation.
 
# Lists provide fast O(1) insertion and removal while avoiding large allocations, typically 
# requiring memory only for a single element. Their ideal use case is scenarios where the 
# contents of the collection are not important in a way that would require iteration, but 
# where efficient acquisition and removal are essential (e.g., object pooling).


ADT<public> := module:

    readable<public>(value_type: type) := interface<computes>:

        GetValue<public>()<reads> : value_type

    modifiable<public>(value_type: type) := interface<computes>:

        SetValue<public>(
            Value: value_type
        )<transacts> : void

    have_next<public>(value_type: type) := interface<computes>:

        TryGetNext<public>()<transacts><decides> : void

    const_iterator<public>(value_type: type) := interface<computes>(
        readable(value_type),
        have_next(value_type)
    ):

    iterator<public>(value_type: type) := interface<computes>(
        const_iterator(value_type),
        modifiable(value_type)
    ):

    List<public> := module:

        # WARNING. Iterators have no concept of ownership. The user must ensure that
        # operations that involve iterators (e.g., Insert, Remove) 
        # are called with iterators originated from the list on which the operation is being 
        # performed.
        parametric_list<public>(value_type: type) := class<allocates>:

            var MaybeFirst<private> : ?node(value_type) = false
            var MaybeLast<private> : ?node(value_type) = false
            var<private> Size<public> : int = 0

            TryGetFirst<public>()<reads><decides> : value_type =
                return MaybeFirst?.Value

            TryGetLast<public>()<reads><decides> : value_type =
                return MaybeLast?.Value

            # Inserts the element before iterator. No iterators should be invalidated.
            # Accepts a HaveNext policy, which will be forwarded to the returned iterator.
            # This allows the caller to control whether the returned iterator is forward or 
            # reverse.
            # Returns an iterator to the inserted element.
            Insert<public>(
                Value: value_type,
                Iterator: const_list_iterator(value_type),
                ?HaveNext: list_have_next(value_type) = list_forward_have_next(value_type){}
            )<transacts> : list_iterator(value_type) =
                if:
                    not Iterator.CurrentNode.MaybePrevious?
                then:
                    return PushFront(Value, ?HaveNext := HaveNext)
                PreviousNode := 
                    Iterator.CurrentNode.MaybePrevious? or 
                        Err("List -> Insert Element: Expected list node")
                Node := node(value_type). Value := Value
                set PreviousNode.MaybeNext = option. Node
                set Iterator.CurrentNode.MaybePrevious = option. Node
                set Node.MaybePrevious = option. PreviousNode
                set Node.MaybeNext = option. Iterator.CurrentNode
                set Size += 1
                return MakeIteratorToNode(Node, HaveNext)

            # Removes the element at iterator. 
            # Iterators to the removed element will be invalidated.
            Remove<public>(
                Iterator: const_list_iterator(value_type)
            )<transacts> : void =
                if:
                    not Iterator.CurrentNode.MaybePrevious?
                then:
                    TryPopFront[] or Err("List -> Remove: Expected Pop Front to succeed")
                    return
                if:
                    not Iterator.CurrentNode.MaybeNext?
                then:
                    TryPopBack[] or Err("List -> Remove: Expected Pop Back to succeed")
                    return
                PreviousNode :=
                    Iterator.CurrentNode.MaybePrevious? or 
                        Err("List -> Remove: Expected list node")
                NextNode :=
                    Iterator.CurrentNode.MaybeNext? or
                        Err("List -> Remove: Expected list node")
                set PreviousNode.MaybeNext = option. NextNode
                set NextNode.MaybePrevious = option. PreviousNode
                set Iterator.CurrentNode.MaybePrevious = false
                set Iterator.CurrentNode.MaybeNext = false
                set Size -= 1

            # Adds an element to the end of the list. No iterators should be invalidated.
            # Returns an iterator to the inserted element.
            PushBack<public>(
                Value: value_type,
                ?HaveNext: list_have_next(value_type) = list_forward_have_next(value_type){}
            )<transacts> : list_iterator(value_type) =
                if:
                    Size = 0
                then:
                    return AllocateFirstElement(Value, HaveNext)
                Node := node(value_type). Value := Value
                Iterator := MakeIteratorToNode(Node, HaveNext)
                Last := MaybeLast? or Err("List -> Push Back: Expected list node")
                set Node.MaybePrevious = MaybeLast
                set Last.MaybeNext = option. Node
                set MaybeLast = option. Node
                set Size += 1
                return Iterator

            # Adds an element to the front of the list. No iterators should be invalidated.
            # Returns an iterator to the inserted element.
            PushFront<public>(
                Value: value_type,
                ?HaveNext: list_have_next(value_type) = list_forward_have_next(value_type){}
            )<transacts> : list_iterator(value_type) =
                if:
                    Size = 0
                then:
                    return AllocateFirstElement(Value, HaveNext)
                First := MaybeFirst? or Err("List -> Push Front: Expected list node")
                Node := node(value_type). Value := Value
                Iterator := MakeIteratorToNode(Node, HaveNext)
                set Node.MaybeNext = MaybeFirst
                set First.MaybePrevious = option. Node
                set MaybeFirst = option. Node
                set Size += 1
                return Iterator

            # Removes the last element of the list and returns its value. 
            # Iterators to the removed element will be invalidated.
            TryPopBack<public>()<transacts><decides> : value_type =
                Last := MaybeLast?
                if. set Last.MaybePrevious?.MaybeNext = false
                set MaybeLast = Last.MaybePrevious
                set Last.MaybePrevious = false
                set Size -= 1
                if:
                    Size = 0
                    set MaybeFirst = false
                return Last.Value

            # Removes the first element of the list and returns its value. 
            # Iterators to the removed element will be invalidated.
            TryPopFront<public>()<transacts><decides> : value_type =
                First := MaybeFirst?
                if. set First.MaybeNext?.MaybePrevious = false
                set MaybeFirst = First.MaybeNext
                set First.MaybeNext = false
                set Size -= 1
                if:
                    Size = 0
                    set MaybeLast = false
                return First.Value

            Clear<public>()<transacts> : void =
                set MaybeFirst = false
                set MaybeLast = false
                set Size = 0

            # Returns a forward iterator to the first element of the list.
            # Forward iterators allow traversal of the list from front to back.
            # For instance, if the list is [A,B,C], a forward iterator would return A, 
            # then B, then C.
            TryBegin<public>()<reads><allocates><decides> : list_iterator(value_type) =
                return MakeIteratorToNode(MaybeFirst?, list_forward_have_next(value_type){})

            # Returns a reverse iterator to the last element of the list.
            # Reverse iterators allow traversal of the list from back to front.
            # For instance, if the list is [A,B,C], a reverse iterator would return C,
            # then B, then A.
            TryEndReversed<public>(
            )<reads><allocates><decides> : list_iterator(value_type) =
                return MakeIteratorToNode(MaybeLast?, list_reverse_have_next(value_type){})

            # Allocates an array and copies the elements of the list into it.
            # The ordering of the elements in the array matches the ordering of the elements in 
            # the list (i.e., the first element of the list is copied to index 0 of the array, 
            # and so on).
            TryMakeArray<public>()<transacts><decides> : []value_type =
                Iterator: const_list_iterator(value_type) = TryBegin[]
                EndIndex := Size - 1
                return:
                    for:
                        Index := 0..EndIndex
                    do:
                        Value := Iterator.GetValue()
                        if:
                            Index < EndIndex
                            Iterator.TryGetNext[] or 
                                Err("List -> Make Array: Expected next element")
                        Value

            MakeIteratorToNode<private>(
                Node: node(value_type),
                HaveNext: list_have_next(value_type)
            )<allocates> : list_iterator(value_type) =
                return:
                    list_iterator(value_type):
                        HaveNext := HaveNext
                        CurrentNode := Node

            AllocateFirstElement<private>(
                Value: value_type,
                HaveNext: list_have_next(value_type)
            )<transacts> : list_iterator(value_type) =
                Size = 0 or Err("List -> Allocate First Element: Expected empty list")
                Node := node(value_type). Value := Value
                set MaybeFirst = option. Node
                set MaybeLast = MaybeFirst
                set Size = 1
                return MakeIteratorToNode(Node, HaveNext)

        const_list_iterator<public>(value_type: type) := class<internal><allocates>(
            const_iterator(value_type)
        ):

            HaveNext<internal> : list_have_next(value_type)

            var CurrentNode<internal> : node(value_type)

            GetValue<override>()<reads> : value_type =
                return CurrentNode.Value

            TryGetNext<override>()<transacts><decides> : void =
                NextNode := HaveNext.TryGetNext[CurrentNode]
                set CurrentNode = NextNode

        list_iterator<public>(value_type: type) := class<internal><allocates>(
            const_list_iterator(value_type),
            modifiable(value_type)
        ):

            SetValue<override>(
                Value: value_type
            )<transacts> : void =
                set CurrentNode.Value = Value

        list_have_next<public>(value_type: type) := interface<computes>:

            TryGetNext<public>(
                CurrentNode: node(value_type)
            )<reads><decides> : node(value_type)

        list_forward_have_next<public>(value_type: type) := class<computes>(
            list_have_next(value_type)
        ):

            TryGetNext<override>(
                CurrentNode: node(value_type)
            )<reads><decides> : node(value_type) =
                return CurrentNode.MaybeNext?

        list_reverse_have_next<public>(value_type: type) := class<computes>(
            list_have_next(value_type)
        ):

            TryGetNext<override>(
                CurrentNode: node(value_type)
            )<reads><decides> : node(value_type) =
                return CurrentNode.MaybePrevious?

        node<internal>(value_type: type) := class<allocates>:

            var MaybePrevious<internal> : ?node(value_type) = false
            var MaybeNext<internal> : ?node(value_type) = false
            var Value<internal> : value_type

        # Removes all elements matching the value. Iterators may be invalidated.
        # We still cannot have the parametric type defined by an implict type parameter 
        # (i.e., parameters defined with the 'where' keyword). 
        # 
        # RemoveAll<public>(
        #   Value: value_type, 
        #   List: parametric_list(value_type) where value_type: subtype(comparable)
        # )<transacts> : void 
        #
        # Using explict ValueType parameter for now.
        RemoveAll<public>(
            ValueType: subtype(comparable),
            Value: ValueType,
            (local:)List: parametric_list(ValueType)
        )<transacts> : void =
            MaybeIterator: ?const_list_iterator(ValueType) = option. (local:)List.TryBegin[]
            if:
                not MaybeIterator?
            then:
                return
            Iterator := MaybeIterator? or Err("List -> Remove All: Expected list iterator")
            loop:
                if:
                    Iterator.CurrentNode.Value = Value
                then:
                    MaybeNextNode := Iterator.CurrentNode.MaybeNext
                    (local:)List.Remove(Iterator)
                    if:
                        NextNode := MaybeNextNode?
                    then:
                        set Iterator.CurrentNode = NextNode
                    else:
                        return
                else:
                    HaveNext := logic. Iterator.TryGetNext[]
                    if:
                        not HaveNext?
                    then:   
                        return

        # Removes all elements matching the predicate. Iterators may be invalidated.
        RemoveAll<public>(
            ValueType: type,
            Predicate(:ValueType, :payload_type)<reads><decides> : void,
            (local:)List: parametric_list(ValueType),
            Payload: payload_type where payload_type: type
        )<transacts> : void =
            MaybeIterator: ?const_list_iterator(ValueType) = option. (local:)List.TryBegin[]
            if:
                not MaybeIterator?
            then:
                return
            Iterator := MaybeIterator? or Err("List -> Remove All: Expected list iterator")
            loop:
                if:
                    Predicate[Iterator.CurrentNode.Value, Payload]
                then:
                    MaybeNextNode := Iterator.CurrentNode.MaybeNext
                    (local:)List.Remove(Iterator)
                    if:
                        NextNode := MaybeNextNode?
                    then:
                        set Iterator.CurrentNode = NextNode
                    else:
                        return
                else:
                    HaveNext := logic. Iterator.TryGetNext[]
                    if:
                        not HaveNext?
                    then:   
                        return