Fuzion Logo
flang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

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
# initalized immutable array
#
# NYI: This uses three dummy unit-type args (i.e. total of 5 args or 4 value
# args) to avoid name clashes with routine array(T,length,init) (i.e., 3 args
# or  2 value args).  These unit-type args can go if the routine would be
# moved to 'array.type.new' or 'arrays.new'
#
array(redef T type,
      internalArray fuzion.sys.array T,
      _ unit,
      _ unit,
      _ unit) : Sequence T is

# public:

  length => internalArray.length

  indices => 0..length-1

  index [ ] (i i32) T
    pre
      safety: 0 <= i < length
  is
    internalArray[i]

  # create a new array with element i set to v. Grow the array in case i == length.
  #
  # Complexity: O(array.this.length)
  #
  put (i i32, v T) array T
    pre
      safety: 0 <= i <= length
  is
    # 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 length.max(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))
  #
  put (i i32, v T, z T) array T
    pre
      safety: 0 <= i
  is
    # 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 length.max(i+1) (ix -> if (ix == i) v else if (ix >= length) z else array.this[ix])


  redef asStream ref : stream T is

    # NYI: we create heap allocated instance of array explicitly, needed while
    # issue #30 is not fixed.  Once issue is fixed, array.this can be used instead.
    # See idiom40ex.fz for a test case
    #
    array_this ref array T := array.this

    x := 0
    redef hasNext => x < array_this.length
    redef next => set x := x + 1; array_this[x-1]

  redef forAll (f T -> unit) unit is
    for i in indices do
      f index[](i)


  # create a list from this array
  #
  redef asList => asList 0


  # create a list from this array starting at the given index
  #
  asList(i i32) list T
    pre
      debug: i >= 0
  is
    if length <= i
      nil
    else
      arrayCons i


  # create a cons cell for a list of this array starting at the given
  # index
  #
  arrayCons (i i32) : Cons T (list T)
    pre
      debug: 0 <= i < length
  is
    head => array.this[i]
    tail => asList i+1


  # create a slice from this array's elements at index 'from' (included)
  # up to 'to' (excluded).
  #
  # NYI: array.slice should better return an array containing a slice of
  # internalArray.
  #
  redef slice(from, to i32) list T
    pre
      debug: from >= 0
  is
    if to <= from
      nil
    else
      arrayCons from to


  # create a cons cell for a list of this array starting at the given
  # index and up to to
  #
  arrayCons (i, to i32) : Cons T (list T)
    pre
      debug: 0 <= i < to <= length
  is
    head => array.this[i]
    tail => slice i+1 to


  # map the array to a new array applying function f to all elements
  #
  map(B type, f T -> B) array B is
    array B array.this.length (i -> f array.this[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
  #
  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
  #
  fold (i i32, s T, m Monoid T) T
    pre
      debug: 0 <= i <= length
  is
    if i == length
      s
    else
      fold i+1 (m.op s array.this[i]) m


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


  # get a list of tuples indices and elements in this array
  #
  enumerate list (tuple i32 T) is
    if length == 0
      nil
    else
      enumerateCons 0


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


  # collect the contents of this Sequence into an array
  #
  redef asArray array T is
    array T internalArray unit unit unit


# array -- create initialized one-dimensional immutable array
#
# NYI: move this to 'arrays.new' or similar to avoid overloading
# with 'array(T,internalArray,_,_,_)'.
#
array(T type, length i32, init i32 -> T) array T
  pre
    safety: length >= 0
is

# private:
  indices => 0..length-1

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

  array T internal unit unit unit