From: Robert Klemme <bob.news@...>
Date: 2004-09-04T19:25:16+09:00
Subject: Re: Hashes and ordering

------=_NextPart_000_04BF_01C4927A.06D82330
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit


"Dave Burt" <burtdav@hotmail.com> schrieb im Newsbeitrag
news:Gye_c.18929$D7.7399@news-server.bigpond.net.au...
> I think I agree with Matz that as Hash.equal? shouldn't be changing, but
an
> ordered hash could be useful even if its .equal? was limited in that way.
It
> wouldn't break Hash for order to be maintained. But Hal's right in
thinking
> that this the ordered hash ideally is a new beast, a slightly different
> concept from Hash, that deserves its own .equal?.
>
> "Yukihiro Matsumoto" <matz@ruby-lang.org> wrote:
> > Hash value orders (if any) should not affect equality check to honor
> > tradition, I think.
> >
> > Predictable order is a subset of unpredictable orders ;-)
>
> "Hal Fulton" <hal9000@hypermetrics.com> wrote:
> > does anyone depend on these hashes being equal?
> >    x = {1=>2, 3=>4}
> >    y = {3=>4, 1=>2}
> >    x == y            #  => true
> >
> > Or does anyone have code that depends in some other way
> > on the fact that the ordering in a hash is NOT predictable?
>
>

As far as I understood Hal he doesn't want to mandate Hash to change but
rather a new class that implements an ordered map.  (experimental impl
attached)

    robert

------=_NextPart_000_04BF_01C4927A.06D82330
Content-Type: application/octet-stream;
	name="TreeMap.rb"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="TreeMap.rb"

class TreeMap=0A=
  include Enumerable=0A=
=0A=
  TreeNode =3D Struct.new(:key, :val, :parent, :left, :right)=0A=
  DefaultOrder =3D lambda {|a,b| a <=3D> b}=0A=
  ReverseOrder =3D lambda {|a,b| b <=3D> a}=0A=
=0A=
  def initialize(&order)=0A=
    @order =3D order || DefaultOrder=0A=
  end=0A=
=0A=
  def []=3D(key, val)=0A=
    find(key) do |last, node, dir|=0A=
      if last=0A=
        last.send( "#{dir}=3D", TreeNode.new( key, val, last ) )=0A=
      else=0A=
        @root =3D TreeNode.new( key, val )=0A=
      end=0A=
    end.val =3D val=0A=
  end=0A=
=0A=
  def [](key)=0A=
    node =3D find(key)=0A=
    node && node .val=0A=
  end=0A=
=0A=
  def each(&b)=0A=
    walk( @root, &b )=0A=
    self=0A=
  end=0A=
=0A=
  def inspect=0A=
    s =3D "{"=0A=
    first =3D true=0A=
=0A=
    each do |k,v|=0A=
      if first=0A=
        first =3D false=0A=
      else=0A=
        s << ", "=0A=
      end=0A=
=0A=
      s << k.inspect << "=3D>" << v.inspect=0A=
    end=0A=
=0A=
    s << "}"=0A=
  end=0A=
=0A=
  def to_s=0A=
    s =3D ""=0A=
    first =3D true=0A=
=0A=
    each do |k,v|=0A=
      first =3D false if first=0A=
      s << k.to_s << v.to_s=0A=
    end=0A=
=0A=
    s=0A=
  end=0A=
=0A=
  def keys=0A=
    inject([]) {|ks, (k, v)| ks << k}=0A=
  end=0A=
=0A=
  def values=0A=
    inject([]) {|vs, (k, v)| vs << v}=0A=
  end=0A=
=0A=
  def hash=0A=
    inject(0){|h, (k, v)| ( (h << 1) ^ hv(k) ^ (hv(v) << 3) ) & =
HASH_LIMIT}=0A=
  end=0A=
=0A=
  def equal?(obj)=0A=
    keys =3D=3D obj.keys && values =3D=3D obj.values=0A=
  end=0A=
=0A=
  def update(hash)=0A=
    hash.each {|k, v| self[k]=3Dv}=0A=
    self=0A=
  end=0A=
=0A=
  def clear() @root =3D nil end=0A=
=0A=
  def empty?() @root.nil? end=0A=
=0A=
  def size() inject(0) {|sum,| sum + 1} end=0A=
=0A=
private=0A=
=0A=
  HASH_LIMIT =3D 1 << 24 - 1=0A=
=0A=
  def hv(obj) obj.nil? ? 0 : obj.hash end=0A=
=0A=
=0A=
  def walk(node, &b)=0A=
    if node=0A=
      walk( node.left, &b )=0A=
      b.call( node.key, node.val )=0A=
      walk( node.right, &b )=0A=
    end=0A=
  end=0A=
=0A=
  def find(key)=0A=
    last, node, dir =3D nil, @root, nil=0A=
=0A=
    until node.nil?=0A=
      ord =3D @order[key, node.key]=0A=
      return node if ord =3D=3D 0=0A=
=0A=
      if ord < 0=0A=
        last, node, dir =3D node, node.left, :left=0A=
      else=0A=
        last, node, dir =3D node, node.right, :right=0A=
      end=0A=
    end=0A=
=0A=
    if block_given? then yield last, node, dir else node end=0A=
  end=0A=
=0A=
end=0A=

------=_NextPart_000_04BF_01C4927A.06D82330--