recursive code

Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

« Newer Snippets

Older Snippets »

Showing 1-10 of 15 total RSS

Numbering left and right attributes of a nested set

Uses a hash to model a tree that numbers the left and right attributes of a nested set.

# test case for depth_first traversal
#
# tree = { :electronics => {
# :televisions => { :tube => {},
# :lcd => {},
# :plasma => {} },
# :portable_elec => { :mp3_players => {
# :flash => { }
# },
# :cd_player => { },
# :two_way_radio => { }
# }
# }
# }
#
# tree.depth_first do |name, parent_name, lft, rgt|
# puts "#{parent_name}/#{name}: #{lft} - #{rgt}"
# end

class Hash
  def depth_first(&block)
    root_node = self.keys.first
    root_children = self[root_node]
    depth_first_helper(root_node, root_children, nil, 1, &block)
  end

  private
  def depth_first_helper(name, children, parent_name, lft, &block)
    if children.empty?
      rgt = lft + 1
    else
      children_lft = lft + 1
      children.each do |child_name, grandchildren|
        rgt = depth_first_helper(child_name, grandchildren, name, children_lft, &block)
        children_lft = rgt
      end
    end
    block.call(name, parent_name, lft, rgt)
    return rgt + 1
  end
end

to recursive tree by iamwil on Jun 06, 2008

Hash#deep_delete


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)   #=> []

to ruby hash recursive delete deep by ntk on Nov 01, 2007

Hash#deep_merge


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

to ruby hash recursive merge deep by ntk on Oct 27, 2007

Tower of Hanoi

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

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

#include <stdio.h>

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

to c recursive divide et impera by scvalex on Sep 28, 2007

Recursively dump imbricated Map of Maps

// 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);
            }
        }
    }

to recursive iterate key map value by Archanciel on Sep 12, 2007

Recursively find files by filename pattern.

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);
    }
  }
}

to php find recursive file by troelskn on Jun 15, 2007

Find every path and it's value in a Hash

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

to ruby hash recursive parsing by boof on Feb 22, 2007

Extracting all keys from a multi-dimensional hash

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

to ruby hash recursive key extract dimension multi-dimensional by ntk on Apr 12, 2006 5 Comments

Factorial in Scheme

;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))))))

to recursive math scheme Factorial by willpost on Mar 23, 2006

pass variable as hidden

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 {
    ?><input type="hidden" name="<?=$key?>" value="<?=htmlspecialchars($val)?>">
    <?
  }
}

to php recursive by reynardmh on Mar 22, 2006