recursive snippets

Find a text pattern in jar files

Tagged jar, find, search, recursive, linux, unzip  Languages bash

Helpful when you need to find a class or package in some jar file recursively below the current directory. Still needs a test to see if the file found was a file or directory. Works case insensitively. Uses the unzip command because of it's performance superiority in comparison to jar.

#!/bin/sh
for f in find . -type f -name '*\.jar'
do
        unzip -l $f | grep -i $1 && echo "was found in $f"
done

Recursively add files to ClearCase

Tagged add, recursive, clearcase, ruby, script  Languages ruby

This script adds all files in the current directory to ClearCase.

Save the following script as add_recursively.rb in the directory you want to add to ClearCase:

%x{cleartool ls -view_only -r -s . > view_private_files.txt}

lines = File.open('view_private_files.txt').readlines.collect{|line| %Q{"#{line.chomp}"} }

# Work around command line length limit in Windows
while lines.size > 0
  %x{cleardlg /addtosrc #{lines.slice!(0..100).join(' ')}}
end

Next open a command line window and execute the script:

cd clearcase_vob
ruby add_recursively.rb

ClearCase sucks, use Mercurial or git instead...

Recurse through a Ruby tree

Tagged recursive, tree, category, ruby  Languages css

The model:

class Category
...
  def recurse
    yield(self)

    children.each do |child|
      child.recurse {|sibling| yield sibling}
    end
  end
end

The recusion:

Category.root.recurse do |child|
  puts child
end

Recursive Postgres Query That Finds Descendants of a Node in a Tree

Tagged tree, parent, descendants, child, recursive, postgres, cte  Languages sql

The recursive query:

WITH RECURSIVE tree AS (
  SELECT id, name, parent_id FROM nodes WHERE id = 25
  UNION ALL
  SELECT nodes.id, nodes.name, nodes.parent_id FROM nodes, tree WHERE nodes.parent_id = tree.id)

This is where we define a virtual table called tree:

WITH RECURSIVE tree

This SQL finds the root node and initializes the recursive function:

SELECT id, name, parent_id FROM nodes WHERE id = 25

The next part recursively fetches the descendants of the specified node:

SELECT nodes.id, nodes.name, nodes.parent_id FROM nodes, tree WHERE nodes.parent_id = tree.id)

This SQL query shows the descendants, and the parent which has an ID of 25:

SELECT * FROM tree;

In Ruby you could use this code to generate your SQL:

def tree_sql(opts={})
    table = opts.fetch(:table) # e.g. 'categories'
    cols = opts.fetch(:cols) # e.g. %w(id name)
    <<-SQL
      WITH RECURSIVE #{table}_tree AS (
        -- initialize
        SELECT
          #{cols.join(', ')}, 0 as n_depth
        FROM
          #{table}
        WHERE
          -- Use bind variables and ? here if you want
          id = #{parent_id}
        UNION ALL
          -- iterate
          SELECT
            #{cols.map { |col| "#{table}.#{col}" }.join(', ')}, n_depth +1
          FROM
            #{table}, #{table}_tree
          WHERE
            #{table}.parent_id = #{table}_tree.id)
    SQL
  end

In Rails you probably want the method to return an ActiveRecord::Relation object so you can chain e.g. pagination, order, and limit method calls. One way of doing that is shown here:

class User
  def descendants
      ids_query = User.select('users.id') # return only ids
         .joins(:memberships)
        .group('users.id') # avoid duplicates
        .where("memberships.organization_id in (#{tree_sql})", organization).to_sql
      User.where("id in (#{ids_query})")
  end
end

Details: * Use UNION instead of UNION ALL if you have duplicates, or if you're not worried about performance when Postgres has to scan for duplicates. * WITH Queries in Postgres * Recursive queries can loop indefinitely if e.g. self.parent = self. If this happens, use the ANY() function to check if path has been visited once already. Alternatively, use validations to make sure circular references don't happen, and hope for the best. * Use Arel's recursive feature to generate recursive CTE queries with Arel.

Recursive queries with connectby in Postgres

Tagged postgres, recursive, connectby  Languages sql

Create an organization hierarchy and display the organization from the top:

CREATE EXTENSION "tablefunc";
CREATE TABLE organizations(id text, parent_id text, pos int);

INSERT INTO organizations VALUES('row1',NULL, 0);
INSERT INTO organizations VALUES('row2','row1', 0);
INSERT INTO organizations VALUES('row3','row1', 0);
INSERT INTO organizations VALUES('row4','row2', 1);
INSERT INTO organizations VALUES('row5','row2', 0);
INSERT INTO organizations VALUES('row6','row4', 0);
INSERT INTO organizations VALUES('row7','row3', 0);
INSERT INTO organizations VALUES('row8','row6', 0);
INSERT INTO organizations VALUES('row9','row5', 0);

-- Fetch self and descendants for row1
SELECT * FROM connectby('organizations', 'id', 'parent_id', 'row1', 0, '~') AS t(id text, parent_id text, level int, branch text);

Output:

id  | parent_id | level |          branch
------+-----------+-------+--------------------------
 row1 |           |     0 | row1
 row2 | row1      |     1 | row1~row2
 row4 | row2      |     2 | row1~row2~row4
 row6 | row4      |     3 | row1~row2~row4~row6
 row8 | row6      |     4 | row1~row2~row4~row6~row8
 row5 | row2      |     2 | row1~row2~row5
 row9 | row5      |     3 | row1~row2~row5~row9
 row3 | row1      |     1 | row1~row3
 row7 | row3      |     2 | row1~row3~row7

Usually it's better to use recursive CTE queries:

WITH RECURSIVE organization_tree AS (
  SELECT 
    id, parent_id 
  FROM
    organizations
  WHERE
    id = 'row1'
UNION ALL
  SELECT 
    organizations.id, organizations.parent_id 
  FROM 
    organizations, organization_tree
  WHERE
    organizations.parent_id = organization_tree.id
) select * from organization_tree;