Class: TreeMap::BoundedMap

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

Overview

A map with optional limits on its range. This is intended to be used only by the TreeMap class.

Defined Under Namespace

Classes: BoundedNodeIterator

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(treemap, ascending, from, from_bound, to, to_bound) ⇒ BoundedMap

Returns a new instance of BoundedMap.



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/tree_map/bounded_map.rb', line 15

def initialize(treemap, ascending, from, from_bound, to, to_bound)
  @treemap = treemap
  @ascending = ascending
  @from = from
  @from_bound = from_bound
  @to = to
  @to_bound = to_bound

  # Validate the bounds. In addition to checking that from <= to, we verify that the comparator supports our bound objects.
  if from_bound != Bound::NO_BOUND && to_bound != Bound::NO_BOUND
    raise "Invalid from and to arguments: #{from} (from) > #{to} (to)" if comparator.call(from, to) > 0
  elsif from_bound != Bound::NO_BOUND
    comparator.call(from, from)
  elsif to_bound != Bound::NO_BOUND
    comparator.call(to, to)
  end
end

Instance Attribute Details

#ascending ⇒ Object

Returns the value of attribute ascending.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def ascending
  @ascending
end

#from ⇒ Object

Returns the value of attribute from.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def from
  @from
end

#from_bound ⇒ Object

Returns the value of attribute from_bound.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def from_bound
  @from_bound
end

#to ⇒ Object

Returns the value of attribute to.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def to
  @to
end

#to_bound ⇒ Object

Returns the value of attribute to_bound.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def to_bound
  @to_bound
end

#treemap ⇒ Object

Returns the value of attribute treemap.



13
14
15
 
# File 'lib/tree_map/bounded_map.rb', line 13

def treemap
  @treemap
end

Instance Method Details

#bound(node, from_bound, to_bound) ⇒ Object

Returns the entry if it is in bounds, or null if it is out of bounds.



78
79
80
 
# File 'lib/tree_map/bounded_map.rb', line 78

def bound(node, from_bound, to_bound)
  node if node && in_closed_bounds?(node.key, from_bound, to_bound)
end

#bounded_sub_map(from, from_bound, to, to_bound) ⇒ Object 



275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
 
# File 'lib/tree_map/bounded_map.rb', line 275

def bounded_sub_map(from, from_bound, to, to_bound)
  if !@ascending
    from, to = to, from
    from_bound, to_bound = to_bound, from_bound
  end

  # If both the current and requested bounds are exclusive, the isInBounds check must be
  # inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds.
  if from_bound == Bound::NO_BOUND
    from = @from
    from_bound = @from_bound
  else
    from_bound_to_check = from_bound == @from_bound ? Bound::INCLUSIVE : @from_bound
    raise out_of_bounds(to, from_bound_to_check, @to_bound) if !in_closed_bounds?(from, from_bound_to_check, @to_bound)
  end
  if to_bound == Bound::NO_BOUND
    to = @to
    to_bound = @to_bound
  else
    to_bound_to_check = to_bound == @to_bound ? Bound::INCLUSIVE : @to_bound
    raise out_of_bounds(to, @from_bound, to_bound_to_check) if !in_closed_bounds?(to, @from_bound, to_bound_to_check)
  end
  BoundedMap.new(@treemap, ascending, from, from_bound, to, to_bound)
end

#ceiling_entry(key) ⇒ Object 



212
213
214
 
# File 'lib/tree_map/bounded_map.rb', line 212

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

#ceiling_key(key) ⇒ Object 



216
217
218
219
 
# File 'lib/tree_map/bounded_map.rb', line 216

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

#comparator ⇒ Object 



230
231
232
233
234
235
236
 
# File 'lib/tree_map/bounded_map.rb', line 230

def comparator
  if @ascending
    @treemap.comparator
  else
    ->(this, that) { -@treemap.comparator.call(this, that) }
  end
end

#contains_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/tree_map/bounded_map.rb', line 41

def contains_key?(key)
  in_bounds?(key) && @treemap.contains_key?(key)
end

#descending_map ⇒ Object 



254
255
256
 
# File 'lib/tree_map/bounded_map.rb', line 254

def descending_map
  BoundedMap.new(@treemap, !@ascending, @from, @from_bound, @to, @to_bound)
end

#each(&blk) ⇒ Object

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



359
360
361
362
363
364
365
 
# File 'lib/tree_map/bounded_map.rb', line 359

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::BoundedMap.nodenode.value”}



368
369
370
371
372
373
374
375
376
377
 
# File 'lib/tree_map/bounded_map.rb', line 368

def each_node
  if block_given?
    iter = BoundedNodeIterator.new(self, endpoint(true))
    while iter.has_next?
      yield iter.step_forward()
    end
  else
    enum_for(:each_node)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
 
# File 'lib/tree_map/bounded_map.rb', line 33

def empty?
  endpoint(true).nil?
end

#endpoint(first) ⇒ Object

<first> - true for the first element, false for the last



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

def endpoint(first)
  node, from, to = if @ascending == first
    node = case @from_bound
    when Bound::NO_BOUND
      @treemap.root.first if @treemap.root
    when Bound::INCLUSIVE
      @treemap.find(@from, Relation::CEILING)
    when Bound::EXCLUSIVE
      @treemap.find(@from, Relation::HIGHER)
    else
      raise "Undefined bound."
    end
    [node, Bound::NO_BOUND, @to_bound]
  else
    node = case @to_bound
    when Bound::NO_BOUND
      @treemap.root.last if @treemap.root
    when Bound::INCLUSIVE
      @treemap.find(@to, Relation::FLOOR)
    when Bound::EXCLUSIVE
      @treemap.find(@to, Relation::LOWER)
    else
      raise "Undefined bound."
    end
    [node, @from_bound, Bound::NO_BOUND]
  end
  bound(node, from, to)
end

#entry_set ⇒ Object

View factory methods



240
241
242
 
# File 'lib/tree_map/bounded_map.rb', line 240

def entry_set
  Set.new(each_node.to_a)
end

#find_bounded(key, relation) ⇒ Object

Performs a find on the underlying tree after constraining it to the bounds of this view. Examples:

bound is (A..C)
find_bounded(B, FLOOR) stays source.find(B, FLOOR)

bound is (A..C)
find_bounded(C, FLOOR) becomes source.find(C, LOWER)

bound is (A..C)
find_bounded(D, LOWER) becomes source.find(C, LOWER)

bound is (A..C]
find_bounded(D, FLOOR) becomes source.find(C, FLOOR)

bound is (A..C]
find_bounded(D, LOWER) becomes source.find(C, FLOOR)



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

def find_bounded(key, relation)
  relation = Relation.for_order(relation, @ascending)
  from_bound_for_check = @from_bound
  to_bound_for_check = @to_bound
  if @to_bound != Bound::NO_BOUND && (relation == Relation::LOWER || relation == Relation::FLOOR)
    comparison = comparator.call(@to, key)
    if comparison <= 0
      key = @to
      if @to_bound == Bound::EXCLUSIVE
        relation = Relation::LOWER # 'to' is too high
      elsif comparison < 0
        relation = Relation::FLOOR # we already went lower
      end
    end
    to_bound_for_check = Bound::NO_BOUND # we've already checked the upper bound
  end
  if @from_bound != Bound::NO_BOUND && (relation == Relation::CEILING || relation == Relation::HIGHER)
    comparison = comparator.call(@from, key)
    if comparison >= 0
      key = @from
      if @from_bound == Bound::EXCLUSIVE
        relation = Relation::HIGHER # 'from' is too low
      elsif comparison > 0
        relation = Relation::CEILING # we already went higher
      end
    end
    from_bound_for_check = Bound::NO_BOUND # we've already checked the lower bound
  end
  bound(@treemap.find(key, relation), from_bound_for_check, to_bound_for_check)
end

#first_entry ⇒ Object

Navigable methods



84
85
86
 
# File 'lib/tree_map/bounded_map.rb', line 84

def first_entry
  endpoint(true)
end

#first_key ⇒ Object 



94
95
96
97
98
 
# File 'lib/tree_map/bounded_map.rb', line 94

def first_key
  entry = endpoint(true)
  raise "No such element" unless entry
  entry.key
end

#floor_entry(key) ⇒ Object 



203
204
205
 
# File 'lib/tree_map/bounded_map.rb', line 203

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

#floor_key(key) ⇒ Object 



207
208
209
210
 
# File 'lib/tree_map/bounded_map.rb', line 207

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

#get(key) ⇒ Object 



37
38
39
 
# File 'lib/tree_map/bounded_map.rb', line 37

def get(key)
  @treemap.get(key) if in_bounds?(key)
end

#head_map(*args) ⇒ Object

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



304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/tree_map/bounded_map.rb', line 304

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

#higher_entry(key) ⇒ Object 



221
222
223
 
# File 'lib/tree_map/bounded_map.rb', line 221

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

#higher_key(key) ⇒ Object 



225
226
227
228
 
# File 'lib/tree_map/bounded_map.rb', line 225

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

#in_bounds?(key) ⇒ Boolean

Returns true if the key is in bounds. Note: The reference implementation calls this function isInBounds

Returns:

  • (Boolean) 


56
57
58
 
# File 'lib/tree_map/bounded_map.rb', line 56

def in_bounds?(key)
  in_closed_bounds?(key, @from_bound, @to_bound)
end

#in_closed_bounds?(key, from_bound, to_bound) ⇒ Boolean

Returns true if the key is in bounds. Use this overload with NO_BOUND to skip bounds checking on either end. Note: The reference implementation calls this function isInBounds

Returns:

  • (Boolean) 


63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/tree_map/bounded_map.rb', line 63

def in_closed_bounds?(key, from_bound, to_bound)
  if from_bound == Bound::INCLUSIVE
    return false if comparator.call(key, from) < 0      # less than from
  elsif from_bound == Bound::EXCLUSIVE
    return false if comparator.call(key, from) <= 0     # less than or equal to from
  end
  if to_bound == Bound::INCLUSIVE
    return false if comparator.call(key, to) > 0        # greater than 'to'
  elsif to_bound == Bound::EXCLUSIVE
    return false if comparator.call(key, to) >= 0       # greater than or equal to 'to'
  end
  true
end

#key_set ⇒ Object Also known as: keys 



244
245
246
 
# File 'lib/tree_map/bounded_map.rb', line 244

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

#last_entry ⇒ Object 



100
101
102
 
# File 'lib/tree_map/bounded_map.rb', line 100

def last_entry
  endpoint(false)
end

#last_key ⇒ Object 



110
111
112
113
114
 
# File 'lib/tree_map/bounded_map.rb', line 110

def last_key
  entry = endpoint(false)
  raise "No such element" unless entry
  entry.key
end

#lower_entry(key) ⇒ Object 



194
195
196
 
# File 'lib/tree_map/bounded_map.rb', line 194

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

#lower_key(key) ⇒ Object 



198
199
200
201
 
# File 'lib/tree_map/bounded_map.rb', line 198

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

#out_of_bounds(value, from_bound, to_bound) ⇒ Object 



332
333
334
 
# File 'lib/tree_map/bounded_map.rb', line 332

def out_of_bounds(value, from_bound, to_bound)
  Exception.new("#{value} not in range #{from_bound.left_cap(@from)}..#{to_bound.right_cap(@to)}")
end

#poll_first_entry ⇒ Object 



88
89
90
91
92
 
# File 'lib/tree_map/bounded_map.rb', line 88

def poll_first_entry
  result = endpoint(true)
  @treemap.remove_internal(result) if result
  result
end

#poll_last_entry ⇒ Object 



104
105
106
107
108
 
# File 'lib/tree_map/bounded_map.rb', line 104

def poll_last_entry
  result = endpoint(false)
  @treemap.remove_internal(result) if result
  result
end

#put(key, value) ⇒ Object 



45
46
47
48
 
# File 'lib/tree_map/bounded_map.rb', line 45

def put(key, value)
  raise "Key out of bounds." unless in_bounds?(key)
  put_internal(key, value)
end

#remove(key) ⇒ Object 



50
51
52
 
# File 'lib/tree_map/bounded_map.rb', line 50

def remove(key)
  @treemap.remove(key) if in_bounds?(key)
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)



262
263
264
265
266
267
268
269
270
271
272
273
 
# File 'lib/tree_map/bounded_map.rb', line 262

def sub_map(*args)
  case args.count
  when 2
    from_inclusive, to_exclusive = *args
    bounded_sub_map(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
    bounded_sub_map(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)



320
321
322
323
324
325
326
327
328
329
330
 
# File 'lib/tree_map/bounded_map.rb', line 320

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

#values ⇒ Object 



250
251
252
 
# File 'lib/tree_map/bounded_map.rb', line 250

def values
  each_node.map(&:value)
end