map.pony

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
primitive _MapEmpty
primitive _MapDeleted

type Map[K: (Hashable #read & Equatable[K] #read), V] is
  HashMap[K, V, HashEq[K]]
  """
  This is a map that uses structural equality on the key.
  """

type MapIs[K, V] is HashMap[K, V, HashIs[K]]
  """
  This is a map that uses identity comparison on the key.
  """

class HashMap[K, V, H: HashFunction[K] val]
  """
  A quadratic probing hash map. Resize occurs at a load factor of 0.75. A
  resized map has 2 times the space. The hash function can be plugged in to the
  type to create different kinds of maps.
  """
  var _size: USize = 0
  var _array: Array[((K, V) | _MapEmpty | _MapDeleted)]

  new create(prealloc: USize = 6) =>
    """
    Create an array with space for prealloc elements without triggering a
    resize. Defaults to 6.
    """
    let len = (prealloc * 4) / 3
    let n = len.max(8).next_pow2()
    _array = _array.init(_MapEmpty, n)

  fun size(): USize =>
    """
    The number of items in the map.
    """
    _size

  fun space(): USize =>
    """
    The available space in the map. Resize will happen when
    size / space >= 0.75.
    """
    _array.space()

  fun apply(key: box->K!): this->V ? =>
    """
    Gets a value from the map. Raises an error if no such item exists.
    """
    (let i, let found) = _search(key)

    if found then
      _array(i)? as (_, this->V)
    else
      error
    end

  fun ref update(key: K, value: V): (V^ | None) =>
    """
    Sets a value in the map. Returns the old value if there was one, otherwise
    returns None. If there was no previous value, this may trigger a resize.
    """
    try
      (let i, let found) = _search(key)

      match _array(i)? = (consume key, consume value)
      | (_, let v: V) =>
        return consume v
      else
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end
    end

  fun ref upsert(key: K, value: V, f: {(V, V): V^} box): V! =>
    """
    Combines a provided value with the current value for the provided key
    using the provided function. If the provided key has not been added to
    the map yet, it sets its value to the provided value and ignores the
    provided function.

    As a simple example, say we had a map with I64 values and we wanted to
    add 4 to the current value for key "test", which let's say is currently 2.
    We call

    m.upsert("test", 4, {(current, provided) => current + provided })

    This changes the value associated with "test" to 6.

    If we have not yet added the key "new-key" to the map and we call

    m.upsert("new-key", 4, {(current, provided) => current + provided })

    then "new-key" is added to the map with a value of 4.

    Returns the value that we set the key to
    """

    (let i, let found) = _search(key)
    let value' = value

    try
      if found then
        (let pkey, let pvalue) = (_array(i)? = _MapEmpty) as (K^, V^)

        let new_value = f(consume pvalue, consume value)
        let new_value' = new_value

        _array(i)? = (consume pkey, consume new_value)

        return _array(i)? as (_, V)
      else
        let key' = key

        _array(i)? = (consume key, consume value)
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end

      value'
    else
      // This is unreachable, since index will never be out-of-bounds
      value'
    end

  fun ref insert(key: K, value: V): V! =>
    """
    Set a value in the map. Returns the new value, allowing reuse.
    """
    let value' = value
    try
      (let i, let found) = _search(key)
      let key' = key
      _array(i)? = (consume key, consume value)

      if not found then
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end

      value'
    else
      // This is unreachable, since index will never be out-of-bounds.
      value'
    end

  fun ref insert_if_absent(key: K, value: V): V! =>
    """
    Set a value in the map if the key doesn't already exist in the Map.
    Saves an extra lookup when doing a pattern like:

    ```pony
    if not my_map.contains(my_key) then
      my_map(my_key) = my_value
    end
    ```

    Returns the value, the same as `insert`, allowing 'insert_if_absent'
    to be used as a drop-in replacement for `insert`.
    """
    let value' = value

    try
      (let i, let found) = _search(key)
      let key' = key

      if not found then
        _array(i)? = (consume key, consume value)

        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end

      _array(i)? as (_, V)
    else
      // This is unreachable, since index will never be out-of-bounds.
      value'
    end

  fun ref remove(key: box->K!): (K^, V^) ? =>
    """
    Delete a value from the map and return it. Raises an error if there was no
    value for the given key.
    """
    try
      (let i, let found) = _search(key)

      if found then
        _size = _size - 1

        match _array(i)? = _MapDeleted
        | (let k: K, let v: V) =>
          return (consume k, consume v)
        end
      end
    end
    error

  fun get_or_else(key: box->K!, alt: this->V): this->V =>
    """
    Get the value associated with provided key if present. Otherwise,
    return the provided alternate value.
    """
    (let i, let found) = _search(key)

    if found then
      try
        _array(i)? as (_, this->V)
      else
        // This should never happen as we have already
        // proven that _array(i) exists
        consume alt
      end
    else
      consume alt
    end

  fun contains(k: box->K!): Bool =>
    """
    Checks whether the map contains the key k
    """
    (_, let found) = _search(k)
    found

  fun ref concat(iter: Iterator[(K^, V^)]) =>
    """
    Add K, V pairs from the iterator to the map.
    """
    for (k, v) in iter do
      this(consume k) = consume v
    end

  fun add[H2: HashFunction[this->K!] val = H](
    key: this->K!,
    value: this->V!)
    : HashMap[this->K!, this->V!, H2]^
  =>
    """
    This with the new (key, value) mapping.
    """
    let r = clone[H2]()
    r(key) = value
    r

  fun sub[H2: HashFunction[this->K!] val = H](key: this->K!)
    : HashMap[this->K!, this->V!, H2]^
  =>
    """
    This without the given key.
    """
    let r = clone[H2]()
    try r.remove(key)? end
    r

  fun next_index(prev: USize = -1): USize ? =>
    """
    Given an index, return the next index that has a populated key and value.
    Raise an error if there is no next populated index.
    """
    for i in Range(prev + 1, _array.size()) do
      match _array(i)?
      | (_, _) => return i
      end
    end
    error

  fun index(i: USize): (this->K, this->V) ? =>
    """
    Returns the key and value at a given index.
    Raise an error if the index is not populated.
    """
    _array(i)? as (this->K, this->V)

  fun ref compact() =>
    """
    Minimise the memory used for the map.
    """
    _resize(((_size * 4) / 3).next_pow2().max(8))

  fun clone[H2: HashFunction[this->K!] val = H]()
    : HashMap[this->K!, this->V!, H2]^
  =>
    """
    Create a clone. The key and value types may be different due to aliasing
    and viewpoint adaptation.
    """
    let r = HashMap[this->K!, this->V!, H2](_size)

    for (k, v) in pairs() do
      r(k) = v
    end
    r

  fun ref clear() =>
    """
    Remove all entries.
    """
    _size = 0
    // Our default prealloc of 6 corresponds to an array alloc size of 8.
    let n: USize = 8
    _array = _array.init(_MapEmpty, n)

  fun _search(key: box->K!): (USize, Bool) =>
    """
    Return a slot number and whether or not it's currently occupied.
    """
    var idx_del = _array.size()
    let mask = idx_del - 1
    let h = H.hash(key).usize()
    var idx = h and mask

    try
      for i in Range(0, _array.size()) do
        let entry = _array(idx)?

        match entry
        | (let k: this->K!, _) =>
          if H.eq(k, key) then
            return (idx, true)
          end
        | _MapEmpty =>
          if idx_del <= mask then
            return (idx_del, false)
          else
            return (idx, false)
          end
        | _MapDeleted =>
          if idx_del > mask then
            idx_del = idx
          end
        end

        idx = (h + ((i + (i * i)) / 2)) and mask
      end
    end

    (idx_del, false)

  fun ref _resize(len: USize) =>
    """
    Change the available space.
    """
    let old = _array
    let old_len = old.size()

    _array = _array.init(_MapEmpty, len)
    _size = 0

    try
      for i in Range(0, old_len) do
        match old(i)? = _MapDeleted
        | (let k: K, let v: V) =>
          this(consume k) = consume v
        end
      end
    end

  fun keys(): MapKeys[K, V, H, this->HashMap[K, V, H]]^ =>
    """
    Return an iterator over the keys.
    """
    MapKeys[K, V, H, this->HashMap[K, V, H]](this)

  fun values(): MapValues[K, V, H, this->HashMap[K, V, H]]^ =>
    """
    Return an iterator over the values.
    """
    MapValues[K, V, H, this->HashMap[K, V, H]](this)

  fun pairs(): MapPairs[K, V, H, this->HashMap[K, V, H]]^ =>
    """
    Return an iterator over the keys and values.
    """
    MapPairs[K, V, H, this->HashMap[K, V, H]](this)

class MapKeys[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
  Iterator[M->K]
  """
  An iterator over the keys in a map.
  """
  let _map: M
  var _i: USize = -1
  var _count: USize = 0

  new create(map: M) =>
    """
    Creates an iterator for the given map.
    """
    _map = map

  fun has_next(): Bool =>
    """
    True if it believes there are remaining entries. May not be right if values
    were added or removed from the map.
    """
    _count < _map.size()

  fun ref next(): M->K ? =>
    """
    Returns the next key, or raises an error if there isn't one. If keys are
    added during iteration, this may not return all keys.
    """
    _i = _map.next_index(_i)?
    _count = _count + 1
    _map.index(_i)?._1

class MapValues[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
  Iterator[M->V]
  """
  An iterator over the values in a map.
  """
  let _map: M
  var _i: USize = -1
  var _count: USize = 0

  new create(map: M) =>
    """
    Creates an iterator for the given map.
    """
    _map = map

  fun has_next(): Bool =>
    """
    True if it believes there are remaining entries. May not be right if values
    were added or removed from the map.
    """
    _count < _map.size()

  fun ref next(): M->V ? =>
    """
    Returns the next value, or raises an error if there isn't one. If values
    are added during iteration, this may not return all values.
    """
    _i = _map.next_index(_i)?
    _count = _count + 1
    _map.index(_i)?._2

class MapPairs[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
  Iterator[(M->K, M->V)]
  """
  An iterator over the keys and values in a map.
  """
  let _map: M
  var _i: USize = -1
  var _count: USize = 0

  new create(map: M) =>
    """
    Creates an iterator for the given map.
    """
    _map = map

  fun has_next(): Bool =>
    """
    True if it believes there are remaining entries. May not be right if values
    were added or removed from the map.
    """
    _count < _map.size()

  fun ref next(): (M->K, M->V) ? =>
    """
    Returns the next entry, or raises an error if there isn't one. If entries
    are added during iteration, this may not return all entries.
    """
    _i = _map.next_index(_i)?
    _count = _count + 1
    _map.index(_i)?