require "cgi"
require "rbconfig"
require "thread"

Thread.abort_on_exception	= true

$DEBUG	= ($DEBUG or ENV["RUBYDEBUG"] or false)

#tekens	= '\w\~\@\#\$\%\^\&\*\-\+'
tekens		= '^\s\r\n\`\!\(\)\[\]\{\}\<\>\,\.\/\?\\\|\=\;\:\"'

#tekens11	= '\w'
tekens11	= tekens + "'"

tekens21	= tekens + "'"
tekens22	= tekens
tekens23	= tekens + "'"

tekens31	= '\w\s\r\n'

RegExpStringWord	= "([#{tekens11}]+)"									; RegExpWord	= Regexp.new(RegExpStringWord)
RegExpStringWord2	= "([#{tekens21}]([#{tekens22}]*[#{tekens23}])?)"					; RegExpWord2	= Regexp.new(RegExpStringWord2)
RegExpStringText	= "([#{tekens31}]+)"									; RegExpText	= Regexp.new(RegExpStringText)
RegExpStringFile	= '(\w[\w\.\-]*)'									; RegExpFile	= Regexp.new(RegExpStringFile)
RegExpStringEmail	= '([\w\-\.]+@[\w\-\.]+)'								; RegExpEmail	= Regexp.new(RegExpStringEmail)
RegExpStringURL		= '(\w+:\/\/[\w\.\-]+(:\d*)?\/[\w\.\-\/\#\?\=\%]*)'					; RegExpURL	= Regexp.new(RegExpStringURL)
RegExpStringPrint	= '([\w \t\r\n\`\~\!\@\#\$\%\^\&\*\(\)\-\+\=\[\]\{\}\;\:\'\"\,\.\/\<\>\?\\\|]+)'	; RegExpPrint	= Regexp.new(RegExpStringPrint)
RegExpStringDiff	= '(^[\-\+]([^\-\+].*)?)'								; RegExpDiff	= Regexp.new(RegExpStringDiff)

module Enumerable
  def deep_dup
    Marshal::load(Marshal::dump(dup))
  end

  def deep_clone
    Marshal::load(Marshal::dump(clone))
  end
end

class Thread
  def self.background(*args)
    new(*args) do |*args|
      Thread.pass

      yield(*args)
    end
  end
end

class Object
  alias deep_dup :dup
  alias deep_clone :clone

  def to_fs
    to_s
  end

  def ids
    id
  end
end

class Numeric
  def to_fs
    to_f
  end
end

class Integer
  def oct
    n	= self
    res	= []

    while n > 8
      n, x	= n.divmod(8)
      res << x
    end
    res << n

    res.reverse.join("")
  end
end

class String
  def chomp!(dummy=nil)
    self.gsub!(/[\r\n]*\z/, "")
  end

  def chomp(dummy=nil)
    self.gsub(/[\r\n]*\z/, "")
  end

  def lf
    self.gsub(/\r*\n/, "\n").gsub(/\n\z/, "") + "\n"
  end

  def crlf
    self.gsub(/\r*\n/, "\r\n").gsub(/\r\n\z/, "") + "\r\n"
  end

  def strip
    self.stripbefore.stripafter
  end

  def stripbefore
    self.gsub(/\A[[:blank:]\r\n]*/, "")
  end

  def stripafter
    self.gsub(/[[:blank:]\r\n]*\z/, "")
  end

  def compress
    self.gsub(/[[:blank:]\r\n]+/, " ").strip
  end

  def compressspaces
    self.gsub(/[[:blank:]]+/, " ")
  end

  def compressperline
    res	= self.split(/\n/)
    res.collect!{|line| line.compress}
    res.delete_if{|line| line.empty?}
    res.join("\n")
  end

  def numeric?
    d, a, n	= [self].to_par

    not n.empty?
  end

  def exec(input=nil, output=true)
    res	= []

    IO.popen(self, "w+") do |f|
      f.puts input	unless input.nil?
      f.close_write

      res	= f.readlines if output
    end

    res.join("")
  end

  def eval
    Kernel::eval(self)
  end

  def speak
    require "drb"

    DRb.start_service
    DRbObject.new(nil, "druby://localhost:3100").speak(self)
  end

  def splitblocks(*delimiters)
    begindelimiters	= []
    enddelimiters	= []

    delimiters.each do |k, v|
      begindelimiters	<< k.downcase
      enddelimiters	<< v.downcase
    end

    bd	= begindelimiters.collect	{|s| Regexp.escape(s)}
    ed	= enddelimiters.collect		{|s| Regexp.escape(s)}

    be	= bd.join("|")
    ee	= ed.join("|")

    res		= []
    type	= 0
    tmp		= ""
    bs		= ""
    es		= ""

    self.split(/(#{ee}|#{be})/i).each do |s|
      if type == 0
        if begindelimiters.include?(s.downcase)
          i	= begindelimiters.index(s.downcase)
          type	= i+1
          tmp	= s
          bs	= s.downcase
          es	= enddelimiters[i]
        else
          res << [0, s]	unless s.empty?
        end
      else
        if s.downcase == es
          res << [type, tmp + s]
          type	= 0
          tmp	= ""
          bs	= ""
          es	= ""
        else
          if s.downcase == bs
            res << [0, tmp]
            tmp	= s
          else
            tmp	= tmp + s
          end
        end
      end
    end

    res << [0, tmp]	unless tmp.empty?

    return res
  end

  def splitwords(tokens=[])
    tokens	= [tokens]	unless tokens.kind_of?(Array)
    res		= []

    self.splitblocks(["'", "'"], ['"', '"']).each do |type, s|
      case type
      when 0
        tokens.each do |token|
          token2	= token
          token2	= Regexp.escape(token2)	if token2.kind_of?(String)
          s.gsub!(/#{token2}/, " #{token} ")
        end
        s.split().each do |w|
          res << w
        end
      when 1, 2
        res << s[1..-2]
      end
    end

    return res
  end

  def uncomment
    res	= []

    self.splitblocks(["'", "'"], ['"', '"'], ["#", "\n"]).each do |type, s|
      case type
      when 0, 1, 2	then	res << s
      when 3		then	res << "\n"
      end
    end

    res.join("")
  end

  def noquotes
    self.sub(/\A['"]/, "").sub(/['"]\z/, "")
  end

  def to_html(eolconversion=true)
    s	= CGI.escapeHTML(self)

    s.gsub!(/\"/, "\&#34;")
    s.gsub!(/\'/, "\&#180;")

    if eolconversion
      s.gsub!(/\n/ , "<br>")
    end

    s
  end

  def from_html(eolconversion=true)
    s	= self

    s.gsub!(/&#34;/ , "\"")
    s.gsub!(/&#180;/, "\'")

    s	= CGI.unescapeHTML(self)

    if eolconversion
      s.gsub!(/<br>/, "\n")
    end

    s
  end

  def to_fs
    if numeric?
      to_f
    else
      to_s
    end
  end
end

class Array
  def chomp!
    self.collect!{|s| s.chomp}
  end

  def chomp
    self.collect{|s| s.chomp}
  end

  def compress
    self.collect{|s| s.compress}
  end

  def uncomment
    self.join("\0").uncomment.split("\0")
  end

  def strip
    self.collect{|s| s.strip}
  end

  def sum
    res	= 0
    self.each do |n|
      res += n
    end
    res
  end

  def product
    res	= 1
    self.each do |n|
      res *= n
    end
    res
  end

  def joinwords(sep=" ", quote='"')
    self.collect do |s|
      s	= quote + s + quote	if s =~ /[[:blank:]]/
      s
    end.join(sep)
  end

  def domino(tabellen, kolom=nil, onlymatchinglines=false)
    links	= self
    res		= []
    res		= self.dup	unless onlymatchinglines

    tabellen.each do |rechts|
      tmp	= []

      links.each do |l|
        if kolom.nil? or l.length == kolom
          rechts.each do |r|
            tmp << l + r[1..-1]	if l[-1] == r[0]
          end
        end
      end

      links	= tmp
      res.concat(tmp)
    end

    res	= res.sort.uniq
  end

  def dominoloop(tabellen)
    lres	= []
    res		= self.dup
    kolom	= 2

    while lres.length != res.length do
      lres	= res.dup
      res	= res.domino(tabellen, kolom)

      res.each do |line|
        line << "*"	if (line.length != line.uniq.length and line[-1] != "*")
      end

      $stderr.print "#{100*(res.length)/(lres.length)}% "

      kolom += 1
    end

    $stderr.puts ""

    return res
  end

  def buildtree
    self.dominoloop([self])
  end

  def subset(fields, values, results, exact=true, emptyline=nil, joinwith=nil)
    fields	= [fields]		unless fields.kind_of? Array
    values	= [values]		unless values.kind_of? Array
    results	= [results]		unless results.kind_of? Array
    emptyline	= emptyline.downcase	unless emptyline.nil?
    res		= self.dup
    res.delete_if {true}

    self.each do |l|
      ok	= true

      case l.class.to_s
      when "String"
        c		= l.splitwords
        correction	= 1
        joinwith	= " "	if joinwith.nil?
      when "Array"
        c		= l
        correction	= 0
      end

      #catch :stop do
        values2	= values.dup
        fields.each do |f|
          v	= values2.shift
          v	= v.downcase	unless v.nil?
          if emptyline.nil? or (not v == emptyline)
            if exact
              unless (v.nil? or c[f-correction].downcase == v)
                ok	= false
                #throw :stop
              end
            else
              unless (v.nil? or c[f-correction].downcase.include?(v))
                ok	= false
                #throw :stop
              end
            end
          end
        end
      #end

      if ok
        res2	= []
        results.each do |n|
          res2 << c[n-1]
        end
        res2	= res2.join(joinwith)	unless joinwith.nil?
        res << res2
      end
    end

    return res
  end

  def format(format)
    res		= []

    [format.length, self.length].min.times do |n|
      case format[n].chr
      when "i"	then res << self[n].to_i
      when "s"	then res << self[n].to_s
      when "x"	then res << self[n]
      end
    end

    res
  end

  def to_i
    collect{|c| c.to_i}
  end

  def to_par
    dash	= self.dup
    alpha	= self.dup
    numeric	= self.dup

    dash.delete_if do |s|
      not (s =~ /\A-/) or
      (s =~ /\A-?[[:digit:]\.]+\z/) or
      (s =~ /^-+$/)
    end

    alpha.delete_if do |s|
      ((s =~ /\A-/) or
       (s =~ /\A-?[[:digit:]\.]+\z/)) and
      not ((s =~ /^\.+$/) or (s =~ /^-+$/))
    end

    numeric.delete_if do |s|
      not (s =~ /\A-?[[:digit:]\.]+\z/) or
      (s =~ /^\.+$/)
    end

    raise "Oops!"	if dash.length + alpha.length + numeric.length != length

    return dash, alpha, numeric
  end

  def self.file(file)
    res	= new

    File.open(file) do |f|
      f.readlines.uncomment.chomp.each do |line|
        res << line
      end
    end

    res
  end

  def numsort
    sort do |a, b|
      a2	= a.to_fs
      b2	= b.to_fs

      if a2.class != b2.class
        a2	= a
        b2	= b
      end

      a2 <=> b2
    end
  end

  def to_fs
    collect{|s| s.to_fs}
  end

  def chaos
    res	= self.dup

    (length^2).times do
      a	= rand(length)
      b	= rand(length)

      res[a], res[b]	= res[b], res[a]
    end

    res
  end

  def any
    if empty?
      nil
    else
      self[rand(self.length)]
    end
  end

  def minmax
    min, value, max	= self
    [min, [value, max].min].max
  end

  def ids
    collect{|e| e.ids}
  end
end

class Hash
  def save(file, append=false)
    org	= {}
    org	= Hash.file(file)	if (append and File.file?(file))

    self.sort.each do |k, v|
      org[k]	= v
    end

    File.open(file, "w") do |f|
      org.sort.each do |k, v|
        f.puts "%s\t= %s" % [k, v]
      end
    end
  end

  def subset(fields, values, results=nil, exact=true, emptyline=nil, joinwith=nil)
    fields	= [fields]		unless fields.kind_of? Array
    values	= [values]		unless values.kind_of? Array
    results	= [results]		unless results.kind_of? Array
    emptyline	= emptyline.downcase	unless emptyline.nil?
    res		= self.dup
    res.delete_if {true}

    self.each do |k, l|
      ok	= true

      case l.class.to_s
      when "String"
        c		= l.splitwords
        correction	= 1
        joinwith	= " "	if joinwith.nil?
      when "Array"
        c		= l
        correction	= 0
      end

      #catch :stop do
        values2	= values.dup
        fields.each do |f|
          v	= values2.shift
          v	= v.downcase	unless v.nil?
          if emptyline.nil? or (not v == emptyline)
            if exact
              unless (v.nil? or c[f-correction].downcase == v)
                ok	= false
                #throw :stop
              end
            else
              unless (v.nil? or c[f-correction].downcase.include?(v))
                ok	= false
                #throw :stop
              end
            end
          end
        end
      #end

      if ok
        res2	= []
        if results == [nil]
          res2	= c
        else
          results.each do |n|
            res2 << c[n-correction]
          end
        end
        res2	= res2.join(joinwith)	unless joinwith.nil?
        res[k]	= res2
      end
    end

    return res
  end

  def to_i
    collect{|k, v| v.to_i}
  end

  def self.file(file)
    res	= new

    File.open(file) do |f|
      #f.readlines.chomp.each do |line|
      while line = f.gets do
        line.chomp!

        unless line.empty?
          k, v	= line.split(/\s*=\s*/, 2)
          res[k]	= v
        end
      end
    end

    res
  end

  def ids
    collect{|k, v| [k, v].ids}
  end
end

def id2ref(id)
  ObjectSpace._id2ref(id)
end

def after(seconds, *args)
  if not seconds.nil? and not seconds.zero?
    Thread.new(*args) do |*args2|
      sleep seconds
      yield(*args2)
    end
  end
end

def every(seconds, *args)
  if not seconds.nil? and not seconds.zero?
    Thread.new(*args) do |*args2|
      loop do
        sleep seconds
        yield(*args2)
      end
    end
  end
end

def evtimeout(seconds)
  begin
    timeout(seconds) do
      yield
    end
  rescue TimeoutError
  end
end

def evtimeoutretry(seconds)
  ok	= false

  while not ok
    evtimeout(seconds) do
      yield
      ok	= true
    end
  end
end

def trap(signal)
  Kernel::trap(signal) do
    yield
  end

	# Seems pointless, but it's for catching ^C under Windows...

  every(1)	{}	if windows?
end

def linux?
  not windows? and not cygwin?
end

def windows?
  not (target_os.downcase =~ /32/).nil?
end

def cygwin?
  not (target_os.downcase =~ /cyg/).nil?
end

def target_os
  Config::CONFIG["target_os"] or ""
end

def user
  ENV["USER"] or ENV["USERNAME"]
end

def home
  (ENV["HOME"] or ENV["USERPROFILE"] or (File.directory?("h:/") ? "h:" : "c:")).gsub(/\\/, "/")
end

def temp
  (ENV["TMPDIR"] or ENV["TMP"] or ENV["TEMP"] or "/tmp").gsub(/\\/, "/")
end

def stdtmp
  $stderr = $stdout = File.new("#{temp}/ruby.#{Process.pid}.log", "a")	unless ARGV.include?("--rwd-exit")
end

$nobm	= false

def nobm
  $nobm	= true
end

def bm(label="")
  if $nobm
    if block_given?
      return yield
    else
      return nil
    end
  end

  label	= label.to_s
  res	= nil

  $bm_mutex	= ($bm_mutex or Mutex.new)

  $bm_mutex.synchronize do
    if $bm.nil?
      require "ev/bm"

      $bm		= {}

      at_exit do
	format1	= "%10s %10s %10s %10s %10s %10s %10s"
	format2	= "%10s %10.6f %10.6f %10.6f %10.6f %10.6f %10d"

	$stderr.puts format1 % ["LABEL", "USERCPU", "SYSCPU", "CUSERCPU", "CSYSCPU", "ELAPSED", "TIMES"]
	$bm.sort{|a, b| [a[1], a[0]] <=> [b[1], b[0]]}.each do |k, v|
	  $stderr.puts format2 % [k, *v]
	end
      end
    end

    $bm[label] = [0.0]*5 + [0]	unless $bm.include?(label)
  end

  if block_given?
    bm	= Benchmark.measure{res = yield}
    bma	= bm.to_a	# [dummy label, user CPU time, system CPU time, childrens user CPU time, childrens system CPU time, elapsed real time]

    $bm_mutex.synchronize do
      0.upto(4) do |n|
        $bm[label][n] += bma[n+1]
      end

      $bm[label][5] += 1
    end
  end

  res
end

def trace
  res	=nil

  set_trace_func lambda { |event, file, line, id, binding, classname|
    $stderr.printf "%8s %s:%-2d %10s %8s\n", event, file, line, id, classname
  }

  if block_given?
    res	= yield

    notrace
  end

  res
end

def notrace
  set_trace_func nil
end

def lambda_cached(&block)
  hash	= {}
  lambda do |*args|
    res	= hash[args]
    if res.nil?
      res		= block.call(*args)
      hash[args]	= res
    end
    res
  end
end