1
\$\begingroup\$

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: enter image description here enter image description here

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')
\$\endgroup\$
3
  • \$\begingroup\$ raise 'NoSuchElementException' if @keys.empty? what about the case that the key does not exist? \$\endgroup\$ Oct 22, 2020 at 22:36
  • \$\begingroup\$ it always gives the floor by the keys[i - 1]. i will always return a index position in the array, if no key is there it will return keys[i - 1] which would be the floor \$\endgroup\$ Oct 22, 2020 at 23:21
  • \$\begingroup\$ if you for example pass f to floor it would return e \$\endgroup\$ Oct 22, 2020 at 23:22

1 Answer 1

1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.