Создание структуры данных Set в Java с использованием только предикатов, без коллекций или массивов. Как реализовать функции, связанные с итератором? - PullRequest
Новая
       38

Создание структуры данных Set в Java с использованием только предикатов, без коллекций или массивов. Как реализовать функции, связанные с итератором?

0 голосов
/ 28 августа 2018

Примечание: это для практики программирования функционального стиля, а не для фактического использования.

Я создал реализацию Set, которая использует Java Predicates для проверки, существует ли объект в наборе или нет. Добавление объекта выполняется путем создания нового предиката (чтобы проверить, равен ли входящий объект вновь добавленному объекту) и ИЛИ с помощью предыдущих предикатов.

Я завершил реализацию и тестирование основных функций: contains, add, remove, intersect, setMinus, union.

Однако я застрял на том, как реализовать любые функции, связанные с итератором, например, так что пользователь может использовать цикл for each.

Есть ли функциональный способ сделать это? (т.е. избегая коллекций или массивов)

Вот что у меня есть. Я также создал несколько модульных тестов здесь . 

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;
    }
}

1 Ответ

0 голосов
/ 28 августа 2018

Я действительно изо всех сил пытаюсь понять, как вы пытаетесь реализовать структуру данных, которая хранит значения без базовой структуры данных для хранения указанных значений.

Ваши различные методы, которые фактически обновляют содержимое структуры данных, ничего не делают, кроме как возвращают true или false на основе результата проверенного предиката.

Например, HashSet, который является реализацией интерфейса Set (который сам является расширением интерфейса Collection), использует HashMap в качестве базовой структуры данных поддержки.

Я полагаю, что поскольку вы пытаетесь реализовать нечто подобное, хотя и с использованием Predicate, вам следует подумать о чем-то подобном.

Таким образом, если вы действительно хотите продолжить, вы можете использовать реализацию, использующую объект List в качестве вспомогательной структуры данных. Учитывая это, ваш класс PredicateSet должен был бы пойти дальше и расширить класс AbstractSet (таким образом получая все функциональные возможности), а также реализовать интерфейс Set.

Если все сделано правильно, ваш класс должен будет предоставить и реализацию iterator, которая бы автоматически позволяла использовать метод AbstractCollection#toArray.

Я бы посоветовал прочитать о реализации HashSet, чтобы получить больше идей.

...