DistinctMappedList

[thomasnield]

It would be nice to see a DistinctMappedList<R> that allows you to take a source ObservableList<T>, and map each T item to R and produce an ObservableList<R> that only holds distinct instances.

ObservableList<String> values = 
    FXCollections.observableArrayList("Alpha","Beta","Gamma","Delta","Epsilon");

DistinctMappedList<Integer> distinctLengths = new DistinctMappedList<>(values,v -> v.length());

distinctLengths would then only contain elements 5, 4, and 7 until more elements are added to values. A use case this would have been helpful is an Excel-like table filter control I contributed to ControlsFX.

I thought about adding this to the RxJavaFX project. But I think ReactFX would be a better home for something like this. RxJavaFX is not seeking to improve JavaFX but rather simply enable interoperability between RxJava and JavaFX.

[thomasnield]

I supposed you could just come up with a DistinctList implementation and pass it a MappedList as well.

[JordanMartinez]

@thomasnield Your second approach would be more modular, especially if no mapping was desired. Otherwise, you'd have something like:

ObservableList<Integer> values = FXCollections.observableArrayList(3, 3, 3, 2, 5, 1, 3, 5);
DistinctList<Integer> distinctValues = new DistinctList(values, Function.identity());

and not

DistinctList<Integer> distinctValues = new DistinctList(values);

[thomasnield]

Yeah, that was my thought too. I might put in a PR just for the exercise.

[JordanMartinez]

Do it!!!! lol.... However, just a headsup, Tomas is a bit busy with some other things so I'm not sure how soon he'd merge that. Still, he might respond sooner rather than later

[thomasnield]

I'm sure he is. I'm in no rush either but I may put this on my docket. If anybody else wants to run with this I wont mind though.

[TomasMikula]

Go for it!

I think an efficient implementation is far from trivial. (Let's define "efficient" as: a one-element change in the underlying list of size n should require at most O(log n) time to generate a change in the distinct list.)

[thomasnield]

Dang it, and I've never been good at those kinds of algorithms. The best I can think of is porting this RxJavaFX factory I've worked on and using that to drive a DistinctList.

Unless I start creating my own hashcode tracking system, is there anything better than a HashSet?

[thomasnield]

Oh, or are you referring to the calculations occupying the UI thread?

[JordanMartinez]

Since ReactFX can also be used for threads other than the JavaFX Application Thread, I'm guessing he's not referring to that...?

[TomasMikula]

Doesn't matter which thread.

The implementation you linked to is not efficient, because it calls source.contains which is O(n). I believe you would be able to optimize that. But even then, I don't see a straightforward way to extend it to keep track of indices at which changes occur. (FXCollectionChange doesn't keep track of that, but to create an ObservableList, the changes need indices.)

[TomasMikula]

Re HashSet, it is of course OK to use a HashSet/HashMap inside.

[thomasnield]

... but not necessarily efficient like you said. I may try a pass anyway when I get time. If anybody has better ideas I'd be eager to hear their implementation. Maybe I could then borrow it for the ControlsFX TableFilter.

[TomasMikula]

The efficiency problem with the method you linked to does not come from HashSet, but from calling List#contains, which is linear time (O(n)). Basic operations on a HashSet are constant time (O(1)).

[thomasnield]

I forgot about that List#contains. Alright I'm glad I brought this up, I need to rethink if there's a better way.

[thomasnield]

Perhaps I can use a HashMap<T,Integer> to keep track of distinct instance counts instead of a HashSet, and increment/decrement for each dupe add/removal. When it hits zero then remove that key altogether.

[TomasMikula]

That will probably work for your RxJavaFX method. For DistinctList, it would be more like HashMap<T, List<Integer>>, to keep ordered list of all indices of an element. That's still not the whole story, but getting there :)

[thomasnield]

Thanks, I'll give it some thought. Trying to reason why I need to keep track of the order of items... I guess ill find out.