"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:4058C84D.2000008@redshift-software.com...
[...] I look at the implementation and it doesn't do what a rank tree does. It does make it easier to base a rank tree implementation against it. The part that is missing is keeping track of the rank of nodes as the tree changes, the constant time op, that lets one have the logN ops later on. [ Unless I missed something -- So correct me at will ;-) ]
Hmm...are you sure? Did you look at the rotate_right() and rotate_left() functions? The "indexes" wouldn't be correct if you didn't adjust them on insert/delete. Essentially, what I call "index" is probably what you call "rank".
It also looks to me that there is a much better way to support the custom index aspect of assoc containers with something I thought about recently, tuple_adaptor... The idea is to have a tuple compatible interface that can access a subset of a larger structure. You can then use the tuple adaptor as the comparison/index. Basically abstracting out the "index" like functionality you have. Here are some notes I made up about it last week... [...]
Actually, this sounds almost exactly like what Joaquin's IndexedSet does. You might want to take a closer look at that if you haven't already. I probably will soon so I can give it a thorough review. Dave --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.581 / Virus Database: 368 - Release Date: 2/9/2004