class TreeMap::BoundedMap

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

Attributes

ascending[RW]
from[RW]
from_bound[RW]
to[RW]
to_bound[RW]
treemap[RW]

Public Class Methods

new(treemap, ascending, from, from_bound, to, to_bound) click to toggle source
# File lib/treemap/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

Public Instance Methods

bound(node, from_bound, to_bound) click to toggle source

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

# File lib/treemap/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) click to toggle source
# File lib/treemap/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) click to toggle source
# File lib/treemap/bounded_map.rb, line 212
def ceiling_entry(key)
  find_bounded(key, Relation::CEILING)
end
ceiling_key(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 216
def ceiling_key(key)
  entry = find_bounded(key, Relation::CEILING)
  entry.key if entry
end
comparator() click to toggle source
# File lib/treemap/bounded_map.rb, line 230
def comparator
  if @ascending
    @treemap.comparator
  else
    ->(this, that) { -@treemap.comparator.call(this, that) }
  end
end
contains_key?(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 41
def contains_key?(key)
  in_bounds?(key) && @treemap.contains_key?(key)
end
descending_map() click to toggle source
# File lib/treemap/bounded_map.rb, line 254
def descending_map
  BoundedMap.new(@treemap, !@ascending, @from, @from_bound, @to, @to_bound)
end
each(&blk) click to toggle source

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

# File lib/treemap/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() { |step_forward| ... } click to toggle source

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

# File lib/treemap/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?() click to toggle source
# File lib/treemap/bounded_map.rb, line 33
def empty?
  endpoint(true).nil?
end
endpoint(first) click to toggle source

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

# File lib/treemap/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() click to toggle source

View factory methods

# File lib/treemap/bounded_map.rb, line 240
def entry_set
  Set.new(each_node.to_a)
end
find_bounded(key, relation) click to toggle source

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)
# File lib/treemap/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
      else 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
      else 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() click to toggle source

Navigable methods

# File lib/treemap/bounded_map.rb, line 84
def first_entry
  endpoint(true)
end
first_key() click to toggle source
# File lib/treemap/bounded_map.rb, line 94
def first_key
  entry = endpoint(true)
  raise "No such element" unless entry
  entry.key
end
floor_entry(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 203
def floor_entry(key)
  find_bounded(key, Relation::FLOOR)
end
floor_key(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 207
def floor_key(key)
  entry = find_bounded(key, Relation::FLOOR)
  entry.key if entry
end
get(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 37
def get(key)
  @treemap.get(key) if in_bounds?(key)
end
head_map(*args) click to toggle source

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

# File lib/treemap/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) click to toggle source
# File lib/treemap/bounded_map.rb, line 221
def higher_entry(key)
  find_bounded(key, Relation::HIGHER)
end
higher_key(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 225
def higher_key(key)
  entry = find_bounded(key, Relation::HIGHER)
  entry.key if entry
end
in_bounds?(key) click to toggle source

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

# File lib/treemap/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) click to toggle source

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

# File lib/treemap/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() click to toggle source
# File lib/treemap/bounded_map.rb, line 244
def key_set
  Set.new(each_node.map(&:key))
end
Also aliased as: keys
keys()
Alias for: key_set
last_entry() click to toggle source
# File lib/treemap/bounded_map.rb, line 100
def last_entry
  endpoint(false)
end
last_key() click to toggle source
# File lib/treemap/bounded_map.rb, line 110
def last_key
  entry = endpoint(false)
  raise "No such element" unless entry
  entry.key
end
lower_entry(key) click to toggle source
# File lib/treemap/bounded_map.rb, line 194
def lower_entry(key)
  find_bounded(key, Relation::LOWER)
end
lower_key(key) click to toggle source
# File lib/treemap/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) click to toggle source
# File lib/treemap/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() click to toggle source
# File lib/treemap/bounded_map.rb, line 88
def poll_first_entry
  result = endpoint(true)
  @treemap.remove_internal(result) if result
  result
end
poll_last_entry() click to toggle source
# File lib/treemap/bounded_map.rb, line 104
def poll_last_entry
  result = endpoint(false)
  @treemap.remove_internal(result) if result
  result
end
put(key, value) click to toggle source
# File lib/treemap/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) click to toggle source
# File lib/treemap/bounded_map.rb, line 50
def remove(key)
  @treemap.remove(key) if in_bounds?(key)
end
sub_map(*args) click to toggle source

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

# File lib/treemap/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) click to toggle source

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

# File lib/treemap/bounded_map.rb, line 320
def tail_map(*args)
  case args.count
  when 1
    from_inclusive = args.first
    bounded_sub_map(fromInclusive, 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() click to toggle source
# File lib/treemap/bounded_map.rb, line 250
def values
  each_node.map(&:value)
end