Binary traversal

From OrganicDesign Wiki

1 Associations

An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key "bob" is 7, we say that our array maps "bob" to 7. Associative arrays are very closely related to the mathematical concept of a function with a finite domain. As a consequence, a common and important use of associative arrays is in memoization.

Nodal associations

From the perspective of a programmer using an associative array, it can be viewed as a generalization of an array: While a regular array maps integers to arbitrarily typed objects like integers, strings, pointers and objects, an associative array maps arbitrarily typed objects to arbitrarily typed objects.

In the nodal model, the node is the only kind of entity that exists, so all the keys and values contained by any node must both be node references. Nodes reside in a lower-level data structure called list space and uses a method called binary traversal which is what enables this associative-array-like functionality.

• In the nodal model, associations are not ordered, ie there is no atomic process which can iterate through the associations
• See example nodal structures for diagrams of various nodal structures.
• It is possible for a number of keys to have the same value, effectively allowing the same instance to be in many places at the same time

The null association

Due to the way that list space works, there arrises the possibility of a so-called null-association which involves a zero-length traversal. There is however nothing inherently special about the null association apart from the fact that it involves the least processing time, so it makes sense that the most commonly used association be the null association.

2 Making a unique bit sequence from a node index

The nodes of a node space are all identified by an integer index which starts at 0 for the first element created (the root node), and 1 for the next and so on. All integers can be represented as a unique binary sequence which allows them to all exhibit an address based on a unique path, this kind of data structure is called trie. here is a table showing some integers and their binary and path representations:

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".

In the actual implementations of the listTraverse function, a multiplication by three must also occur to account for the fact that list items are groups of three node references.

3 Zero length traversal

In the table above showing the conversion of integer node references into binary paths, we see that the first two indexes, 0 and 1 both translate to a null path which involves no traversal at all, and then index 2 and 3 translate to the paths of "0" and "1" which involve a single iteration of traversal. In the actual implementations of the listTraverse function an addition of 1 occurs before translation to a binary sequence so that only index 0 results in no traversal, and indexes 1 and 2 result in the two single iteration traversals.

This zero length traversal is still valid because the subject node from which traversal would start has a value just like every other node or list item. If a non-zero value is returned from nodeGetValue when passed a zero key, the value is the focus of the subject node's loop.

// Start at subject listItem and traverse the key as an association to a new listItem
// - key is also a listItem reference and its binary address is used as the traversal path
// - subject and key (all list-item references are ints starting at item 0)
// - if key is 0 the subject is returned unchanged, key 1 and 2 are the two single-iteration traversals
item listTraverse(item subject, item key) {
	if (key++ > 0) {
		int i,j;
		for (i = 1; i <= key >> 1; i <<= 1) {
			j = subject * 3;
			if (key & i) j++;
			if (space[j] == 0) space[j] = listInsert();
			subject = space[j];
		}
	}
	return subject;
}

4 Notes

• It may be possible to make traversal work as a Patricia trie which combines all path segments that have only one direction
• Wikipedia:Trie
• Wikipedia:Linked list