From: Sebastian Hungerecker <sepp2k@...>
Date: 2008-11-18T17:37:19+09:00
Subject: Re: Subclassing Hash to enforce value uniqueness ala key uniqueness.

Adam Gardner wrote:
> The second problem is efficiency: It seems to me that this could
> probably be done much more efficiently, especially if implemented in C.

Every time you add a value you iterate over all the other values to check 
whether the value is already there. This makes adding an element O(n). Having 
adding to a datastructure be an O(n) operation is usually a bad idea. Here's 
how I'd probably do it (untested):

class OneToOne
  def initialize()
    @key_value = {}
    @value_key = {}
  end

  def [](k)
    @key_value[k]
  end

  def []=(k,v)
    if @key_value.has_key?(k)
      @value_key.delete(@key_value[k])
    end
    if @value_key.has_key(?v)
      @key_value.delete(@value_key[v])
    end
    @key_value[k] = v
    @value_key[v] = k
  end

  def to_hash
    @key_value
  end
  def invert
    @value_key
  end
  ...
end


HTH,
Sebastian
-- 
Jabber: sepp2k@jabber.org
ICQ: 205544826