From: Robert Klemme <bob.news@...>
Date: 2005-11-10T23:37:13+09:00
Subject: Re: Question about symbols

------=_NextPart_000_002A_01C5E60C.9599FC60
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

Robert Klemme wrote:
> 3.
> Build a trie like structure where each string is stored quite
> efficiently. A trie is basically a tree like data structure where
> each node represents a char.  Then you just need to store nodes of
> this structure. 
> 
> Pro: That way you might even save so much mem, that you can forget
> cleanup 

Sample impl attached.

    robert

------=_NextPart_000_002A_01C5E60C.9599FC60
Content-Type: application/octet-stream;
	name="trie.rb"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="trie.rb"

class Trie=0A=
  class Node=0A=
    attr_reader :char, :parent=0A=
=0A=
    def initialize(char =3D nil, parent =3D nil)=0A=
      @char, @parent =3D char, parent=0A=
      @h =3D Hash.new {|h,k| h[k] =3D Node.new(k, self)}=0A=
    end=0A=
=0A=
    def [](c) @h[c] end=0A=
=0A=
    def to_s=0A=
      s =3D ""=0A=
      n =3D self=0A=
      while n.char=0A=
        s << n.char=0A=
        n =3D n.parent=0A=
      end=0A=
      s.reverse!=0A=
    end=0A=
  end=0A=
=0A=
  def initialize=0A=
    @root =3D Node.new=0A=
  end=0A=
=0A=
  def lookup(str)=0A=
    node =3D @root=0A=
    str.each_byte {|b| node=3Dnode[b]}=0A=
    node=0A=
  end=0A=
=0A=
  alias :[] :lookup=0A=
end=0A=
=0A=
t=3DTrie.new=0A=
n1 =3D t.lookup "foo"=0A=
n2 =3D t["fo"]=0A=
n3 =3D t.lookup "bar"=0A=
=0A=
require 'pp'=0A=
pp t=0A=
=0A=
puts n1, n2, n3=0A=
=0A=

------=_NextPart_000_002A_01C5E60C.9599FC60--