"Joaquin M Lopez Munoz" <joaquin@tid.es> wrote in message news:loom.20060420T234946-849@post.gmane.org...
Hello Gennadiy, I'm returning to this discussion. Excuse the big delay.
By the end of your post, you wrote:
I am not really crazy about the term Bookmark. IMO Order/Index is much better reflect the nature of the concepts we are trying to model. But above is step in right direction IMO.
Well, let me use Index/Bookmark if only during this discussion so as to not introduce further confusion, since I think you agree with me it is concepts we're most interested now, rather than words. I'm not in love with "bookmark" either, it is just a hack word I came by with some resonance to the concept it is being used to refer to here.
Now, returning to the original flow of your post:
Gennadiy Rozental <gennadiy.rozental <at> thomson.com> writes:
That's the primary reason I would need an Index. Aa Order may have have different complexity guarantees. But in some cases I need partucular search to be performed much faster then it is guaranted by order search complexity. Essentially I am looking for an ability to do something like this:
address_book_t ab; typedef address_book_t::order<2>::type full_name_order;
// this operation is compile time full_name_order fno = ab.get_order<FullName>();
// this operation has constant complexity, since Last name Index provide direct access std::pair<full_name_order::iterator,full_name_order::iterator> p = fno.get_index<LastName>::equal_range( "Smith" );
...
In some cases Index could have non-constant complexity, but still could be used to significantly speedup orderred collection search. Lets say I have Input messages log ordered sequencially (meaning that the order is just natuaral order messages where comming in). And I have int64 number of theses comming in every day. Now for this order I want to define Time index to speedup lookup for messages in partucilar time interval. This operation most probably wont be constant (due to continues nature of time) but still could be implemented much faster then global serach through messages collection. In addition for the same collection I may want to define Symbol (some attribute in a messages) order. And for that order I need first letter index. My primary point in above examples is that both Order and Index are first class citizents and current desing doesn't account for the latter. [...]
IMO we need another level of indirection that would support Index within an Order concept. I do not see how existing design could handle this.
Well, if we concentrate now on the kind of data structures we'd need in order to achieve what you request, I come up with the following conclusions:
1. If the index to be sped up is of the ordered kind, then the only way to have faster lookups for clusters of elements (which, according to my terminology, are groups of elements equivalent under some sorting criterion compatible to that used by the index, see http://tinyurl.com/zm6h3), we'd probably have to resort to hashing (which improves rb-tree O(log n) lookup) and have some inner structures like hash_map<key_type,oredered_index_type::iterator>
storing pointers to the first element of each cluster. This has to be properly synchronized with the ordered index on insertion/deletion.
It could be hash, it could be random access or it could be any other custom faster lookup. This is essencially is just a way to jump particulat position in the Order based on some conditions. I may have records ordered by creation time for last week and index that allows me to jump to start of todays and yestadays entries.
2. If the index to be sped up is of the sequenced kind, we've got a problem: you require that the bookmark refer to clusters by using iterators from the index itself, as implied in your example:
std::pair<full_name_order::iterator,full_name_order::iterator> p = fno.get_index<LastName>::equal_range( "Smith" );
and explicitly stated by you in a previous post:
"All indexes for the same order present the same iterator which is a view iterator."
This is AFAICS impossible if the index is sequenced,
I may misunderstand what sequenced order is. I understand it as just a "natural" order entries where added into collection with. Why couldn't I have an Index that would allow me to jump directly to the every 10000th entry?
since the elements can be freely rearranged and thus a cluster need not be adjacent (from the point of view of the sequenced index iterator).
What do you mean by rearanged and cluster here? Gennadiy