summaryrefslogtreecommitdiff
path: root/chapter25/docs/examples/Dijkstra.smp
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-08-20 10:56:30 -0700
committerCliff Click <cliffc@acm.org>2026-08-20 10:56:30 -0700
commit3568f3deed586327f885ac98b73d07ae3ade6e57 (patch)
treefce7865468dc9e2beabeb68342f23bfea5bdae1a /chapter25/docs/examples/Dijkstra.smp
parent1cb8279a64f4f79615ac8358927b11237df29bf2 (diff)
downloadSimple-3568f3deed586327f885ac98b73d07ae3ade6e57.tar.gz
Simple-3568f3deed586327f885ac98b73d07ae3ade6e57.zip
Squashed commit of the following:
commit c05d7df4f9c90984d2c04126772be3fee1d81fd1 Author: Cliff Click <cliffc@acm.org> Date: Thu Aug 20 10:52:58 2026 -0700 Fix local frefs, deferred inlining, and sys FileIO support - Defer non-trivial inlining out of CallEnd idealization and run it from IterPeeps after normal peepholes reach a fixed point. - Keep forward refs local to their lexical scope, promote them outward on scope pop, and track created FRefNodes directly for dependency discovery. - Preserve loop scope shape when frefs are first seen inside loop bodies. - Treat frefs as final constants from creation and force lazy self lookups before implicit calls. - Reset imported pointer/struct types conservatively for post-parse Iter. - Pin Start-owned global machine value chains and clone global constants per function during GCM. - Improve late ASM printing before encoding and namespace constant-pool symbols. - Add optional regalloc function-local edge verifier and improve empty-mask splitting for multi-def/fixed-register LRGs. - Add sys array compare, safer array copy bounds, libc open/creat/close/unlink bindings, aryu8.str0, and higher-level sys.io file operations. - Add docs/examples/FileIO.smp and a Chapter25 FileIO test. - Update spill/code-size goldens after the allocator and scheduling changes. commit ef5316979732ac118612d310b75923c8f59ecdc1 Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 16:29:56 2026 -0700 Dijkstra uses bitset. TestC.exec for repeated test runs with different stdins. Support &= and |= op-update forms. commit 728a527587f19bb49860f02ae5ac5968ab01ae33 Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 12:13:28 2026 -0700 Fix live demo commit e4c069b9ef2cbfafe28d8edfcbff55396cde085e Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 09:52:24 2026 -0700 Update Dijkstra.smp commit b8015739b4056e3f7a715a030e846a441021a9f1 Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 09:41:17 2026 -0700 Better looking Dijkstra commit 7cce587804c6169b24829e0b5bdc10be94357a31 Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 09:33:33 2026 -0700 Fix CmpMemX86 encoding Use sys.aryu8 for number printing commit 310b5d8c9978a3b09622a4b89dac97f0e5e6f3fb Author: Cliff Click <cliffc@acm.org> Date: Fri Aug 14 09:04:58 2026 -0700 Progress dijlstra Fix NotX86 encoding. Allow Not-sinking through Phis; the Nots both take Scalar and might take different types (ptr vs int). Better guard installing during && || opers. Drop the csv parse flavor in sys lib. commit 5917d5322521dd5e762c4698d34e5d7ac9b3a37f Author: Cliff Click <cliffc@acm.org> Date: Thu Aug 13 14:44:12 2026 -0700 missed commit da35ad4d8a330559a21c04ae6326536e0fd62c48 Author: Cliff Click <cliffc@acm.org> Date: Thu Aug 13 14:43:42 2026 -0700 Major cleanup of allocation All the graph-gen is moved to the <ctor> declaration and not at the alloc site. commit c4223216099ccbc526d282bb263972532d48c5b2 Author: Cliff Click <cliffc@acm.org> Date: Thu Aug 13 13:26:01 2026 -0700 Some work from Dykstra (more coming) commit a03bc567f61dc7e4355e453ee4be16ac2528d1ab Author: Cliff Click <cliffc@acm.org> Date: Thu Aug 13 09:32:55 2026 -0700 Spill correctness and improvements Had the callee-save pick-risky backwards vs cloneables. commit 2d306e4430225f916cb7fb999f4926e52f6fb70a Author: Cliff Click <cliffc@acm.org> Date: Wed Aug 12 19:40:04 2026 -0700 Tighter parser handling of missing fields Bug fix add libc.errno, read can return -1, sys.ary exists commit b7eeefda4cafa1e86153170dca6f13d45ef63f69 Author: Cliff Click <cliffc@acm.org> Date: Wed Aug 12 16:22:48 2026 -0700 Printer improvements commit 8b9112226f1d2d1c843b080eecefe0d5ddc1f8cf Author: Cliff Click <cliffc@acm.org> Date: Wed Aug 12 15:30:46 2026 -0700 Remove GLB commit ae566f5c610b9c30831906d3f024901d8930a227 Author: Cliff Click <cliffc@acm.org> Date: Wed Aug 12 14:38:51 2026 -0700 Add Capitalize example Rename Ary to ary. Fix bug || carrying state along. Fix bug load-array removing control. Add sys.char tolower/upper
Diffstat (limited to 'chapter25/docs/examples/Dijkstra.smp')
-rw-r--r--chapter25/docs/examples/Dijkstra.smp73
1 files changed, 73 insertions, 0 deletions
diff --git a/chapter25/docs/examples/Dijkstra.smp b/chapter25/docs/examples/Dijkstra.smp
new file mode 100644
index 00000000..57e1fad4
--- /dev/null
+++ b/chapter25/docs/examples/Dijkstra.smp
@@ -0,0 +1,73 @@
+// -*- mode: java; -*-
+
+// An implementation of
+// https://sampleprograms.io/projects/dijkstra/
+
+val shortestPath = { sys.aryi64 matrix, int nodes, int src, int dst ->
+ i64 infinity = (1 << 63)-1;
+ var dist = new i64[nodes];
+ var visited = new sys.adt.bitset();
+ // All nodes are infinitely far from each other
+ for( int i=0; i<nodes; i++ ) dist[i] = infinity;
+ // Starting point is zero far from starting point
+ dist[src] = 0;
+
+ i64 result = -1;
+ int count = 0;
+ while( count < nodes && result < 0 ) {
+ int nearest = -1;
+ i64 best = infinity;
+ for( int node=0; node<nodes; node++ )
+ if( !visited.get(node) && dist[node] < best ) {
+ nearest = node;
+ best = dist[node];
+ }
+ if( nearest < 0 ) count = nodes;
+ else {
+ if( nearest == dst ) return best;
+ visited.set(nearest);
+ for( int node=0; node<nodes; node++ ) {
+ i64 weight = matrix.get(nearest*nodes + node);
+ if( weight > 0 && !visited.get(node) && best+weight < dist[node] )
+ dist[node] = best+weight;
+ }
+ }
+ count++;
+ }
+ return result;
+};
+
+val usage = { ->
+ sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n");
+ return 0;
+};
+
+val main = { u8[~][] args ->
+ // Exactly 3 args
+ if( args# != 4 ) return usage();
+ // First is a serialized square matrix of positive numbers
+ var matrix = sys.aryi64.parseAryI64(args[1]);
+ if( !matrix ) return usage();
+ if( !matrix.len ) return usage();
+ // All numbers are positive
+ for( int i=0; i<matrix.len; i++ )
+ if( matrix.get(i) < 0 ) return usage();
+ // Matrix is square
+ int nodes = 0;
+ while( nodes*nodes < matrix.len ) nodes++;
+ if( nodes*nodes != matrix.len )
+ return usage(); // Not a square matrix
+
+ // src,dst are values within the matrix
+ i64 src = sys.aryu8.atoi(args[2]);
+ i64 dst = sys.aryu8.atoi(args[3]);
+ if( src < 0 || src >= nodes || dst < 0 || dst >= nodes )
+ return usage(); // Source and destination land within the graph
+
+ i64 cost = shortestPath(matrix,nodes,src,dst);
+ if( cost >= 0 ) {
+ new sys.aryu8().num(cost).add('\n').write(1);
+ return 0;
+ }
+ return usage();
+};