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

# ps_map -- a partially sorted map
#
# ps_map is a persistent map from an ordered key PK to a value V.  This map is
# generally well-behaved with respect to cumulative and average performance.
#
# The keys and values are stored in arrays consisting of sorted sub-arrays,
# with sub-arrays corresponding to the 1-bits in the binary representation
# of the size.
#
# This results in cumulative memory usage in O(size log? size), worst-case
# lookup time in O(log? size) and average addition time in O(1) and worst-case
# addition time in O(size log? size).
#
# WARNING: Due to the high worst-case time for addition, this structure should
# not be used in situations when adding a single element repeatedly to the same
# instance of ps_map is performance critical. If the resulting map's size n is a
# power of 2, this will trigger the worst-case addition time resulting in
# O(m*n log? n) for adding an element m times.
#
# This constructor is for internal use only, to create instance of ps_map, use
# ps_map PK V without arguments.
#
private:public ps_map
  (
   # key type
   PK type : property.orderable,

   # value type
   V type,

   # the array containing the sorted arrays, see below for details
   data container.expanding_array (PK, V),

   # the number of key and value pairs in this map.
   public redef size i32,

   # the first index in data that is unused
   fill i32)

   : Map PK V

is

/*

The structure of the data array for different values of size and fill is as follows.

size fill data.length data array structure
 0    0     0         .
 1    1     1         A
 2    2     3         AA-
 3    3     3         AAB
 4    4     8         AAAA----
 5    5     8         AAAAB---
 6    7     8         AAAA-BB-
 7    8     8         AAAA-BBC
 8    8    20         AAAAAAAA------------
 9    9    20         AAAAAAAAB-----------
10   11    20         AAAAAAAA-BB---------
11   12    20         AAAAAAAA-BBC--------
12   16    20         AAAAAAAA----BBBB----
13   17    20         AAAAAAAA----BBBBC---
14   19    20         AAAAAAAA----BBBB-CC-
15   20    20         AAAAAAAA----BBBB-CCD
16   16    48         AAAAAAAAAAAAAAAA--------------------------------
17   17    48         AAAAAAAAAAAAAAAAB-------------------------------
18   19    48         AAAAAAAAAAAAAAAA-BB-----------------------------
19   20    48         AAAAAAAAAAAAAAAA-BBC----------------------------
20   24    48         AAAAAAAAAAAAAAAA----BBBB------------------------
21   25    48         AAAAAAAAAAAAAAAA----BBBBC-----------------------
22   27    48         AAAAAAAAAAAAAAAA----BBBB-CC---------------------
23   28    48         AAAAAAAAAAAAAAAA----BBBB-CCD--------------------
24   36    48         AAAAAAAAAAAAAAAA------------BBBBBBBB------------
25   37    48         AAAAAAAAAAAAAAAA------------BBBBBBBBC-----------
26   39    48         AAAAAAAAAAAAAAAA------------BBBBBBBB-CC---------
27   40    48         AAAAAAAAAAAAAAAA------------BBBBBBBB-CCD--------
28   44    48         AAAAAAAAAAAAAAAA------------BBBBBBBB----CCCC----
29   45    48         AAAAAAAAAAAAAAAA------------BBBBBBBB----CCCCD---
30   47    48         AAAAAAAAAAAAAAAA------------BBBBBBBB----CCCC-DD-
31   48    48         AAAAAAAAAAAAAAAA------------BBBBBBBB----CCCC-DDE
32   32   112         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA--------------------------------------------------------------------------------
33   33   112         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB-------------------------------------------------------------------------------
34   35   112         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA-BB-----------------------------------------------------------------------------
35   36   112         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA-BBC----------------------------------------------------------------------------
 etc.

Whenever size reaches a power of two, a new data array is allocated.

The length of the initial data array is 0, the new length for an allocation when
size is a power of two is the old data.length * 2 + ceil(size / 2), i.e, the
allocation f for size

   0,1,2, 4, 8,16, 32, 64, 128, 256, 512, 1024, 2048, 4096,  8192, 16384,...

is 0,1,3, 8,20,48,112,256, 576,1280,2816, 6144,13312,28672, 61440,131072,...

and the cumulative allocation is

is 0,1,4,12,32,80,192,448,1024,2304,5120,11264,24576,53248,114688,245760,...

The memory usage for size n as well as the cumulative memory usage are hence in
O(n log n).

*/


  # add mapping from k to v
  #
  public fixed add (k PK, v V) ps_map PK V =>
    if has k
      panic "NYI: ps_map currently does not handle updates for existing key"
    else
      add (k,v)


  # add mapping from kv.values.0 to kv.values.1
  #
  # Adding has a cumulative average runtime in O(log size) and a worst-case
  # runtime of O(size)
  #
  public add (kv (tuple PK V)) ps_map PK V =>
    nsize := size + 1
    ndata, nfill := if (nsize & size) = 0
                    then ((container.expanding_array (PK,V)).empty (data.capacity * 2 + (nsize+1) / 2), 0)
                    else (data, fill)
    nsz := (1 << (size+1).trailing_zeros)

    d := ndata.expand nsz ()->
      a := (container.expanding (tuple PK V)).env

      # join arrays data[ole..ole+sz-1] and a[new..new+sz-1] to a[new-sz..new+sz-1]
      #
      join (ole i32, new i32, sz i32) =>
        if (size & sz) != 0
          _ :=
            for
              i := 0, i+1
              i1 := 0, if (use1) i1+1 else i1
              i2 := 0, if (use1) i2   else i2+1
              use1 := i1 < sz && (i2 ? sz || data[ole + i1].0 < a[new+i2].0)
            while  i < 2*sz
              a[new-sz+i] := if use1 then data[ole + i1] else a[new+i2]
          join (fill - sz - 2*(fill - ole - sz) - 2*sz) new-sz 2*sz

      a[nfill+nsz-1] := kv
      join fill-1 nfill+nsz-1 1

    ps_map d nsize nfill+nsz


  # find the value k is mapped to or nil if k is not part of this map
  #
  public redef index [] (k PK) option V =>

    binary_search(l, r i32) option V =>
      m := (l + r) / 2
      if l > r
        nil
      else
        mk, mv := data[m]
        match (mk) ? k
          less    => binary_search m+1 r
          greater => binary_search l m-1
          equal   => mv

    # find k in sub-arrays starting at data[at]
    #
    get (at i32, sz i32, tail i32) option V =>
      if sz = 0
        nil
      else
        sz0 := sz / 2
        nt := (tail - sz0) / 2
        at0 := (at
                + (if (size & sz0) != 0 nt else 0)
                + (if (size & sz ) != 0 sz else 0))
        if (size & sz) != 0
          match binary_search at at+sz-1
            v V => v
            nil => get at0 sz0 nt
        else
          get at0 sz0 nt

    sub_sz := size.highest_one_bit
    get 0 sub_sz (data.capacity - sub_sz)


  # create sorted array of all keys in this map
  #
  public as_key_array array PK =>
    re := (container.expanding_array PK).empty.expand size ()->
      a := (container.expanding PK).env

      # join arrays data[ole..ole+sz-1] and a[dest..dest+rsz-1] to r[dest..dest+sz+rsz-1]
      #
      join (ole i32, sz i32, rsz i32, skip i32) unit =>
        if sz ? size
          if (size & sz) != 0
            _ :=
              for
                i in 0..
                i1 := 0, if (use1) i1+1 else i1
                i2 := 0, if (use1) i2   else i2+1
                use1 := i1 < sz && ((i2 ? rsz) || (data[ole + i1].0 < a[size-rsz+i2]))
              while i < sz+rsz
                a[size-rsz-sz + i1 + i2] := if (use1) data[ole + i1].0 else a[size-rsz+i2]
            join (ole - skip - 2*sz) 2*sz rsz+sz (skip + sz + skip)
          else
            join ole-sz 2*sz rsz (skip + sz + skip)

      join fill-1 1 0 0

    array PK size i->re[i]


  # get an array of all key/value pairs in this map
  #
  public redef items Sequence (tuple PK V) =>
    as_key_array.map (k -> (k, ps_map.this[k].get))


  # get the lowest key in this map
  #
  public min option PK =>

    min0 (m PK, l i32, r i32) PK =>
      lk, _ := data[l]
      if (m ? lk) m else lk

    min (m PK, at i32, sz i32, tail i32) PK =>
      if sz = 0
        m
      else
        sz0 := sz / 2
        nt := (tail - sz0) / 2
        at0 := (at
                + (if (size & sz0) != 0 nt else 0)
                + (if (size & sz ) != 0 sz else 0))
        m0 := if (size & sz) != 0
                min0 m at at+sz-1
              else
                m
        min m0 at0 sz0 nt

    if size = 0
      nil
    else
      sub_sz := size.highest_one_bit
      min data[0].0 0 sub_sz (data.capacity - sub_sz)


  # get the highest key in this map
  #
  public max option PK =>

    max0 (m PK, l i32, r i32) PK =>
      rk, _ := data[r]
      if (m ? rk) m else rk

    max (m PK, at i32, sz i32, tail i32) PK =>
      if sz = 0
        m
      else
        sz0 := sz / 2
        nt := (tail - sz0) / 2
        at0 := (at
                + (if (size & sz0) != 0 nt else 0)
                + (if (size & sz ) != 0 sz else 0))
        m0 := if (size & sz) != 0
                max0 m at at+sz-1
              else
                m
        max m0 at0 sz0 nt

    if size = 0
      nil
    else
      sub_sz := size.highest_one_bit
      max data[0].0 0 sub_sz (data.capacity - sub_sz)


  # union of two ps_maps
  #
  # creates a new ps_map that maps all the keys that exist either in ps_map.this
  # or in other to the values they are mapped to.  In case a key k exists in
  # both ps_map.this and other, it will be mapped to ps_map.this[k] or to other[k],
  # but it is undefined to which of these two.
  #
  public fixed union (other ps_map PK V) ps_map PK V =>

    # helper to add 'ps_map.this.data[l..r]' to 'a' and return the resulting map.
    #
    add_all (a ps_map PK V, l i32, r i32) ps_map PK V =>
      if l > r
        a
      else
        kv := data[l]
        a0 := if (a.has kv.0) a else a.add kv
        add_all a0 l+1 r

    # helper to add 'sz' elements from 'ps_map.this.data[at..at+sz]' to 'a', with
    # 'tail' elements at indices larger or equal to 'at+sz' added recursively as
    # well.
    #
    add_all (a ps_map PK V, at i32, sz i32, tail i32) ps_map PK V =>
      if sz = 0
        a
      else
        sz0 := sz / 2
        nt := (tail - sz0) / 2
        at0 := (at
                + (if (size & sz0) != 0 nt else 0)
                + (if (size & sz ) != 0 sz else 0))
        a0 := if (size & sz) != 0
                add_all a at at+sz-1
              else
                a
        add_all a0 at0 sz0 nt

    if other.size < size
      other ? ps_map.this
    else
      sub_sz := size.highest_one_bit
      add_all other 0 sub_sz (data.capacity - sub_sz)


  # infix operator synonym for union of two ps_maps
  #
  public infix ? (other ps_map PK V) ps_map PK V => union other


  # create a mutable map from this
  #
  public redef as_mutable_map(LM type : mutate) container.Mutable_Map PK V =>
    (container.mutable_tree_map LM PK V).from items


  # empty -- an empty partially sorted map
  #
  # This feature creates an empty instance of ps_map.
  #
  public fixed redef type.empty container.ps_map PK V => container.ps_map ((container.expanding_array (PK,V)).empty 0) 0 0


  # ps_map -- routine to initialize a partially sorted map from two Sequences
  #
  # This feature creates a pre-initialized instance of ps_map.
  #
  public type.new(
      # list of keys in the map
      ks Sequence PK,
      # list of values corresponding to keys in the map
      vs Sequence V) container.ps_map PK V
  =>
    for
      r := (container.ps_map PK V).empty, r.add k v
      k in ks
      v in vs
    else
      r