Skip to Content
Guides

Index spaces, domains & slices

Typed positions, .l/.r boundaries, grids, slices, arenas, and coordinate compression.

Most off-by-one bugs come from storing two kinds of numbers in the same int: an element position, a gap between elements, a count, or a vertex from a different graph. CP Lang separates them with two complementary tools: structural range arrays [0..n]T / [0..=k]T for quick integer-indexed tables, and nominal domains domain V = 1..=n when you want compile-time separation between index spaces.

Structural range arrays ([0..n]T, [0..=k]T)

When an array is just a scratch table indexed by plain integers—like a frequency count or digit bucket—you do not need to name a domain:

let n: 0..=100 = read()
let k: 0..=100 = read()
let a: [0..n]0..=k = read()
var cnt: [0..=k]Int = 0
for i in 0..n:
    cnt[a[i]] += 1
cnt.fill(0)                     // reset the whole array in place

Structural range arrays unify across functions whenever their written bounds match ([0..n]Int matches [0..n]Int). Index an array using the same bounds it was declared with (for i in 1..=n: for [1..=n]T, for i in 0..n: for [0..n]T; indexing [1..=n]T at 0 traps at runtime). for i in 0..n binds i: Int, so i + 1 is Int. Nominal domain values (v: V) are not Int: you cannot multiply or pass v where Int is expected, nor index [V]T with an Int — convert explicitly with v.ord / v.to_idx (to Int) or V(k) (from Int), or use a structural range array [0..n]T / [1..=n]T when you need integer arithmetic on indices. Generic stdlib structures (Dsu<V>, DsuOf<V, ...>, Fenwick<V>, SegTree<V, ...>, Graph<V>) require a named domain V = ..., never an inline range like Dsu<1..=n>. Neighbor properties v.next / v.prev and domain arithmetic v + 1 / v - 1 / V.last - 1 return ?V (they may step outside the domain — unwrap with if let nxt = v.next: or ?? before indexing or forming a range). Multi-dimensional [R, C]T arrays take comma-separated indices (g[r, c]) and accept a scalar fill (var g: [R, C]T = 0), whereas nested [R][C]T is an array of arrays and [R]List<T> is indexed as adj[r][k]. Unnamed grid cell tuples (r, c): (Row, Col) (not named records (r: Row, c: Col)) have built-in .adj4 and .adj8 neighbor properties without importing anything. Use a.fill(x) (or seen.fill(none) on [D]?T) to clear an array between test cases.

Nominal domains and Index

Declare a nominal domain with domain Name = lo..=hi (or counted shorthand domain Name = n, which means 0..n) whenever you want zero-check indexing and compile-time protection against mixing different index spaces:

let n = read(1..=2e5)
let m = read(1..=2e5)
domain Row = 1..=n
domain Col = 1..=m
domain Bucket = 10              // counted domain: same as 0..10
print(Row.count, Bucket.count)

Row and Col are distinct types even when n == m. An array [Row, Col]Int accepts (r, c) in that order only; swapping r and c is a type error before the program runs.

let n: 1..=2e5 = read()
domain V = 1..=n
let a: [V]Int = read()
print(a.sum())

A domain implements the Index and Seq traits:

  • V.count (and V.K) is the number of elements; V.first and V.last are the endpoints as ?V (none for an empty domain; unwrap with !).
  • v.to_idx converts to 0..V.count and V.from_idx(i) -> ?V converts back safely.
  • v + k -> ?V and v - k -> ?V step by an integer offset and return none past the ends; b - a -> Int is the signed distance; v.cyc(k) -> V wraps cyclically.
  • Step along a named domain in either direction with for v in V by k: and for v in V.rev by k:.

Array endpoints are values, not domain indices: a.first and a.last return ?T, while V.first and V.last are optional indices. Like lists, empty arrays return none; unwrap with a.first! or a.last! only when nonempty. An unwrapped endpoint is also a mutable place, so a.last! += 1 works on a mutable array or list:

domain V = 5..8
let a: [V]Int = [V] v => 10 + v.to_idx
let endpoints: (?Int, ?Int) = (a.first, a.last)
print(V.first, V.last, endpoints.0!, endpoints.1!) // 5 7 10 12
domain Empty = 0..0
let empty: [Empty]Int = 0
print(empty.first ?? -1, empty.last ?? -1) // -1 -1

Boundaries: .l and .r

Prefix sums, difference arrays, and knapsack tables live on the n + 1 gaps around n elements. Every ordered domain V has a companion boundary space V.cuts with V.K + 1 positions.

let n: 1..=100 = read()
domain V = 1..=n
let a: [V]Int = read()

var pre: [V.cuts]Int = 0
for v in V:
    pre[v.r] = pre[v.l] + a[v]
print(pre[V.last!.r])

Every element v: V sits between two boundaries:

  • v.l is the gap immediately to the left of v; v.r is the gap immediately to the right of v.
  • v.l(k) and v.r(k) jump to the k-element window boundaries counting v (v.l == v.l(1), v.r == v.r(1)).
  • b.left -> ?V and b.right -> ?V move from a boundary back to the adjacent element.

The same .l/.r notation works directly in multi-dimensional DP tables such as 0/1 knapsack ([I.cuts, 0..=cap]Int):

let n: 1..=50 = read()
let cap: 1..=1000 = read()
domain I = 1..=n
let items: [I](w: 1..=1000, v: 0..=1e9) = read()

var best: [I.cuts, 0..=cap]Int = 0
for i in I:
    for c in 0..=cap:
        best[i.r, c] = best[i.l, c]
        if c >= items[i].w:
            best[i.r, c] max= best[i.l, c - items[i].w] + items[i].v
print(best[I.last!.r, cap])

Ranges, open ends, and slices

One Range<I> type covers half-open l..r, inclusive l..=r, and open-ended ..i, ..=i, i.., i.r.., and l.r..r.l (strictly between l and r). Every range provides .first -> ?I, .last -> ?I, .mid -> ?I, .len, .is_empty, .rev, .step(k), and (lo..=hi).clamp(D); Range<Int>.sum() and (a..b).step(k).sum() are O(1) closed forms.

Range data structures accept range arguments such as st.fold(..h[i]) and pre.fold(..i). Array slices use the array's own index base (a[2..=4] on a [1..=4]Int is its last three cells), and grid slices g[r, ..] / g[.., c] act as 1-D [D]T arrays that can be passed directly to generic functions such as sum and argmax. In-place slice mutation remains specification work; use the explicit copy-and-writeback example when sorting a window.

let one: [1..=4]Int = [10, 20, 30, 40]
print(one[2..=4].sum())          // 90 (1-based slice)
let g: [1..=2, 1..=3]Int = [[1, 5, 2], [4, 3, 6]]
print(argmax(g[.., 3])!)        // 2 (row index along the 1..=2 axis)

An open-ended Int range l.. also works in a loop. Unlike an open-ended slice, it has no container to supply its endpoint: stop explicitly rather than trying to collect an unbounded iteration.

let l = 3
for i in l..:
    if i == 6: break
    print(i) // 3, then 4, then 5

Grids and Cell = (Row, Col)

A 2D array [Row, Col]T uses row and column domains. The example below names their pair Cell, iterates the two domains separately, and indexes g[r, c]. Product-domain iteration and fully generic cell-indexed structures are still being completed.

use std.grid.{adj4}

let h: 1..=50 = read()
let w: 1..=50 = read()
domain Row = 1..=h
domain Col = 1..=w
type Cell = (Row, Col)
let g: [Row, Col]Char = read()
fn visit(p: Cell): print(p)

for r in Row:
    for c in Col:
        let p: Cell = (r, c)
        for q in p.adj4:
            if g[q.0, q.1] != '#':
                visit(q)

The imported p.adj4 yields in-bounds orthogonal neighbors. std.grid also declares adj8, step, ray, and Dir4. Generic row/column lends and transformed grid views remain specification work rather than runnable APIs.

Coordinate compression with compress(all)

Coordinate compression produces a fresh nominal domain xs.D together with value lookup and inverse mapping:

let all_coords = [30, 10, 20]
let queries = [10, 30]
let xs = compress(all_coords)
var bit = Fenwick<xs.D, Int>()
var ans = 0

for x in queries:
    let id = xs.at(x)           // exact lookup -> xs.D
    let original = xs[id]       // original value at id
    bit.add(id, 1)
    if let ge = xs.first_ge(x): // lower bound -> ?xs.D
        ans += bit.prefix(ge.l)
print(ans)

You never accidentally pass an uncompressed value into bit or mix a compressed index with raw coordinates.

Fresh runtime domains and existential returns

A domain can be declared from any runtime expression that yields a count, a range, a sequence, or another domain — including domain V = read(1..=n) and domain C = compress(xs). Each declaration site owns one runtime slot (saved and restored automatically across recursive calls), and runtime-sized arrays live on the heap rather than the stack.

A fresh domain cannot escape the block or function that declares it (E0313) unless the function exposes it explicitly in an existential return type:

fn make_seq(k: Int) -> (domain P, [P]Int):
    domain Local = 0..k
    (Local, [Local] i => i.to_idx * 2)

let (domain Q, vals) = make_seq(4)
print(Q.count, vals.sum())

Standard-library functions that introduce a new index space (components, scc, two_edge_components) use the same pattern: let (domain C, comp) = scc(adj). Record types read by read() may also bound fields by earlier runtime values, e.g. let edges: [0..m](u: V, v: V, w: 0..=m) = read().

Symmetric tables and domain iteration helpers

For undirected adjacency matrices and other symmetric relations over a domain V, [Sym<V>]T stores unordered pairs in a flat triangular array of n * (n + 1) / 2 cells where adj[u, v] and adj[v, u] refer to the same entry. Domains also provide typed slicing and unordered pair iteration (V.after(i), V.before(i), V.pairs, and domain P = V.pairs):

domain V = 1..=4
var adj: [Sym<V>]Bool = false
adj[V(1), V(3)] = true

var missing = 0
for (i, j) in V.pairs if not adj[i, j]:
    missing += 1
var after_first = 0
for j in V.after(V(1)):
    after_first += 1
print(yes(adj[V(3), V(1)]), missing, after_first)

for (i, j) in V.pairs and for j in V.after(i) / V.before(i) lower directly to nested integer loops with no intermediate allocation.

Domain subsets, enum-indexed tables, and sequence operations

Domains compose directly with bitsets (V.all, Bitset<V>, adjacency(edges, into: Bitset)), fieldless enums ([Sign]T and [Sign] x => ...), domain-typed sequence operations (partition, sort(by:), group(by:), at, first(p)), and paired Item/Cut ranges via minmax:

enum Sign: neg = -1, zero = 0, pos = 1
let vals: [Sign]Int = [Sign] s => Int(s) * 10

domain V = 1..=4
let edges: List<(u: V, v: V)> = [(V(1), V(2)), (V(2), V(3))]
let adj = adjacency(edges, into: Bitset)
let rest = V.all - adj[V(2)]
let (evens, odds) = V.partition(v => Int(v) % 2 == 0)
let first_big = V.first(v => Int(v) > 2)
print(vals[Sign.neg], rest.len, evens.len, odds.len, first_big!)

Range structures (SegTree<V.cuts, T>, Fenwick<V.cuts, T>) also accept V.cuts directly as their index domain, so boundary updates (seg.set(v.r, x), seg.apply(..=v.l, 1)) need no shadow 0..=n domain. For divide-and-conquer over any Range<I>, let (left, right) = r.halves() splits r in O(1) with both halves non-empty whenever r.len >= 2.

Product domains

A Cartesian product of finite domains (including fieldless enums and Bool) can be named as one flat domain with domain State = (V, K) or named factors domain State = (v: V, ok: Bool). Values pack in row-major order into a single 0..len(V) * len(K) slot, so [State]T is a flat array, for s in State: and for (v, k) in State: iterate every state, and dp[(v, k)], dp[v, k], and dp[State(v, k)] all index it while rejecting swapped factor order with E0301:

domain V = 0..3
domain K = 1..=2
domain State = (V, K)

var dp: [State]Int = 0
for (v, k) in State:
    dp[(v, k)] = v.ord * 10 + k.label

let s = State(V(2), K(1))
print(dp[s], dp[V(2), K(2)], s.0.ord, State.len)

Inverting bijections and partial injections

a.inverse() inverts any 1D array whose elements are an index domain, fieldless enum, or bounded integer range. On a total bijection a: [D]E it returns [E]D (trapping if a value is repeated or missing); on a partial injection a: [D]?E it returns [E]?D (trapping if two positions map to the same value):

domain P = 1..=4
var a: [P]?(1..=4) = none
a[P(2)] = 4
a[P(4)] = 1
let at = a.inverse()
print(at[1]!.label, yes(at[2] == none), at[4]!.label)

Algebraic Index and escape hatches

The language's Index model (§2.16) covers Bool, finite enums (both fieldless and payload enums whose fields are index types), ?T, integer ranges, tuples/records of index types, and Subset<D> for bitmask DP. Payload enums such as enum Node: Src / Snk / Cell(Row, Col) and tuples/records such as (Row, Col) work directly as array dimensions ([Node]T, [(Row, Col)]T), loop domains (for v in Node:), and generic index arguments (FlowGraph<Node>, FlowGraph<(Row, Col)>, Dsu<Node>):

use std.flow.{FlowGraph}

domain Row = 0..2
domain Col = 0..3
enum Node:
    Src
    Snk
    Cell(Row, Col)

var g = FlowGraph<Node>()
g.add(Node.Src, Node.Cell(Row(0), Col(0)), 4)
g.add(Node.Cell(Row(0), Col(0)), Node.Snk, 3)
print(Node.count, g.max_flow(Node.Src, Node.Snk))

For numeric offsets, use a structural range array such as [0..n]Int. The specified a.raw[i] escape for nominal arrays is not yet supported by the execution backend. unchecked: is available for a loop you have already proved safe; see the C++ guide.

On this page