array3.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(l1,l2,l3)
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------


# array(length0, length1, length2) -- three-dimensional immutable array
#
# array provides three-dimensional immutable arrays. These are actually
# one-dimensional immutable arrays with an additional access function with
# three index parameters.
#
private:public array3(
      T type,
      public length0, length1, length2 i64,

      # the underlying one dimensional array
      #
      # multidimensional indices are mapped to one dimensional indices as follows:
      #
      # [x,y,z] -> [(x * length1 + y) * length2 + z]
      #
      # resulting in the order:
      #
      # arr[0,0,0], arr[0,0,1], arr[0,0,2], ...,
      # arr[0,1,0], arr[0,1,1], arr[0,1,2], ...,
      # arr[1,0,0], arr[1,0,1], arr[1,0,2], ...
      #
      public base array T,
      _ unit,
      _ unit)
 : property.hashable
  pre
    safety: length0 ? 0
    safety: length1 ? 0
    safety: length2 ? 0
    safety: length0 *? length1 *? length2 >=? 0
is


  # equality of two array3s is true iff `a` and `b` have the same dimensions and for all
  # `i in indices0`, `j in indices1` and `k in indices 2` we have `a[i][j][k] = b[i][j][k]`.
  #
  # 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 array3 T) bool
  =>
    if T : property.equatable then
      (a.length0 = b.length0 &&
       a.length1 = b.length1 &&
       a.length2 = b.length2 &&
       (for ae in a.base
            be in b.base
        until ae != be
          false
        else
          true))
    else
      compile_time_panic  # array is not equatable since element type is not


  # NOT implemented, calling this fails at compile time
  #
  # There is no natural total ordering for three-dimensional arrays
  #
  public fixed type.lteq(a, b array3 T) bool =>
    compile_time_panic # no natural total ordering for three-dimensional arrays


  # create hash code for this array3.
  #
  # 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 array3 T) u64
  =>
    if T : property.hashable then
      h0 := xxh_next
              (xxh_next
                (xxh_next xxh_first 0xa495991b7852b855) # created using https://cryptotools.dev/
                # include dimensions so reshaped arrays with identical elements hash differently
                (a.length0.as_u64 << 32 | a.length1.as_u64))
              a.length2.as_u64
      a.base.map (T.hash_code)
       .foldf h0 xxh_next
    else
      compile_time_panic  # array is not hashable since element type is not


  # indices range in first dimension
  #
  public indices0 interval i64 => 0..length0-1


  # indices range in second dimension
  #
  public indices1 interval i64 => 0..length1-1


  # indices range in third dimension
  #
  public indices2 interval i64 => 0..length2-1


  public index [ ] (I type : integer, i0, i1, i2 I) T
    pre
      safety: 0 ? i0.as_i64 < length0
      safety: 0 ? i1.as_i64 < length1
      safety: 0 ? i2.as_i64 < length2
  =>
    array3.this.base[(i0.as_i64 * length1 + i1.as_i64) * length2 + i2.as_i64]


  # create a string representation of this array including all the string
  # representations of its contents, separated by ',' and enclosed in '['
  # and ']'.  Arrays in inner dimensions are grouped using '[' and ']'.
  #
  public redef as_string String : encodings =>
    dim_1(i i64) =>
      ("  [" + ascii.lf_str
        + indices1
            .map (j -> dim_2 i j)
            .fold (String.concat ("," + ascii.lf_str))
        + ascii.lf_str + "  ]")

    dim_2(i i64, j i64) =>
      from := (i * length1 + j) * length2
      to := from + length2
      "    " + base.slice from to

    ("[" + ascii.lf_str
      + indices0
          .map (i -> dim_1 i)
          .fold (String.concat ("," + ascii.lf_str))
      + ascii.lf_str + "]")


  # get a list of tuples indices and elements in this array
  #
  public enumerate3 list (i64, i64, i64, T) =>
    if base.length = 0 then nil else enumerate_cons 0 0 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 type : integer, i, j, k I) : Cons (tuple i64 i64 i64 T) (list (tuple i64 i64 i64 T))
    pre
      debug: 0 ? i.as_i64 < length0
      debug: 0 ? j.as_i64 < length1
      debug: 0 ? k.as_i64 < length2
  is
    public redef head tuple i64 i64 i64 T => (i.as_i64, j.as_i64, k.as_i64, index[] i j k)
    public redef tail list (tuple i64 i64 i64 T) =>
      if      k.as_i64 < length2-1 then enumerate_cons i   j   k+1
      else if j.as_i64 < length1-1 then enumerate_cons i   j+1 0
      else if i.as_i64 < length0-1 then enumerate_cons i+1 0   0
      else                       nil



  # array(length0, length1, length2) -- three-dimensional immutable array
  #
  # array provides three-dimensional immutable arrays. These are actually
  # one-dimensional immutable arrays with an additional access function with
  # three index parameters.
  #
  public type.new(
          I type : integer,
          length0, length1, length2 I,
          init (I, I, I) -> T) array3 T
    pre
      safety: length0 ? 0
      safety: length1 ? 0
      safety: length2 ? 0
      safety: length0.as_i64 *? length1.as_i64 *? length2.as_i64 >=? 0
      debug : length0.fits_in_i64
      debug : length1.fits_in_i64
      debug : length2.fits_in_i64
  =>

    base := array T I length0*length1*length2 (i->init (i/(length1*length2)) ((i/length2) % length1) (i%length2))

    array3 T length0.as_i64 length1.as_i64 length2.as_i64 base unit unit



# array(length0, length1, length2) -- three-dimensional immutable array
#
# array provides three-dimensional immutable arrays. These are actually
# one-dimensional immutable arrays with an additional access function with
# three index parameters.
#
public array3(T type,
        I type : integer,
        length0, length1, length2 I,
        init (I, I, I) -> T) array3 T
  pre
    safety: length0 ? 0
    safety: length1 ? 0
    safety: length2 ? 0
    safety: length0.as_i64 *? length1.as_i64 *? length2.as_i64 >=? 0
    debug : length0.fits_in_i64
    debug : length1.fits_in_i64
    debug : length2.fits_in_i64
=>
  (array3 T).new I length0 length1 length2 init