73f706576cc7 — Leonard Ritter a month ago
* improved toposort
2 files changed, 52 insertions(+), 49 deletions(-)

M testing/test_node2.sc
M testing/toposort.sc
M testing/test_node2.sc +0 -1
@@ 1729,7 1729,6 @@ static-if main-module?
             merge
                 then exit? (constString "exiting...\n")
                 else exit? readline
-            #if exit? (constString "exiting...\n") readline
 
     #'toposort module
     #'catsort module

          
M testing/toposort.sc +52 -48
@@ 1,51 1,52 @@ 
 
-using import Set
+using import Map
 using import Array
 using import Rc
 
-inline topowalker (edgef visitf)
-    fn (vertices ctx...)
-        """"call `visitf` for each vertex in generator `vertices` in topological
-            order. `edgef` must return a generator for each provided vertex index,
-            which provides vertex indices of incoming edges. The generators must
-            be of same iterator type.
+inline topowalk (T edgef visitf)
+    local stack : (Array T)
+    local state : (Map T i32)
 
-            vertex indices may be sparse and must be of type `usize`. `vertices`
-            may only contain a subset of indices in the graph.
-        let vinit vvalid vat vnext = ((vertices as Generator))
-        let it... = (vinit)
-        if (not (vvalid it...))
-            return;
-        let first = (vat it...)
-        let it... = (vnext it...)
-        let init valid at next = (((edgef first ctx...) as Generator))
-        local stack : (Array (tuple usize (va-map typeof (init))))
-        local visited : (Set usize)
+    fn visit (vx stack state ctx...)
+        """"call `visitf` for each vertex connected to `vx` in topological order.
+            `edgef` is provided a vertex and a function which should be called
+            for each incoming vertex.
+
+            vertices may be sparse and must be of type `T`.
+        let STATE_UNSEEN = 0
+        let STATE_QUEUED = 1
+        let STATE_COMPLETE = 2
+
+        inline vstate (v)
+            'getdefault state v STATE_UNSEEN
 
-        for vx in vertices
-            vx as:= usize
-            if (not (vx in visited))
-                'insert visited vx
-                'append stack (tupleof vx ((((edgef vx ctx...) as Generator))))
-                while (not (empty? stack))
-                    let v it... = (unpack ('last stack))
-                    let init valid at next = (((edgef v) as Generator))
-                    if (valid it...)
-                        let vx = (at it...)
-                        vx as:= usize
-                        let nextit... = (next it...)
-                        va-map
-                            inline (i)
-                                (va@ i it...) = (va@ i nextit...)
-                            va-range (va-countof it...)
-                        if (not (vx in visited))
-                            'insert visited vx
-                            'append stack
-                                tupleof vx ((((edgef vx ctx...) as Generator)))
-                    else
-                        'pop stack
-                        visitf v ctx...
-                        ;
+        inline push_vertex (v)
+            if ((vstate v) == STATE_UNSEEN)
+                'append stack v
+        push_vertex vx
+        while (not (empty? stack))
+            let v = ('last stack)
+            switch (vstate v)
+            case STATE_UNSEEN # not yet seen
+                'set state v STATE_QUEUED
+                let stackp1 = (countof stack)
+                edgef v push_vertex ctx...
+                let stackp2 = (countof stack)
+                m := (stackp1 + stackp2) >> 1
+                rend := stackp2 + stackp1 - 1
+                # swap stack order
+                for i in (range stackp1 m)
+                    swap (stack @ i) (stack @ (rend - i))
+            case STATE_QUEUED # children previously queued
+                'set state v STATE_COMPLETE
+                'pop stack
+                visitf v ctx...
+            pass STATE_COMPLETE # completed, ignore
+            default
+                'pop stack
+
+    inline (vx ctx...)
+        visit vx stack state ctx...
 
 global arr : (Array (Rc (Array i32)))
 fn addnode (arr edges...)

          
@@ 72,13 73,16 @@ addnode; # 10
 addnode 12 # 11
 addnode; # 12
 
+# correct order:
+# 10 12 11 9 4 6 7 8 1 5 3 2 0
 
-local sinks = (arrayof usize 0:usize)
-let walk =
-    topowalker
-        inline (vertex)
-            ((arr @ vertex) as Generator)
+let walker =
+    topowalk i32
+        inline (vertex f)
+            for v in (arr @ vertex)
+                f v
         inline (vertex)
             print vertex
-walk sinks
+walker 8
+walker 0