container/sorted_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 sorted_array
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# sorted_array -- 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).
#
public sorted_array
(
# array element type
T type,
# orginal, unsorted Sequence
#
from Sequence T,
# predicate defining total order on T.
#
# must satisfy:
#
# for_all a,b: less_or_equal(a, b) <=> (a = b)
# for_all a,b: less_or_equal(a, b) || less_or_equal(b, a)
# for_all a,b,c: (less_or_equal(a, b) && less_or_equal(b, c)): less_or_equal(a, c)
#
less_or_equal (T, T) -> bool
)
: array T (sort from.as_array 1).internal_array 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 heap_size sorted
a array T,
# the current heap size, 1 on initial call, must be power of 2
heap_size i32
) array T
pre
debug: (heap_size ≥ 0)
debug: ((heap_size & (heap_size-1)) = 0)
# NYI: analysis: for all i=0..a.length/heap_size: a[heap_size*i .. heap_size*(i+1)-1] is sorted
=>
# check if the array is fully sorted
if heap_size ≥ a.length
a
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 & (heap_size*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 + heap_size + h2;
# did we reach end of first or second heap?
heap1_empty := h1 ≥ heap_size
heap2_empty := (h2 ≥ heap_size) || (i2 ≥ a.length)
# check if next element comes from first heap
if heap2_empty || !heap1_empty && less_or_equal(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*heap_size
# 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 sorted_array, the index of one of the matching keys will be
# returned, but is not specified which one.
#
public find_key (key T) option i32
post
match result
i i32 => # sorted_array.this[i] = key, but we do not have 'infix =' available, so
# use less_or_equal instead:
#
less_or_equal sorted_array.this[i] key && less_or_equal key sorted_array.this[i]
nil => true # NYI: analyis: for all i=a.indices, sorted_array.this[i] != key
=>
binary_search(l, r i32) option i32 =>
m := (l + r) / 2
if l > r then nil
else if !less_or_equal key sorted_array.this[m] then binary_search m+1 r
else if !less_or_equal sorted_array.this[m] key then binary_search l m-1
else m
binary_search 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.
#
public 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 sorted_array.this[i]) = 0
nil => true # NYI: analyis: for all i=a.indices, sorted_array.this[i] /= key
=>
binary_search(l, r i32) option i32 =>
m := (l + r) / 2
if l > r
nil
else
c := cmp sorted_array.this[m]
if c < 0 then binary_search m+1 r
else if c > 0 then binary_search l m-1
else m
binary_search 0 length-1
# sorted_array_of -- 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 sorted_array from less_or_equal for details
#
public sorted_array_of
(
T type : property.orderable,
# orginal, unsorted Sequence
from Sequence T
) sorted_array T
=>
sorted_array T from (a,b -> a ≤ b)
last changed: 2024-03-07