grid.bend checks

raw source on the hub · import 0x3b876eed3a748ea7fba8a7834d3c610b/grid.bend as Grid

Grid: a square quadtree, and the parallel walks over it. ========================================================

A Grid of depth d holds 2^d * 2^d values. The four fields keep the screen order that Bend's Image uses, so a board maps onto a frame without a transpose.

The grid is Data, so a + copy costs one reference count. That is what lets every leaf of a parallel walk read the whole previous board at the same time.

1 import

import Base

Types

type Quad source · line 14 · raw

Data

QTL
```
Quad
```
QTR
```
Quad
```
QBL
```
Quad
```
QBR
```
Quad
```

type Grid source · line 20 · raw

@-a:Quant -> @-A:Kind(a) -> Kind(a)

GLeaf

@-a:Quant -> @-A:Kind(a) -> @val:A -> Grid<a, A>

GQuad

@-a:Quant -> @-A:Kind(a) -> @tl:Grid<a, A> -> @tr:Grid<a, A> -> @bl:Grid<a, A> -> @br:Grid<a, A> -> Grid<a, A>

Definitions

def Quad.of source · line 25 · raw

@bx:Bool -> @by:Bool -> Quad

Picks a quadrant from one bit of x and one bit of y.

def Grid.path source · line 38 · raw

@d:Nat -> @+x:U32 -> @+y:U32 -> List<&2, Quad>

The route from the root of a depth-d grid down to cell (x, y). Bit d-1 of x and y picks the first turn, bit 0 the last.

def Grid.get source · line 49 · raw

@-A:Data -> @g:Grid<&2, A> -> @path:List<&2, Quad> -> A

Reads the value at the end of a path. A path shorter than the grid stops at the top-left corner below it.

def Grid.set source · line 68 · raw

@-A:Data -> @g:Grid<&2, A> -> @path:List<&2, Quad> -> @v:A -> Grid<&2, A>

Writes v at the end of a path. Only the nodes on the path change. A path shorter than the grid stops where Grid.get stops, at the top-left corner below it. That is what makes read_back hold for every path, not only for one of the right length.

Templates

template Grid.init source · line 86 · raw

@-A:Data -> @-P:Data -> @-f:(@+q:P -> @+u:U32 -> @+v:U32 -> A) -> @d:Nat -> @+p:P -> @+x:U32 -> @+y:U32 -> Grid<&2, A>

Builds a depth-d grid from a function of the payload and the cell position. The four quadrants run in parallel and are the same size, which is what Bend's fork-join scheduler wants.

template Grid.map source · line 103 · raw

@-A:Data -> @-B:Data -> @-f:(@c:A -> B) -> @g:Grid<&2, A> -> Grid<&2, B>

Maps every value. The four quadrants run in parallel.

template Grid.sum source · line 116 · raw

@-A:Data -> @-f:(@c:A -> U32) -> @g:Grid<&2, A> -> U32

Adds a number up over every value. The four quadrants run in parallel.