Count with for i in a .. b, break, nest fors and let an event's own lists (Pure 018)

2 files changed, 182 insertions, 0 deletions

diff --git a/examples/numbers.aup b/examples/numbers.aup
new file mode 100644
index 0000000..3352993
--- /dev/null
+++ b/examples/numbers.aup
@@ -0,0 +1,62 @@
+# Numbers worked out in one event (Pure 018): a square root by Newton's
+# steps, stopping when they stop shrinking, and the best a knapsack holds,
+# its table an event's list.
+record Item {
+  id = 0
+  weight = 0
+  worth = 0
+}
+record Cell {
+  at = 0
+  best = 0
+}
+state items: list of Item by id
+state root = 0
+state steps = 0
+state packed = 0
+input stock = message {
+  id: u32
+  weight: u32
+  worth: u32
+}
+input sqrt = message {
+  x: number
+}
+input pack = message {
+  capacity: u32
+}
+
+on stock {
+  items.add(Item { id: stock.id, weight: stock.weight, worth: stock.worth })
+}
+
+on sqrt {
+  let r = if sqrt.x > 1 { sqrt.x } else { 1 }
+  steps = 0
+  for i in 0 .. 200 {
+    let next = (r + sqrt.x / r) / 2
+    if next >= r { break }
+    r = next
+    steps = steps + 1
+  }
+  root = r
+}
+
+on pack {
+  let table: list of Cell by at
+  for c in 0 .. pack.capacity + 1 {
+    table.add(Cell { at: c })
+  }
+  for it in items {
+    for k in 0 .. pack.capacity + 1 {
+      let c = pack.capacity - k
+      if c >= it.weight {
+        let with = table[c - it.weight].best + it.worth
+        if with > table[c].best { table[c].best = with }
+      }
+    }
+  }
+  packed = table[pack.capacity].best
+}
+
+view answer = "root {root} in {steps} steps, packed {packed}"
diff --git a/examples/routes.aup b/examples/routes.aup
new file mode 100644
index 0000000..6656947
--- /dev/null
+++ b/examples/routes.aup
@@ -0,0 +1,120 @@
+# Routes over a graph in one event each (Pure 018): breadth first, depth
+# first and the nearest by weight. A node's edges are a slice of the edges
+# list (keyed by from * 1048576 + to); the searches keep their queues and
+# what they have seen in the event's own lists, gone when it ends.
+record Node {
+  id = 0
+}
+record Edge {
+  link = 0
+  to = 0
+  w = 1
+}
+record Seen {
+  node = 0
+  depth = 0
+}
+record Step {
+  node = 0
+}
+record Pending {
+  rank = 0
+}
+state nodes: list of Node by id
+state edges: list of Edge by link
+state hops = -1
+state visited = 0
+state order = 0
+state shortest = -1
+input link = message {
+  from: u32
+  to: u32
+  w: u32
+}
+input route = message {
+  from: u32
+  to: u32
+}
+input walk = message {
+  from: u32
+}
+input path = message {
+  from: u32
+  to: u32
+}
+
+on link {
+  if !nodes.has(link.from) { nodes.add(Node { id: link.from }) }
+  if !nodes.has(link.to) { nodes.add(Node { id: link.to }) }
+  edges.add(Edge { link: link.from * 1048576 + link.to, to: link.to, w: link.w })
+}
+
+# Breadth first: the queue is read by position, every node enters it once.
+on route {
+  let seen: list of Seen by node
+  let queue: list of Step
+  queue.append(Step { node: route.from })
+  seen.add(Seen { node: route.from })
+  for i in 0 .. nodes.count {
+    if i >= queue.count { break }
+    let q = queue.first + i
+    for e in edges[q.node * 1048576 .. q.node * 1048576 + 1048576] {
+      if !seen.has(e.to) {
+        seen.add(Seen { node: e.to, depth: seen[q.node].depth + 1 })
+        queue.append(Step { node: e.to })
+      }
+    }
+  }
+  hops = if seen.has(route.to) { seen[route.to].depth } else { -1 }
+}
+
+# Depth first: a stack, each edge pushed once at most; depth is the order a node was reached in.
+on walk {
+  let seen: list of Seen by node
+  let stack: list of Step
+  stack.append(Step { node: walk.from })
+  let reached = 0
+  for i in 0 .. edges.count + 1 {
+    if stack.count == 0 { break }
+    let v = stack.last.node
+    stack.remove(stack.last)
+    if !seen.has(v) {
+      seen.add(Seen { node: v, depth: reached })
+      reached = reached + 1
+      for e in edges[v * 1048576 .. v * 1048576 + 1048576] {
+        if !seen.has(e.to) { stack.append(Step { node: e.to }) }
+      }
+    }
+  }
+  visited = seen.count
+  order = sum(s.depth * (s.node + 1) for s in seen)
+}
+
+# The nearest by weight (Dijkstra): pending ranks by dist * 1048576 + node, the nearest first.
+on path {
+  let best: list of Seen by node
+  let pending: list of Pending by rank
+  best.add(Seen { node: path.from })
+  pending.add(Pending { rank: path.from })
+  for i in 0 .. edges.count + 1 {
+    if pending.count == 0 { break }
+    let d = floor(pending.first.rank / 1048576)
+    let v = pending.first.rank - d * 1048576
+    pending.remove(pending.first)
+    if best[v].depth == d {
+      for e in edges[v * 1048576 .. v * 1048576 + 1048576] {
+        let far = d + e.w
+        if !best.has(e.to) {
+          best.add(Seen { node: e.to, depth: far })
+          pending.add(Pending { rank: far * 1048576 + e.to })
+        } else if far < best[e.to].depth {
+          best[e.to].depth = far
+          pending.add(Pending { rank: far * 1048576 + e.to })
+        }
+      }
+    }
+  }
+  shortest = if best.has(path.to) { best[path.to].depth } else { -1 }
+}
+
+view graph = "{nodes.count} nodes, {edges.count} edges"