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)
  : container.abstract_array T
is

  internal_array.freeze


  # equality of two arrays is true iff `a` and `b` have the same length and for all
  # `in in indices` we have `a[i] = b[i]`.
  #
  # For performance, this will compare the length of the arrays first.
  #
  # This is defined only if T : property.equatable, it will result in a compile-time panic
  # if this is not the case.
  #
  public redef fixed type.equality(a, b array T) bool
  =>
    if T : property.equatable then
      (a.length = b.length && (for ae in a
                                   be in b
                               until ae != be
                                 false
                               else
                                 true))
    else
      compile_time_panic  # tuple is not hashable since one element type is not


  # A total order for arrays is defined by the lowest index `i` for
  # which `a[i] != b[i]`. If this exists, the result is `a[i] <= b[i]`, otherwise
  # it is `a.length <= b.length`.
  #
  # This is defined only if T : property.orderable, it will result in a compile-time panic
  # if this is not the case.
  #
  public redef fixed type.lteq(a, b array T) bool
  =>
    if T : property.orderable then
      for ae in a
          be in b
      until ae != be
        ae >= be
      else
        a.length <= b.length
    else
      compile_time_panic  # tuple is not hashable since one element type is not


  # create hash code for this array.
  #
  # This should satisfy the following condition:
  #
  #   (T.equality a b) : (T.hash_code a = T.hash_code b)
  #
  # This will result in a compile-time `panic` in case T : property.hashable does not hold.
  #
  # The algorithm used here is a variation of (XXXHash)[https://xxhash.com] as used in
  # (Python's tuple)[https://github.com/python/cpython/blob/849a80ec412c36bbca5d400a7db5645b8cf54f1f/Objects/tupleobject.c#L305]:
  #
  #   we start with a constant `hash_prime1`
  #   for each value:
  #     we take its hash code * `hash_prime2` and add it
  #     then we rotate by `hash_rotate`
  #     and multiply by `hash_prime3`
  #
  public redef fixed type.hash_code(a array T) u64
  =>
    if T : property.hashable then
      h0 := xxh_next xxh_first 0x4f8fbfd3cba601a9  # created using https://cryptotools.dev/
      a.map (T.hash_code)
       .foldf h0 xxh_next
    else
      compile_time_panic  # array is not hashable since element type is not


  # the length of the array
  #
  public redef length i32 => internal_array.length


  # get the contents of this array at the given index
  #
  public redef index [ ] (I type : idx, i I) T
  =>
    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 inefficient since it copies the whole array.  Should
    # better use a persistent array implementation such as persistent hash array
    # mapped trie.
    array (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 inefficient since it copies the whole array.  Should
    # better use a persistent array implementation such as persistent hash array
    # mapped trie.
    array (max length i+1) (ix -> if (ix = i) v else if (ix ? length) z else array.this[ix])


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


  # create an empty array of type T
  #
  public fixed type.empty array T =>
    array (fuzion.sys.internal_array_init T 0) unit unit unit


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

    indices => 0..length-1

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

    array internal unit unit unit


  # return the maximum length of an array
  #
  public type.max_length i32 => i32.max


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