Class: TreeMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/treemap/tree_map.rb,
lib/treemap/bounded_map.rb

Overview

TreeMap is a Ruby port of android.googlesource.com/platform/libcore.git/+/android-6.0.1_r32/luni/src/main/java/java/util/TreeMap.java This is an AVL tree based implementation of Java’s java.util.TreeMap structure. It implements Java’s java.util.NavigableMap interface. Warning: Not all of the reference implementation has been ported.

Defined Under Namespace

Modules: Bound, Relation Classes: BoundedMap, Node, NodeIterator

Constant Summary collapse

NaturalOrder = 
->(this, that) { this <=> that }

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(comparator = NaturalOrder) ⇒ TreeMap

comparator is a function of the form: (this, that) -> int ; where int is -1 if this < that, 0 if this == that, and 1 if this > that



150
151
152
153
154
155
 
# File 'lib/treemap/tree_map.rb', line 150

def initialize(comparator = NaturalOrder)
  @comparator = comparator
  @root = nil
  @size = 0
  @mod_count = 0
end

Instance Attribute Details

#comparator ⇒ Object

Returns the value of attribute comparator.



147
148
149
 
# File 'lib/treemap/tree_map.rb', line 147

def comparator
  @comparator
end

#root ⇒ Object

Returns the value of attribute root.



147
148
149
 
# File 'lib/treemap/tree_map.rb', line 147

def root
  @root
end

#size ⇒ Object

Returns the value of attribute size.



147
148
149
 
# File 'lib/treemap/tree_map.rb', line 147

def size
  @size
end

Instance Method Details

#ceiling_entry(key) ⇒ Object

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.



531
532
533
 
# File 'lib/treemap/tree_map.rb', line 531

def ceiling_entry(key)
  find(key, Relation::CEILING)
end

#ceiling_key(key) ⇒ Object

Returns the least key greater than or equal to the given key, or null if there is no such key.



536
537
538
539
 
# File 'lib/treemap/tree_map.rb', line 536

def ceiling_key(key)
  entry = find(key, Relation::CEILING)
  entry.key if entry
end

#clear ⇒ Object 



176
177
178
179
180
 
# File 'lib/treemap/tree_map.rb', line 176

def clear
  @root = nil
  @size = 0
  @mod_count += 1
end

#contains_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


168
169
170
 
# File 'lib/treemap/tree_map.rb', line 168

def contains_key?(key)
  find_by_object(key)
end

#descending_map ⇒ Object 



617
618
619
 
# File 'lib/treemap/tree_map.rb', line 617

def descending_map
  BoundedMap.new(self, false, nil, Bound::NO_BOUND, nil, Bound::NO_BOUND)
end

#each(&blk) ⇒ Object

each {|k,v| puts “#{k}->#v”}



652
653
654
655
656
657
658
 
# File 'lib/treemap/tree_map.rb', line 652

def each(&blk)
  if block_given?
    each_node {|node| blk.call(node.key, node.value) }
  else
    enum_for(:each)
  end
end

#each_node ⇒ Object

each_node {|node| puts “#{node.key}->#TreeMap.nodenode.value”}



661
662
663
664
665
666
667
668
669
670
 
# File 'lib/treemap/tree_map.rb', line 661

def each_node
  if block_given?
    iter = NodeIterator.new(@root.first)
    while iter.has_next?
      yield iter.step_forward()
    end
  else
    enum_for(:each_node)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


157
158
159
 
# File 'lib/treemap/tree_map.rb', line 157

def empty?
  @size == 0
end

#entry_set ⇒ Object

View factory methods



554
555
556
 
# File 'lib/treemap/tree_map.rb', line 554

def entry_set
  Set.new(each_node.to_a)
end

#find(key, relation) ⇒ Object

Returns the node at or adjacent to the given key, creating it if requested.



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
 
# File 'lib/treemap/tree_map.rb', line 195

def find(key, relation)
  if @root.nil?
    if relation == Relation::CREATE
      @root = Node.new(nil, key)
      @size = 1
      @mod_count += 1
      return @root
    else
      return nil
    end
  end

  nearest = @root
  while true
    comparison = @comparator.call(key, nearest.key)

    # we found the requested key
    if comparison == 0
      case relation
      when Relation::LOWER
        return nearest.prev_node
      when Relation::FLOOR, Relation::EQUAL, Relation::CREATE, Relation::CEILING
        return nearest
      when Relation::HIGHER
        return nearest.next_node
      end
    end

    child = (comparison < 0) ? nearest.left : nearest.right
    if child
      nearest = child
      next  # continue
    end

    # We found a nearest node. Every key not in the tree has up to two nearest nodes, one lower and one higher.
    if comparison < 0     # nearest.key is higher
      case relation
      when Relation::LOWER, Relation::FLOOR
        return nearest.prev_node
      when Relation::CEILING, Relation::HIGHER
        return nearest
      when Relation::EQUAL
        return nil
      when Relation::CREATE
        created = Node.new(nearest, key)
        nearest.left = created
        @size += 1
        @mod_count += 1
        rebalance(nearest, true)
        return created
      end
    else                  # comparison > 0 ; nearest.key is lower
      case relation
      when Relation::LOWER, Relation::FLOOR
        return nearest
      when Relation::CEILING, Relation::HIGHER
        return nearest.next_node
      when Relation::EQUAL
        return nil
      when Relation::CREATE
        created = Node.new(nearest, key)
        nearest.right = created
        @size += 1
        @mod_count += 1
        rebalance(nearest, true)
        return created
      end
    end
  end
end

#find_by_entry(key, value) ⇒ Object

entry is a key-value pair in an array: [key, value] Returns this map’s entry that has the same key and value as <entry>, or null if this map has no such entry.

This method uses the comparator for key equality rather than <equals>. If this map’s comparator isn’t consistent with equals, then remove() and contains() will violate the collections API.

returns a Node



278
279
280
281
282
 
# File 'lib/treemap/tree_map.rb', line 278

def find_by_entry(key, value)
  key, value = *entry
  mine = find_by_object(key)
  mine if mine && mine.value == value
end

#find_by_object(key) ⇒ Object

returns a Node



267
268
269
 
# File 'lib/treemap/tree_map.rb', line 267

def find_by_object(key)
  find(key, Relation::EQUAL)
end

#first_entry ⇒ Object

Returns a key-value mapping associated with the least key in this map, or null if the map is empty.



465
466
467
 
# File 'lib/treemap/tree_map.rb', line 465

def first_entry
  root.first if root
end

#first_key ⇒ Object 



481
482
483
484
 
# File 'lib/treemap/tree_map.rb', line 481

def first_key
  raise "No such element." unless root
  root.first.key
end

#floor_entry(key) ⇒ Object

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.



520
521
522
 
# File 'lib/treemap/tree_map.rb', line 520

def floor_entry(key)
  find(key, Relation::FLOOR)
end

#floor_key(key) ⇒ Object

Returns the greatest key less than or equal to the given key, or null if there is no such key.



525
526
527
528
 
# File 'lib/treemap/tree_map.rb', line 525

def floor_key(key)
  entry = find(key, Relation::FLOOR)
  entry.key if entry
end

#get(key) ⇒ Object Also known as: [] 



161
162
163
164
 
# File 'lib/treemap/tree_map.rb', line 161

def get(key)
  entry = find_by_object(key)
  entry.value if entry
end

#head_map(*args) ⇒ Object

This can be called in 1 of 2 ways: head_map(to_exclusive) OR head_map(to, inclusive)



589
590
591
592
593
594
595
596
597
598
599
 
# File 'lib/treemap/tree_map.rb', line 589

def head_map(*args)
  case args.count
  when 1
    to_exclusive = args.first
    BoundedMap.new(self, true, nil, Bound::NO_BOUND, to_exclusive, Bound::EXCLUSIVE)
  when 2
    to, inclusive = *args
    to_bound = inclusive ? Bound::INCLUSIVE : Bound::EXCLUSIVE
    BoundedMap.new(self, true, nil, Bound::NO_BOUND, to, to_bound)
  end
end

#higher_entry(key) ⇒ Object

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.



542
543
544
 
# File 'lib/treemap/tree_map.rb', line 542

def higher_entry(key)
  find(key, Relation::HIGHER)
end

#higher_key(key) ⇒ Object

Returns the least key strictly greater than the given key, or null if there is no such key.



547
548
549
550
 
# File 'lib/treemap/tree_map.rb', line 547

def higher_key(key)
  entry = find(key, Relation::HIGHER)
  entry.key if entry
end

#internal_poll_first_entry ⇒ Object 



469
470
471
472
473
474
475
 
# File 'lib/treemap/tree_map.rb', line 469

def internal_poll_first_entry
  if root
    result = root.first
    remove_internal(result)
    result
  end
end

#internal_poll_last_entry ⇒ Object 



491
492
493
494
495
496
497
 
# File 'lib/treemap/tree_map.rb', line 491

def internal_poll_last_entry
  if root
    result = root.last
    remove_internal(result)
    result
  end
end

#key_set ⇒ Object Also known as: keys 



558
559
560
 
# File 'lib/treemap/tree_map.rb', line 558

def key_set
  Set.new(each_node.map(&:key))
end

#last_entry ⇒ Object

Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.



487
488
489
 
# File 'lib/treemap/tree_map.rb', line 487

def last_entry
  root.last if root
end

#last_key ⇒ Object 



503
504
505
506
 
# File 'lib/treemap/tree_map.rb', line 503

def last_key
  raise "No such element." unless root
  root.last.key
end

#lower_entry(key) ⇒ Object

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.



509
510
511
 
# File 'lib/treemap/tree_map.rb', line 509

def lower_entry(key)
  find(key, Relation::LOWER)
end

#lower_key(key) ⇒ Object

Returns the greatest key strictly less than the given key, or null if there is no such key.



514
515
516
517
 
# File 'lib/treemap/tree_map.rb', line 514

def lower_key(key)
  entry = find(key, Relation::LOWER)
  entry.key if entry
end

#poll_first_entry ⇒ Object 



477
478
479
 
# File 'lib/treemap/tree_map.rb', line 477

def poll_first_entry
  internal_poll_first_entry
end

#poll_last_entry ⇒ Object 



499
500
501
 
# File 'lib/treemap/tree_map.rb', line 499

def poll_last_entry
  internal_poll_last_entry
end

#put(key, value) ⇒ Object 



172
173
174
 
# File 'lib/treemap/tree_map.rb', line 172

def put(key, value)
  put_internal(key, value)
end

#put_internal(key, value) ⇒ Object 



187
188
189
190
191
192
 
# File 'lib/treemap/tree_map.rb', line 187

def put_internal(key, value)
  created = find(key, Relation::CREATE)
  result = created.value
  created.value = value
  result
end

#rebalance(unbalanced, insert) ⇒ Object

Rebalances the tree by making any AVL rotations necessary between the newly-unbalanced node and the tree’s root.

Parameters:

  • insert —

    true if the node was unbalanced by an insert; false if it was by a removal.



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
 
# File 'lib/treemap/tree_map.rb', line 362

def rebalance(unbalanced, insert)
  node = unbalanced
  while node
    left = node.left
    right = node.right
    left_height = left ? left.height : 0
    right_height = right ? right.height : 0

    delta = left_height - right_height
    if delta == -2
      right_left = right.left
      right_right = right.right
      right_right_height = right_right ? right_right.height : 0
      right_left_height = right_left ? right_left.height : 0

      right_delta = right_left_height - right_right_height
      if right_delta == -1 || (right_delta == 0 && !insert)
        rotate_left(node)
      else
        # assert (right_delta == 1)
        rotate_right(right)   # AVL right left
        rotate_left(node)
      end
      break if insert   # no further rotations will be necessary
    elsif delta == 2
      left_left = left.left
      left_right = left.right
      left_right_height = left_right ? left_right.height : 0
      left_left_height = left_left ? left_left.height : 0

      left_delta = left_left_height - left_right_height
      if left_delta == 1 || (left_delta == 0 && !insert)
        rotate_right(node)    # AVL left left
      else
        # assert (left_delta == -1)
        rotate_left(left)   # AVL left right
        rotate_right(node)
      end
      break if insert
    elsif delta == 0
      node.height = left_height + 1   # left_height == right_height
      break if insert
    else
      # assert (delta == -1 || delta == 1)
      node.height = [left_height, right_height].max + 1
      break if insert    # the height hasn't changed, so rebalancing is done!
    end

    node = node.parent
  end
end

#remove(key) ⇒ Object 



182
183
184
185
 
# File 'lib/treemap/tree_map.rb', line 182

def remove(key)
  node = remove_internal_by_key(key)
  node.value if node
end

#remove_internal(node) ⇒ Object

Removes node from this tree, rearranging the tree’s structure as necessary. return value not meaningful



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
 
# File 'lib/treemap/tree_map.rb', line 286

def remove_internal(node)
  left = node.left
  right = node.right
  original_parent = node.parent

  if left && right
    # To remove a node with both left and right subtrees, move an adjacent node from one of those subtrees into this node's place.
    # Removing the adjacent node may change this node's subtrees. This node may no longer have two subtrees once the adjacent node is gone!

    adjacent = left.height > right.height ? left.last : right.first
    remove_internal(adjacent)   # takes care of rebalance and size--

    left_height = 0
    left = node.left
    if left
      left_height = left.height
      adjacent.left = left
      left.parent = adjacent
      node.left = nil
    end
    right_height = 0
    right = node.right
    if right
      right_height = right.height
      adjacent.right = right
      right.parent = adjacent
      node.right = nil
    end
    adjacent.height = [left_height, right_height].max + 1
    replace_in_parent(node, adjacent)
    return
  elsif left
    replace_in_parent(node, left)
    node.left = nil
  elsif right
    replace_in_parent(node, right)
    node.right = nil
  else
    replace_in_parent(node, nil)
  end

  rebalance(original_parent, false)
  @size -= 1
  @mod_count -= 1
end

#remove_internal_by_key(key) ⇒ Object 



332
333
334
335
336
337
338
 
# File 'lib/treemap/tree_map.rb', line 332

def remove_internal_by_key(key)
  node = find_by_object(key)
  if node
    remove_internal(node)
  end
  node
end

#replace_in_parent(node, replacement) ⇒ Object 



340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
 
# File 'lib/treemap/tree_map.rb', line 340

def replace_in_parent(node, replacement)
  parent = node.parent
  node.parent = nil
  if replacement
    replacement.parent = parent
  end

  if parent
    if parent.left == node
      parent.left = replacement
    else
      # assert (parent.right == node)
      parent.right = replacement
    end
  else
    @root = replacement
  end
end

#rotate_left(root) ⇒ Object

Rotates the subtree so that its root’s right child is the new root



415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
 
# File 'lib/treemap/tree_map.rb', line 415

def rotate_left(root)
  left = root.left
  pivot = root.right
  pivot_left = pivot.left
  pivot_right = pivot.right

  # move the pivot's left child to the root's right
  root.right = pivot_left
  if pivot_left
    pivot_left.parent = root
  end

  replace_in_parent(root, pivot)

  # move the root to the pivot's left
  pivot.left = root
  root.parent = pivot

  # fix heights
  root.height = [left ? left.height : 0, pivot_left ? pivot_left.height : 0].max + 1
  pivot.height = [root.height, pivot_right ? pivot_right.height : 0].max + 1
end

#rotate_right(root) ⇒ Object

Rotates the subtree so that its root’s left child is the new root



439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
 
# File 'lib/treemap/tree_map.rb', line 439

def rotate_right(root)
  pivot = root.left
  right = root.right
  pivot_left = pivot.left
  pivot_right = pivot.right

  # move the pivot's right child to the root's left
  root.left = pivot_right
  if pivot_right
    pivot_right.parent = root
  end

  replace_in_parent(root, pivot)

  # move the root to the pivot's right
  pivot.right = root
  root.parent = pivot

  # fix heights
  root.height = [right ? right.height : 0, pivot_right ? pivot_right.height : 0].max + 1
  pivot.height = [root.height, pivot_left ? pivot_left.height : 0].max + 1
end

#sub_map(*args) ⇒ Object

This can be called in 1 of 2 ways: sub_map(from_inclusive, to_exclusive) OR sub_map(from, from_inclusive, to, to_inclusive)



572
573
574
575
576
577
578
579
580
581
582
583
 
# File 'lib/treemap/tree_map.rb', line 572

def sub_map(*args)
  case args.count
  when 2
    from_inclusive, to_exclusive = *args
    BoundedMap.new(self, true, from_inclusive, Bound::INCLUSIVE, to_exclusive, Bound::EXCLUSIVE)
  when 4
    from, from_inclusive, to, to_inclusive = *args
    from_bound = from_inclusive ? Bound::INCLUSIVE : Bound::EXCLUSIVE
    to_bound = to_inclusive ? Bound::INCLUSIVE : Bound::EXCLUSIVE
    BoundedMap.new(self, true, from, from_bound, to, to_bound);
  end
end

#tail_map(*args) ⇒ Object

This can be called in 1 of 2 ways: tail_map(from_inclusive) OR tail_map(from, inclusive)



605
606
607
608
609
610
611
612
613
614
615
 
# File 'lib/treemap/tree_map.rb', line 605

def tail_map(*args)
  case args.count
  when 1
    from_inclusive = args.first
    BoundedMap.new(self, true, from_inclusive, Bound::INCLUSIVE, nil, Bound::NO_BOUND)
  when 2
    from, inclusive = *args
    from_bound = inclusive ? Bound::INCLUSIVE : Bound::EXCLUSIVE
    BoundedMap.new(self, true, from, from_bound, nil, Bound::NO_BOUND)
  end
end

#values ⇒ Object 



564
565
566
 
# File 'lib/treemap/tree_map.rb', line 564

def values
  each_node.map(&:value)
end