From: Adam Gardner <adam.oddfellow@...>
Date: 2008-11-18T13:33:41+09:00
Subject: Subclassing Hash to enforce value uniqueness ala key uniqueness.

First of all, hello to everyone. This is my first message to this list.

I find myself needing something very much like a Hash, but with unique 
one-to-one mapping in both directions, both key-to-value, and 
value-to-key. Now, I've been looking around a bit on Google, then 
Rubyforge, the RAA, and the archives of this list, and I'm a bit 
surprised I wasn't able to find a prior implimentation of this. Time to 
impliment my own, right?

Well, before I got too far into the process, I though I would ask for 
people's thoughts here. First off, here is the effect I would like to 
see. I'll call my subclass OneToOne for now, though I'm open to better 
names.

 >> oto = OneToOne[:a=>1, :b=>2, :c=>3]
=> {:a=>1, :b=>2, :c=>3}  # or on 1.8.x, {:b=>2, :c=>3,  :a=>1}
 >> oto[:d] = 1
=> 1
 >> oto
=> {:b=>2,:c=>3,:d=>1}
 >> OneToOne[:a=>1,:b=>1,:c=>1]
=> {:c=>1}
...
etc

Here is some code which begins to implement such a class:

class OneToOne < Hash
 
  def self.[](*args)
    super(*args).invert.invert
  end
 
  def initialize(*args)
    super(*args)
    self.fix
  end
 
  def []=(key,val)
    self.delete_if {|k,v| v == val}
    super(key,val)
  end
 
  def store(key,val)
    self.delete_if {|k,v| v == val}
    super(key,val)
  end
 
  def key(val) #this is just a nicety to arrange for code to run in 1.9 
and 1.8
    if Hash.method_defined?(:key)
      super(val)
    else
      self.index(val)
    end
  end

  def fix
    self.replace(self.invert.invert)
  end
end

This code works to a certain degree, but I see two problems going 
forward. First of all, Hash is a built-in in ruby which is written (as 
far as I am aware) entirely in C. As such, there is no 'core' method 
which can be overridden to affect change in all the methods which build 
on it. At least, implementing []= did not give me store, and 
implimenting store did not give me []=. Neither gives me merge. How many 
other methods will I therefore have to override to ensure value 
uniqueness? It seems to me, every method which could modify the contents 
of the hash in some way (other than simply removing entries). Even then, 
could I guarantee no two keys would have the same value, with the same 
level of certainty I have that no two values have the same key?

The second problem is efficiency: It seems to me that this could 
probably be done much more efficiently, especially if implemented in C. 
It doesn't affect my much for what I need it for right now, but if I 
want to reuse it later (or if someone else wants to use it), it could 
matter a great deal.

(Incidentally: searching for information about this has been somewhat 
hampered by the fact that the phrase 'hash value' is very ambiguous 
between the a value contained in a hash and paired with a key, or value 
returned by a hashing algorithm such as Object#hash or MD5. It doesn't 
help that most of other terms I can think of to search for, such as 
bidirectional or unique or one-to-one, are more common when talking 
about the latter than the former. Now I understand why several other 
languages choose the term 'Dictionary'.)

Anyway, if someone has either a) a prior implementation of this, or b) 
some suggestions on improving my implimentation, I'd love to hear it.

Thanks for your time,
- Adam Gardner