
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort




Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.

The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on.

A tool exists that extracts library dependencies.



Task

Write a function that will return a valid compile order of VHDL libraries from their dependencies.

 Assume library names are single words. 
 Items mentioned as only dependents, (sic), have no dependents of their own, but their order of compiling must be given.
 Any self dependencies should be ignored. 
 Any un-orderable dependencies should be flagged.


Use the following data as an example:

LIBRARY          LIBRARY DEPENDENCIES
=======          ====================
des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys


Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.



C.f.

   Topological sort/Extracted top item.


There are two popular algorithms for topological sorting:

   Kahn's 1962 topological sort [1] 
   depth-first search [2] [3]


 
'TOPOLOGICAL SORT
 
uses parseutil 'getword() lenw
uses console
 
string dat="
LIBRARY          LIBRARY DEPENDENCIES
=======          ====================
des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys
"
gosub Dims
gosub CaptureData
gosub GetSystemLibs
gosub RemoveSelfReference
gosub OrderByDependency
gosub DisplayResults
end
 
/*RESULTS:
  libraries in dependency order
  -----------------------------
  std
  ieee
  dware
  gtech
  ramlib
  std_cell_lib
  synopsys
  dw01
  dw02
  des_system_lib
  dw03
  dw04
  dw05
  dw06
  dw07
<<
 
  remainder:
  ----------
  <<
*/
 
 
 
Dims:
=====
'VARIABLES
int p           'width of first column
int h           'length of each line
int i           'iterator / counter
int j           'main iterator
int b           'table char offset
int e           'end of each line
int bd          'each offset of dependencises line
int le          'length of each lib name
int lend        'size of table
int k           'character indexer
int m           'iterator
int n           'iterator
int cw          'presence flag
int lw          'length of keyword  
int a           'iinstr result
int dc          'new lib list indexer / counter
string wr       'keyword
string wn       'keyword
'--arrays--
string datl[64] 'list of lib names
string datd[64] 'lists of lib dependencies
string datn[64] 'new list in dependency ordert
ret
 
 
CaptureData:
============
dat=lcase dat
'GET HEADING POSITION
p=instr dat,"library depend"
p-=3 'crlf -1
'REMOVE HEADING
h=instr 3,dat,cr
h+=2
h=instr h,dat,cr 'to remove underlines
'print h cr
h+=2
dat=mid dat,h
'print dat "<" cr
b=1
'PREPARE DATA
lend=len dat
do
  i++
  datl[i]=rtrim(mid(dat,b,p))
  le=len datl[i]
  e=instr b+le,dat,cr
  bd=b+p
  datd[i]=" "+mid(dat,bd,e-bd)+" "
  'print datl[i] "," datd[i] cr
  b=e+2
  if b>lend-2
    exit do
  endif
loop
ret
 
GetSystemLibs:
==============
'SCAN DEPENDENCIES
'GET SYSTEM LIBS NOT LISTED
for j=1 to i
  k=1
  do
    wr=getword datd[j],k
    if not wr
      exit do
    endif
    cw=0
    for m=1 to i
      if wr=datl[m] 'on lib list
        cw=m
      endif
    next
    if cw=0 'lib not on library list
      'add wr to new lib list
      dc++ : datn[dc]=wr
      'remove lib names from dependency lists
      gosub BlankOutNames
    endif
  loop
next 'j group of dependencies
ret
 
 
RemoveSelfReference:
====================
'REMOVE SELF REFERENCE + NO DEPENDENCIES
for j=1 to i
  wr=" "+datl[j]+" "
  lw=len(wr)
  a=instr(datd[j],wr)
  if a
    mid(datd[j],a,space(lw)) 'blank out self
  endif
  gosub RemoveLibFromLists
next
ret
'
OrderByDependency:
==================
'
for j=1 to i
  if datl[j]
    gosub RemoveLibFromLists
    if cw then j=0 'repeat cycle
  endif
next
ret
'
DisplayResults:
===============
print cr cr
print "libraries in dependency order" cr
print "-----------------------------" cr
for j=1 to dc
  print datn[j] cr
next
print "<<" cr cr
print "remainder:" cr
print "----------" cr
for j=1 to i
  if datl[j]
    print datl[j] " , " datd[j] cr
  endif
next
print "<<" cr
 
pause
end
 
RemoveLibFromLists:
===================
cw=0
k=1 : wr=getword datd[j],k
if lenw=0
  dc++ : datn[dc]=datl[j] 'add to new lib list
  datl[j]="" : datd[j]="" 'eliminate frecord rom further checks
  gosub BlankOutNames     'eliminate all lib references from table
  cw=1                    'flag alteration
endif
ret
 
BlankOutNames:
==============
wn=" "+datn[dc]+" " 'add word boundaries
lw=len wn
for n=1 to i
  if datd[n]
    a=instr(datd[n],wn)
    if a
      mid datd[n],a,space(lw) 'blank out
      endif
  endif
next
ret
 