# Inspired by http://www.rubyquiz.com/quiz103.html
# cf. also http://en.wikipedia.org/wiki/Trie

#!/usr/local/bin/ruby -w

require 'pp'

class Hash

   def deep_merge!(second)
      # cf. http://snippets.dzone.com/posts/show/4146
      merger = proc { |key,v1,v2| Hash === v1 && Hash === v2 ? v1.merge(v2, &merger) : v2 }
      self.merge!(second, &merger)
   end

   def nested_hash(array)
      node = self
      array.each do |i|
         node[i]=Hash.new if node[i].nil?
         node = node[i]
      end 
      self
   end

   def merge_nested_hash!(nested_hash)
      deep_merge!(nested_hash)
   end

   # code basis taken from: "Find every path and it's value in a Hash" by Florian Aßmann,
   # http://snippets.dzone.com/posts/show/3565

   def each_trie_path
      raise ArgumentError unless block_given?
      self.class.each_trie_path(self) { |path, object| yield(path, object) }
   end

   protected
   def self.each_trie_path(object, path = [], &block)  

      if object.is_a?(Hash)
         object.each do |key, value|

            if key == true && value == {}
               if path == [:root]  # special case for empty string: [[:root], {true=>{}}]
                  yield(path, {true=>{}})
                  next
               end
               yield(path, object)
            end

            self.each_trie_path(value, [path , key].flatten, &block)
         end
      else 
         yield(path, object)
      end
   end 

end


class Trie

   @hash = Hash.new.merge_nested_hash!(Hash.new)
   #@hash = Hash.new.merge_nested_hash!({:root=>{}})
   #@hash = Hash.new.merge_nested_hash!(Hash.new.nested_hash([:root]))
   class << self; attr_accessor :hash; end    # Trie.hash

   def initialize
      Trie.hash.merge_nested_hash!({:root=>{}})
   end


   def add_int(int)   # for int >= 0
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  # integer array; ex: [4,6,2]
      ia.unshift(:root).push(true)
      Trie.hash.merge_nested_hash!(Hash.new.nested_hash(ia))
   end

   def matchi(int)  # match integer
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  
      node = Trie.hash.fetch(:root,nil)
      ia.each do |digit|
         node = node[digit]
         #node = node.fetch(digit,nil)
         return false unless node
      end
      node.fetch(true,nil) ? true : false
   end

   def mfpi(int)   # match first part of integer
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }
      node = Trie.hash.fetch(:root,nil)
      ia.each do |digit|
         node = node[digit]
         return false unless node
      end
      return true
   end


   def add_word(word)
      ca = word.split(//u)    # UTF-8 aware character array
      ca.unshift(:root).push(true)
      Trie.hash.merge_nested_hash!(Hash.new.nested_hash(ca))
   end

   def match(word)   # match entire word
      ca = word.split(//u)    
      node = Trie.hash.fetch(:root,nil)
      ca.each do |char|
         node = node[char]
         #node = node.fetch(char,nil)
         return false unless node
      end
      node.fetch(true,nil) ? true : false
   end

   def mfpw(word)   # match first part of word
      ca = word.split(//u)    
      node = Trie.hash.fetch(:root,nil)
      ca.each do |char|
         node = node[char]
         return false unless node
      end
      return true
   end

end


trie = Trie.new
p Trie.hash

trie.add_word("word")
pp Trie.hash            
p trie.match("word")      
p trie.match("word2")   
trie.add_word("word2")
p trie.match("word2")   
pp Trie.hash            # {:root=>{"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}}

trie.add_word("")
p trie.match("")
pp Trie.hash

puts

p trie.match("word")      
p trie.mfpw("wor")     # match first part of word

puts

trie.add_int(12345)
p Trie.hash

trie.add_int(12980345)
pp Trie.hash

trie.add_int(8512)
pp Trie.hash
p trie.matchi(8512)
p trie.matchi(85)
p trie.mfpi(85)     # match first part of integer
p trie.matchi(51)

puts

puts
pp Trie.hash
paths = []
Trie.hash.each_trie_path { |path, value| paths.push([ path ]) }
#Trie.hash.each_trie_path { |path, value| paths.push([ path, value ]) }
#pp paths
puts
paths.each { |x| p x }
puts


#------------------------------------------------------


require 'pp'

class Hash
   def Hash.new_nested_hash
     Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }
   end
end


class Trie

   @hash = Hash.new_nested_hash
   #@hash = Hash.new_nested_hash.update(true=>{})  # add empty string by default
   class << self; attr_accessor :hash; end    # Trie.hash

   def <<(word)
      ca = word.split(//u)    # UTF-8 aware character array
      wl = ca.size            # word length
      str = ""
      wl.times { |x| str << "[ca.at(#{x})]" }
      str = "Trie.hash" << str << "[true]"
      #p str     # example: "Trie.hash[ca.at(0)][ca.at(1)][ca.at(2)][ca.at(3)][true]"
      eval(str)
   end


   def match(word)
      ca = word.split(//u)    # UTF-8 aware character array
      wl = ca.size            # word length
      str = ""

      wl.times { |x| str << ".fetch(ca.at(#{x}),nil)" }
      str = "Trie.hash" << str << ".fetch(true,nil)"
      #p str   # example: "Trie.hash.fetch(ca.at(0),nil).fetch(ca.at(1),nil).fetch(ca.at(2),nil).fetch(true,nil)"
      ret = eval(str) rescue nil

=begin
      # alternative
      wl.times { |x| str << ".fetch(ca.at(#{x}),{})" }
      str = "Trie.hash" << str << ".fetch(true,nil)"
      #p str   # example: "Trie.hash.fetch(ca.at(0),{}).fetch(ca.at(1),{}).fetch(ca.at(2),{}).fetch(true,nil)"
      ret = eval(str)
=end

      ret == {} ? true : false   # {} is the default value created by Trie.hash or Hash.new_nested_hash respectively
   end

end


trie = Trie.new
trie << "word"
pp Trie.hash            
p trie.match("word")      
p trie.match("word2")   
trie << "word2"
p trie.match("word2")   
pp Trie.hash            # {"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}

trie << ""
p trie.match("")
pp Trie.hash


#------------------------------------------


# alternative with default :root element

require 'pp'

class Hash
   def Hash.new_nested_hash
     Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }
   end
end


class Hash

   # code basis taken from: "Find every path and it's value in a Hash" by Florian Aßmann,
   # http://snippets.dzone.com/posts/show/3565

   def each_trie_path
      raise ArgumentError unless block_given?
      self.class.each_trie_path(self) { |path, object| yield(path, object) }
   end

   protected
   def self.each_trie_path(object, path = [], &block)  

      if object.is_a?(Hash)
         object.each do |key, value|

            if key == true && value == {}
               if path == [:root]  # special case for empty string: [[:root], {true=>{}}]
                  yield(path, {true=>{}})
                  next
               end
               yield(path, object)
            end

            self.each_trie_path(value, [path , key].flatten, &block)
         end
      else 
         yield(path, object)
      end
   end 

end


class Trie

   @hash = Hash.new_nested_hash
   class << self; attr_accessor :hash; end    # Trie.hash

   def initialize
      Trie.hash[:root]
   end


   def add_int(int)   # for int >= 0
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  # integer array; ex: [4,6,2]
      ia.unshift(:root)
      str = ""
      ia.size.times { |x| str << "[ia.at(#{x})]" }
      str = "Trie.hash" << str << "[true]"
      eval(str)
   end

   def matchi(int)  # match integer
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  
      node = Trie.hash.fetch(:root,nil)
      ia.each do |digit|
         node = node.fetch(digit,nil)
         return false unless node
      end
      node.fetch(true,nil) ? true : false
   end

   def mfpi(int)   # match first part of integer
      ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }
      node = Trie.hash.fetch(:root,nil)
      ia.each do |digit|
         node = node.fetch(digit,nil)
         return false unless node
      end
      return true
   end


   def <<(word)
      ca = word.split(//u)    # UTF-8 aware character array
      ca.unshift(:root)
      #ca = [:root, *word.split(//u)]
      #ca = [:root].concat(word.split(//u))
      str = ""
      ca.size.times { |x| str << "[ca.at(#{x})]" }
      str = "Trie.hash" << str << "[true]"
      #p str     # example: "Trie.hash[ca.at(0)][ca.at(1)][ca.at(2)][ca.at(3)][true]"
      eval(str)
   end

   def match(word)
      ca = word.split(//u)    
      ca.unshift(:root)
      #ca = [:root, *word.split(//u)]
      #ca = [:root].concat(word.split(//u))
      str = ""
      ca.size.times { |x| str << ".fetch(ca.at(#{x}),nil)" }
      str = "Trie.hash" << str << ".fetch(true,nil)"
      #p str   # example: "Trie.hash.fetch(ca.at(0),nil).fetch(ca.at(1),nil).fetch(ca.at(2),nil).fetch(true,nil)"
      ret = eval(str) rescue nil

=begin
      # alternative
      ca.size.times { |x| str << ".fetch(ca.at(#{x}),{})" }
      str = "Trie.hash" << str << ".fetch(true,nil)"
      #p str   # example: "Trie.hash.fetch(ca.at(0),{}).fetch(ca.at(1),{}).fetch(ca.at(2),{}).fetch(true,nil)"
      ret = eval(str)
=end

      ret == {} ? true : false   # {} is the default value created by Trie.hash or Hash.new_nested_hash respectively
   end

   def match2(word)   # match entire word
      ca = word.split(//u)    
      node = Trie.hash.fetch(:root,nil)
      ca.each do |char|
         node = node.fetch(char,nil)
         return false unless node
      end
      node.fetch(true,nil) ? true : false
   end

   def mfpw(word)   # match first part of word
      ca = word.split(//u)    
      node = Trie.hash.fetch(:root,nil)
      ca.each do |char|
         node = node.fetch(char,nil)
         return false unless node
      end
      return true
   end

end


trie = Trie.new
trie << "word"
pp Trie.hash            
p trie.match("word")      
p trie.match("word2")   
trie << "word2"
p trie.match("word2")   
pp Trie.hash            # {:root=>{"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}}

trie << ""
p trie.match("")
pp Trie.hash

puts

p trie.match2("word")      
p trie.mfpw("wor")     # match first part of word

puts

trie.add_int(8512)
pp Trie.hash
p trie.matchi(8512)
p trie.matchi(85)
p trie.mfpi(85)     # match first part of integer
p trie.matchi(51)

puts

puts
pp Trie.hash
paths = []
Trie.hash.each_trie_path { |path, value| paths.push([ path ]) }
#Trie.hash.each_trie_path { |path, value| paths.push([ path, value ]) }
#pp paths
puts
paths.each { |x| p x }
puts

# From: http://www.ruby-forum.com/topic/135807
# Author: Nobuyoshi Nakada

class Hash
   def collate(h)
      raise ArgumentError unless h.is_a?(Hash)
      update(h) { |key, *values| values }
      #update(h) { |key, *values| values.flatten.uniq }
   end
end

h1 = {:a=>1, :b=>2 }
h2 = {:a=>3, :b=>4, :c=>5}
h1.collate(h2)
p h1, h2     
#=> {:b=>[2, 4], :a=>[1, 3], :c=>5}
#=> {:b=>4, :a=>3, :c=>5}

puts
h1 = {:a=>1, :b=>2 }
h2 = {:a=>3, :b=>4, :c=>5}
h2.collate(h1)
p h1, h2     
#=> {:b=>2, :a=>1}
#=> {:b=>[4, 2], :a=>[3, 1], :c=>5}

class Object
   def deep_clone
      Marshal.load(Marshal.dump(self))
   end
end


class Hash

   # From: http://www.sameshirteveryday.com/2007/09/23/ruby-get-full-history-all-parents-of-a-hash-node
   # Author: Alex Gorbatchev
   # for further recursive hash methods see: 
   # - http://snippets.dzone.com/posts/show/1908
   # - http://snippets.dzone.com/posts/show/4706
   
   def nested_key(desired_key, &block)

      return false unless Hash === self
      #return false unless self.is_a?(Hash)

      self.each_pair do |k,v|  
         if k == desired_key or v.nested_key(desired_key, &block)  
            yield(k,v)  
            return true  
         end  
      end  

      return false  
   end


   def deep_values(key)   # cf. http://snippets.dzone.com/posts/show/1908 

      hash = self.deep_clone
      ret = []

      begin

         ar = []
         result = hash.nested_key(key) { |k, v| ar << k }
         break unless result
         ar = ar.reverse

         hk = ""
         ar.size.times { |i| hk << "[ar[#{i}]]" }
         #str = "hash" << hk << " rescue nil"
         str = "hash" << hk 

         # get value for hash key hk
         ret << eval(str)

         # delete the hash key
         key_to_delete = [ar.pop]

         hk = ""
         ar.size.times { |i| hk << "[ar[#{i}]]" }
         str = "hash" << hk
         str = str << ".delete(key_to_delete.first)"
         eval(str)


      end while result

      hash.clear  # optional
      ret

   end


   def deep_delete(key)

      hash = self

      begin

         ar = []
         result = hash.nested_key(key) { |k, v| ar << k }
         break unless result
         ar = ar.reverse

         # delete the hash key
         key_to_delete = [ar.pop]

         hk = ""
         ar.size.times { |i| hk << "[ar[#{i}]]" }
         str = "hash" << hk
         str = str << ".delete(key_to_delete.first)"
         eval(str)

      end while result

   end

end



puts
hash = {  
  :level_1 => {  
    :level_2 => {  :search => 'test1',
      :level_3 => {  
        :search => 'test2', :level_4 => {:search => 'test3'}
      }  
    }  
  }  
}  


require 'pp'

p hash
puts

pp hash
puts

hash.nested_key(:search) { |k, v| puts "#{k}  ::  #{v.inspect}" }

# prints out...
# search  ::  "test1"
# level_2  ::  {:search=>"test1", :level_3=>{:search=>"test2", :level_4=>{:search=>"test3"}}}
# level_1  ::  {:level_2=>{:search=>"test1", :level_3=>{:search=>"test2", :level_4=>{:search=>"test3"}}}}

puts


puts "DEEP VALUES"
p hash.deep_values(:search)   #=> ["test1", "test2", "test3"]
puts

puts "DEEP VALUES DELETED"
hash.deep_delete(:search)
p hash   #=> {:level_1=>{:level_2=>{:level_3=>{:level_4=>{}}}}}
puts

puts "DEEP VALUES"
p hash.deep_values(:search)   #=> []

# Hash#deep_merge
# From: http://pastie.textmate.org/pastes/30372, Elliott Hird
# Source: http://gemjack.com/gems/tartan-0.1.1/classes/Hash.html
# This file contains extensions to Ruby and other useful snippits of code.
# Time to extend Hash with some recursive merging magic.


class Hash

  # Merges self with another hash, recursively.
  # 
  # This code was lovingly stolen from some random gem:
  # http://gemjack.com/gems/tartan-0.1.1/classes/Hash.html
  # 
  # Thanks to whoever made it.

  def deep_merge(hash)
    target = dup
    
    hash.keys.each do |key|
      if hash[key].is_a? Hash and self[key].is_a? Hash
        target[key] = target[key].deep_merge(hash[key])
        next
      end
      
      target[key] = hash[key]
    end
    
    target
  end


  # From: http://www.gemtacular.com/gemdocs/cerberus-0.2.2/doc/classes/Hash.html
  # File lib/cerberus/utils.rb, line 42

  def deep_merge!(second)
    second.each_pair do |k,v|
      if self[k].is_a?(Hash) and second[k].is_a?(Hash)
        self[k].deep_merge!(second[k])
      else
        self[k] = second[k]
      end
    end
  end


#-----------------
        
   # cf. http://subtech.g.hatena.ne.jp/cho45/20061122
   def deep_merge2(other)
      deep_proc = Proc.new { |k, s, o|
         if s.kind_of?(Hash) && o.kind_of?(Hash)
            next s.merge(o, &deep_proc)
         end
         next o
      }
      merge(other, &deep_proc)
   end


   def deep_merge3(second)

      # From: http://www.ruby-forum.com/topic/142809
      # Author: Stefan Rusterholz

      merger = proc { |key,v1,v2| Hash === v1 && Hash === v2 ? v1.merge(v2, &merger) : v2 }
      self.merge(second, &merger)

   end


   def keep_merge(hash)
      target = dup
      hash.keys.each do |key|
         if hash[key].is_a? Hash and self[key].is_a? Hash
            target[key] = target[key].keep_merge(hash[key])
            next
         end
         #target[key] = hash[key]
         target.update(hash) { |key, *values| values.flatten.uniq }
      end
      target
   end

end


h = {:a => {:b => :c}}.merge({:a => {:l => :x}})
p h  #=> {:a=>{:l=>:x}}

h = {:a => {:b => :c}}.deep_merge({:a => {:l => :x}})
p h  #=> {:a=>{:b=>:c, :l=>:x}}
puts


h1 = {:a => {:b => :c}}
h2 = {:a => {:l => :x}}

h = h1.deep_merge(h2)
p h1, h2, h
puts

h = h1.deep_merge2(h2)
p h1, h2, h
puts

h = h1.deep_merge!(h2)
p h1, h2, h


h1 = {:a => {:b => :c}}
h2 = {:a => {:l => :x}}

p h1.deep_merge3(h2)
p h1, h2


first = {
  :data=>{
    :name=>{
      :first=>'Sam',
      :middle=>'I',
      :last=>'am'
    }
  }
}

second={
  :data=>{
    :name=>{
      :middle=>'you',
      :last=>'are'
    }
  }
}


p first.deep_merge3(second)
#=> {:data=>{:name=>{:middle=>"you", :first=>"Sam", :last=>"are"}}}

p first.keep_merge(second)
#=>  {:data=>{:name=>{:first=>"Sam", :middle=>["I", "you"], :last=>["am", "are"]}}}

# From: http://www.ruby-forum.com/topic/111524
# Author: Daniel Martin

a = Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }

a[2][1]=2
a[2][2][3]=4
a[3][1][1][1]=1

p  a     #=> {2=>{1=>2, 2=>{3=>4}}, 3=>{1=>{1=>{1=>1}}}}


# From: http://www.ruby-forum.com/topic/130324
# Author: Sebastian Hungerecker

blk = lambda {|h,k| h[k] = Hash.new(&blk)}
x = Hash.new(&blk)
x[:la][:li][:lu][:chunky][:bacon][:foo] = "bar"


# From: http://www.ruby-forum.com/topic/130324
# Author: Bob Hutchison

class NestedHash < Hash
   def initialize
     blk = lambda {|h,k| h[k] = NestedHash.new(&blk)}
     super(&blk)
   end
end

class Hash
   def Hash.new_nested_hash
     Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }
   end
end

a = Hash.new_nested_hash

a[2][1]=2
a[2][2][3]=4
a[3][1][1][1]=1

p  a     #=> {2=>{1=>2, 2=>{3=>4}}, 3=>{1=>{1=>{1=>1}}}}


# From: http://www.rubyquiz.com/quiz113.html
# Author: Carl Porth

ar = ('a'..'g').to_a
p  ar.reverse.inject { |mem, var| {var => mem} }    #=> {"a"=>{"b"=>{"c"=>{"d"=>{"e"=>{"f"=>"g"}}}}}}


#-------------------------------------------------


#!/usr/local/bin/ruby -w

require 'pp'

class Hash

   def deep_merge!(second)

      # From: http://www.ruby-forum.com/topic/142809
      # Author: Stefan Rusterholz

      merger = proc { |key,v1,v2| Hash === v1 && Hash === v2 ? v1.merge(v2, &merger) : v2 }
      self.merge!(second, &merger)

   end

   def nested_hash(array)
      node = self
      array.each do |i|
         node[i]=Hash.new if node[i].nil?
         node = node[i]
      end 
      self
   end

   def merge_nested_hash!(nested_hash)
      deep_merge!(nested_hash)
   end


end

h = {}
nested_hash = Hash.new.nested_hash((1..10).to_a)
h.merge_nested_hash!(nested_hash)
p h

nested_hash = Hash.new.nested_hash((1..15).to_a)
h.merge_nested_hash!(nested_hash)
p h

nested_hash = Hash.new.nested_hash([1,2,3,4,5,34,55,66,7786,54,1])
h.merge_nested_hash!(nested_hash)
pp h

class Hash

   def extract_keys