I'll just be brief this time and hit the points quickly:
Yes, technically it is a Complete Binary Tree but you won't find a Complete
Implementation of one anywhere, I have looked, and there isn't. The concept
has been rejected without being tested by anyone who has considered it at
least what I can find.
Those relational functions you mentioned are not correct for a tree with
the array index 0 being the root, this is them here:
Parent:
c.Index = c.Index>>1 - (c.Index+1)%2
Left Child:
c.Index = c.Index<<1 ^ 1
Right Child:
c.Index = c.Index<<1 + 2
I have used bitwise operators because it is always powers of two, and thus
will be faster on a processor with bitshift and no worse than using *2
without. I used an XOR on left because the shift is left and thus the LSB
can be flipped without computation to add one. The right one adds two, this
is related to using 0 as the root also.
The parent function is the one that got me the most excited when I came up
with it - it avoids the use of comparison/branch functions by taking
advantage of the property of the tree rooted at 0, that every left child is
odd and every right is even (that's what the IsOdd function returns - and
computes it with &1, and is used in my Left and Right walk functions that
'flatten' the tree and walk it like it's a sorted list). By adding one to
the index you flip its' odd/even status, gives you a 1 if it then becomes
odd. This effectively is a 'move inwards' operation. It saves on comparison
and branching and I know on 32 bit integers bit shift, addition and modulus
are very fast. (and the code is very short in the cache)
By rooting the tree at array index 0 it becomes possible to pick any given
index and know if it's a left or right child by whether it's odd or even,
and the special case of zero, which is neither (yes, I know it's referred
to as even but it's not really a number, according to number theory), tells
you also you can't move upwards.
Compared to a potential and mostly filled tree of 30 rows, the amount of
space taken up by the code is quite small, with the separation of functions
for tree and data type, there is no wasted space repeating functionality
that can be abstracted. Plus, for up to around 20 rows of tree, the array
will fit mostly within a cpu cache, and since operations take place on one
side and the other, and mainly affect small segments of the subtree, each
subsequent row does not have to be fully loaded into the cache for most
operations.
Technically my approach is more like a functional programming approach to
the problem, as I am passing pointers to functions in order to implement
the data specific elements, only the interface for the array store is OOP
style (and it DOES have to be encapsulated in a struct because Go slices do
not work with interfaces).
As to exposing things, in fact an external payload data type library can
decide exactly what it will expose. I am only writing a base implementation
with uint32 because to test it I have to fill the data with *something* and
quite likely 32 bit hashes will be actually used in my intended application
for this library, as the heads and tails from 64bit hashes.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
