dendrograms/dendro-core — pull request #20 by ChrisBeaumont (2013-06-17 16:56:34+00:00)
Title: Efficient indexing

This is not ready to merge, and should also wait for #17 (which this PR is rebased against)

I've added a `TreeIndex` class for to more efficiently extract the locations of each structure.

At the moment, the usage is as follows:
```
d = Dendrogram.compute(data_array)
ti = TreeIndex(d)
inds = ti.indices(d.trunk[0].idx, subtree=True)
```
`inds` is a tuple of numpy arrays, similar to the output of np.where. They can be used as a fancy index to `data_array.`

`TreeIndex` stores a flattened and permuted version of `np.indices(data_array.shape)`, such that every structure (with or without subtrees) corresponds to a single contiguous slice of this array. This means that its space requirement is ~len(data_array.shape) * data_array.size. The `indices` method is more or less a single array slice, so it should be fast.

@astrofrog, I'd like to change the return value of `Structure.indices` and `Structure.indices_all` to return a tuple of numpy arrays, instead of a list of tuples. Then, at the end of `Dendrogram.compute`, I'd like to compute a TreeIndex, and store this index with each structure. This will let us use the `TreeIndex` to trivially implement `Structure.indices`, without recursion and in O(1) time.

Are you ok with this interface change to `Structure.indices`?

I've also trimmed dendrogram.index_map, as discussed in #18