Topological Sort

First publish: https://rosettacode.org/wiki/Topological_sort 

We want to find an order for libraries for a linker, based on the dependencies, as they deescribed in the following table.

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

If we place at dw04 a dependecy of dw01 then the above data would be un-orderable.

For the solution we use the current stack of values, and inventories (lists of keys/values). First we flush the stack (empty=true). a (listL=1,2,3) return an inventory list, with keys 1,2,3 and values 1,2,3 (when a key has no value, then return the key as value, until we place a value through Return statement). Inventories (List type and Queue type, which handle same keys)  use hash tables, so they have O(1) for append, search and delete. Queue delete from the last insert only using a drop mechanism. Item's place (or index)  may change if we delete an item.

First pass on LL list

We check every item in LL through iterator mm, which an Each(LL) produce, and a While process it. Each item is a list also. So we check if an item in this LL item's list exist in LL, and if not we place it to final list (final is a know word for M2000,  used as a clause for definitions inside groups, so we can use it as a variable). We place "" as mark, so the value now on that item ins't the key but the empty string. The exist() function, when we place a list as first argument, set an internal index to where the key exist, when the function return true, so if we find the key k1$ in LL we just get the pointer of the list at that key mmmm=Eval(LL) , without searching the internal hash table again. We chack if k1$ not exist in final, and if not  we place it. Last we place ab enpry string as value to k1$ key in m list (which we get from LL, base on mm iterator), 

From first path we get any library which not have a key in LL. Those libraries have no dependencies on the above table. At that point a statement Sort final may sort the names, but this isn't what we want.

Second pass on LL list

Now our LL list has lists which have libraries, with dependencies, which means they have a key in LL.We make a new mm as Each(LL), as iterator for LL. If the name of the key exist in final then that means there is no need to process (Why?) so the continue statement skip the statements until End While. If not, then we get m List from Eval(mm), and start a new a new While loop using the mmm iterator. 

So the first While loop inside the LL iteration just add the dependencies to stack if not exist in final, for further process. We use Data statement which append to end or bottom of stack (always we read from start or top), so Data is a statement which use the stack as FIFO. So stack get Libraries which not chacked to final list.

The second While loop depend of stack values, which the previous process place to it (if any). We use Read k1$ to pop the value (from top or start of stack values). We check always if the name exist in final list (because the stack may have this more than one time), and if exist just continue the loop for other indexes. So now, we don't find k1$ in final list and we use it  to get the list m from LL(k1$). See also p we assign delthis a value 0, just before entering the  next While loop (inner one more). 

At the third inner loop, we check the k2$, which is the value from the current item  which is the name of key or an empty string. We have three continue, if k2$="", if k2$=k1$, if k2$ exist in final. If no one from these is true then we push the k2$ to stack (Push place values to top of stack, as LIFO, so the last will be processed first)., also we place to m at k$ key the value "" (empty string). Also we increase the value of delthis by one.

After the third inner loop ends, an if check if delthis is zero. If it is zero, means that the previous loop didn't push something to stack, but has something on it. So we check all keys, as K2$ (the previous  loop check the values, which sometime was equal to keys) and if pass the k2$=k1$ (as false), and not exist k2$  in final, we found the Unsorted k2$, k1$. After the iteration we append k1$ to final and set k1$:=list (empty list) . So if there is no dependencies in stack, we just exit to outer loop, we check if k$ (the key from LL which we process until now), isn't in final and we append to final if not.

After all LL lists processed we make a string for outpit.See the Final$(expr!) return the key at index expr. The eval$(ret) return the key if the value is an object.

we can remove the REM, in line REM append LL, "dw01":=(List:="dw04","ieee", "dw01", "dware", "gtech"), and put a REM in next line, so we place the dw04 as dependency of dw01, so we get the message: unsorted: dw01 dw04

Module testthis {
	\\ empty stack
	Flush
	inventory LL
	append LL, "des_system_lib":=(List:="std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01",  "ramlib", "ieee")
REM	append LL, "dw01":=(List:="dw04","ieee", "dw01", "dware", "gtech")
	append LL, "dw01":=(List:="ieee", "dw01", "dware", "gtech")
	append LL, "dw02":=(List:="ieee", "dw02", "dware")
	append LL, "dw03":=(List:="std", "synopsys", "dware", "dw03", "dw02", "dw01", "ieee", "gtech")
	append LL, "dw04":=(List:= "ieee", "dw01", "dware", "gtech")
	append LL, "dw05":=(List:="dw05", "ieee", "dware")
	append LL, "dw06":=(List:="dw06", "ieee", "dware")
	append LL, "dw07":=(List:="ieee", "dware")
	append LL, "dware":=(List:="ieee", "dware")
	append LL, "gtech":=(List:="ieee", "gtech")
	append LL, "ramlib":=(List:="std", "ieee")
	append LL, "std_cell_lib":=(List:="ieee", "std_cell_lib")
	append LL, "synopsys":=List
	\\ inventory itmes may have keys/items or keys.
	\\ here we have keys so keys return as item also
	\\ when we place an item in a key (an empty string) ...
	\\ we mark the item to not return the key but an empty string
	inventory final
	mm=each(LL)
	while mm
		m=eval(mm)
		mmm=each(m)
		While mmm
			k1$=eval$(mmm!)
			if not exist(LL, k1$) then
				if not exist(final, k1$) then append final, k1$
				return m, k1$:=""      \\ mark that item
			else
				mmmm=Eval(LL)
				if len(mmmm)=0 then
					if not exist(final, k1$) then append final, k1$
					return m, k1$:=""     \\ mark that item
				end if
			end if
		end while
	end while
	print final
	mm=each(LL)
	while mm
		\\ using eval$(mm!) we read the key as string
		k$=eval$(mm!)
		if exist(final, k$) then continue
		m=eval(mm)
		mmm=each(m)
		While mmm
			\\ we read the item, if no item exist we get the key
			k1$=eval$(mmm)
			if k1$="" then continue
			if exist(final, k1$) then  continue
			data k1$    \\ push to end to stack
		end while
		// print final
		while not empty
			read k1$
			if exist(final, k1$) then continue
			m=LL(k1$)
			mmm=each(m)
			delthis=0
			While mmm
				k2$=eval$(mmm)
				if k2$="" then continue
				if k1$=k2$ then continue
				if exist(final, k2$) then continue
				push k2$   \\ push to top of stack
				return m, k2$:=""
				delthis++
			end while
			if delthis=0 then
				mmm=each(m)
				While mmm
					k2$=eval$(mmm!)
					if k2$=k1$ then continue
					if exist(final, k2$) Else
						Print "unsorted:";k1$, k2$
					end if
				end while
		 		append final, k1$ : Return LL, k1$:=List
			end if
		end while
		if not exist(final, k$) then append final, k$
	end while
	document doc$
	ret=each(final,1, -2)
	while ret
		doc$=eval$(ret)+" -> "
	end while
	doc$=final$(len(final)-1!)
	Report doc$
	clipboard doc$
}
testthis