#!/bin/sh
# Find an order of loading tables with referential dependencies
# Uses dbaccess, awk, sh.
# Note: name of awk may have to be adjusted for your system (nawk).
# Algorithm of depth first sort of directed graph
# from AWK by Aho,Kernigan, W...
#

usage () {
    echo
    echo 'Usage: '$0 '[order|child|parent] database [table]'
    echo 'Example: '$0 'order project2'
    echo 'Example: '$0 'child project2 organization'
    echo 'Example: '$0 'parent project2 organization'
    echo '"order" lists a loading order of tables to comply with constraints.'
    echo '"child" lists children of a table in a loadable order.'
    echo '"parent" lists parents of a table in a loadable order.'
    echo
    exit 1
}

# Query for finding referential dependency pairs.
# Usage: $0 database_name
ref_sql () {
DB=$1

# remove blanks, duplicates
$INFORMIXDIR/bin/dbaccess << EOF | sed '/^$/d'
    database $DB;
    output to pipe "sort -u" without headings
    select a.tabname, b.tabname
    from "informix".sysreferences r, "informix".systables a,
    "informix".systables b, "informix".sysconstraints c
    where r.ptabid = a.tabid
    and c.tabid = b.tabid
    and c.constrid = r.constrid;
EOF
}

# Depth first sort of directed graph.
# input: pairs of names representing dependency:  name  name
# use in pipeline: ref_sql| ref_parent NAME| rtsort| reverse
# output in reversed order.
rtsort () {
nawk '
{ if (!($1 in pcnt))
     pcnt[$1] = 0
  pcnt[$2]++
  slist[$1, ++scnt[$1]] = $2
}

END { for (node in pcnt) {
          nodecnt++
          if (pcnt[node] == 0)
              rtsort(node)
      }
      if (pncnt != nodecnt) {
          print "error: input contains a cycle"
          print "node: ",node
      }
      printf("\n")
    }

function rtsort(node, i, s) {
    visited[node] = 1
    for ( i = 1; i <= scnt[node]; i++)
        if (visited[s = slist[node, i]] == 0)
            rtsort(s)
        else if (visited[s] == 1)
            printf("error: nodes %s and %s are in a cycle\n",s,node)
    visited[node] = 2
    printf("%s\n", node)
    pncnt++
}'
}

# Reverse order of lines input.
reverse () {
    nawk '{ x[NR] = $0}
          END { for (i = NR; i > 0; i--) print x[i] }'
}

# input list of referential dependency pairs
# usage: ref_parent <name>
# output: tree of parent dependency pairs on name
# use in pipeline: ref_sql | ref_parent NAME | rtsort | reverse
# Note: recursive function tree_parent, will explode
# harmlessly with circular graph.
# use rtsort to depth first search the dependency tree, sort
# and find cycles.
# Usage: ref_parent <name>'
ref_parent () {
    # In BEGIN is trick to set variables.
    nawk 'BEGIN { start_node=ARGV[2]; ARGC = ARGC-1;}
    { nlist[++cnt] = $0; }
    END { tree_parent(start_node) }

    function tree_parent(newnode) {
        for ( node in nlist) {
              split(nlist[node],refs);
              if (newnode == refs[2]){
                  print nlist[node];
                  tree_parent(refs[1]);
              }
        }
    }' - $1
}

# input list of referential dependency pairs
# usage: ref_child <name>
# output: tree of child dependency on name
# use in pipeline:   ref_sql | ref_child NAME | rtsort | reverse
# Note: recursive function tree_child, will explode
# harmlessly with circular graph.
# use rtsort to depth first search the dependency tree, sort
# and find cycles.
# Usage: ref_child <name>'
ref_child () {
    test $# -ne 1 && usage
    # In BEGIN is trick to set variables.
    nawk 'BEGIN { start_node=ARGV[2]; ARGC = ARGC-1;}
      {nlist[++cnt] = $0;}
    END { tree_child(start_node) }

    function tree_child(newnode) {
        for ( node in nlist) {
              split(nlist[node],refs);
              if (newnode == refs[1]){
                  print nlist[node];
                  tree_child(refs[2]);
              }
        }
    }' - $1
}

order () {
    ref_sql $1 | rtsort | reverse
}

child () {
    ref_sql $1 | ref_child $2 | rtsort | reverse
}

parent () {
    ref_sql $1 | ref_parent $2 | rtsort | reverse
}

##############################################
# Main

    case $# in
        2|3 ) $1 $2 $3 ;;
         * ) usage ;;
    esac