Skip to content

Commit 249ee1d

Browse files
itakurahitakurah
authored
Add 2P-Set (Two-Phase Set) for both addition and removal operations in distributed systems (TheAlgorithms#4977)
1 parent 36580ba commit 249ee1d

File tree

3 files changed

+155
-1
lines changed

3 files changed

+155
-1
lines changed

‎DIRECTORY.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@
8686
* [GCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GCounter.java)
8787
* [GSet](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GSet.java)
8888
* [PNCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/PNCounter.java)
89+
* [TwoPSet](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/TwoPSet.java)
8990
* disjointsetunion
9091
* [DisjointSetUnion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java)
9192
* [Node](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java)
@@ -528,7 +529,7 @@
528529
* [InfixToPostfix](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/InfixToPostfix.java)
529530
* [LargestRectangle](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/LargestRectangle.java)
530531
* [MaximumMinimumWindow](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/MaximumMinimumWindow.java)
531-
* [NextGraterElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/NextGraterElement.java)
532+
* [NextGreaterElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/NextGreaterElement.java)
532533
* [NextSmallerElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/NextSmallerElement.java)
533534
* [PostfixToInfix](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/PostfixToInfix.java)
534535
* [StackPostfixNotation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/StackPostfixNotation.java)
@@ -621,6 +622,7 @@
621622
* [GCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GCounterTest.java)
622623
* [GSetTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GSetTest.java)
623624
* [PNCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/PNCounterTest.java)
625+
* [TwoPSetTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/TwoPSetTest.java)
624626
* disjointsetunion
625627
* [DisjointSetUnionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java)
626628
* graphs

‎src/main/java/com/thealgorithms/datastructures/crdt/TwoPSet.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.thealgorithms.datastructures.crdt;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* TwoPhaseSet (2P-Set) is a state-based CRDT (Conflict-free Replicated Data Type) designed for managing sets
8+
* with support for both addition and removal operations in a distributed and concurrent environment.
9+
* It combines two G-Sets (grow-only sets) - one set for additions and another set (tombstone set) for removals.
10+
* Once an element is removed and placed in the tombstone set, it cannot be re-added, adhering to "remove-wins" semantics.
11+
* This implementation supports querying the presence of elements, adding elements, removing elements,
12+
* comparing with other 2P-Sets, and merging two 2P-Sets while preserving the remove-wins semantics.
13+
* (https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type)
14+
*
15+
* @author itakurah (Niklas Hoefflin) (https://github.com/itakurah)
16+
*/
17+
18+
public class TwoPSet {
19+
private Set<String> setA;
20+
private Set<String> setR;
21+
22+
/**
23+
* Constructs an empty Two-Phase Set.
24+
*/
25+
public TwoPSet() {
26+
this.setA = new HashSet<>();
27+
this.setR = new HashSet<>();
28+
}
29+
30+
/**
31+
* Checks if an element is in the set and has not been removed.
32+
*
33+
* @param element The element to be checked.
34+
* @return True if the element is in the set and has not been removed, otherwise false.
35+
*/
36+
public boolean lookup(String element) {
37+
return setA.contains(element) && !setR.contains(element);
38+
}
39+
40+
/**
41+
* Adds an element to the set.
42+
*
43+
* @param element The element to be added.
44+
*/
45+
public void add(String element) {
46+
setA.add(element);
47+
}
48+
49+
/**
50+
* Removes an element from the set. The element will be placed in the tombstone set.
51+
*
52+
* @param element The element to be removed.
53+
*/
54+
public void remove(String element) {
55+
if (lookup(element)) {
56+
setR.add(element);
57+
}
58+
}
59+
60+
/**
61+
* Compares the current 2P-Set with another 2P-Set.
62+
*
63+
* @param otherSet The other 2P-Set to compare with.
64+
* @return True if both SetA and SetR are subset, otherwise false.
65+
*/
66+
public boolean compare(TwoPSet otherSet) {
67+
return otherSet.setA.containsAll(setA) && otherSet.setR.containsAll(setR);
68+
}
69+
70+
/**
71+
* Merges the current 2P-Set with another 2P-Set.
72+
*
73+
* @param otherSet The other 2P-Set to merge with.
74+
* @return A new 2P-Set containing the merged elements.
75+
*/
76+
public TwoPSet merge(TwoPSet otherSet) {
77+
TwoPSet mergedSet = new TwoPSet();
78+
mergedSet.setA.addAll(this.setA);
79+
mergedSet.setA.addAll(otherSet.setA);
80+
mergedSet.setR.addAll(this.setR);
81+
mergedSet.setR.addAll(otherSet.setR);
82+
return mergedSet;
83+
}
84+
}

‎src/test/java/com/thealgorithms/datastructures/crdt/TwoPSetTest.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.thealgorithms.datastructures.crdt;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import org.junit.jupiter.api.BeforeEach;
6+
import org.junit.jupiter.api.Test;
7+
8+
class TwoPSetTest {
9+
10+
private TwoPSet set;
11+
12+
@BeforeEach
13+
void setUp() {
14+
set = new TwoPSet();
15+
}
16+
17+
@Test
18+
void testLookup() {
19+
set.add("A");
20+
assertTrue(set.lookup("A"));
21+
assertFalse(set.lookup("B"));
22+
set.remove("A");
23+
assertFalse(set.lookup("A"));
24+
}
25+
26+
@Test
27+
void testAdd() {
28+
set.add("A");
29+
assertTrue(set.lookup("A"));
30+
}
31+
32+
@Test
33+
void testRemove() {
34+
set.add("A");
35+
set.remove("A");
36+
assertFalse(set.lookup("A"));
37+
}
38+
39+
@Test
40+
void testCompare() {
41+
TwoPSet set1 = new TwoPSet();
42+
set1.add("A");
43+
set1.add("B");
44+
TwoPSet set2 = new TwoPSet();
45+
set2.add("A");
46+
assertFalse(set1.compare(set2));
47+
set2.add("B");
48+
assertTrue(set1.compare(set2));
49+
set1.remove("A");
50+
assertFalse(set1.compare(set2));
51+
set2.remove("A");
52+
assertTrue(set1.compare(set2));
53+
}
54+
55+
@Test
56+
void testMerge() {
57+
TwoPSet set1 = new TwoPSet();
58+
set1.add("A");
59+
set1.add("B");
60+
TwoPSet set2 = new TwoPSet();
61+
set2.add("B");
62+
set2.add("C");
63+
TwoPSet mergedSet = set1.merge(set2);
64+
assertTrue(mergedSet.lookup("A"));
65+
assertTrue(mergedSet.lookup("B"));
66+
assertTrue(mergedSet.lookup("C"));
67+
}
68+
}

0 commit comments

Comments
 (0)