[ovirt-devel] SortedListModel

Mon Jun 2 13:33:15 UTC 2014

Hi guys,

I've discussed this issue with Alex last week, we've decided to approach
it using item's hashCode, as suggested by Daniel in his review comment:

  http://gerrit.ovirt.org/#/c/28225/1/frontend/webadmin/modules/uicommonweb/src/main/java/org/ovirt/engine/ui/uicommonweb/comparators/CompoundEntityComparator.java

So the current approach is to fallback to comparing items' hashCode
values if the user-provided Comparator returns 0 (items seem equal):

  http://gerrit.ovirt.org/#/c/28225/2/frontend/webadmin/modules/uicommonweb/src/main/java/org/ovirt/engine/ui/uicommonweb/comparators/EntityComparator.java

This approach means that:

- we don't need any additional (second/third/etc.) fallback Comparator
  or property when the user-provided Comparator returns 0

- if two items differ in *any* of their significant ("key") fields,
  hashCode value should be different for such different items

(In other words, business entities must properly implement hashCode,
which should be the case anyway.)

Lior's idea of using item's original position (before sorting) is very
interesting, however the Collection interface by definition does *not*
impose any ordering on its items, so determining item's position within
a Collection would be *always* dependant on implementation of given
Collection, i.e. ArrayList<SomeBusinessEntity> deserialized from GWT
RPC response. Because of that, I don't think we can reliably determine
item's position within a Collection in a reliable manner (unless we
switch to using List or similar ordered Collection interface).

Regards,
Vojtech

----- Original Message -----
> From: "Lior Vernia" <lvernia at redhat.com>
> To: awels at redhat.com
> Cc: devel at ovirt.org
> Sent: Sunday, June 1, 2014 9:32:46 AM
> Subject: Re: [ovirt-devel] SortedListModel
> 
> 
> 
> On 29/05/14 18:44, Alexander Wels wrote:
> > On Thursday, May 29, 2014 04:29:11 PM Lior Vernia wrote:
> >> Hello Alex,
> >>
> >> On 29/05/14 16:05, Alexander Wels wrote:
> >>> Hi guys,
> >>>
> >>> I have a question about the SortedListModel. If you look at the
> >>> setItems(Collection<T> value) method. You will notice that eventually all
> >>> the items are added to a SortedSet. This is not a problem if all the
> >>> elements of your collection are different. But what happens if the
> >>> elements of your collection are not all different. More specifically if I
> >>> pass in a comparator that matches on a field of the object that is not
> >>> different like description, or size or something of that nature.
> >>>
> >>> The set will reduce the number of elements. Before I change it to be a
> >>> list
> >>> that can have duplicates, I would like to know the origin of the set and
> >>> if
> >>> there are going to be any issues when I do that.
> >>
> >> It was originally conceived as a way to consistently keep items in a
> >> sorted manner, whether they're added via setItems() or getItems().add().
> >> It had nothing to do with the fact that duplicates aren't allowed, so I
> >> doubt a change will adversely affect current uses (of which there aren't
> >> many, if I'm not mistaken, so it's better to verify).
> >>
> >> However, a list doesn't automatically sort itself as items are added, so
> >> you should preserve that functionality if you decide to change the
> >> implementation.
> >>
> >> You could implement a customized List that invokes sort() upon add(). I
> >> think the current implementation is far more efficient in that insertion
> >> and removal is done in O(logn), whereas the alternative would be O(n).
> >> You might say that's not important, I think it might be important for
> >> scalability in the future.
> >>
> > 
> > Personally I think that having correct behavior is more important than
> > having
> > incorrect but fast behavior. Basically the set works fine if you use the
> > natural order of the objects. However if you pass in a different Comparator
> > the
> > set falls apart as you now potentially have duplicates based on the
> > Comparator. A good example is entities with a description or comment field.
> > If
> > I pass in a Comparator that simply compares the description field of the
> > entities, I can and do have duplicates. The resulting collection is now
> > smaller than the original which is obviously not what we want.
> 
> First of all, I'm not sure that description and comment are useful
> columns to sort by.
> 
> Secondly, I saw you mentioned in another thread that you were using a
> compound comparator with a secondary property to sort by - I think this
> is a very correct solution, and actually something we should do
> regardless of the issue you raised; otherwise on refresh items could
> switch places. So I would try to have comparators enforce a consistent
> ordering (i.e. never return 0).
> 
> By the way, a good secondary sort property would be the item's position
> in the collection prior to sorting. This would enable users to
> implicitly define secondary (and tertiary, etc.) sort criteria,
> according to the order in which they clicked on column headers. And of
> course it satisfies consistency.
> 
> When I get to the network-related sorting (next couple of days) I'll see
> if I can design a nice shareable utility to help with that and put it in
> the Linq class.
> 
> > 
> > You are right that I will be unable to force a sort when someone does a
> > getItems.add. There seems to be only one data structure in java that is
> > automatically sorted on adds as well as allows for duplicate entries, which
> > is
> > a PriorityQueue.  Since we are using Collections this should not be a
> > problem,
> > however if anyone casts it to a list, it will explode.
> > 
> 
> ...or SortedSet, which is why it was used :) And which would also
> explode if cast to List. Which is okay because ListModel only guarantees
> a Collection to be returned - casting to List isn't great practice.
> 
> There is the other choice of using a customized List in ListModel, which
> would work perfectly fine. But if comparators are constructed so that
> they never return 0, as discussed above, this becomes a non-issue.
> 
> >> But frankly, it's not difficult to notice what one inserts into their
> >> SortedListModel, and to make sure that its equals() method is consistent
> >> with what they're trying to achieve (or wrap the items in case it isn't).
> >>
> >>> Thanks,
> >>> Alexander
> >>> _______________________________________________
> >>> Devel mailing list
> >>> Devel at ovirt.org
> >>> http://lists.ovirt.org/mailman/listinfo/devel
> > 
> _______________________________________________
> Devel mailing list
> Devel at ovirt.org
> http://lists.ovirt.org/mailman/listinfo/devel
> 