On Fri, Dec 03, 2004 at 02:35:42AM +0900, Austin Ziegler scribed:
> On Fri, 3 Dec 2004 02:16:17 +0900, Brian Schr?der
> <ruby / brian-schroeder.de> wrote:
> > Why is everybody in this thread so fixed on using array and hash.
> > As I see it the requirements are:
> > 
> > insert(k1, k2, value)
> > delete_by_k1(k1, value)
> > delete_by_k2(k2, value)
> > get_by_k1(k1)
> > get_by_k2(k2)
> > each_by_k1
> 
> Actually, my needs are:
> 
> insert(key, value)
> delete(key)
> get(key)
> each_by_insertion_order
> 
> I don't want to manage two sets of keys.

  Which, if you had Brian's mechanism as a base, you could
implement as:

  class OrderedThingy < BriansMultiKeyThingy
    def initialize
      @sequence = 0
    end
    def insert(key, value)
      # XXX:  Note lack of thread safety here.
      super(@sequence, key, value)
      @sequence += 1
    end
    def delete(key)
      delete_by_k2(key)
    end
    def get(key)
      get_by_k2(key)
    end
    def each_by_insertion_order(&proc)
      each_by_k1(&proc)
    end
  end

Brian's point is the right one to consider:  insertion order, in a
sense, is merely another key, one that's defined implicitly.  The
only reason to not use the general case were if you gained significant
speed or ease of implementation from using insertion order specifically.
Insertion order _is_ particularly easy to manage using a linked
list in a way that the doubly keyed implementation above isn't
(though the naive list.delete operation has to go - you'd be better
off maintaining a doubly linked list so that you can do the delete
from the key), but unless you're super concerned with performance,
the generality of the above implementation is a pretty nice thing
to have.

  -Dave

-- 
work: dga / lcs.mit.edu                          me:  dga / pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/