Write a strategy

The built-in strategies are grid, radial, tree and layers. A strategy of your own gets the same treatment. The engine measures, places, routes and audits its output. The text language and the builder work with it.

The contract

The engine uses arrange once for each node with children, after it knows the size of each child subtree. The function gives the top-left corner of each child box. It does not recurse, does not add padding and does not know the absolute positions.

interface Strategy<O> {
  readonly type: string;              // the name in a NodeSpec and in the text language
  readonly description: string;       // one sentence for the reference
  readonly options: OptionSchema<O>;  // the type, the default and the range of each option
  arrange(input: ArrangeInput<O>): Arrangement;
  audit?(input: AuditInput<O>): readonly Issue[];
}

Input	Meaning
`children[i].box`	The size of the box of child `i`.
`children[i].extent`	The rectangle that holds child `i` and its whole subtree, relative to the top-left corner of its box. Keep the extents apart, not only the boxes.
`self`	The size of the box of the node.
`mode`	`linked`: give offsets relative to the top-left corner of the node box, and keep the children outside it. `nested`: the offsets are free, and the engine moves the content into the box.
`options`	The defaults of the schema, merged with the options of the node. The engine examined each value.
`gap`	The distance to keep between two subtrees.
`edges`	The extra edges between the subtrees of two children, as indexes of the children. The `layers` strategy uses them.
`children[i].shape`	Only for a strategy with `shapes: true`: bands that cover each box of the subtree, on each axis. The `tree` strategy uses them to put subtrees closer than their extents permit.

The output is { offsets }, one point for each child, in the order of the children. In the nested mode, an optional content rectangle makes the container larger than its children. In the linked mode, an optional direction ("down", "up", "left" or "right") tells the router where the children are. The orthogonal router then draws the edges of an organization chart. An optional flow gives the direction of the edges between the children, for a flowchart.

An example: spiral

This strategy puts the children on a spiral. It keeps the circle around each subtree away from all circles before it.

/**
 * The strategy "spiral": the children go on a spiral, from the center out. The page "Write a strategy" shows this file
 * as its example, and its live editor uses it.
 */
import { createEngine, defineStrategy, type Engine, type MeasuredChild, type Point } from "ireko";

/** The options of the strategy "spiral". */
export interface SpiralOptions {
  /** The distance between two turns, as a factor of the size of the largest child. */
  readonly growth: number;
  /** If true, the spiral turns in the clockwise direction on the screen. */
  readonly clockwise: boolean;
}

/** This function gives the radius of the smallest circle around the center of the box that holds the whole subtree. */
function rhoOf(child: MeasuredChild): number {
  const cx = child.box.width / 2;
  const cy = child.box.height / 2;
  const { x, y, width, height } = child.extent;
  return Math.max(Math.hypot(x - cx, y - cy), Math.hypot(x + width - cx, y - cy), Math.hypot(x - cx, y + height - cy), Math.hypot(x + width - cx, y + height - cy));
}

/** The strategy. */
export const spiral = defineStrategy<SpiralOptions>({
  type: "spiral",
  description: "The spiral strategy puts the children on a spiral, from the center out.",
  options: {
    growth: { type: "number", default: 1, min: 1, max: 4, description: "The distance between two turns, as a factor of the size of the largest child." },
    clockwise: { type: "boolean", default: true, description: "If true, the spiral turns in the clockwise direction on the screen." },
  },
  arrange({ mode, self, children, options, gap }) {
    const rhos = children.map(rhoOf);
    const largest = Math.max(...rhos);
    // The radius grows by one turn distance for each full turn, so two turns never touch.
    const perRadian = ((2 * largest + gap) * options.growth) / (2 * Math.PI);
    // In the linked mode, the spiral starts outside the box of the node.
    const start = mode === "linked" ? Math.hypot(self.width, self.height) / 2 + largest + gap : 0;
    const direction = options.clockwise ? 1 : -1;
    const at = (theta: number): Point => {
      const r = start + perRadian * theta;
      return { x: r * Math.cos(direction * theta), y: r * Math.sin(direction * theta) };
    };

    const centers: Point[] = [];
    let theta = 0;
    children.forEach((_, i) => {
      // Walk along the spiral until the circle of this child touches no circle before it.
      const clear = (p: Point): boolean => centers.every((c, j) => Math.hypot(p.x - c.x, p.y - c.y) >= (rhos[i] ?? 0) + (rhos[j] ?? 0) + gap);
      for (let guard = 0; !clear(at(theta)) && guard < 100_000; guard++) theta += 0.02;
      centers.push(at(theta));
    });

    // An offset is the top-left corner of a child box. In the linked mode, it is relative to the box of the node.
    const origin = mode === "linked" ? { x: self.width / 2, y: self.height / 2 } : { x: 0, y: 0 };
    return { offsets: children.map((c, i) => ({ x: origin.x + (centers[i]?.x ?? 0) - c.box.width / 2, y: origin.y + (centers[i]?.y ?? 0) - c.box.height / 2 })) };
  },
});

/** An engine with the strategy "spiral" and the built-in strategies. */
export const spiralEngine: Engine = createEngine({ strategies: [spiral] });

Change the text below. The editor uses an engine with the strategy spiral.

# The strategy spiral comes from the code below.
galaxy spiral nested {
  sol spiral { mercury venus earth mars }
  a b c d e f g h
  core nested { x y z }
  i j k
}

21 boxes, 4 edges. The audit finds no defect.

Register it

An engine holds its strategies. createEngine gives a new engine with the built-in strategies and yours. An engine does not change after you make it: extend gives a new engine.

import { builder, createEngine } from "ireko";
import { parse } from "ireko/text";
import { spiral, type SpiralOptions } from "./spiral.ts";

const engine = createEngine({ strategies: [spiral] });

// The builder: a typed function for the new strategy.
const spiralOf = builder<SpiralOptions>("spiral");
const root = spiralOf.nested("galaxy", { growth: 2 }, "a", "b", "c", "d");
engine.layout({ root });

// The text language: give the names of the strategies to the parser.
const parsed = parse("galaxy spiral(growth: 2) nested { a b c d }", { strategies: [...engine.strategies.keys()] });

A strategy with the type of a built-in strategy replaces it.

Check it

The engine examines the output of each strategy:

A strategy that throws, gives the wrong number of offsets or gives an offset that is not a finite number gives the finding STRATEGY_FAILED. The engine uses grid for that node.
The audit finds overlaps between sibling subtrees, and boxes outside their container. A strategy that ignores the extents gives OVERLAP.
An optional audit function adds findings of the strategy.

The test suite of ireko uses random trees to examine the built-in strategies. Do the same for yours. The strict mode throws for each error, and the audit gives an overlap as a warning, so examine issues too.

import { createEngine } from "ireko";

const engine = createEngine({ strategies: [spiral] });
for (let seed = 0; seed < 1000; seed++) {
  const out = engine.layout({ root: randomTree(seed, "spiral") }, { strict: true });
  expect(out.issues.filter((i) => i.code === "OVERLAP" || i.code === "ESCAPE")).toEqual([]);
}