3
\$\begingroup\$

For fun and to learn a bit, I decided to implement a bidirectional map in Ruby, relying on Ruby core libraries where possible.

Its behavior is intended to be that of a Ruby Hash, but one in which 'values' are also hashed as keys for quick reverse lookup. I've implemented nearly all the methods from Hash, except those I don't think make sense.

I put the beginner tag on my code, though I've been doing automated testing in Ruby for about a year.

I'm looking for feedback on performance and correctness in unanticipated cases. Feel free to browse through and if you find something to lock onto, great. I can use those lessons elsewhere. But I decided to put the whole ADT there as each method itself is pretty minimal.

require 'forwardable'

class Bihash
  include Enumerable
  extend Forwardable

  def initialize(*args, &block)
    raise_error_if_frozen
    if block_given? && !args.empty?
      raise ArgumentError, "wrong number of arguments (#{args.size} for 0)"
    elsif args.size > 1
      raise ArgumentError, "wrong number of arguments (#{args.size} for 0..1)"
    end
    super()
    @forward, @reverse = Hash.new, Hash.new
    @default, @default_proc = args[0], block
  end

  def self.[](*args)
    new_from_hash(Hash[*args])
  end

  def self.try_convert(arg)
    h = Hash.try_convert(arg)
    h ? new_from_hash(h) : nil
  end

  def [](key)
    if key?(key)
      @forward.key?(key) ? @forward[key] : @reverse[key]
    else
      default_value(key)
    end
  end

  def []=(key1, key2)
    raise_error_if_frozen
    delete(key1)
    delete(key2)
    @reverse[key2] = key1
    @forward[key1] = key2
  end
  alias :store :[]=

  def delete(key, &block)
    raise_error_if_frozen
    if @forward.key?(key)
      @reverse.delete(@forward[key])
      @forward.delete(key)
    elsif @reverse.key?(key)
      @forward.delete(@reverse[key])
      @reverse.delete(key)
    else
      @reverse.delete(key, &block)
    end
  end

  def each(&block)
    if block_given?
      @forward.each(&block)
      self
    else
      to_enum(:each)
    end
  end
  alias :each_pair :each

  def ==(rhs)
    rhs.is_a?(self.class) && rhs.send(:merged_hash_attrs) == merged_hash_attrs
  end
  alias :eql? :==

  def key?(arg)
    @forward.key?(arg) || @reverse.key?(arg)
  end
  alias :has_key? :key?
  alias :include? :key?
  alias :member? :key?

  def fetch(key)
    @forward.key?(key) ? @forward.fetch(key) : @reverse.fetch(key)
  end

  def clear
    raise_error_if_frozen
    @forward.clear
    @reverse.clear
    self
  end

  def rehash
    raise_error_if_frozen
    @forward.rehash
    @reverse.rehash
    self
  end

  def to_h
    @forward.dup
  end
  alias :to_hash :to_h

  def values_at(*keys)
    keys.map { |key| self[key] }
  end

  def shift
    raise_error_if_frozen
    if empty?
      default_value(nil)
    else
      @reverse.shift
      @forward.shift
    end
  end

  def assoc(key)
    @forward.assoc(key) || @reverse.assoc(key)
  end

  def to_s
    "Bihash[#{@forward.to_s[1..-2]}]"
  end
  alias :inspect :to_s

  def hash
    self.class.hash ^ merged_hash_attrs.hash
  end

  def select(&block)
    if block_given?
      dup.keep_if(&block)
    else
      to_enum(:select)
    end
  end

  def reject(&block)
    if block_given?
      dup.delete_if(&block)
    else
      to_enum(:reject)
    end
  end

  def default(*args)
    case args.count
    when 0
      @default
    when 1
      default_value(args[0])
    else
      raise ArgumentError, "wrong number of arguments (#{args.size} for 0..1)"
    end
  end

  def default=(default)
    raise_error_if_frozen
    @default_proc = nil
    @default = default
  end

  def default_proc
    @default_proc
  end

  def default_proc=(arg)
    raise_error_if_frozen
    if !arg.nil?
      if !arg.is_a?(Proc)
    raise TypeError, "wrong default_proc type #{arg.class} (expected Proc)"
      end
      if arg.lambda? && arg.arity != 2
    raise TypeError, "default_proc takes two arguments (2 for #{arg.arity})"
      end
    end
    @default = nil
    @default_proc = arg
  end

  def replace(other_bh)
    raise_error_if_frozen
    raise_error_unless_bihash(other_bh)
    @forward = other_bh.instance_variable_get(:@forward).dup
    @reverse = other_bh.instance_variable_get(:@reverse).dup
    self
  end

  def compare_by_identity
    raise_error_if_frozen
    @forward.compare_by_identity
    @reverse.compare_by_identity
    self
  end

  def delete_if(&block)
    if block_given?
      raise_error_if_frozen
      @forward.each { |k,v| delete(k) if block.call(k,v) }
      self
    else
      to_enum(:delete_if)
    end
  end

  def keep_if(&block)
    if block_given?
      raise_error_if_frozen
      @forward.each { |k,v| delete(k) if !block.call(k,v) }
      self
    else
      to_enum(:keep_if)
    end
  end

  def select!(&block)
    if block_given?
      raise_error_if_frozen
      old_size = size
      @forward.each { |k,v| delete(k) if !block.call(k,v) }
      old_size == size ? nil : self
    else
      to_enum(:select!)
    end
  end

  def reject!(&block)
    if block_given?
      raise_error_if_frozen
      old_size = size
      @forward.each { |k,v| delete(k) if block.call(k,v) }
      old_size == size ? nil : self
    else
      to_enum(:reject!)
    end
  end

  def merge!(other_bh)
    raise_error_if_frozen
    raise_error_unless_bihash(other_bh)
    other_bh.each { |k,v| store(k,v) }
    self
  end
  alias :update :merge!

  def merge(other_bh)
    dup.merge!(other_bh)
  end

  def_delegator :@forward, :empty?
  def_delegator :@forward, :length
  def_delegator :@forward, :size
  def_delegator :@forward, :flatten
  def_delegator :@forward, :compare_by_identity?

  def self.new_from_hash(h)
    if (h.keys | h.values).size + h.select { |k,v| k == v }.size < h.size * 2
      raise ArgumentError, 'A key would be duplicated outside its own pair'
    end
    bihash = new
    bihash.instance_variable_set(:@reverse, h.invert)
    bihash.instance_variable_set(:@forward, h)
    bihash
  end
  private_class_method :new_from_hash

  private

  def initialize_copy(source)
    super
    @forward, @reverse = @forward.dup, @reverse.dup
  end

  def raise_error_if_frozen
    raise "can't modify frozen Bihash" if frozen?
  end

  def raise_error_unless_bihash(obj)
    unless obj.is_a?(Bihash)
      raise TypeError, "wrong argument type #{obj.class} (expected Bihash)"
    end
  end

  def default_value(key)
    @default_proc ? @default_proc.call(self, key) : @default
  end

  def merged_hash_attrs
    @reverse.merge(@forward)
  end
end
\$\endgroup\$
  • \$\begingroup\$ Could you provide some client code showing you this would be used, and the expected correct output? \$\endgroup\$ – Jonah Nov 6 '15 at 19:50
  • \$\begingroup\$ @Jonah Here's a link to my specs. It should work just like the Ruby core class Hash, except that you can reverse lookup a key by value in O(1) time. For example, bh = Bihash[1 => :one, 2 => :two]; bh[1] == :one; bh[:one] == 1; \$\endgroup\$ – user88900 Nov 6 '15 at 21:48
  • \$\begingroup\$ Thanks, I get it now. At a glance your code looks fine to me. \$\endgroup\$ – Jonah Nov 6 '15 at 21:49
1
\$\begingroup\$

Your code looks good. I only found an edge case with rehash, missing functionality in fetch, and some minor fixes.

h ? new_from_hash(h) : nil

This can be written as:

h && new_from_hash(h)
def [](key)
  if key?(key)
    @forward.key?(key) ? @forward[key] : @reverse[key]
  else
    default_value(key)
  end
end

@forward.key? is called twice (once in #key?). The code can be rewritten to avoid this:

def [](key)
  if @forward.key?(key)
    @forward[key]
  elsif @reverse.key?(key)
    @reverse[key]
  else
    default_value(key)
  end
end
def delete(key, &block)
  raise_error_if_frozen
  if @forward.key?(key)
    @reverse.delete(@forward[key])
    @forward.delete(key)
  elsif @reverse.key?(key)
    @forward.delete(@reverse[key])
    @reverse.delete(key)
  else
    @reverse.delete(key, &block)
  end
end

You can remove the &block argument and change the else clause to:

yield(key) if block_given?
def fetch(key)
  @forward.key?(key) ? @forward.fetch(key) : @reverse.fetch(key)
end

You're not supporting passing a default value/block to fetch. Change to:

def fetch(key, *args, &block)
  (@forward.key?(key) ? @forward : @reverse).fetch(key, *args, &block)
end
def rehash
  raise_error_if_frozen
  @forward.rehash
  @reverse.rehash
  self
end

I found an edge case with rehash. Hash#rehash merges two pairs if their keys become equal, but not if their values become equal. Therefore the following code leaves a Bihash in an inconsistent state:

b = Bihash.new
key_a = ["a"]
key_b = ["b"]
key_c = ["c"]
b[key_a] = key_b
b[key_c] = key_c
key_a[0] = "c" # make key_a equal to key_c
b.rehash # @forward.size is now 1, but @reverse.size is still 2
puts b[["b"]].inspect # => ["c"] # found in @reverse
puts b[["c"]].inspect # => ["c"] # found in @forward

I don't know how this should be handled.

def replace(other_bh)
  raise_error_if_frozen
  raise_error_unless_bihash(other_bh)
  @forward = other_bh.instance_variable_get(:@forward).dup
  @reverse = other_bh.instance_variable_get(:@reverse).dup
  self
end

You can call replace on @forward and @reverse:

def replace(other_bh)
  raise_error_if_frozen
  raise_error_unless_bihash(other_bh)
  @forward.replace other_bh.instance_variable_get(:@forward)
  @reverse.replace other_bh.instance_variable_get(:@reverse)
  self
end
def select!(&block)
  if block_given?
    raise_error_if_frozen
    old_size = size
    @forward.each { |k,v| delete(k) if !block.call(k,v) }
    old_size == size ? nil : self
  else
    to_enum(:select!)
  end
end

The @forward.each line can be changed to keep_if(&block). Similarly for reject! and delete_if.

\$\endgroup\$
  • \$\begingroup\$ Thanks Spike! These all look like good changes. I'll sit down and review/incorporate them tonight. \$\endgroup\$ – user88900 Nov 15 '15 at 21:07

Your Answer

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