The current focus in the roitEmbed project is the SpliceArray class. The aim being a tree array structure, where each leaf does not have to be full. The cumulative counts of the leaves make for a simple binary search algorithm to find the correct leaf and element. Splicing involves removing and adding in elements. This makes the expensive linear copy of almost all elements on a large array splice into just insertion and deletion of smaller arrays, and so makes the splice not dependant on the number of array elements. The depth of the array tree needed, depends on the maximum size and is a trade off between differing efficiencies. An optimal size for each leaf node is about sixteen elements. This means the branch nodes have thirty two elements, as both a link and a cumulative count is required. A tree depth of six allows for a 16.7 million element array maximum. This is more than sufficient for any task I can imagine being done by browser side JS.
