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

# array -- one-dimensional immutable array
#
# This is the result type of array(type, i32, i32 -> T) which creates an
# initialized immutable array
#
# Note: This uses dummy unit-type args to avoid
# name clash with routine array(T,length,init).
#
module:public array(
      public T type,
      module internal_array fuzion.sys.internal_array T,
      _ unit,
      _ unit,
      _ unit) : Sequence T is

  internal_array.freeze

  public length => internal_array.length


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


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


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


  # 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 (n i32) =>
    as_list (max 0 n)


  # 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 => 0..length-1


  # get the contents of this array at the given index
  #
  public redef index [ ] (i i32) T
    pre
      safety: 0 ≤ i
      safety: i < length
  =>
    internal_array[i]

  # create a new array with element i set to v. Grow the array in case i == length.
  #
  # Complexity: O(array.this.length)
  #
  public put (i i32, v T) array T
    pre
      safety: 0 ≤ i ≤ length
  =>
    # NYI: This is very inefficent since it copies the whole array.  Should
    # better use a persistent array implementation such as persistent hash array
    # mapped trie.
    array T (max length i+1) (ix -> if (ix = i) v else array.this[ix])

  # create a new array with element i set to v. Grow the array in case i >= length.
  # New array elements at indices array.this.length..i-1 will be set to z.
  #
  # Complexity: O(max(i, array.this.length))
  #
  public put (i i32, v T, z T) array T
    pre
      safety: 0 ≤ i
  =>
    # NYI: This is very inefficent since it copies the whole array.  Should
    # better use a persistent array implementation such as persistent hash array
    # mapped trie.
    array T (max length i+1) (ix -> if (ix = i) v else if (ix ≥ length) z else array.this[ix])


  # 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 => 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
  =>
    (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(from, to i32) Sequence T
    pre
      debug: from ≥ 0
  =>

    ref : Sequence T

      # this array slice as a list
      #
      public redef as_list list T =>
        if to ≤ from
          nil
        else
          array_cons from to

      # get the contents of this slice at the given index
      #
      public redef index [ ] (i i32) T
      =>
        array.this[from+i]

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


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


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


      # 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 (n i32) =>
        array.this.slice from+(max 0 n) to
                  .as_list


  # create a cons cell for a list of this array starting at the given
  # index `i` and up to `to`
  #
  array_cons (i, to i32) : Cons T (list T)
    pre
      debug: 0 ≤ i < to ≤ length
  is
    head => array.this[i]
    tail => (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 array.this.length (i -> f 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 array.this.length (i -> f 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) => 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 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 T array.this.length (i -> array.this[array.this.length-1-i])


  # get a list of tuples indices and elements in this array
  #
  public enumerate list (tuple i32 T) =>
    if length = 0
      nil
    else
      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 (tuple i32 T))
    pre
      debug: 0 ≤ i
      debug: i < length
  is
    head => (i, index[] i)
    tail list (tuple i32 T) =>
      if i < length-1 then enumerate_cons i+1
      else                 nil


  # collect the contents of this Sequence into an array
  #
  public redef fixed as_array array T =>
    array.this


  # array -- create initialized one-dimensional immutable array
  #
  public type.new(length i32, init i32 -> T) array T
    pre
      safety: length ≥ 0
  =>

    private indices => 0..length-1

    internal := fuzion.sys.internal_array_init T length
    for x in indices do
      internal[x] := init x

    array T internal unit unit unit



# array -- create initialized one-dimensional immutable array
#
public array(T type, length i32, init i32 -> T) array T =>
  (array T).new length init