container/abstract_array.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 abstract_array
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# abstract_array -- parent of array implementation like `array` and `expanding_array`
#
# This provides basic functionality that an array should provide based on `index[i]`
# and `length` that have to be provided by children of `abstract_array`.
#
public abstract_array
  (
   # element type
   public T type
  ) : Sequence T is


  # length of this array
  #
  public length i32 => abstract


  # redefines Sequence.count for array,
  # reducing complexity from O(n) to O(1).
  #
  public redef count i32 => length


  # is this Sequence empty?
  #
  public redef is_empty bool => length = 0


  # get the first element of this Sequence
  #
  public redef first option T
  => if is_empty then nil else index [ ] 0


  # get the last element of this Sequence
  #
  # This may take time in O(count), in particular, it may not terminate
  # for an infinite Sequence.
  #
  public redef last option T
  => if is_empty then nil else index [ ] length-1


  # is this sequence known to be finite?  For infinite sequences, features like
  # count diverge.
  #
  public redef finite trit => trit.yes


  # is this Sequence known to be array backed? If so, this means that operations
  # like index[] are fast.
  #
  public redef is_array_backed bool => true


  # check if argument is a valid index in this array.
  #
  # Unlike for general Sequences, this performs in O(1).
  #
  public redef is_valid_index(I type : integer, i I) bool => 0 ? i.as_i32 < length


  # create a list that consists of the elements of this Sequence except the first
  # n elements
  #
  # For arrays, this has performance in O(1).
  #
  public redef drop (I type : integer, n I) Sequence T =>
    if n.as_i32 >= count
      []
    else if n < 0
      abstract_array.this
    else
      slice n.as_i32 count


  # create a Sequence that consists only of the first n elements of this
  # Sequence, fewer if this Sequence has fewer elements
  #
  # For arrays, this has performance in O(1).
  #
  public redef take (I type : integer, n I) Sequence T =>
    if n.as_i32 >= count
      abstract_array.this
    else if n < 0
      []
    else
      slice 0 n


  # drop the first elements for which predicate 'p' holds.
  #
  public redef drop_while (p T -> bool) Sequence T
  =>
    for i in indices
    until !p (index[] i)
      drop i
    else
      []


  # take the first elements for which predicate 'p' holds.
  #
  public redef take_while (p T -> bool) Sequence T
  =>
    for i in indices
    until !p (index[] i)
      take i
    else
      abstract_array.this


  # a sequence of all valid indices to access this array. Useful e.g., for
  # `for`-loops:
  #
  #     for i in arr.indices do
  #       say arr[i]
  #
  public indices interval i32 => 0..length-1


  # get the contents of this array at the given index
  #
  public redef index [ ] (I type : integer, i I) T
  =>
    abstract


  # apply f to all elements in this array
  #
  public redef for_each (f T -> unit) unit =>
    for i in indices do
      f (index[] i)


  # create a list from this array
  #
  public redef as_list list T => as_list 0


  # create a list from this array starting at the given index
  #
  public as_list(i i32) list T
    pre
      debug: i ? 0
      debug: i=0 || i<length
  =>
    (slice i length).as_list


  # create a slice from this array's elements at index 'from' (included)
  # up to 'to' (excluded).
  #
  # Complexity:
  # index access : O(1)
  # count        : O(1)
  #
  public redef slice(I type : integer, from, to I) Sequence T
  =>
    array_slice : container.abstract_array T is

      # this array slice as a list
      #
      public redef as_list list T =>
        if to ? from
          nil
        else
          array_slice.this.array_cons abstract_array.this from to


      # get the contents of this slice at the given index
      #
      public redef index [ ] (J type : integer, i J) T
      =>
        abstract_array.this[from.as_i32+i.as_i32]


      # redefines abstract_array.length for array.
      #
      public redef length i32 := (to-from).as_i32


      # a slice of a slice, need to adjust from and to args
      #
      public redef slice(J type : integer, from_, to_ J) Sequence T
      =>
        abstract_array.this.slice from.as_i32+from_.as_i32 from.as_i32+to_.as_i32

    array_slice


  # create a cons cell for a list of this array starting at the given
  # index `i` and up to `to`
  #
  array_cons(I type : integer, a A : container.abstract_array T, i, to I)
    pre
      debug: 0 ? i.as_i32 < to.as_i32 ? a.length
  =>
    (list T).of_finite a[i] (a.slice i+1 to).as_list


  # map the array to a new array applying function f to all elements
  #
  public map_to_array(B type, f T -> B) array B =>
    array B abstract_array.this.length (i -> f abstract_array.this[i])


  # variant of map which additionally passes the index to
  # the mapping function f
  #
  public map_indexed(B type, f (T, i32) -> B) array B =>
    array B abstract_array.this.length (i -> f abstract_array.this[i] i)


  # fold the elements of this array using the given monoid.
  #
  # e.g., to sum the elements of an array of i32, use a.fold i32.sum
  #
  public redef fold (m Monoid T) T => fold 0 m.e m


  # fold the elements of this array using the given monoid and initial value
  #
  # Used to fold an array tail-recursively
  #
  public fold (i i32, s T, m Monoid T) T
    pre
      debug: 0 ? i ? length
  =>
    if i = length
      s
    else
      fold i+1 (m.op s abstract_array.this[i]) m


  # reverse the order of the elements in this array
  #
  public redef reverse Sequence T => reverse_array


  # reverse the order of the elements in this array
  #
  public reverse_array array T =>
    array abstract_array.this.length (i -> abstract_array.this[abstract_array.this.length-1-i])


  # get a list of tuples of indices and elements in this array
  #
  public enumerate Sequence (i32, T) =>
    if length = 0
      id (list (i32,T)) nil
    else
      id (list (i32,T)) (enumerate_cons 0)


  # create a cons cell for a list of tuples of this array's indices and elements
  # starting at the given indices.
  #
  enumerate_cons (i i32) : Cons (i32, T) (list (i32, T))
    pre
      debug: 0 ? i
      debug: i < length
  is
    public redef head tuple i32 T => (i, index[] i)
    public redef tail list (tuple i32 T) =>
      if i < length-1 then enumerate_cons i+1
      else                 nil


  # create a mutable copy of this array
  #
  public as_mutable(LM type : mutate) LM.array T =>
    data := fuzion.sys.internal_array_init T length

    # NYI: PERFORMANCE: copy complete array at once
    for x in data.indices do
      data[x] := abstract_array.this[x]

    LM.env.array data length.as_i64 (mutate.array unit .type.default_min_length) unit