Created 2004-12-11 / Edited 2004-12-11

I wrote GrabBag as a datastructure to hold genetically evolving programs (see OGPF). Unlike most collections, this one assumes that when you add an element you don't care where it goes (unordered insertion) and that when you pull out an element you specifically want a uniformly random element.

See the grabbag directory for the source code (GPLed unless you talk to me).

This particular implementation is based on a binary tree which keeps track

of how many leaves it has on both its left and right side (the actual data is stored in the leaves). This makes it

easy to find the size -- you just add those two numbers from the root of the

tree. To grab something at random we take the size (total number of things

we have), pick a random number up to that. Then we start at the root... if

the number is bigger than the left, we go right and so on until we find the

node and pull it out. We make a note of the removal by subtraction on the

way back out. 2^n nodes can thus be accessed in 2*n operations (which is equivalent to O(ln n) I believe). Adding works

similarly -- we move down the tree finding out where it is lopsided and add

the new thingie there, thereby keeping things pretty even.