Class: MultiRBTree

Inherits:
RBTree show all
Defined in:
lib/rbtree/multi_rb_tree.rb,
lib/rbtree/multi_rb_tree.rb,
lib/rbtree/multi_rb_tree.rb

Overview

:nodoc: hash behavior

Instance Attribute Summary collapse

Attributes inherited from RBTree

#cmp_proc, #default_proc, #tree

Instance Method Summary collapse

Methods inherited from RBTree

#==, [], #bound_nodes, #default, #default=, #delete_if, #has_key?, #has_value?, #initialize_copy, #invert, #keys, #readjust, #to_s, #values, #values_at

Constructor Details

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

Returns a new instance of MultiRBTree.



3
4
5
6
 
# File 'lib/rbtree/multi_rb_tree.rb', line 3

def initialize(default = nil, &default_proc)
  super(default, &default_proc)
  @size = 0
end

Instance Attribute Details

#size ⇒ Object (readonly)

See Hash#size



109
110
111
 
# File 'lib/rbtree/multi_rb_tree.rb', line 109

def size
  @size
end

Instance Method Details

#[](key) ⇒ Object

See Hash#[]



93
94
95
96
 
# File 'lib/rbtree/multi_rb_tree.rb', line 93

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

#[]=(key, value) ⇒ Object

See Hash#[]=

Raises:

  • (TypeError) 


99
100
101
102
103
104
105
106
 
# File 'lib/rbtree/multi_rb_tree.rb', line 99

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
  @size += 1
  value
end

#bound(lower_key, upper_key = nil) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/rbtree/multi_rb_tree.rb', line 18

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

#clear ⇒ Object

See Hash#clear



117
118
119
120
 
# File 'lib/rbtree/multi_rb_tree.rb', line 117

def clear
  super
  @size = 0
end

#delete(key) ⇒ Object

See Hash#delete



178
179
180
181
182
183
184
185
186
187
 
# File 'lib/rbtree/multi_rb_tree.rb', line 178

def delete(key)
  node = @tree.search key
  unless node
    return block_given? ? yield : nil
  end
  value = node.value.shift
  @tree.delete node if node.value.empty?
  @size -= 1
  value
end

#each ⇒ Object Also known as: each_pair

See Hash#each



123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/rbtree/multi_rb_tree.rb', line 123

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

#each_key ⇒ Object

See Hash#each_key.



219
220
221
222
223
224
225
226
227
 
# File 'lib/rbtree/multi_rb_tree.rb', line 219

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

#each_value ⇒ Object

See Hash#each_value.



231
232
233
234
235
236
237
238
239
 
# File 'lib/rbtree/multi_rb_tree.rb', line 231

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

#empty? ⇒ Boolean

See Hash#empty

Returns:

  • (Boolean) 


112
113
114
 
# File 'lib/rbtree/multi_rb_tree.rb', line 112

def empty?
  @tree.empty?
end

#fetch(key, *default) ⇒ Object

See Hash#fetch



156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
# File 'lib/rbtree/multi_rb_tree.rb', line 156

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.first 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.



60
61
62
63
 
# File 'lib/rbtree/multi_rb_tree.rb', line 60

def first
  node = @tree.minimum
  node.nil? ? default : [node.key, node.value.first]
end

#index(value) ⇒ Object

See Hash#index



150
151
152
153
 
# File 'lib/rbtree/multi_rb_tree.rb', line 150

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

#inspect ⇒ Object

:nodoc:



275
276
277
278
279
280
281
282
283
 
# File 'lib/rbtree/multi_rb_tree.rb', line 275

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
  "#<MultiRBTree: {#{contents}}, default=#{default_inspect}, cmp_proc=#{@cmp_proc.inspect}>"
end

#last ⇒ Object

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



66
67
68
69
 
# File 'lib/rbtree/multi_rb_tree.rb', line 66

def last
  node = @tree.maximum
  node.nil? ? default : [node.key, node.value.last]
end

#lower_bound(key) ⇒ Object 



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

def lower_bound(key)
  node = @tree.lower_bound(key)
  [node.key, node.value.first]
end

#merge(other) ⇒ Object

See Hash#merge



263
264
265
266
267
 
# File 'lib/rbtree/multi_rb_tree.rb', line 263

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

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

See Hash#merge!



242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'lib/rbtree/multi_rb_tree.rb', line 242

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)
        self[key] = yield key, node.value.first, 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.



72
73
74
75
76
77
78
 
# File 'lib/rbtree/multi_rb_tree.rb', line 72

def pop
  return default if (node = @tree.maximum).nil? 
  value = node.value.pop
  @tree.delete node if node.value.empty?
  @size -= 1
  [node.key, value]
end

#pretty_print(q) ⇒ Object

:nodoc: custom pp output



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

def pretty_print(q)
  q.group(1, "#<#{self.class.name}: ", '>') do
    q.group(1, '{', '}') do
      first = true
      each do |key, value|
        if first
          first = false
        else
          q.text ','
          q.breakable ' '
        end
        q.pp key
        q.text '=>'
        q.pp value
      end
    end
    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

:nodoc: custom pp output



314
315
316
 
# File 'lib/rbtree/multi_rb_tree.rb', line 314

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

#reject(&block) ⇒ Object

See Hash#reject



210
211
212
213
214
215
216
 
# File 'lib/rbtree/multi_rb_tree.rb', line 210

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!



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
# File 'lib/rbtree/multi_rb_tree.rb', line 190

def reject!
  if block_given?
    dead_nodes = []
    lock_changes do
      @tree.inorder do |node|
        node.value.reject! do |value|
          @size -= 1 if result = yield(node.key, value)
          result
        end
        dead_nodes << node if node.value.empty?
      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) 


34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/rbtree/multi_rb_tree.rb', line 34

def replace(other)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  unless other.kind_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
  @size = other.size
  
  unless other.instance_of? MultiRBTree
    # Wrap values in arrays to convert RBTree -> MultiRBTree.
    @tree.inorder do |node|
      node.value = [node.value]
    end
  end
  
  self
end

#reverse_each ⇒ Object

See Hash#reverse_each



137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/rbtree/multi_rb_tree.rb', line 137

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

#shift ⇒ Object

Removes the smallest key in the tree.



81
82
83
84
85
86
87
 
# File 'lib/rbtree/multi_rb_tree.rb', line 81

def shift
  return default if (node = @tree.minimum).nil? 
  value = node.value.shift
  @tree.delete node if node.value.empty?
  @size -= 1
  [node.key, value]
end

#to_hash ⇒ Object

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

Raises:

  • (TypeError) 


270
271
272
 
# File 'lib/rbtree/multi_rb_tree.rb', line 270

def to_hash
  raise TypeError, "can't convert MultiRBTree to Hash"
end

#to_rbtree ⇒ Object 



30
31
32
 
# File 'lib/rbtree/multi_rb_tree.rb', line 30

def to_rbtree
  self
end

#upper_bound(key) ⇒ Object 



13
14
15
16
 
# File 'lib/rbtree/multi_rb_tree.rb', line 13

def upper_bound(key)
  node = @tree.lower_bound(key)
  [node.key, node.value.last]
end