container/Doubly_Linked_List.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature Doubly_Linked_List
#
# -----------------------------------------------------------------------

# a list node
#
L_Node(
  # mutate effect to be used manipulate pointers and stored element
  #
  LM type : mutate,

  # type of the element stored in the node
  #
  T type,

  # the previous list node
  #
  prev LM.new (option (L_Node LM T)),

  # the next list node
  #
  next LM.new (option (L_Node LM T)),

  # the element stored in this list node
  #
  val option T

) ref is

  # is this node the special node marking start/end of the list
  #
  is_sentinel bool => val.is_nil


# Doubly_Linked_List - a simple mutable doubly linked list
#
# Adding and removing elements at either end takes O(1) time.
#
private:public Doubly_Linked_List(
  # mutate effect to be used to create mutable variables
  #
  LM type : mutate,

  # type the elements the list
  #
  T type

) ref ! LM is


  # list is linked in a circle, sentinel marks start/end
  #
  sentinel := L_Node LM T (LM.env.new (option (L_Node LM T)) nil) (LM.env.new (option (L_Node LM T)) nil) nil
  sentinel.prev <- sentinel
  sentinel.next <- sentinel


  # number of elements currently in the list (does not include the sentinel)
  #
  len := LM.env.new i64 0


  # is this list empty?
  #
  public is_empty bool ! LM
    post debug : !result ^ sentinel.prev.or_panic.is_sentinel
  =>
    LM.env.exclusive ()->sentinel.next.or_panic.is_sentinel


  # add an element to the front of the list
  #
  public add_first(elem T) unit ! LM =>
    LM.env.exclusive ()->
      old_first := sentinel.next.or_panic
      e := L_Node LM
                  T
                  (LM.env.new (option (L_Node LM T)) sentinel)
                  (LM.env.new (option (L_Node LM T)) old_first)
                  elem
      old_first.prev <- e
      sentinel.next  <- e
      len <- len+1
      check debug : !sentinel.next.or_panic.is_sentinel
      check debug : !sentinel.prev.or_panic.is_sentinel


  # add an element at the back of the list
  #
  public add_last(elem T) unit ! LM =>
    LM.env.exclusive ()->
      old_last := sentinel.prev.or_panic
      e := L_Node LM
                  T
                  (LM.env.new (option (L_Node LM T)) old_last)
                  (LM.env.new (option (L_Node LM T)) sentinel)
                  elem
      old_last.next <- e
      sentinel.prev <- e
      len <- len+1
      check debug : !sentinel.next.or_panic.is_sentinel
      check debug : !sentinel.prev.or_panic.is_sentinel


  # remove the first element, if there is one, and return it
  #
  public remove_first option T ! LM =>
    LM.env.exclusive (option T) _ ()->
      if is_empty then nil
      else
        fst := sentinel.next.or_panic
        sentinel.next <- fst.next.or_panic
        fst.next.or_panic.prev <- sentinel
        len <- len-1
        fst.val


  # remove the last element, if there is one, and return it
  #
  public remove_last option T ! LM =>
    LM.env.exclusive (option T) _ ()->
      if is_empty then nil
      else
        lst := sentinel.prev.or_panic
        sentinel.prev <- lst.prev.or_panic
        lst.prev.or_panic.next <- sentinel
        len <- len-1
        lst.val


  # remove the first element that matches the given predicate
  #
  public remove_first_match(f T->bool) option T ! LM =>
    LM.env.exclusive (option T) _ ()->
      for e := sentinel.next.or_panic, e.next.or_panic
      until e.is_sentinel || f e.val.or_panic
        if e.is_sentinel then nil
        else
          remove e
          e.val


  # remove a node from the list
  #
  remove(node L_Node LM T) unit
    pre debug : !node.is_sentinel
  =>
    node.prev.or_panic.next <- node.next.or_panic
    node.next.or_panic.prev <- node.prev.or_panic
    len <- len-1


  # this list as an immutable array
  #
  public as_array array T ! LM =>
    LM.env.exclusive ()->
      as_list_from(node L_Node LM T) list T =>
        node.is_sentinel ? nil : cons T (list T) node.val.or_panic (as_list_from node.next.or_panic)
      as_list_from sentinel.next.or_panic .as_array


  # return a string representation of this list
  #
  public redef as_string String ! LM =>
    LM.env.exclusive ()->
      "[$(
        if is_empty then ""
        else
          for
            e := sentinel.next.or_panic, e.next.or_panic
            s := "$(e.val)", "$s, $(e.val)"
          until e.next.or_panic.is_sentinel
            s
        )]"


  # number of elements currently in this list
  #
  # O(1) operation, as length is saved separately
  #
  public count i64 ! LM => LM.env.exclusive ()->len


  # does this list contain elem?
  #
  public contains(elem T) bool ! LM
    pre T : property.equatable
  =>
    LM.env.exclusive ()->
      for e := sentinel.next.or_panic, e.next.or_panic
      until e.is_sentinel || e.val = elem
        !e.is_sentinel





  # create a new, empty Doubly_Linked_List
  #
  public fixed type.empty container.Doubly_Linked_List LM T ! LM =>
    LM.env.exclusive (container.Doubly_Linked_List LM T) _ ()->
      container.Doubly_Linked_List LM T