Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DistinctMappedList #54

Open
thomasnield opened this issue Mar 9, 2016 · 17 comments
Open

DistinctMappedList #54

thomasnield opened this issue Mar 9, 2016 · 17 comments

Comments

@thomasnield
Copy link

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
Copy link
Author

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

@JordanMartinez
Copy link
Contributor

@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
Copy link
Author

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

@JordanMartinez
Copy link
Contributor

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
Copy link
Author

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
Copy link
Owner

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
Copy link
Author

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
Copy link
Author

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

@JordanMartinez
Copy link
Contributor

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

@TomasMikula
Copy link
Owner

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
Copy link
Owner

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

@thomasnield
Copy link
Author

... 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
Copy link
Owner

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
Copy link
Author

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
Copy link
Author

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
Copy link
Owner

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
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants
@TomasMikula @thomasnield @JordanMartinez and others