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

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

# sortedarray -- sorted one-dimensional immutable array
#
# This takes an unsorted array and a compare function as an arguments and
# returns a sorted one.
#
# Non-mutating heap sort is used internally. This gives guaranteed peformance in
# O(n log n) comparisons and assignments for an array of size n.
#
# This is a little wasteful on allocated memory, which is also O(n log n) since
# partially sorted arrays are thrown away.  This might be improved to use an
# in-place heap sort to bring allocated memory down to O(n).
#
sortedArray
  (
  # array element type
  redef T type,

  # orginal, unsorted Sequence
  #
  from Sequence<T>,

  # predicate defining total order on T.
  #
  # must satisfy:
  #
  #   forAll a,b: lessOrEqual(a, b) <=> (a = b)
  #   forAll a,b: lessOrEqual(a, b) || lessOrEqual(b, a)
  #   forAll a,b,c: (lessOrEqual(a, b) && lessOrEqual(b, c)): lessOrEqual(a, c)
  #
  lessOrEqual (T, T) -> bool

  )

  : array T (sort from.asArray 1).internalArray unit unit unit

is

  # perform heap sort on the given array
  #
  # result is a new array that is sorted
  #
  sort
    (
    # array with sub-heaps of heapSize sorted
    a array<T>,

    # the current heap size, 1 on initial call, must be power of 2
    heapSize i32
    ) array<T>

    pre
      debug: heapSize >= 0,
      debug: (heapSize & (heapSize-1)) = 0
      # NYI: analysis: for all i=0..a.length/heapSize: a[heapSize*i .. heapSize*(i+1)-1] is sorted
  is
    # check if the array is fully sorted
    if heapSize >= a.length
      a.asArray  # NYI: convert 'ref'-array due to lack of 'like this' back to non-'ref' array
    else
      # h1 is the mutable index within the current first heap, this is updated
      # by the function passed to the array constructor.
      #
      # NYI: This might eventually be done using a monad with monadic lifting
      # of array.
      h1 := 0;

      na := array<T> a.length (i ->
        # index in current pair of heaps
        hi := i & (heapSize*2-1)
        # reset h1 in case we start new pair of heaps
        set h1 := if (hi = 0) 0 else h1
        # index within second heap
        h2 := hi - h1

        # absolute indices in first and second heap
        i1 := i - hi + h1;
        i2 := i - hi + heapSize + h2;

        # did we reach end of first or second heap?
        heap1Empty := h1 >= heapSize
        heap2Empty := h2 >= heapSize || i2 >= a.length

        # check if next element comes from first heap
        if heap2Empty || !heap1Empty && lessOrEqual(a[i1], a[i2])
          # if so, increment index in first heap and return element from first heap
          set h1 := h1 + 1
          a[i1]
        else
          # otherwise, return element from second heap
          a[i2]
        )

      # continue sorting with doubled heap size
      sort na 2*heapSize


  # find index of given key using binary search
  #
  # The guaranteed performance is in O(log n) comparisons.
  #
  # result is the index where key was found or nil if key is not
  # in this array.  In case several instance equal to key are in
  # this sortedArray, the index of one of the matching keys will be
  # returned, but is not specified which one.
  #
  findKey (key T) option<i32>
    post
      match result
        i i32 => # sortedArray.this[i] = key, but we do not have 'infix =' available, so
                 # use lessOrEqual instead:
                 #
                 lessOrEqual sortedArray.this[i] key && lessOrEqual key sortedArray.this[i]
        nil   => true # NYI: analyis: for all i=0..a.length-1, sortedArray.this[i] /= key
  is
    binarySearch(l, r i32) option<i32> is
      m := (l + r) / 2
      if l > r                                     then nil
      else if !lessOrEqual key sortedArray.this[m] then binarySearch m+1 r
      else if !lessOrEqual sortedArray.this[m] key then binarySearch l m-1
      else                                              m

    binarySearch 0 length-1


  # find index of key for which cmp returns 0
  #
  # The guaranteed performance is in O(log n) comparisons.
  #
  # result is the index where cmp results in 0 or nil if no such index
  # was found in this array.  In case several instance equal match,
  # the index of one matching key will be returned, but is not
  # specified which one.
  #
  find (

    # cmp must be < 0 (> 0) if key is less (larger) than desired key.
    #
    # cmp must implement the same total order as 'T.infix <='.
    #
    cmp T -> i32

    ) option<i32>

    post
      match result
        i i32 => (cmp sortedArray.this[i]) = 0
        nil   => true # NYI: analyis: for all i=0..a.length-1, sortedArray.this[i] /= key
  is
    binarySearch(l, r i32) option<i32> is
      m := (l + r) / 2
      if l > r
        nil
      else
        c := cmp sortedArray.this[m]
        if      c < 0 then binarySearch m+1 r
        else if c > 0 then binarySearch l m-1
        else               m

    binarySearch 0 length-1


# sortedarray -- sorted one-dimensional immutable array of ordered elements
#
# This takes an unsorted array as an argument and returns a sorted one using
# the order defined by the type of the elements T.
#
# See sortedArray(from, lessOrEqual) for details
#
sortedArrayOf<T: ordered<T>>
  (
  # orginal, unsorted Sequence
  from Sequence<T>
  ) sortedArray<T>

is
  sortedArray<T> from (a,b -> a <= b)