After the posts about Rhythmical Arrays and Rhythmical Objects, I want to investigate the actual data structure that is at play: trees. This is an attempt to explain why trees are a really elegant way to represent rhythm and music.

Note: This post is not optimized for dark mode.

Tree Basics

This is a tree:

Now if we turn this upside down, cut of the stem and draw it like a 3 year old, we get what computer scientists call a tree:

You can learn the basic terminology by exploration. Just click on different nodes and watch what happens. The color coding should explain itself. If not...

{
    name: '1',
    children: [
      { name: '2', children: [{ name: '5' }, { name: '6' }] },
      { name: '3', children: [{ name: '7' }, { name: '8' }] },
      { name: '4', children: [{ name: '9' }, { name: '10' }] },
    ],
  }

Visual: Tree vs Score

Let's ignite a visual explosion of a score notation, using the common Bolero rhythm as an example:

• The tree essentially contains the same information as the score, though using less visual encoding (taking more space).
• Each group represents different subdivisions of time
• Each member of a group (color) takes the same amount of time!
• Each fraction is the duration of the member, relative to the length of 4/4

Aural: Hearing the Layers of Rhythm

As we are talking about music, let's make the tree layers audible:

Using the same color coding as above, we now use a different sound for each layer of the tree:

The actual bolero rhythm just switches between different layers:

Textual: Nested vs Flat

Let's oppose two possible textual representations of the bolero:

Nested

As JSON, this is the most compact and readable version I can think of:

[
  [
    ["sn", ["sn", "sn", "sn"]],
    ["sn", ["sn", "sn", "sn"]],
    ["sn", "sn"],
  ],
  [
    ["sn", ["sn", "sn", "sn"]],
    ["sn", ["sn", "sn", "sn"]],
    [["sn", "sn", "sn"], ["sn", "sn", "sn"]],
  ],
];

The nesting of the braces directly resembles the structure of the notes. To understand more about this syntax, check out my post about Rhythmical Arrays.

We could also just ignore the outer two levels:

[
  "sn",
  ["sn", "sn", "sn"],
  "sn",
  ["sn", "sn", "sn"],
  "sn",
  "sn",
  "sn",
  ["sn", "sn", "sn"],
  "sn",
  ["sn", "sn", "sn"],
  ["sn", "sn", "sn"],
  ["sn", "sn", "sn"]
]

This piece of text also represents the bolero rhyhtm. It might not be as readable, but it still works.. It depends on the use case, which representation should be chosen.

Flat

A more machine readable version looks like this:

[
  ["sn", 0, 0.75],
  ["sn", 0.75, 0.25],
  ["sn", 1, 0.25],
  ["sn", 1.25, 0.25],
  ["sn", 1.5, 0.75],
  ["sn", 2.25, 0.25],
  ["sn", 2.5, 0.25],
  ["sn", 2.75, 0.25],
  ["sn", 3, 0.75],
  ["sn", 3.75, 0.75],
  ["sn", 4.5, 0.75],
  ["sn", 5.25, 0.25],
  ["sn", 5.5, 0.25],
  ["sn", 5.75, 0.25],
  ["sn", 6, 0.75],
  ["sn", 6.75, 0.25],
  ["sn", 7, 0.25],
  ["sn", 7.25, 0.25],
  ["sn", 7.5, 0.25],
  ["sn", 7.75, 0.25],
  ["sn", 8, 0.25],
  ["sn", 8.25, 0.25],
  ["sn", 8.5, 0.25],
  ["sn", 8.75, 0.25]
]

This is an absolute representation of the bolero at 45 bpm (quite slow, but has the nicest looking floats..). The format is [value, time, duration]. While it is readable for machines, it is quite unpractical for humans..

The important question: How can we transform the first notation into the second? With it, the human interface would be the first, while the second one would be used for rendering / playback.

Calculating Absolute Time & Duration

Let's find out how to calculate the absolute time and duration for each node, based on the tree.

Fraction Paths

Let's identify each node by the index in its group of children:

Click step to walk the tree

• When stepping into the tree, the path of indices uniquely identifies each node
• This path will help us to calculate time and duration

Calculating Durations

Let's divide each index by the number of children in that group:

Click step to walk the tree (prepare for math...)

• If we divide each node index by the total number of children (also called branching factor), we get a fraction that represents the duration of each node in its group.
• By multiplying that fraction with all the fractions of the node's parents, we get the relative duration fraction.
• We can calculate the absolute duration by multiplying that relative duration by the total length of everything

Calculating Time

To get something usable, we also need the absolute time for each node. The process is similar to calculating durations, with a slightly more complicated looking calculation:

Click step to walk the tree (prepare for math...)

• to calculate the relative time fraction, we need to sum the relative times of each node in the path
• the relative time of a single node is the factor of its path and its parent's relative durations

Variable Durations

In the bolero example, there are no duration fractions with a numerator other than 1. To be able to cover any rhythm of this world, we need to extend our paths.

Take this as an example:

Using our current textual representation, this is impossible to express. We need a way to declare durations, for example:

[
  ["C4*3", "D4"],
  ["E4", "D4*2", "B3"]
]

If we just represent the durations as a tree, it looks like this:

Calculating Variable Durations

Now, to get the correct fractions, we cannot just use the indices like before. Instead, we can use the duration as the numerator and the sum of all durations for the denominator:

Calculating Time With Variable Durations

To know the time fraction, our numerator must be the sum of all durations that came before the node in question:

Flat representation

Using the calculated values above, we get this flat representation:

[
  ["C4", 0, 3],
  ["D4", 3, 1],
  ["E4", 4, 1],
  ["D4", 5, 2],
  ["B3", 7, 1]
]

Nice! Now chewed through all the theory that is needed to calculate any rhythm.

Implementation

Let's transfer the above ideas into code. In general, we need to

1. Visit every node of the tree
2. Calculate time and duration of every node

1. Visiting every node of a tree

Simple Walker

This recursive generator function visits every tree node, while being agnostic about the tree structure:

export function* walk(getChildren, tree) {
  yield tree;
  const children = getChildren(tree) || [];
  for (let i = 0; i < children.length; ++i) {
    yield* walk(getChildren, children[i]);
  }
}

Using the getChildren accessor function, we can stay agnostic about the tree structure. This is inspired by d3-hierarchy.

Walking over a simple nested array is pretty straightforward:

const nestedWalker = (tree) => walk((node) => Array.isArray(node) && node, tree);
const tree = ['A', ['B', 'C'], 'D'];

for (let node of nestedWalker(tree)) {
  console.log(node);
}

Output:

['A', ['B', 'C'], 'D'];
'A'[('B', 'C')];
('B');
('C');
('D');

Walking rhythmical objects

To be able to walk over a rhythmical object, we just have to implement a different getChildren accessor:

function getRhythmChildren(node) {
  return Array.isArray(node) ? node : node?.parallel || node?.sequential;
}
const rhythmWalker = (tree) => walk(getRhythmChildren, tree);

const rhythm = {
  duration: 4,
  sequential: [
    [{ value: 'C3', duration: 3 }, 'D3'],
    ['E3', { value: 'D3', duration: 2 }, 'B2'],
  ],
};

for (let node of rhythmWalker(rhythm)) {
  console.log(node);
}

Output:

{
  duration: 4,
  sequential: [ [ [Object], 'D3' ], [ 'E3', [Object], 'B2' ] ]
}
[ { value: 'C3', duration: 3 }, 'D3' ]
{ value: 'C3', duration: 3 }
D3
[ 'E3', { value: 'D3', duration: 2 }, 'B2' ]
E3
{ value: 'D3', duration: 2 }
B2

Now we are able to look at nodes one after the other. This is still too primitive to be usable.

Exposing More Data

The problem: We have no information about the current index or the siblings. So, instead of just yielding the node, let's enrich the data:

export function* visit(getChildren, tree, index?, siblings?, parent?) {
  const children = getChildren(tree) || [];
  const isRoot = parent === undefined;
  const isLeaf = !children?.length;
  yield { node: tree, index, siblings, children, isBefore: true, isRoot, isLeaf, parent };
  for (let i = 0; i < children.length; ++i) {
    yield* visit(getChildren, children[i], i, children, tree);
  }
  yield { node: tree, index, siblings, children, isBefore: false, isRoot, isLeaf, parent };
}

What's new:

• the current index + siblings is fed back into the function
• we are now yielding an object with more information on the state of the iteration
• we are yielding again after the children have been processed, passing an isBefore flag

Generating Index Paths

Using that, we can build an index path like this:

const nestedWalker = (tree) => visit((node) => Array.isArray(node) && node, tree);

const tree = ['A', ['B', 'C'], 'D'];

const path = []; // stack of indices
const events = []; // collection of path states

for (let { index, isBefore, isLeaf, isRoot } of nestedWalker(tree)) {
  if (isBefore) {
    // before children have been visited
    !isRoot && path.push(index);
    isLeaf && events.push([...path]); // we only care for leaves
  } else {
    // after children have been visited
    !isRoot && path.pop();
  }
}
expect(events).toEqual([[0], [1, 0], [1, 1], [2]]); // leaf index paths

• the path array acts as a stack of indices, where we add the index before and remove it after visiting the children
• for each leaf, we add the current path to the events array

2. Calculate time and duration of every node

Now let's find out how we can perform the calculations in code.

Division Paths

Before we can calculate the time & duration, we need to keep track of the relative times and durations.

function divisionPaths(tree) {
  const path = [];
  const events = [];
  for (let { node, index, isBefore, isLeaf, siblings } of nestedWalker(tree)) {
    if (isBefore) {
      siblings && path.push([index, siblings.length]);
      isLeaf && events.push({ node, path: path.join(' ') });
    } else {
      siblings && path.pop();
    }
  }
  return events;
}

expect(getPaths(['A', ['B', 'C'], 'D'])).toEqual([
  { node: 'A', path: '0,3' },
  { node: 'B', path: '1,3 0,2' },
  { node: 'C', path: '1,3 1,2' },
  { node: 'D', path: '2,3' },
]);

Like in Calculating Durations, we represent the position of a node as a number pair of index and number of siblings.

Calculating absolute times

To turn those paths into concrete numbers we can run the following logic:

function pathTimeDurationSimple(path, whole = 1) {
  let time = 0;
  let duration = whole;
  for (let i = 0; i < path.length; i++) {
    time = time + (path[i][0] / path[i][1]) * duration;
    duration /= path[i][1];
  }
  return { time, duration };
}

const renderEvents = (tree, duration) =>
  divisionPaths(tree).map(({ node, path }) => ({ node, ...pathTimeDurationSimple(path, duration) }));

expect(renderEvents(['A', ['B', 'C'], 'D'], 6)).toEqual([
  { node: 'A', time: 0, duration: 2 },
  { node: 'B', time: 2, duration: 1 },
  { node: 'C', time: 3, duration: 1 },
  { node: 'D', time: 4, duration: 2 },
]);

Et voir-la! This is it for rendering without variable durations.

With variable durations

To add variable durations, we can just add a third number to our path:

function timeDurationPaths(walker, getDuration) {
  const path = [];
  const events = [];
  const sumDurations = (nodes) => nodes.reduce((sum, current) => sum + getDuration(current), 0);
  for (let { node, index, isBefore, isRoot, isLeaf, siblings } of walker) {
    if (!isRoot && isBefore) {
      siblings = siblings || [];
      const time = sumDurations(siblings.slice(0, index));
      const duration = getDuration(node);
      const total = time + sumDurations(siblings.slice(index));
      path.push([time, duration, total]);
      isLeaf && events.push({ node, path: [...path] });
    } else if (!isRoot) {
      path.pop();
    }
  }
  return events;
}

Now we are using the sum of all preceding durations as time and the sum of all siblings durations as total duration. To stay agnostic of the node format, we just pass a function that should resolve the duration of a node.

Before we test this, let's fix our calculation:

export function pathTimeDuration(path, whole = 1) {
  let time = 0;
  let duration = whole;
  for (let i = 0; i < path.length; i++) {
    time = time + (path[i][0] / path[i][2]) * duration;
    duration *= path[i][1] / path[i][2];
  }
  return { time, duration };
}

Running this on our variable duration example:

const renderEvents = (tree, duration, getDuration) =>
  timeDurationPaths(nestedWalker(tree), getDuration).map(({ node, path }) => ({
    node,
    ...pathTimeDuration(path, duration),
  }));

expect(
  renderEvents(
    [
      ['C4*3', 'D4'],
      ['E4', 'D4*2', 'B3'],
    ],
    8,
    (node) => (typeof node === 'string' ? +node.split('*')[1] || 1 : 1)
  )
).toEqual([
  { node: 'C4*3', time: 0, duration: 3 },
  { node: 'D4', time: 3, duration: 1 },
  { node: 'E4', time: 4, duration: 1 },
  { node: 'D4*2', time: 5, duration: 2 },
  { node: 'B3', time: 7, duration: 1 },
]);

And that's it!

Rendering Rhythmical Objects

Rendering a rhythmical object works like this:

export default function renderRhythmTree(rhythm) {
  const rhythmDuration = (node) => toRhythmObject(node).duration || 1;
  const totalDuration = rhythmDuration(rhythm);
  const path = [];
  const events = [];
  for (let { node, index, isBefore, isRoot, isLeaf, siblings, parent } of visit(getRhythmChildren, rhythm)) {
    if (!isRoot && isBefore) {
      path.push(rhythmFraction(node, index, siblings, parent));
      isLeaf && events.push({ ...toRhythmObject(node), ...pathTimeDuration(path, totalDuration) });
    } else if (!isRoot) {
      path.pop();
    }
  }
  return events;
}

Here, the duration of the root node is interpreted as seconds. The path fraction can be calculated using sibling and parent information:

export function rhythmFraction<T>(
  node: RhythmNode<T>,
  index?: number,
  siblings?: RhythmNode<T>[],
  parent?: RhythmNode<T>
): Fraction {
  const duration = (node as RhythmObject<T>).duration ?? 1;
  if (!parent) {
    // root node
    return [0, duration, 1]
  }
  const durations = siblings.map((sibling: RhythmObject<T>) => sibling.duration ?? 1);
  const total = sum(durations);
  if ((parent as RhythmObject<T>)?.parallel) {
    // parallel path
    return [0, duration, max(durations)];
  }
  const time = sum(durations.slice(0, index));
  // sequential path
  return [time, duration, total]
}

Now we can test the variable duration example from above:

test('renderRhythmTree', () => {
  expect(
    renderRhythmTree({
      duration: 8,
      sequential: [
        [{ value: 'C4', duration: 3 }, 'D4'],
        ['E4', { value: 'D4', duration: 2 }, 'B3'],
      ],
    }).map(({ value, time, duration }) => [value, time, duration])
  ).toEqual([
    ['C4', 0, 3],
    ['D4', 3, 1],
    ['E4', 4, 1],
    ['D4', 5, 2],
    ['B3', 7, 1],
  ]);
});

And it works! Now we worked out a complete reimplementation of rendering rhythmical objects. The complexity of the implementation is much lower, using less clutter.

But enough of that cheap test sequence, let's render a much more complex tune:

const d = (e) => {
  // duration short notation
  const [value, duration] = e.split('*');
  if (duration) {
    return { sequential: [value], duration: parseInt(duration) };
  }
  return value;
};
const s = (str, duration = 1) => ({ sequential: str.split(' ').map(d), duration }); // sequential short notation
const p = (str, duration = 1) => ({ parallel: str.split(' ').map(d), duration }); // parallel short notation
const w = (str) => ['r', p(str), p(str)]; // waltz chord comping

const swimming = {
  name: 'Swimming',
  composer: 'Koji Kondo',
  duration: 51,
  parallel: [
    {
      description: 'melody',
      velocity: 1,
      sequential: [
        d('r*3'),
        ['A5', s('F5*2 C5'), s('D5*2 F5'), 'F5'],
        [s('C5*2 F5'), s('F5*2 C6'), 'A5', 'G5'],
        ['A5', s('F5*2 C5'), s('D5*2 F5'), 'F5'],
        [s('C5*2 F5'), ['Bb5', 'A5', 'G5'], d('F5*2')],
        ['A5', s('F5*2 C5'), s('D5*2 F5'), 'F5'],
        [s('C5*2 F5'), s('F5*2 C6'), 'A5', 'G5'],
        ['A5', s('F5*2 C5'), s('D5*2 F5'), 'F5'],
        [s('C5*2 F5'), ['Bb5', 'A5', 'G5'], d('F5*2')],
        ['A5', s('F5*2 C5'), 'A5', 'F5'],
        ['Ab5', s('F5*2 Ab5'), d('G5*2')],
        ['A5', s('F5*2 C5'), 'A5', 'F5'],
        ['Ab5', s('F5*2 C5'), d('C6*2')],
        ['A5', s('F5*2 C5'), s('D5*2 F5'), 'F5'],
        [s('C5*2 F5'), ['Bb5', 'A5', 'G5'], d('F5*2')],
      ],
    },
    {
      description: 'chords',
      velocity: 0.6,
      sequential: [
        [
          p('F4 Bb4 D5'),
          [p('D4 G4 Bb4', 2), p('Bb3 D4 F4')],
          [p('G3 C4 E4', 2), [p('Ab3 F4'), p('A3 Gb4')]],
          p('Bb3 E4 G4'),
        ],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 Bb3 Db3')],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('A3 C4 E4'), w('Ab3 C4 Eb4'), w('F3 Bb3 D3'), w('G3 C4 E4')],
        [w('F3 A3 C4'), w('F3 A3 C4'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('F3 Bb3 D4'), w('F3 Bb3 C4'), w('F3 A3 C4'), w('F3 A3 C4')],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('A3 C4 E4'), w('Ab3 C4 Eb4'), w('F3 Bb3 D3'), w('G3 C4 E4')],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('F3 Bb3 D4'), w('F3 Bb3 C4'), w('F3 A3 C4'), w('F3 A3 C4')],
        [w('Bb3 D3 F4'), w('Bb3 D3 F4'), w('A3 C4 F4'), w('A3 C4 F4')],
        [w('Ab3 B3 F4'), w('Ab3 B3 F4'), w('G3 Bb3 F4'), w('G3 Bb3 E4')],
        [w('Bb3 D3 F4'), w('Bb3 D3 F4'), w('A3 C4 F4'), w('A3 C4 F4')],
        [w('Ab3 B3 F4'), w('Ab3 B3 F4'), w('G3 Bb3 F4'), w('G3 Bb3 E4')],
        [w('F3 A3 C3'), w('F3 A3 C3'), w('F3 Bb3 D3'), w('F3 B3 D3')],
        [w('F3 Bb3 D4'), w('F3 Bb3 C4'), w('F3 A3 C4'), w('F3 A3 C4')],
      ],
    },
    {
      description: 'bass',
      sequential: [
        ['G3', 'G3', 'C3', 'E3'],
        ['F2', 'D2', 'G2', 'C2'],
        ['F2', 'D2', 'G2', 'C2'],
        ['F2', 'A2', 'Bb2', 'B2'],
        ['A2', 'Ab2', 'G2', 'C2'],
        ['F2', 'A2', 'Bb2', 'B2'],
        ['G2', 'C2', 'F2', 'F2'],
        ['F2', 'A2', 'Bb2', 'B2'],
        ['A2', 'Ab2', 'G2', 'C2'],
        ['F2', 'A2', 'Bb2', 'B2'],
        ['G2', 'C2', 'F2', 'F2'],
        ['Bb2', 'Bb2', 'A2', 'A2'],
        ['Ab2', 'Ab2', 'G2', ['C2', 'D2', 'E2']],
        ['Bb2', 'Bb2', 'A2', 'A2'],
        ['Ab2', 'Ab2', 'G2', ['C2', 'D2', 'E2']],
        ['F2', 'A2', 'Bb2', 'B2'],
        ['G2', 'C2', 'F2', 'F2'],
      ],
    },
  ],
};

<Player fold={true} hierarchy={false} instruments={{ piano }} events={renderRhythmTree(swimming)} />

That's it for today! In a future post, I want to implement plugins by tree mutation.