Class: RBTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rbtree.rb,
lib/rbtree/node.rb,
lib/rbtree/tree.rb,
lib/rbtree/rb_tree.rb,
lib/rbtree/rb_tree.rb,
lib/rbtree/rb_tree.rb,
lib/rbtree/tree_cmp.rb,
lib/rbtree/guard_node.rb

Overview

:nodoc: namespace

Direct Known Subclasses

MultiRBTree

Defined Under Namespace

Classes: GuardNode, Node, Tree, TreeCmp

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = nil, &default_proc) ⇒ RBTree

Returns a new instance of RBTree.

Raises:

  • (ArgumentError) 


31
32
33
34
35
36
37
38
 
# File 'lib/rbtree/rb_tree.rb', line 31

def initialize(default = nil, &default_proc)
  raise ArgumentError, "wrong number of arguments" if default && default_proc
  @default = default
  @default_proc = default_proc
  @cmp_proc = nil
  @lock_count = 0
  @tree = RBTree::Tree.new
end

Instance Attribute Details

#cmp_proc ⇒ Object (readonly)

Block used to implement custom comparisons.



29
30
31
 
# File 'lib/rbtree/rb_tree.rb', line 29

def cmp_proc
  @cmp_proc
end

#default_proc ⇒ Object

Block called when trying to read keys that don’t exist in the tree.



20
21
22
 
# File 'lib/rbtree/rb_tree.rb', line 20

def default_proc
  @default_proc
end

#tree ⇒ Object (readonly)

The red-black tree backing this store.



6
7
8
 
# File 'lib/rbtree/rb_tree.rb', line 6

def tree
  @tree
end

Class Method Details

.[](*key_values) ⇒ Object 



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
 
# File 'lib/rbtree/rb_tree.rb', line 46

def self.[](*key_values)
  if key_values.length == 1
    hash = key_values.first
    unless hash.respond_to? :values_at
      raise ArgumentError, "expected a Hash-like argument"
    end
    if self == RBTree && hash.instance_of?(MultiRBTree)
      raise TypeError, "can't convert MultiRBTree to RBTree"
    end
    tree = self.new
    begin
      hash.each { |k, v| tree[k] = v }
    rescue NoMethodError
      raise ArgumentError, "expected a Hash-like argument"
    end
    return tree
  end
  
  if key_values.length % 2 == 1
    raise ArgumentError, 'odd number of arguments for RBTree'
  end
  
  tree = self.new
  0.upto(key_values.length / 2 - 1) do |i|
    tree[key_values[i * 2]] = key_values[i * 2 + 1]
  end
  tree
end

Instance Method Details

#==(other) ⇒ Object

See Hash#==



241
242
243
244
245
246
247
248
249
250
 
# File 'lib/rbtree/rb_tree.rb', line 241

def ==(other)
  return false unless other.kind_of?(RBTree)
  return false unless other.size == self.size
  return false unless other.cmp_proc == @cmp_proc
  
  ary = self.to_a
  other_ary = other.to_a
  ary.each_with_index { |v, i| return false unless other_ary[i] == v }
  true
end

#[](key) ⇒ Object

See Hash#[]



212
213
214
215
 
# File 'lib/rbtree/rb_tree.rb', line 212

def [](key)
  node = tree.search key
  node ? node.value : default(key)
end

#[]=(key, value) ⇒ Object

See Hash#[]=

Raises:

  • (TypeError) 


218
219
220
221
222
223
 
# File 'lib/rbtree/rb_tree.rb', line 218

def []=(key, value)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0

  key = key.clone.freeze if key.kind_of? String
  @tree.insert(@tree.node(key, value)).value = value
end

#bound(lower_key, upper_key = nil) ⇒ Object 



94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/rbtree/rb_tree.rb', line 94

def bound(lower_key, upper_key = nil)
  result = []
  bound_nodes lower_key, upper_key do |node|
    if block_given?
      yield node.key, node.value
    else
      result << node.to_a
    end
  end
  block_given? ? self : result
end

#bound_nodes(lower_key, upper_key = nil) ⇒ Object

Internal version of bound that yields the corresponding nodes.



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/rbtree/rb_tree.rb', line 107

def bound_nodes(lower_key, upper_key = nil)
  upper_key ||= lower_key
  node = @tree.lower_bound(lower_key)
  return block_given? ? self : [] if node.nil?

  lock_changes do
    if @cmp_proc
      # Slow path
      until node.nil? || @cmp_proc.call(upper_key, node.key) < 0
        yield node
        node = @tree.successor node
      end
    else
      # Fast path.
      until node.nil? || upper_key < node.key
        yield node
        node = @tree.successor node
      end
    end
  end
end

#clear ⇒ Object

See Hash#clear



236
237
238
 
# File 'lib/rbtree/rb_tree.rb', line 236

def clear
  @tree = RBTree::Tree.new
end

#default(key = nil) ⇒ Object

The value returned when trying to read keys that don’t exist in the tree.



9
10
11
 
# File 'lib/rbtree/rb_tree.rb', line 9

def default(key = nil)
  @default_proc ? @default_proc.call(tree, key) : @default
end

#default=(new_default) ⇒ Object

The value returned when trying to read keys that don’t exist in the tree.



14
15
16
17
 
# File 'lib/rbtree/rb_tree.rb', line 14

def default=(new_default)
  @default_proc = nil
  @default = new_default
end

#delete(key) ⇒ Object

See Hash#delete



305
306
307
308
309
310
311
312
 
# File 'lib/rbtree/rb_tree.rb', line 305

def delete(key)
  node = @tree.search key
  unless node
    return block_given? ? yield : nil
  end
  @tree.delete node
  node.value
end

#delete_if(&block) ⇒ Object

See Hash#delete_if



315
316
317
318
 
# File 'lib/rbtree/rb_tree.rb', line 315

def delete_if(&block)
  reject!(&block)
  self
end

#each ⇒ Object Also known as: each_pair

See Hash#each



253
254
255
256
257
258
259
260
261
 
# File 'lib/rbtree/rb_tree.rb', line 253

def each
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.key, node.value }
    end
  else
    Enumerator.new self, :each
  end
end

#each_key ⇒ Object

See Hash#each_key.



346
347
348
349
350
351
352
353
354
 
# File 'lib/rbtree/rb_tree.rb', line 346

def each_key
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.key }
    end
  else
    Enumerator.new self, :each_key
  end
end

#each_value ⇒ Object

See Hash#each_value.



357
358
359
360
361
362
363
364
365
 
# File 'lib/rbtree/rb_tree.rb', line 357

def each_value
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.value }
    end
  else
    Enumerator.new self, :each_value
  end
end

#empty? ⇒ Boolean

See Hash#empty

Returns:

  • (Boolean) 


231
232
233
 
# File 'lib/rbtree/rb_tree.rb', line 231

def empty?
  @tree.empty?
end

#fetch(key, *default) ⇒ Object

See Hash#fetch



283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
 
# File 'lib/rbtree/rb_tree.rb', line 283

def fetch(key, *default)
  if default.length > 1
    raise ArgumentError, "expected at most 1 default, got #{default.length}"
  end
  if default.length == 1 && block_given?
    $stderr << "warning: block supersedes default value argument"
  end
  
  node = tree.search key
  return node.value if node
  if block_given?
    yield key
  else
    if default.length == 1
      default.first
    else
      raise IndexError, 'key not found'
    end
  end
end

#first ⇒ Object

The [key, value] for the smallest key in the tree.



183
184
185
186
 
# File 'lib/rbtree/rb_tree.rb', line 183

def first
  node = @tree.minimum
  node.nil? ? default : node.to_a
end

#has_key?(key) ⇒ Boolean

See Hash#has_key?

Returns:

  • (Boolean) 


382
383
384
 
# File 'lib/rbtree/rb_tree.rb', line 382

def has_key?(key)
  !!@tree.search(key)
end

#has_value?(value) ⇒ Boolean

See Hash#has_value?

Returns:

  • (Boolean) 


387
388
389
390
391
392
 
# File 'lib/rbtree/rb_tree.rb', line 387

def has_value?(value)
  lock_changes do
    each_value { |v| return true if value == v }
  end
  false
end

#index(value) ⇒ Object

See Hash#index



277
278
279
280
 
# File 'lib/rbtree/rb_tree.rb', line 277

def index(value)
  each { |k, v| return k if value == v }
  nil
end

#initialize_copy(source) ⇒ Object 



40
41
42
43
44
 
# File 'lib/rbtree/rb_tree.rb', line 40

def initialize_copy(source)
  super
  @tree = source.tree.dup
  @lock_count = 0
end

#inspect ⇒ Object

:nodoc:



458
459
460
461
462
463
464
465
466
 
# File 'lib/rbtree/rb_tree.rb', line 458

def inspect
  contents = map { |k, v|
    k_inspect = k.equal?(self) ? '#<RBTree: ...>' : k.inspect
    v_inspect = v.equal?(self) ? '#<RBTree: ...>' : v.inspect
    "#{k_inspect}=>#{v_inspect}"
  }.join(', ')
  default_inspect = default.equal?(self) ? '#<RBTree: ...>' : default.inspect
  "#<RBTree: {#{contents}}, default=#{default_inspect}, cmp_proc=#{@cmp_proc.inspect}>"
end

#invert ⇒ Object

See Hash#invert



395
396
397
398
399
 
# File 'lib/rbtree/rb_tree.rb', line 395

def invert
  tree = self.class.new
  each { |key, value| tree[value] = key }
  tree
end

#keys ⇒ Object

See Hash#keys.



368
369
370
371
372
 
# File 'lib/rbtree/rb_tree.rb', line 368

def keys
  result = Array.new
  each_key { |key| result << key }
  result
end

#last ⇒ Object

The [key, value] for the largest key in the tree.



189
190
191
192
 
# File 'lib/rbtree/rb_tree.rb', line 189

def last
  node = @tree.maximum
  node.nil? ? default : node.to_a
end

#lower_bound(key) ⇒ Object 



86
87
88
 
# File 'lib/rbtree/rb_tree.rb', line 86

def lower_bound(key)
  @tree.lower_bound(key).to_a
end

#merge(other) ⇒ Object

See Hash#merge



428
429
430
431
432
 
# File 'lib/rbtree/rb_tree.rb', line 428

def merge(other)
  copy = self.dup
  copy.merge! other
  copy
end

#merge!(other) ⇒ Object Also known as: update

See Hash#merge!



407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
 
# File 'lib/rbtree/rb_tree.rb', line 407

def merge!(other)
  unless other.instance_of? RBTree
    raise TypeError, "wrong argument type #{other.class} (expected RBTree)"
  end
  
  if block_given?
    other.each do |key, value|
      if node = @tree.search(key)
        node.value = yield key, node.value, value
      else
        self[key] = value
      end
    end
  else
    other.each { |key, value| self[key] = value }
  end
  self
end

#pop ⇒ Object

Removes the largest key in the tree.



195
196
197
198
199
 
# File 'lib/rbtree/rb_tree.rb', line 195

def pop
  return default if (node = @tree.maximum).nil? 
  @tree.delete node
  node.to_a
end

#pretty_print(q) ⇒ Object 



468
469
470
471
472
473
474
475
476
477
478
479
480
 
# File 'lib/rbtree/rb_tree.rb', line 468

def pretty_print(q)
  q.group(1, '#<RBTree: ', '>') do
    q.pp_hash self
    q.text ','
    q.breakable ' '
    q.text 'default='
    q.pp default
    q.text ','
    q.breakable ' '
    q.text 'cmp_proc='
    q.pp cmp_proc
  end
end

#pretty_print_cycle(q) ⇒ Object 



482
483
484
 
# File 'lib/rbtree/rb_tree.rb', line 482

def pretty_print_cycle(q)
  q.text '"#<RBTree: ...>"'
end

#readjust(*proc_arg, &new_cmp_proc) ⇒ Object

Raises:

  • (TypeError) 


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
 
# File 'lib/rbtree/rb_tree.rb', line 133

def readjust(*proc_arg, &new_cmp_proc)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  
  if new_cmp_proc
    cmp_proc = new_cmp_proc
    unless proc_arg.empty?
      raise ArgumentError, "expected 0 arguments when given a block"
    end
  else
    unless proc_arg.length <= 1
      raise ArgumentError, "expected 1 arguments (given #{proc_arg.length})"        
    end
    unless proc_arg.first.respond_to?(:call) || proc_arg.first.nil?
      raise TypeError, "expected a proc argument"
    end
    cmp_proc = proc_arg.first
  end
  
  lock_changes do
    if cmp_proc
      new_tree = RBTree::TreeCmp.new(&cmp_proc)
    else
      new_tree = RBTree::Tree.new
    end
    
    @tree.inorder do |node|
      new_tree.insert new_tree.node(node.key, node.value)
    end
    @tree = new_tree
    @cmp_proc = cmp_proc
  end
end

#reject(&block) ⇒ Object

See Hash#reject



337
338
339
340
341
342
343
 
# File 'lib/rbtree/rb_tree.rb', line 337

def reject(&block)
  copy = self.dup
  copy.reject!(&block)
  # NOTE: the correct answer should be "copy", but we're copying RBTree
  #       bug-for-bug
  # copy
end

#reject! ⇒ Object

See Hash#reject!



321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/rbtree/rb_tree.rb', line 321

def reject!
  if block_given?
    dead_nodes = []
    lock_changes do
      @tree.inorder do |node|
        dead_nodes << node if yield node.key, node.value
      end
    end
    dead_nodes.each { |node| @tree.delete node }
    dead_nodes.empty? ? nil : self
  else
    Enumerator.new self, :each
  end
end

#replace(other) ⇒ Object

Raises:

  • (TypeError) 


166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/rbtree/rb_tree.rb', line 166

def replace(other)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  unless other.instance_of? RBTree
    raise TypeError, "expected RBTree, got #{other.class}"
  end
  
  @tree = other.tree.dup
  @default_proc = other.default_proc
  @default = other.default
  @cmp_proc = other.cmp_proc
  self
end

#reverse_each ⇒ Object

See Hash#reverse_each



265
266
267
268
269
270
271
272
273
 
# File 'lib/rbtree/rb_tree.rb', line 265

def reverse_each
  if block_given?
    lock_changes do
      @tree.reverse_inorder { |node| yield node.key, node.value }
    end
  else
    Enumerator.new self, :reverse_each
  end
end

#shift ⇒ Object

Removes the smallest key in the tree.



202
203
204
205
206
 
# File 'lib/rbtree/rb_tree.rb', line 202

def shift
  return default if (node = @tree.minimum).nil? 
  @tree.delete node
  node.to_a
end

#size ⇒ Object

See Hash#size



226
227
228
 
# File 'lib/rbtree/rb_tree.rb', line 226

def size
  @tree.size
end

#to_hash ⇒ Object

A new Hash with the same contents and defaults as this RBTree instance.



440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
 
# File 'lib/rbtree/rb_tree.rb', line 440

def to_hash
  if @default_proc && !Hash.method_defined?(:default_proc=)
    # Slow path for default block and Ruby 1.8.7
    hash = Hash.new &@default_proc
    each { |key, value| hash[key] = value }
    return hash
  end

  hash = Hash[to_a]
  if @default_proc
    hash.default_proc = @default_proc if hash.respond_to? :default_proc=
  else
    hash.default = @default
  end
  hash
end

#to_rbtree ⇒ Object 



129
130
131
 
# File 'lib/rbtree/rb_tree.rb', line 129

def to_rbtree
  self
end

#to_s ⇒ Object

:nodoc:



435
436
437
 
# File 'lib/rbtree/rb_tree.rb', line 435

def to_s
  to_a.to_s
end

#upper_bound(key) ⇒ Object 



90
91
92
 
# File 'lib/rbtree/rb_tree.rb', line 90

def upper_bound(key)
  @tree.upper_bound(key).to_a
end

#values ⇒ Object

See Hash#values.



375
376
377
378
379
 
# File 'lib/rbtree/rb_tree.rb', line 375

def values
  result = Array.new
  each_value { |value| result << value }
  result
end

#values_at(*keys) ⇒ Object

See Hash#values_at



402
403
404
 
# File 'lib/rbtree/rb_tree.rb', line 402

def values_at(*keys)
  keys.map { |key| self[key] }
end