lib/treemap/tree_map.rb
# Returns the node at or adjacent to the given key, creating it if requested.
Returns the node at or adjacent to the given key, creating it if requested.
Returns the node at or adjacent to the given key creating it if requested .
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)
      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  
      end
      if comparison < 0     
        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                  
        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
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 ) 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 end if comparison < 0 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 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
Returns the node at or adjacent to the given key, creating it if requested.
Returns the node at or adjacent to the given key creating it if requested .
# we found the requested key # continue # We found a nearest node. Every key not in the tree has up to two nearest nodes, one lower and one higher. # nearest.key is higher # comparison > 0 ; nearest.key is lower
key
relation