Binary traversal

The array elements of a Nodal Space are all identified by an integer index which starts at 0 for the first element created, and one for the next and so on. All integers can be represented as a unique binary sequence as in the decimal and binary columns of the following list of example index numbers:

Decimal    Binary    Nodal Path 0    0    - 1    1    - 2    10    0 3    11    1 4    100    0-0 ⋮    ⋮    ⋮ 100    1100100    0-0-1-0-0-1 ⋮    ⋮    ⋮ 1000    1111101000    0-0-0-1-0-1-1-1-1 ⋮    ⋮    ⋮ 1023    1111111111    1-1-1-1-1-1-1-1-1 1024    10000000000    0-0-0-0-0-0-0-0-0-0 1025    10000000001    1-0-0-0-0-0-0-0-0-0

Both the decimal and the binary numbers really have an infinite number of leading zeros before them, but we can still maintain a unique sequence of digits to represent every integer even if we omit all leading zeros as we have in this table. The point is that this rule means that every single number except for 0 always ends with a non-zero digit (numbers are read from right to left). While this may not be of much interest for most number systems, you will notice that with binary it means that every number except zero ends with a 1 - and if we forget about the two first items in the list, then we could drop the last bit altogether. As can be seen from the Nodal Path column in the list, that's exactly what we do in path traversal. This can't usually work with normal numeric data types because 0 and 00 evaluate to the same, but a sequence of binary digits is more like a string comparison of "0" and "00".

So that's how the binary conversion from a decimal index goes, but in the actual code, a multiplication by the size of three list items is also needed, and an addition of one so that the indexes 1 and 2 map to the single-bit sequences of 0 and 1. Traversing the index of zero (root) means to return the subject unchanged with no traversal occuring (i.e. a zero-length traversal). Here's the traversal function from the peerd.c version.

[[+LT.c|]]

See also

• List Space - the abstraction layer which uses binary traversal
• listSpace.c - functioning implementation of List Space
• Trie data structure