Making a Set data structure in Java using Predicates only, no collections or arrays. How to implement iterator related features?

Question

Note: this is for practicing functional style programming, not for actual use.

I've created a Set implementation which uses Java Predicates to check if an object exists in the set or not. Adding an object is handled by creating a new Predicate (to check if the incoming object is equal to the newly added one), and OR-ing it with the previous predicates.

I have finished implementing and testing the basic features: contains, add, remove, intersect, setMinus, union.

However, I'm stuck on how to implement any iterator related functions, e.g. so that the user can use a for each loop.

Is there any functional way to do this? (i.e. avoiding Collections or arrays)

Here is what I have so far. I've also created some unit tests here.

import java.util.Collection; import java.util.function.Predicate; public class PredicateSet<E> { private Predicate<E> rootPredicate = e -> false; private int size = 0; public int size() { return size; } public boolean isEmpty() { return size == 0; } public boolean contains(Object o) { try { return rootPredicate.test((E) o); } catch (ClassCastException cce) { return false; } } public boolean add(E e) { if (contains(e)) return false; Predicate<E> newPredicate = e::equals; rootPredicate = newPredicate.or(rootPredicate); size++; return true; } public boolean remove(Object o) { try { if (!contains(o)) return false; } catch (ClassCastException cce) { return false; } E e = (E) o; Predicate<E> newPredicate = e::equals; rootPredicate = newPredicate.negate().and(rootPredicate); size--; return true; } public boolean containsAll(Collection<? extends E> c) { return c.stream().allMatch(this::contains); } public boolean addAll(Collection<? extends E> c) { var changed = false; for (E e : c) { if (add(e)) changed = true; } return changed; } public boolean removeAll(Collection<? extends E> c) { var changed = false; for (E e : c) { if (remove(e)) changed = true; } return changed; } public boolean intersect(Collection<? extends E> c) { PredicateSet<E> intersection = new PredicateSet<>(); for (var x : c) { try { if (contains(x)) intersection.add(x); } catch (ClassCastException ignored) { } } var changed = this.size != intersection.size; this.rootPredicate = intersection.rootPredicate; this.size = intersection.size; return changed; } public boolean setMinus(Collection<? extends E> c) { var changed = false; for (var x : c) { try { if (remove(x)) changed = true; } catch (ClassCastException ignored) { } } return changed; } public boolean union(Collection<? extends E> c) { var changed = false; for (var x : c) { try { if (add(x)) changed = true; } catch (ClassCastException ignored) { } } return changed; } public void clear() { this.size = 0; rootPredicate = e -> false; } }

vkourt · Accepted Answer · 2018-08-28 16:47:54Z

I'm really struggling to understand how you're trying to implement a data structure that holds values without an underlying data structure to store said values.

Your various methods that actually update the contents of the data structure do nothing other than return true or false based on the result on the tested predicate.

For instance, HashSet which is an implementation of the Set interface (itself an extension of the Collection interface) uses a HashMap as an underlying backing data structure.

I suppose that since you're attempting to implement something similar, albeit with the usage of Predicate you should consider something similar.

Thus if you really want to proceed with this, you could have the implementation use the List object as the backing data structure. With that in hand your PredicateSet class, would need to go ahead and extend the AbstractSet class (thus obtaining all of each functionality) as well as implement the Set interface.

If done correctly your class will then need to provide and iterator implementation which would then automatically allow to use the AbstractCollection#toArray method.

I would suggest to read up on the implementation of HashSet to get some more ideas.

I suppose this is my attempt at creating a purely functional data structure, albeit not exactly pure, since I keep track of the size. Currently, the basic set operations already work (add, remove, contains, intersect, union, setMinus). The only missing part is the iterator implementation. If possible, I want to do it in a functional style, i.e. avoiding using any collections to store the data.
I think you're failing to understand the definition and I quote In computer science, a purely functional data structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable.. This means that purely functional data structures are the one that are immutable. Furthermore, you can't have a collection of elements without a place to store those N elements.

Collectives™ on Stack Overflow

Making a Set data structure in Java using Predicates only, no collections or arrays. How to implement iterator related features?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related