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

require 'benchmark' 

class Integer    
   def prime?         # cf. http://snippets.dzone.com/posts/show/4636
     n = self.abs()
     return true if n == 2
     return false if n == 1 || n & 1 == 0
     d = n-1
     d >>= 1 while d & 1 == 0
     20.times do                               # 20 = k from above
       a = rand(n-2) + 1
       t = d
       y = ModMath.pow(a,t,n)                  # implemented below
       while t != n-1 && y != 1 && y != n-1
         y = (y * y) % n
         t <<= 1
       end
       return false if y != n-1 && t & 1 == 0
     end
     return true
   end
end
 
module ModMath
   def ModMath.pow(base, power, mod)
     result = 1
     while power > 0
       result = (result * base) % mod if power & 1 == 1
       base = (base * base) % mod
       power >>= 1;
     end
     result
   end
end



class Integer

   def primes   # cf. http://snippets.dzone.com/posts/show/3734

      sieve = []
      3.step(self, 2) { |i| sieve[i] = i }
      sieve[1] = nil
      sieve[2] = 2

      3.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|
            sieve[j] = nil
         end
      end

      sieve.compact!

   end 


   def primes2       # cf. http://snippets.dzone.com/posts/show/3734

      primes = [nil, nil].concat((2..self).to_a)

      (2 .. Math.sqrt(self)).each do |i|
         next unless primes[i]
            (i*i).step(self, i) do |j|
               primes[j] = nil
            end
      end
	
      primes.compact!

   end

end



class Integer

   @primes_cache ||= 100.primes
   #@primes_cache ||= [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
   class << self; attr_accessor :primes_cache; end

   @nthprime_limit ||= 5_000_000
   class << self; attr_reader :nthprime_limit; end
   #class << self; attr_accessor :nthprime_limit; end


   def sieve_size
      num = self.to_i.abs
      logn = Math.log(num)
      if num < 15985     # cf. http://primes.utm.edu/howmany.shtml
         ( num * (logn + Math.log(logn) - 1 + 1.8 * Math.log(logn) / logn) ).floor
      else
         ( num * (logn + Math.log(logn) - 0.9427) ).floor
      end
   end


   def nthprime

      num = self.to_i.abs

      # set a limit; cf. http://primes.utm.edu/nthprime/: The 5,000,000th prime is 86,028,121.
      raise "#{num}: number too big for Integer#nthprime" if num > Integer.nthprime_limit      

      primes_cache_size = Integer.primes_cache.size

      if num > primes_cache_size

         # optional; cf. Integer#nthprime_add and Integer#nthprime_add_mr below
         if num >= 50_000 && num < 100_000 && (num - primes_cache_size) < 5000 then return num.nthprime_add end
         if num >= 100_000 && num < 200_000 && (num - primes_cache_size) < 15000 then return num.nthprime_add end
         if num >= 200_000 && (num - primes_cache_size) < 35000 then return num.nthprime_add end
         
         logn = Math.log(num)

         if num < 15985       # cf. http://primes.utm.edu/howmany.shtml
            limit = ( num * (logn + Math.log(logn) - 1 + 1.8 * Math.log(logn) / logn) ).floor
            Integer.primes_cache = limit.primes
         else
            limit = ( num * (logn + Math.log(logn) - 0.9427) ).floor
            Integer.primes_cache = limit.primes
         end

=begin
         elsif num >= 15985 && num <= 1_000_000
            limit = ( num * (logn + Math.log(logn) - 0.9427) ).floor
            Integer.primes_cache = limit.primes
         elsif num > 1_000_000
            Integer.primes_cache = 20_000_000.primes
         end
=end

      else
         return Integer.primes_cache.at(num-1)
      end


      if num <= Integer.primes_cache.size
         return Integer.primes_cache.at(num-1)
      end

      if Integer.primes_cache.size > 2_500_000
         num.nthprime_add_mr 
      else
         num.nthprime_add   # faster for a (relatively) small prime cache
      end

   end


   def nthprime_add       #  add primes to Integer.primes_cache up to the nth prime

      num = self.to_i.abs

      if num <= Integer.primes_cache.size
         return Integer.primes_cache.at(num-1)
      end

      last_prime = Integer.primes_cache.last
      last_prime_divmod = last_prime.divmod(6)

      if last_prime_divmod.last == 1
         i = last_prime_divmod.first
         Integer.primes_cache.pop      # avoid a duplicate prime
      else
         i = last_prime_divmod.first + 1
      end


      while Integer.primes_cache.size < num

         n1 = 6*i+1       # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
         n2 = n1+4        # http://everything2.com/index.pl?node_id=1176369
         i += 1

         [n1, n2].each do |p| 

            next if p % 5 == 0 || p % 7 == 0

            next_num_sqrt = Math.sqrt(p).floor

            Integer.primes_cache.each do |d| 
               if d > next_num_sqrt 
                  Integer.primes_cache << p
                  #print "\r\e[0K#{Integer.primes_cache.size}"
                  #$stdout.flush
                  break
               elsif p % d == 0
                  break
               end  
            end
         end   # each  

      end  # while

      return Integer.primes_cache.at(num-1)

   end


   def nthprime_add_mr       #  add Miller-Rabin primes to Integer.primes_cache up to the nth prime

      num = self.to_i.abs

      if num <= Integer.primes_cache.size
         return Integer.primes_cache.at(num-1)
      end

      last_prime = Integer.primes_cache.last
      last_prime_divmod = last_prime.divmod(6)

      if last_prime_divmod.last == 1
         i = last_prime_divmod.first
         Integer.primes_cache.pop
      else
         i = last_prime_divmod.first + 1
      end


      while Integer.primes_cache.size < num

         search_next_prime = true

         while search_next_prime

            n1 = 6*i+1       
            n2 = n1+4        
            i += 1

            [n1, n2].each do |p| 

               next if p % 5 == 0 || p % 7 == 0

               if p.prime?
                  Integer.primes_cache << p
                  search_next_prime = false
                  #print "\r\e[0K#{Integer.primes_cache.size}"
                  #$stdout.flush
               end
            end
         end

      end  #  first while loop

      return Integer.primes_cache.at(num-1)

   end


#------------------------------------------- some additional prime methods


   def next_primes_in_cache    # next primes in Integer.primes_cache

      search_next_primes = self.to_i.abs

      last_prime = Integer.primes_cache.last
      last_prime_divmod = last_prime.divmod(6)

      if last_prime_divmod.last == 1
         i = last_prime_divmod.first
         Integer.primes_cache.pop
      else
         i = last_prime_divmod.first + 1
      end

      while search_next_primes > 0

         n1 = 6*i+1       
         n2 = n1+4        
         i += 1

         [n1, n2].each do |p| 

            next if p % 5 == 0 || p % 7 == 0
            next_num_sqrt = Math.sqrt(p).floor

            Integer.primes_cache.each do |d| 
               if d > next_num_sqrt 
                  Integer.primes_cache << p
                  search_next_primes -= 1
                  #print "\r\e[0K#{Integer.primes_cache.size}"
                  #$stdout.flush
                  break
               elsif p % d == 0
                  break
               end  
            end
         end 
      end   # while

      Integer.primes_cache.last(self.to_i.abs)

   end


   def next_mr_prime     # next Miller-Rabin prime
     
      last_num = self.to_i.abs
      last_num_divmod = last_num.divmod(6)

      if last_num_divmod.last == 1
         i = last_num_divmod.first
      else
         i = last_num_divmod.first + 1
      end

      next_prime = nil
      search_next_prime = true

      while search_next_prime

         n1 = 6*i+1       
         n2 = n1+4        
         i += 1

         [n1, n2].each do |p| 

            next if p % 5 == 0 || p % 7 == 0

            if p > last_num && p.prime?
               next_prime = p
               search_next_prime = false 
               break
            end
         end
      end

         next_prime

   end



   def next_mr_primes(n)     # next Miller-Rabin primes

      last_num = self.to_i.abs
      last_num_divmod = last_num.divmod(6)

      if last_num_divmod.last == 1
         i = last_num_divmod.first
      else
         i = last_num_divmod.first + 1
      end

      next_primes = []
      search_next_primes = n.to_i.abs

      while search_next_primes > 0

         n1 = 6*i+1      
         n2 = n1+4       
         i += 1

         [n1, n2].each do |p| 

            next if p % 5 == 0 || p % 7 == 0

            if p > last_num && p.prime?
               next_primes << p
               search_next_primes -= 1 
            end
         end
      end

      next_primes

   end

end



num1 = 10_000
num1 = 1_000
num1 = 5_000

num2 = 210_349
num2 = 100_125
num2 = 55_000

ret1 = nil
ret2 = nil
ret3 = nil
ret4 = nil


Benchmark.bm(16) do |t| 

   t.report("first #{num1} primes: ") do
      ret1 = num1.nthprime_add
   end 

   Integer.primes_cache.clear
   Integer.primes_cache.concat(100.primes)

   t.report("first #{num1} primes: ") do
      ret2 = num1.nthprime_add_mr
   end 

   Integer.primes_cache.clear
   Integer.primes_cache.concat(100.primes)

   t.report("first #{num1} primes: ") do
      ret3 = num1.nthprime
   end 

   Integer.primes_cache.clear
   Integer.primes_cache.concat(100.primes)

   t.report("first #{num2} primes: ") do
      ret4 = num2.nthprime
   end 

end


puts
puts "the #{num1}th prime number: #{ret1}"
puts "the #{num1}th prime number: #{ret2}"
puts "the #{num1}th prime number: #{ret3}"
puts "the #{num2}th prime number: #{ret4}"
puts
puts "the #{num1}th prime: #{Integer.primes_cache.at(num1-1)}"
puts "the #{num2}th prime: #{Integer.primes_cache.at(num2-1)}"
puts
p Integer.primes_cache.first(10)
p Integer.primes_cache.last(10)
p Integer.primes_cache.size
puts


p 15.next_primes_in_cache

puts 594_213.next_mr_prime

p 149_137.next_mr_primes(5)

puts
p 1_000.sieve_size
p 1_000_000.sieve_size
p 2_500_000.sieve_size
p 5_000_000.sieve_size
p 10_000_000.sieve_size
p 100_000_000.sieve_size


=begin

# check with primegen.c, http://cr.yp.to/primegen.html
primes 2 48611 | nl | tail -n 1
primes 2 104729 | nl | tail -n 1
primes 2 679277 | nl | tail -n 1
primes 2 1301423 | nl | tail -n 1
primes 2 2903603 | nl | tail -n 1
primes 1303129 1303283 | nl
primes 594213 $((594213 + 500)) | head -n 1
primes 149137 $((149137 + 1000)) | head -n 5

# further prime tools from http://libtom.org
- LibTomMath
   bn_mp_prime_is_prime.c
   bn_mp_prime_miller_rabin.c
- TomsFastMath
   fp_isprime.c
   fp_prime_miller_rabin.c

=end

# 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}

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

# Regular expressions and strings with embedded objects
# From: http://t-a-w.blogspot.com/2007/06/regular-expressions-and-strings-with.html
# Author: Tomasz Węgrzanowski
# License: 
# Creative Commons License, http://creativecommons.org/licenses/by-sa/3.0/
# GNU Free Documentation License, http://en.wikipedia.org/wiki/GNU_Free_Documentation_License


def hash_or_die(kw)
  Hash.new{|ht,k| raise "Unknown key: #{k}"}.merge(kw)
end

def parse(data)
  esc = hash_or_die "\\" => "A", "\"" => "B", "n" => "C", "'" => "D"
  rev_esc = hash_or_die "A" => "\\", 'B' => "\"", "C" => "n", "D" => "'"
  data = data.gsub(/\\(.)/) {"\x00" + esc[$1]}
  strs = []
  data = data.gsub(/('[^']*')/) { # '
    strs << $1
    "\x01<#{strs.size-1}>"
  }
  records = []
  data.scan(/\((.*?)\)/) {
    records << $1.split(/,/).map{|field|
      field.gsub(/\x01<(\d+)>/) {
        strs[$1.to_i]}.gsub(/\x00(.)/){ rev_esc[$1]
      }
    }
  }
  records
end

def sql_str_unquote(str)
  str =~ /\A'(.*)'\Z/ or raise "SQL string format is wrong: #{str}"
  $1.gsub(/\\(.)/) {$1}
end


=begin

page_fn = Dir["plwiki-*-page.sql"].sort[-1]
externallinks_fn = Dir["plwiki-*-externallinks.sql"].sort[-1]

pages = {}

File.open(page_fn).each{|line|
  next unless line =~ /\AINSERT INTO `page` VALUES (.*)\Z/
  parse($1).each{|id,ns,title,*stuff|
    next unless ns == "0"
    title = sql_str_unquote(title)
    pages[id] = title
  }
}

File.open(externallinks_fn).each{|line|
  next unless line =~ /\AINSERT INTO `externallinks` VALUES (.*)\Z/
  parse($1).each{|from,to,index|
    title = pages[from]
    next unless title
    to = sql_str_unquote(to)
    next unless to =~ /\Ahttp:\/\//
    puts "#{title}\t#{to}"
  }
}

=end


sql_dump = <<-EOS

INSERT INTO `page` VALUES (1,0,'Astronomia','',1800,0,0,0.600461925007833,'20070601091320',8076762,8584,0), (2,0,'AWK','',329,0,0,0.487812640599732,'20070530195555',8058046,4265,0), (4,0,'Alergologia','',108,0,0,0.580574716050713,'20070520093413',7912844,292,0), ...
INSERT INTO `page` VALUES (14880,0,'Dźwignica_linotorowa','',26,0,0,0.597327036408081,'20060814072401',4282357,727,0), (14881,0,'Urządzenia_transportowe','',91,0,0,0.176666489966834,'20070527090143',2976610,1041,0), ...

EOS


pages = {}

sql_dump.each{|line|
  next unless line =~ /\AINSERT INTO `page` VALUES (.*)\Z/
  parse($1).each{|id,ns,title,*stuff|
    next unless ns == "0"
    title = sql_str_unquote(title)
    pages[id] = title
  }
}


p pages

=begin

sql_dump.each{|line|
  next unless line =~ /\AINSERT INTO `externallinks` VALUES (.*)\Z/
  parse($1).each{|from,to,index|
    title = pages[from]
    next unless title
    to = sql_str_unquote(to)
    next unless to =~ /\Ahttp:\/\//
    puts "#{title}\t#{to}"
  }
}

=end


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


require 'pp'

lisp_code = '(a (b c) (d (e) f g) (((h))))'
nodes = []

lisp_code.gsub!(/([a-z]+)/) {
  nodes << [:atom, $1]
  "<#{nodes.size-1}>"
}

#p nodes

lisp_code.gsub!(/\s/,"")
#puts lisp_code

true while lisp_code.gsub!(/\(((?:<\d+>)*)\)/) {
  #p nodes
  nodes << [:app, *$1.scan(/<(\d+)>/).map{|x,| nodes[x.to_i]}]
  "<#{nodes.size-1}>"
}
lisp_code =~ /<(\d+)>/

#puts
#p nodes
#puts

pp nodes[$1.to_i]

# Output:
#  [:app,
#  [:atom, "a"],
#  [:app, [:atom, "b"], [:atom, "c"]],
#  [:app, [:atom, "d"], [:app, [:atom, "e"]], [:atom, "f"], [:atom, "g"]],
#  [:app, [:app, [:app, [:atom, "h"]]]]]


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


math_code = '(2 + 2 * 2) / ((2 + 2) * 2)'
nodes = []

math_code.gsub!(/(\d+)/) {
  nodes << $1.to_i
  "<#{nodes.size-1}>"
}
math_code.gsub!(/\s/,"")

until math_code =~ /\A<(\d+)>\Z/
  next if math_code.gsub!(/\((<\d+>)\)/) { $1 }
  next if math_code.gsub!(/<(\d+)>([\*\/])<(\d+)>/) {
    nodes << [$2, nodes[$1.to_i], nodes[$3.to_i]]
    "<#{nodes.size-1}>"
  }
  next if math_code.gsub!(/<(\d+)>([\+\-])<(\d+)>/) {
    nodes << [$2, nodes[$1.to_i], nodes[$3.to_i]]
    "<#{nodes.size-1}>"
  }
end

pp nodes[$1.to_i]

# Output:
# ["/", ["+", 2, ["*", 2, 2]], ["*", ["+", 2, 2], 2]]

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"]}}}

# cf. http://www.ruby-forum.com/topic/97105

6.times { k=0; p $*.map!{|i|k+k=i} << 1 }

# ... or ...

ar=[]; 6.times { k=