Repository: TheAlgorithms/Java
Pull request #4979 (2023-12-08 14:39:55)

Introduce LWW-Element-Set (Last-Write-Wins-Element-Set) for managing sets in a distributed and concurrent environment
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

This PR consists of an implementation of a LWW-Element-Set (Last-Write-Wins-Element-Set), which is a state-based CRDT (Conflict-free Replicated Data Type) for managing sets in a distributed and concurrent environment.

See: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized it.
- [X] All filenames are in PascalCase.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [X] All new code is formatted with `clang-format -i --style=file path/to/your/file.java


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 703642a0..f033416d 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -85,6 +85,7 @@
             * crdt
               * [GCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GCounter.java)
               * [GSet](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GSet.java)
+              * [LWWElementSet](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java)
               * [PNCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/PNCounter.java)
               * [TwoPSet](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/TwoPSet.java)
             * disjointsetunion
@@ -621,6 +622,7 @@
             * crdt
               * [GCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GCounterTest.java)
               * [GSetTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GSetTest.java)
+              * [LWWElementSetTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java)
               * [PNCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/PNCounterTest.java)
               * [TwoPSetTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/TwoPSetTest.java)
             * disjointsetunion
diff --git a/src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java b/src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java
new file mode 100644
index 00000000..722c916a
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java
@@ -0,0 +1,138 @@
+package com.thealgorithms.datastructures.crdt;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Last-Write-Wins Element Set (LWWElementSet) is a state-based CRDT (Conflict-free Replicated Data Type)
+ * designed for managing sets in a distributed and concurrent environment. It supports the addition and removal
+ * of elements, using timestamps to determine the order of operations. The set is split into two subsets:
+ * the add set for elements to be added and the remove set for elements to be removed.
+ *
+ * @author itakurah (Niklas Hoefflin) (https://github.com/itakurah)
+ * @see <a href="https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type">Conflict-free_replicated_data_type</a>
+ * @see <a href="https://github.com/itakurah">itakurah (Niklas Hoefflin)</a>
+ */
+
+class Element {
+    String key;
+    int timestamp;
+    Bias bias;
+
+    /**
+     * Constructs a new Element with the specified key, timestamp and bias.
+     *
+     * @param key       The key of the element.
+     * @param timestamp The timestamp associated with the element.
+     * @param bias      The bias of the element (ADDS or REMOVALS).
+     */
+    public Element(String key, int timestamp, Bias bias) {
+        this.key = key;
+        this.timestamp = timestamp;
+        this.bias = bias;
+    }
+}
+
+enum Bias {
+    /**
+     * ADDS bias for the add set.
+     * REMOVALS bias for the remove set.
+     */
+    ADDS,
+    REMOVALS
+}
+
+class LWWElementSet {
+    private final Map<String, Element> addSet;
+    private final Map<String, Element> removeSet;
+
+    /**
+     * Constructs an empty LWWElementSet.
+     */
+    public LWWElementSet() {
+        this.addSet = new HashMap<>();
+        this.removeSet = new HashMap<>();
+    }
+
+    /**
+     * Adds an element to the addSet.
+     *
+     * @param e The element to be added.
+     */
+    public void add(Element e) {
+        addSet.put(e.key, e);
+    }
+
+    /**
+     * Removes an element from the removeSet.
+     *
+     * @param e The element to be removed.
+     */
+    public void remove(Element e) {
+        if (lookup(e)) {
+            removeSet.put(e.key, e);
+        }
+    }
+
+    /**
+     * Checks if an element is in the LWWElementSet by comparing timestamps in the addSet and removeSet.
+     *
+     * @param e The element to be checked.
+     * @return True if the element is present, false otherwise.
+     */
+    public boolean lookup(Element e) {
+        Element inAddSet = addSet.get(e.key);
+        Element inRemoveSet = removeSet.get(e.key);
+
+        return (inAddSet != null && (inRemoveSet == null || inAddSet.timestamp > inRemoveSet.timestamp));
+    }
+
+    /**
+     * Compares the LWWElementSet with another LWWElementSet to check if addSet and removeSet are a subset.
+     *
+     * @param other The LWWElementSet to compare.
+     * @return True if the set is subset, false otherwise.
+     */
+    public boolean compare(LWWElementSet other) {
+        return other.addSet.keySet().containsAll(addSet.keySet()) && other.removeSet.keySet().containsAll(removeSet.keySet());
+    }
+
+    /**
+     * Merges another LWWElementSet into this set by resolving conflicts based on timestamps.
+     *
+     * @param other The LWWElementSet to merge.
+     */
+    public void merge(LWWElementSet other) {
+        for (Element e : other.addSet.values()) {
+            if (!addSet.containsKey(e.key) || compareTimestamps(addSet.get(e.key), e)) {
+                addSet.put(e.key, e);
+            }
+        }
+
+        for (Element e : other.removeSet.values()) {
+            if (!removeSet.containsKey(e.key) || compareTimestamps(removeSet.get(e.key), e)) {
+                removeSet.put(e.key, e);
+            }
+        }
+    }
+
+    /**
+     * Compares timestamps of two elements based on their bias (ADDS or REMOVALS).
+     *
+     * @param e     The first element.
+     * @param other The second element.
+     * @return True if the first element's timestamp is greater or the bias is ADDS and timestamps are equal.
+     */
+    public boolean compareTimestamps(Element e, Element other) {
+        if (!e.bias.equals(other.bias)) {
+            throw new IllegalArgumentException("Invalid bias value");
+        }
+        Bias bias = e.bias;
+        int timestampComparison = Integer.compare(e.timestamp, other.timestamp);
+
+        if (timestampComparison == 0) {
+            return !bias.equals(Bias.ADDS);
+        }
+        return timestampComparison < 0;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java b/src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java
new file mode 100644
index 00000000..6fb227bd
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java
@@ -0,0 +1,107 @@
+package com.thealgorithms.datastructures.crdt;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+class LWWElementSetTest {
+
+    private LWWElementSet set;
+    private final Bias bias = Bias.ADDS;
+
+    @BeforeEach
+    void setUp() {
+        set = new LWWElementSet();
+    }
+
+    @Test
+    void testAdd() {
+        Element element = new Element("key1", 1, bias);
+        set.add(element);
+
+        assertTrue(set.lookup(element));
+    }
+
+    @Test
+    void testRemove() {
+        Element element = new Element("key1", 1, bias);
+        set.add(element);
+        set.remove(element);
+
+        assertFalse(set.lookup(element));
+    }
+
+    @Test
+    void testRemoveNonexistentElement() {
+        Element element = new Element("key1", 1, bias);
+        set.remove(element);
+
+        assertFalse(set.lookup(element));
+    }
+
+    @Test
+    void testLookupNonexistentElement() {
+        Element element = new Element("key1", 1, bias);
+
+        assertFalse(set.lookup(element));
+    }
+
+    @Test
+    void testCompareEqualSets() {
+        LWWElementSet otherSet = new LWWElementSet();
+
+        Element element = new Element("key1", 1, bias);
+        set.add(element);
+        otherSet.add(element);
+
+        assertTrue(set.compare(otherSet));
+
+        otherSet.add(new Element("key2", 2, bias));
+        assertTrue(set.compare(otherSet));
+    }
+
+    @Test
+    void testCompareDifferentSets() {
+        LWWElementSet otherSet = new LWWElementSet();
+
+        Element element1 = new Element("key1", 1, bias);
+        Element element2 = new Element("key2", 2, bias);
+
+        set.add(element1);
+        otherSet.add(element2);
+
+        assertFalse(set.compare(otherSet));
+    }
+
+    @Test
+    void testMerge() {
+        LWWElementSet otherSet = new LWWElementSet();
+
+        Element element1 = new Element("key1", 1, bias);
+        Element element2 = new Element("key2", 2, bias);
+
+        set.add(element1);
+        otherSet.add(element2);
+
+        set.merge(otherSet);
+
+        assertTrue(set.lookup(element1));
+        assertTrue(set.lookup(element2));
+    }
+
+    @Test
+    void testCompareTimestampsEqualTimestamps() {
+        LWWElementSet lwwElementSet = new LWWElementSet();
+
+        Element e1 = new Element("key1", 10, Bias.REMOVALS);
+        Element e2 = new Element("key1", 10, Bias.REMOVALS);
+
+        assertTrue(lwwElementSet.compareTimestamps(e1, e2));
+
+        e1 = new Element("key1", 10, Bias.ADDS);
+        e2 = new Element("key1", 10, Bias.ADDS);
+
+        assertFalse(lwwElementSet.compareTimestamps(e1, e2));
+    }
+}