DZone Snippets: recursive code

Hash#deep_delete

ntk () — Thu, 01 Nov 2007 15:42:50 GMT





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

ntk () — Sat, 27 Oct 2007 18:07:40 GMT





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

Tower of Hanoi

scvalex (Alexandru Scvortov) — Fri, 28 Sep 2007 06:37:43 GMT

Solves the old "Tower of Hanoi" problem using a recursive divide et impera approach.

http://en.wikipedia.org/wiki/Tower_of_Hanoi



#include 



void hanoi(int n, char a, char b, char c) {

	if (!n)	

		return;

	

	hanoi(n - 1, a, c, b);

	printf("%c -> %c\n", a, b);

	hanoi(n - 1, c, b, a);

}



int main(int argc, char *argv[]) {

	int n = 3;

	hanoi(n, 'a', 'b', 'c');

	

	return 0;

}

Recursively dump imbricated Map of Maps

Archanciel (Jean-Pierre Schnyder) — Wed, 12 Sep 2007 12:58:09 GMT

// description of your code here



    public void dumpMapOfMap(Map map) {

        Set s = map.entrySet();

        Iterator sit = s.iterator();

        boolean isFirst = true;



        while (sit.hasNext()) {

            Map.Entry elem = (Map.Entry)sit.next();

            String key = (String)elem.getKey();

            Object value = elem.getValue();



            if (value instanceof String) {

                // recursivity stop condition

                System.out.print(key);

                System.out.print(" : ");

                System.out.println(value);

            } else {

                if (!isFirst) {

                    System.out.println("");

                } else {

                    isFirst = false;

                }

                System.out.println(key);

                Map valueMap = (Map)elem.getValue();

                dumpMapOfMap(valueMap);

            }

        }

    }

Recursively find files by filename pattern.

troelskn (Troels) — Fri, 15 Jun 2007 13:17:56 GMT

Scans a directory, and all subdirectories for files, matching a regular expression. Each match is sent to the callback provided as third argument. A simple example:



function my_handler($filename) {

  echo $filename . "\n";

}

find_files('c:/', '/php$/', 'my_handler');

And the actual snippet



function find_files($path, $pattern, $callback) {

  $path = rtrim(str_replace("\\", "/", $path), '/') . '/';

  $matches = Array();

  $entries = Array();

  $dir = dir($path);

  while (false !== ($entry = $dir->read())) {

    $entries[] = $entry;

  }

  $dir->close();

  foreach ($entries as $entry) {

    $fullname = $path . $entry;

    if ($entry != '.' && $entry != '..' && is_dir($fullname)) {

      find_files($fullname, $pattern, $callback);

    } else if (is_file($fullname) && preg_match($pattern, $entry)) {

      call_user_func($callback, $fullname);

    }

  }

}

Find every path and it's value in a Hash

boof (Florian Aßmann) — Thu, 22 Feb 2007 14:54:41 GMT

Extends Hash class with each_path method.

This method takes a block as argument which is called each time a the recursivly searched Hash returns a key that does not point to another Hash.

Example:



paths = []

complex_hash = Hash[

  :a => { :aa => '1', :ab => '2' },

  :b => { :ba => '3', :bb => '4' }

]

complex_hash.each_path { |path, value| paths << [ path, value ] }

paths.inspect

# => "[[\"b/ba/\", \"3\"], [\"b/bb/\", \"4\"], [\"a/aa/\", \"1\"], [\"a/ab/\", \"2\"]]"



class Hash

  def each_path

    raise ArgumentError unless block_given?

    self.class.each_path( self ) { |path, object| yield path, object }

  end



  protected

  def self.each_path( object, path = '', &block )

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

        self.each_path value, "#{ path }#{ key }/", &block

      end

    else yield path, object

    end

  end

end

Extracting all keys from a multi-dimensional hash

ntk () — Wed, 12 Apr 2006 20:29:09 GMT

Extract all complete key sequences from a multi-dimensional hash (with the last key not pointing to another hash; cf. h[1][2][3] vs h[1][2][3][4] below).





class Hash



   def extract_keys



      keys = []



      each_pair do |k1, v1|



         if v1.is_a?(Hash)



            v1.each_pair { |k2, v2|

               if !v2.is_a?(Hash) then keys << [k1, k2]; next end

            v2.each_pair { |k3, v3|

               if !v3.is_a?(Hash) then keys << [k1, k2, k3]; next end

            v3.each_pair { |k4, v4|

               if !v4.is_a?(Hash) then keys << [k1, k2, k3, k4]; next end

            v4.each_pair { |k5, v5|

               if !v5.is_a?(Hash) then keys << [k1, k2, k3, k4, k5]; next end

            v5.each_pair { |k6, v6|

               if !v6.is_a?(Hash) then keys << [k1, k2, k3, k4, k5, k6]; next end

               # add more v[n].each_pair ... loops to process more hash dimensions

            } } } } }      # "}" * 5



         else

            keys << [k1]

         end



      end

      

      keys



   end





   def all_values

      extract_keys.map do |subar|

         key = ""

         subar.size.times { |i| key << "[subar[#{i}]]" }

         hash_str = "self" << key << " rescue nil"   # example: "self[subar[0]][subar[1]][subar[2]][subar[3]] rescue nil"

         hash_value = eval(hash_str) 

      end

   end





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





   # Find every path and it's value in a Hash, http://snippets.dzone.com/posts/show/3565

   # Author: Florian Aßmann



   def each_path

      raise ArgumentError unless block_given?

      self.class.each_path(self) { |path, object| yield(path, object) }

   end



   protected

   #def self.each_path(object, path = '', &block)

   def self.each_path(object, path = [], &block)   # alternative

      if object.is_a?(Hash)

         object.each do |key, value|

            #self.each_path(value, "#{ path }#{ key }/", &block)

            self.each_path(value, [path , key].flatten, &block)   # alternative

         end

      else 

         yield(path, object)

      end

   end 



end





h = {"a"=>"b", "c"=>"d", 1=>{2=>{"e"=>"f", 3=>{4=>"value"}}}} 



puts h[1][2].class          # Hash

puts h[1][2]["e"].class     # String



extracted_keys = h.extract_keys

puts extracted_keys.inspect         # [["a"], [1, 2, "e"], [1, 2, 3, 4], ["c"]]



puts h[1][2].has_key?("e")                 # true

puts extracted_keys.include?([1, 2, "e"])  # true





h = {700=>{4=>"value"}, "a"=>"b", 3=>{4=>"value"}, "c"=>"d", 1=>{2=>{"e"=>"f", 3=>{4=>"value"}, 300=>{4=>"value"}}}} 

p h

p h.extract_keys    #=> [["a"], [1, 2, "e"], [1, 2, 300, 4], [1, 2, 3, 4], ["c"], [700, 4], [3, 4]]

p h.all_values      #=> ["b", "f", "value", "value", "d", "value", "value"]





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





paths = []

complex_hash = Hash[

  :a => { :aa => '1', :ab => '2' },

  :b => { :ba => '3', :bb => '4' }

]

complex_hash.each_path { |path, value| paths << [ path, value ] }



p paths    # => [[[:b, :ba], "3"], [[:b, :bb], "4"], [[:a, :ab], "2"], [[:a, :aa], "1"]]

puts





h = {"a"=>"b", "c"=>"d", 1=>{2=>{"e"=>"f", 3=>{4=>"value"}}}} 

h = {"a"=>"b", "l" => lambda { |x| x+1 }, 1=>{2=>{"e"=>"f", 3=>{4=>"value"}}}} 

h = {700=>{4=>"value"}, "a"=>"b", nil => "NILVALUE", 3=>{4=>"value"}, "c"=>"d", 1=>{2=>{"e"=>"f", 3=>{4=>"value"}, 300=>{4=>"value"}}}} 



p h

p h.extract_keys



keys = []

h.each_path { |path, value| keys << path }

p keys   # complete key sequences (with last key not pointing to another hash)



paths = []

h.each_path { |path, value| paths << [ path, value ] }

p paths   # complete key sequences plus values



vals = []

h.each_path { |path, value| vals << value }

p vals   # all values of complete key sequences



p h.all_values   # same

Factorial in Scheme

willpost () — Thu, 23 Mar 2006 12:59:22 GMT

;Calculate the factorial of a number
;(factorial 5) = 1 * 2 * 3 * 4 * 5 = 120
;(factorial 50) = 30414093201713378043612608166064768844377641568960512000000000000



(define factorial

  (lambda (n)

    (if (= n 0) 1

        (* n (factorial (- n 1))))))

pass variable as hidden

reynardmh () — Thu, 23 Mar 2006 01:37:50 GMT

pass variable as hidden field
recursively handles array
eg usage:
foreach ($_REQUEST as $key => $val)
pass_hidden($key, $val);

 

function pass_hidden($key, $val) {

  if (is_array($val)) {

    foreach ($val as $k => $v) 

      pass_hidden("{$key}[{$k}]", $v);

  } else {

    ?>

      }

}

Memoizing functions in JavaScript

keith (Keith Gaughan) — Fri, 22 Jul 2005 05:35:49 GMT

Here's something I knocked together a fortnight ago because I wanted to see if I could produce Perl's Memoize.pm in JavaScript.

Memoization is a method of increasing the speed of slow referentially transparent functions by caching their arguments and results. This trades a marginal amount of memory space for a potentially huge gain in speed.

Take the canonical definition of the fibonacci sequence, for instance:



function fib(n) {

    if (n < 2) {

        return n;

    }

    return fib(n - 1) + fib(n - 2);

}

As you can guess, this quickly becomes quite slow once you start using numbers greater than around 20. Once you're dealing with numbers in the mid-thirties range, it cripples the computer.

The solution is to memoize the function. You can either do it by hand:



var iterMemoFib = (function() {

    var cache = [1, 1];

    var fib = function(n) {

        if (n >= cache.length) {

            for (var i = cache.length; i <= n; i++) {

                cache[i] = cache[i - 2] + cache[i - 1];

            }

        }

        return cache[n];

    }



    return fib;

})();

Which is a wee bit of a pain and not exactly readable; or get the computer to do it for you:



fib = fib.memoize();

Due to technical (browser security) constraints, the arguments for memoized functions can only be arrays or scalar values. No objects.

The code extends the Function object to add the memoization functionality. If the function is a method, then you can pass the object into memoize().



Function.prototype.memoize = function() {

    var pad  = {};

    var self = this;

    var obj  = arguments.length > 0 ? arguments[i] : null;



    var memoizedFn = function() {

        // Copy the arguments object into an array: allows it to

        // be used as a cache key.

        var args = [];

        for (var i = 0; i < arguments.length; i++) {

            args[i] = arguments[i];

        }



        // Evaluate the memoized function if it hasn't been

        // evaluated with these arguments before.

        if (!(args in pad)) {

            pad[args] = self.apply(obj, arguments);

        }



        return pad[args];

    }



    memoizedFn.unmemoize = function() {

        return self;

    }



    return memoizedFn;

}



Function.prototype.unmemoize = function() {

    alert("Attempt to unmemoize an unmemoized function.");

    return null;

}