Ruby Symbol Table implementation using Binary Search

Question

I'm currently going over Robert Sedgewick's Algorithms book. I implemented a Symbol Table using two parallel array one for keys and one for values. The keys array is ordered and the Symbol Table uses binary search to find the position of the elements in the array.

In the practice section, the implementation of the delete and floor method were left as exercises. Here are the directions for delete and floor:

I would like to see if there is any feedback in the implementation of those elements. Specially floor. Here is the code:

# Binary Search Symbol Table in Ruby
class BinarySearchST
  attr_accessor :n, :keys, :vals

  def initialize
    @n = 0
    @keys = []
    @vals = []
  end

  def size
    @n
  end

  def is_empty?
    @n.zero?
  end

  def get(key)
    return nil if is_empty?

    i = rank(key)
    if i < @n && @keys[i] == key
      @vals[i]
    else
      nil
    end
  end

  def rank(key)
    lo = 0
    hi = @n - 1

    while lo <= hi
      mid = lo + (hi - lo) / 2
      cmp = (key <=> @keys[mid])
      if cmp < 0
        hi = mid - 1
      elsif cmp > 0
        lo = mid + 1
      else
        return mid
      end
    end
    lo
  end

  def put(key, val)
    #  Search for key. Update value if found; grow table if new
    i = rank(key)
    if i < @n && @keys[i] == key
      return @vals[i] = val
    end

    j = @n
    while j > i
      @keys[j] = @keys[j - 1]
      @vals[j] = @vals[j - 1]

      j -= 1
    end

    @keys[i] = key
    @vals[i] = val
    @n += 1
  end

  def min
    @keys[0]
  end

  def max
    @keys[-1]
  end

  def select(k)
    @keys[k]
  end

  def ceiling(key)
    i = rank(key)
    @keys[i]
  end

  def floor(key)
   raise 'ilegalArgumentException' if key == nil
   raise 'NoSuchElementException' if @keys.empty?

    i = rank(key)
    if keys[i] == key || i == 0
      keys[i]
    else
      keys[i - 1]
    end
  end

  def delete(key)
    raise 'ilegalArgumentException' if key.nil?

    i = rank(key)
    @keys.delete_at(i)
    @vals.delete_at(i)
  end
end


bst = BinarySearchST.new

bst.put('s', 0)
bst.put('e', 1)
bst.put('a', 2)
bst.put('r', 3)
bst.put('c', 4)
bst.put('h', 5)
bst.put('e', 6)
bst.put('x', 7)
bst.put('a', 8)
bst.put('m', 9)
bst.put('p', 10)
bst.put('l', 11)
bst.put('e', 12)

binding.pry
p bst.get('e')

Answer 1

It's a good implementation, I can make the following improvement suggestions:

• size/n aliasing: either add a comment explaining its purpose (a legitimate one could be the need to comply with some external interface), or pick one name and use it throughout the class.
• rank(key) < @n checks: change rank to return nil when the key is not found. This is a common Ruby idiom. In Ruby 0 is truthy unlike many other languages.
• @keys[i] == key: This check may be better off in a separate method, i.e. instead of a single rank method have one method that returns the rank when finding and one that returns the place for insertion.
• Exception raises: the idiomatic Ruby way is to define needed exception classes (you could nest them in the BinarySearchST class) rather than raising strings.
• Further on exception raises, it is a good practice to provide a descriptive message when raising each exception.
• It's understandable if you want to move array elements yourself, but Ruby standard library does provide the Array#insert method which would do that for you.