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
last changed: 2024-03-07