src/main/java/com/thealgorithms/datastructures/crdt/TwoPSet.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/datastructures/crdt/TwoPSet.java
84 строки3 KB
Niklas Hoefflin
Updated TwoPSet to use Generics instead of Strings (#4981)
11 дек 2023, 21:58
11 дек 2023, 21:584aa8e6a
package com.thealgorithms.datastructures.crdt;

import java.util.HashSet;
import java.util.Set;

/**
 * TwoPhaseSet (2P-Set) is a state-based CRDT (Conflict-free Replicated Data Type) designed for managing sets
 * with support for both addition and removal operations in a distributed and concurrent environment.
 * It combines two G-Sets (grow-only sets) - one set for additions and another set (tombstone set) for removals.
 * Once an element is removed and placed in the tombstone set, it cannot be re-added, adhering to "remove-wins" semantics.
 * This implementation supports querying the presence of elements, adding elements, removing elements,
 * comparing with other 2P-Sets, and merging two 2P-Sets while preserving the remove-wins semantics.
 * (https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type)
 *
 * @author itakurah (Niklas Hoefflin) (https://github.com/itakurah)
 */

public class TwoPSet<T> {
    private final Set<T> setA;
    private final Set<T> setR;

    /**
     * Constructs an empty Two-Phase Set.
     */
    public TwoPSet() {
        this.setA = new HashSet<>();
        this.setR = new HashSet<>();
    }

    /**
     * Checks if an element is in the set and has not been removed.
     *
     * @param element The element to be checked.
     * @return True if the element is in the set and has not been removed, otherwise false.
     */
    public boolean lookup(T element) {
        return setA.contains(element) && !setR.contains(element);
    }

    /**
     * Adds an element to the set.
     *
     * @param element The element to be added.
     */
    public void add(T element) {
        setA.add(element);
    }

    /**
     * Removes an element from the set. The element will be placed in the tombstone set.
     *
     * @param element The element to be removed.
     */
    public void remove(T element) {
        if (lookup(element)) {
            setR.add(element);
        }
    }

    /**
     * Compares the current 2P-Set with another 2P-Set.
     *
     * @param otherSet The other 2P-Set to compare with.
     * @return True if both SetA and SetR are subset, otherwise false.
     */
    public boolean compare(TwoPSet<T> otherSet) {
        return otherSet.setA.containsAll(setA) && otherSet.setR.containsAll(setR);
    }

    /**
     * Merges the current 2P-Set with another 2P-Set.
     *
     * @param otherSet The other 2P-Set to merge with.
     * @return A new 2P-Set containing the merged elements.
     */
    public TwoPSet<T> merge(TwoPSet<T> otherSet) {
        TwoPSet<T> mergedSet = new TwoPSet<>();
        mergedSet.setA.addAll(this.setA);
        mergedSet.setA.addAll(otherSet.setA);
        mergedSet.setR.addAll(this.setR);
        mergedSet.setR.addAll(otherSet.setR);
        return mergedSet;
    }
}