[litwindow-users] Re: <map> as container

[Hajo K. <mai...@ha...>]

yrs90 wrote:
> I have been pondering <map> containers again.
> 
> The reason that <map> could not be used as a container was that it didn't
> have a way to be bookmarked like a vector, is that right?  I'm not sure I
> understand the limitation.  It seems that there are at least two possible
> ways of dealing with bookmarks using a <map>.

The bookmarks referred to in the vision document do not exist yet. Also 
the discussion in the vision document is at a very high level of 
abstraction. map<> are not suitable for the high-level container concept 
because it does not preserve a sorting order. map<> always impose their 
own sorting order.

This high-level container might even contain more than one 'index'. 
Implementation wise it could be an stl vector that maintains the custom 
sort order plus several other vectors, each representing a different 
'index' that contain pointers to the original data. Sorting offers a 
subtle design problem. Is the sort order an inherent attribute of the 
collection? Or is the sort order just a 'view' to the collection, 
imposed by the user. This problem becomes clear when you think of a 
multi-user scenario. Suppose you had a list of addresses. My preferred 
sort order will be different from your sort order, so 'sort' is not an 
attribute of the collection. So, should sorting be part of the container 
or not?


The current reason why map<> cannot be used with 
IMPLEMENT_CONTAINER_ADAPTER is much simpler. I haven't had the time to 
write a map container adapter. The only container adapter that exists so 
far is the vector container adapter.

> If the bookmarks are refreshed when a NotifyChanged() is received, the
> existing implementation of indexing off the begin() iterator looks
> sufficient.  As it stands now, when a new data element is inserted or
> deleted, the entire view is repopulated, so the index can be refreshed with
> the updated ordering.
> 
> If the bookmark needs to persist in the face of insertions and deletions,
> the iterator itself could be used as the bookmark.  <map> has the nice
> feature of not invalidating the iterators when an element is inserted or
> deleted (other than the deleted element).  This is less volatile than a
> <vector>.

Yes, true.

Currently, NotifyChanged works with the entire container only. What 
would be needed is NotifyInserted and NotifyDeleted for containers.

This area of the Lit Window Library is not implemented yet.

Here is what I think needs to be done:

Idea 1:
Insertion / deletion is being handled by the container itself. 
Interested objects are being notified.

NotifyInserted should notify any interested object that an insertion has 
occurred in a container. It should also include a 'bookmark' as to where 
this insertion has occurred. The bookmark should point to the object 
immediately behind the insertion. Bookmarks in this sense are an 
abstract concept of iterators. ODBC bookmarks will look entirely 
different than STL iterators, so 'bookmark' is a high level abstraction, 
much as the container adapter is a high level abstraction to a concrete 
container.

NotifyDeleted should notify any interested object that a deletion has 
occurred.
Perhaps the notification should also include
NotifyInserting - NotifyDeleting
events that are being sent just before the insertion/deletion is being made.

Idea 2:
Insertion / deletion is never done by the container itself, but by some 
control that owns the container.

This would make the insertion/deletion easier, but you couldn't bind 
more than one control to a container.


My current advice is not to rely on the library for this case. There 
still needs some conceptual work to be done and the container 
abstraction needs to be enhanced for this in order to work.

If you need a map, you could use a map as an index in addition to the 
vector. Or write the container adapter for a map, which is not very 
difficult. IMPLEMENT_CONTAINER_ADAPTER will then work for map<> as well.

To avoid repopulating the entire view every time a single element is 
inserted or removed from the view, you will have to write your own 
notification mechanism at this time. The problem is that you can 
currently access elements inside a container only sequentially.




That is if you have a

litwindow::container mycontainer=myaccessor.get_container();

and want to access a specific (say the 12th) element, you can only use

size_t element_index=12;
container::iterator i;
while (element_index--)
   ++i;

There is no [] operator yet. This would be equivalent to a 'seek' 
operation. What is needed is something along the lines of

container::bookmark bmark;
container my_container=my_accessor.get_container();
container::iterator i=my_container.seek(bmark);

which would return a container iterator pointing to the element at 'bmark'.

bmark would either have to be valid even after insert/delete operations 
or all affected bmarks would have to be invalidated.

Alternatively, instead of having both, iterators and bookmarks, I could 
imagine combining the two classes and give iterators the properties of a 
bookmark.

Currently iterators are bound closely to the underlying iterator 
algorithm, vector::iterator in this case. So they can become invalid 
after an insert operation.

Bookmarks otoh would be a much higher-level abstraction and should be 
unique for every object inside the container.

My current thinking is having bookmark as a unique 'address' of an 
element in a container. Bookmarks should remain valid for all operations.

Iterators otoh will be short-lived objects used to access and iterate 
the container. Their sort order can be changed without changing the 
actual sort order of the underlying container.

If you are familiar with databases, another way to think of bookmarks, 
containers and iterators is this:

A container is a database table. It does not have a sort order - or 
perhaps it as a default sort order.

A bookmark is just that, a bookmark. Most database engines support 
bookmarks for rows inside a table. A bookmark remains valid as long as 
the row exists, regardless of other insertion/deletion operations.

An iterator is a cursor. When you 'SELECT * FROM table' you really open 
a cursor and iterate over the table with GetFirst() and GetNext(). 
Optionally cou can pass a sort order to the SELECT statement so the 
cursor will return the objects in a particular order.


Translated to the container adapters this would mean:

// get a handle to the container (table)
container my_container=my_accessor.get_container();

// iterate over the container using a particular sort order
container::iterator i;
for (i=my_container.get_iterator("SORT BY m_name"); i.at_end()==false; ++i)

// save a bookmark for an element that iterests me
// return the bookmark for the current iterator as a long value
// associate the bookmark with the 'ItemData' property of the current 
list control element
   some_list_ctrl->SetItemData(index, i.get_bookmark().as_long());


// seek to a specific bookmark
i=my_container.get_iterator("SORT BY other_property");
i.seek(bookmark((long)some_list_ctrl->GetItemData()));




Something along these lines.

Best regards

Hajo