Re: [boost] [multi_index]terminology/design concern

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-05-21 11:01:28

"Joaquin M Lopez Munoz" <joaquin_at_[hidden]> wrote in message 
news:loom.20060420T234946-849_at_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