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, ruby

Voilà, the recursive query we are going disect in this snippet:

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)

Here 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 root node:

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

This SQL query fetches the root node and all its descendants from the tree:

SELECT * FROM tree;

ActiveRecord / Rails

This example shows how to use CTEs in ActiveRecord to find the parent and suborganizations in a conglomerate:

class Organization
  belongs_to :parent, class_name: 'Organization', required: false
  has_many :children, class_name: 'Organization', foreign_key: :parent_id
  scope :roots, -> { where(parent_id: nil) }
  
  def ancestors(id, columns=Organization.column_names)
    cols = columns.join(', ')
    child_id = ActiveRecord::Base.connection.quote(id)
    Organization.from <<~SQL
      (WITH RECURSIVE org_tree(#{cols}, path) AS (
        SELECT
          #{cols}, ARRAY[id]
        FROM
          organizations
        WHERE
          id = #{child_id}
      UNION ALL
        SELECT
          #{columns.map { |col| "organizations.#{col}" }.join(', ') }, path || organizations.id
        FROM
          org_tree
        JOIN
          organizations ON organizations.id = org_tree.parent_id
        WHERE NOT
          organizations.id = ANY(path) -- avoid infinite loops where e.g. parent = self
      ) SELECT #{cols} FROM org_tree WHERE id != #{child_id}) as organizations
    SQL
  end

  def descendants(id, columns=Organization.column_names)
    cols = columns.join(', ')
    parent_id = ActiveRecord::Base.connection.quote(id)
    Organization.from <<~SQL
      (WITH RECURSIVE org_tree(#{cols}, path) AS (
        SELECT
          #{cols}, ARRAY[id]
        FROM
          organizations
        WHERE
          id = #{parent_id}
      UNION ALL
        SELECT
          #{columns.map { |col| "organizations.#{col}" }.join(', ') }, path || organizations.id
        FROM
          org_tree
        JOIN
          organizations ON organizations.parent_id = org_tree.id
        WHERE NOT
          organizations.id = ANY(path) -- avoid infinite loops where e.g. parent = self
      ) SELECT #{cols} FROM org_tree WHERE id != #{parent_id}) as organizations
    SQL
  end
end
# Find parent companies
Organization.find(1).ancestors
# Find suborganizations
Organization.find(1).descendants

Details

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;