From: Justin To <tekmc@...>
Date: 2008-06-13T06:54:00+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
    info = [value,number_exists, children]
    yield(info)
    @children.each do |child_node|
        child_node.each { |e| yield e  }
      end
    end

  def output
    numberCollector = []
    tempString= ''
    each do |x|
        tempString.concat(x[0].to_s)
        if(x[1])
          numberCollector.push(tempString)
          if(x[2].size!=0)
            tempString=''
          else
            x[2].each
          end
        end
    end

    puts numberCollector
  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 can display numbers that don't have similar prefixes.. e.g. 123, 234, 
345; but I can't store these examples: 123, 145, 146

My algorithm should be:
1) Check nodes until node[i].number_exists = true
   - True: store the number up until this point:
     node[i]
     - If there are more nodes after node[i], then
       keep going and start from (1)

Any help is appreciated, thanks!!!
-- 
Posted via http://www.ruby-forum.com/.