Skip to content

Commit 3001620

Browse files
itakurahitakurah
authored
Add PN-Counter (#4974)
1 parent e759544 commit 3001620

File tree

3 files changed

+156
-0
lines changed

3 files changed

+156
-0
lines changed

‎DIRECTORY.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,7 @@
8484
* [MRUCache](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java)
8585
* crdt
8686
* [GCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/GCounter.java)
87+
* [PNCounter](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/crdt/PNCounter.java)
8788
* disjointsetunion
8889
* [DisjointSetUnion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java)
8990
* [Node](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java)
@@ -617,6 +618,7 @@
617618
* [MRUCacheTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/caches/MRUCacheTest.java)
618619
* crdt
619620
* [GCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/GCounterTest.java)
621+
* [PNCounterTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/crdt/PNCounterTest.java)
620622
* disjointsetunion
621623
* [DisjointSetUnionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java)
622624
* graphs

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

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package com.thealgorithms.datastructures.crdt;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* PN-Counter (Positive-Negative Counter) is a state-based CRDT (Conflict-free Replicated Data Type)
8+
* designed for tracking counts with both increments and decrements in a distributed and concurrent environment.
9+
* It combines two G-Counters, one for increments (P) and one for decrements (N).
10+
* The total count is obtained by subtracting the value of the decrement counter from the increment counter.
11+
* This implementation supports incrementing, decrementing, querying the total count,
12+
* comparing with other PN-Counters, and merging with another PN-Counter
13+
* to compute the element-wise maximum for both increment and decrement counters.
14+
* (https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type)
15+
*
16+
* @author itakurah (Niklas Hoefflin) (https://github.com/itakurah)
17+
*/
18+
19+
class PNCounter {
20+
private final Map<Integer, Integer> P;
21+
private final Map<Integer, Integer> N;
22+
private final int myId;
23+
private final int n;
24+
25+
/**
26+
* Constructs a PN-Counter for a cluster of n nodes.
27+
*
28+
* @param myId The identifier of the current node.
29+
* @param n The number of nodes in the cluster.
30+
*/
31+
public PNCounter(int myId, int n) {
32+
this.myId = myId;
33+
this.n = n;
34+
this.P = new HashMap<>();
35+
this.N = new HashMap<>();
36+
37+
for (int i = 0; i < n; i++) {
38+
P.put(i, 0);
39+
N.put(i, 0);
40+
}
41+
}
42+
43+
/**
44+
* Increments the increment counter for the current node.
45+
*/
46+
public void increment() {
47+
P.put(myId, P.get(myId) + 1);
48+
}
49+
50+
/**
51+
* Increments the decrement counter for the current node.
52+
*/
53+
public void decrement() {
54+
N.put(myId, N.get(myId) + 1);
55+
}
56+
57+
/**
58+
* Gets the total value of the counter by subtracting the decrement counter from the increment counter.
59+
*
60+
* @return The total value of the counter.
61+
*/
62+
public int value() {
63+
int sumP = P.values().stream().mapToInt(Integer::intValue).sum();
64+
int sumN = N.values().stream().mapToInt(Integer::intValue).sum();
65+
return sumP - sumN;
66+
}
67+
68+
/**
69+
* Compares the state of this PN-Counter with another PN-Counter.
70+
*
71+
* @param other The other PN-Counter to compare with.
72+
* @return True if the state of this PN-Counter is less than or equal to the state of the other PN-Counter.
73+
*/
74+
public boolean compare(PNCounter other) {
75+
if (this.n != other.n) {
76+
throw new IllegalArgumentException("Cannot compare PN-Counters with different number of nodes");
77+
}
78+
for (int i = 0; i < n; i++) {
79+
if (this.P.get(i) > other.P.get(i) && this.N.get(i) > other.N.get(i)) {
80+
return false;
81+
}
82+
}
83+
return true;
84+
}
85+
86+
/**
87+
* Merges the state of this PN-Counter with another PN-Counter.
88+
*
89+
* @param other The other PN-Counter to merge with.
90+
*/
91+
public void merge(PNCounter other) {
92+
if (this.n != other.n) {
93+
throw new IllegalArgumentException("Cannot merge PN-Counters with different number of nodes");
94+
}
95+
for (int i = 0; i < n; i++) {
96+
this.P.put(i, Math.max(this.P.get(i), other.P.get(i)));
97+
this.N.put(i, Math.max(this.N.get(i), other.N.get(i)));
98+
}
99+
}
100+
}

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

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.thealgorithms.datastructures.crdt;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class PNCounterTest {
8+
9+
@Test
10+
public void testIncrement() {
11+
PNCounter counter = new PNCounter(0, 3);
12+
counter.increment();
13+
assertEquals(1, counter.value());
14+
}
15+
16+
@Test
17+
public void testDecrement() {
18+
PNCounter counter = new PNCounter(0, 3);
19+
counter.decrement();
20+
assertEquals(-1, counter.value());
21+
}
22+
23+
@Test
24+
public void testIncrementAndDecrement() {
25+
PNCounter counter = new PNCounter(0, 3);
26+
counter.increment();
27+
counter.increment();
28+
counter.decrement();
29+
assertEquals(1, counter.value());
30+
}
31+
32+
@Test
33+
public void testCompare() {
34+
PNCounter counter1 = new PNCounter(0, 3);
35+
counter1.increment();
36+
PNCounter counter2 = new PNCounter(1, 3);
37+
assertTrue(counter1.compare(counter2));
38+
counter2.increment();
39+
assertTrue(counter2.compare(counter1));
40+
counter1.decrement();
41+
assertFalse(counter1.compare(counter2));
42+
}
43+
44+
@Test
45+
public void testMerge() {
46+
PNCounter counter1 = new PNCounter(0, 3);
47+
counter1.increment();
48+
counter1.increment();
49+
PNCounter counter2 = new PNCounter(1, 3);
50+
counter2.increment();
51+
counter1.merge(counter2);
52+
assertEquals(3, counter1.value());
53+
}
54+
}

0 commit comments

Comments
 (0)