From: Justin To <tekmc@...>
Date: 2008-06-13T06:34:51+09:00
Subject: Re: Trie data structure

class Trie
  attr_reader :value, :children
  attr_accessor :number_exists
  def initialize(value=nil, number_exists=false)
    @value = value
    @children = []
    @number_exists = number_exists # BOOL
  end

  def <<(value)
    sub_trie = Trie.new(value)
    children << sub_trie
    return sub_trie
  end

  def each
    yield value
    @children.each do |child_node|
        child_node.each { |e| yield e  }
      end
    end

  def output
    each { |x| puts x }
  end
  #--------------------------------------------------------------------------------------

  def child_value?(value, node)
    if(node.children.empty?)
      return 'empty'                     # Return: 'empty', children[i], 
'D.N.E.'
    else
      i=0; while(i<node.children.size)
        if(node.children[i].value==value)
          return node.children[i]       # Something wrong here ????
        else if(i==node.children.size-1)
          return 'D.N.E.'
        end
      end
      i+=1
      end
    end

  end


  def add_digits(digitArray)
    node = self
    while(digitArray[0])
    scan = child_value?(digitArray[0], node)       # Scan the trie for 
the digit

        # Empty case
        if(scan=='empty')
          node = node<<(digitArray[0])
          if(digitArray.size==1)
            node.number_exists = true
          end
          digitArray.delete_at(0)

        # D.N.E. case
        else if(scan=='D.N.E.')
          node = node<<(digitArray[0])
          if(digitArray.size==1)
           node.number_exists = true
          end
          digitArray.delete_at(0)

        # Value exists case
        else if(scan.is_a?(Trie))
          if(digitArray.size==1)
            scan.number_exists = true # ??
          end
          node = scan
          digitArray.delete_at(0)

        # If the number already exists ---- ???
        else
          #set node = child node
          puts "**Scan error**"
          digitArray.delete_at(0)
        end
        end
        end

    end
  #end function
end


  #--------------------------------------------------------------------------------------
  def add_number(number)
    if(number.is_a?(Fixnum))
      digitArray = []
      number.to_s.each_byte { |byte| digitArray.push(byte.chr.to_i) }
      add_digits(digitArray)
    else
      puts "\'#{number}\' not a valid *Fixnum*"
    end
  end

# End of class Trie
end


t = Trie.new

File.open('output.txt', 'r').each do |x|

  t.add_number(x.chomp.to_i)

end

t.output



I think I've finally got it to work. Now, I'm going to try to implement 
a method #output to output all of the numbers... now I'm in the crap 
T_T. Firstly, the #output I have above displays all of the nodes, but 
now I need to say:
   (*) Traverse every node and
       when you reach a node whose
       number_exists = true,
       make that list of letters
       into a word and store it in
       an array.

Ex.

      nil
      /
     1
    /
   2 => number_exists = true (12)
  /
 3 => number_exists = true (123)

Final array:  storage[12, 123]

Thanks for any help!

Justin

-- 
Posted via http://www.ruby-forum.com/.