Content-Length: 922455 | pFad | http://github.com/alxkm/TheAlgorithmsJava/commit/aeb7d4ad08f8db11ff86b9bb49c3514c92611375

05 Merge branch 'master' into testing/DequeTest · alxkm/TheAlgorithmsJava@aeb7d4a · GitHub
Skip to content

Commit aeb7d4a

Browse files
DenizAltunkapanDenizAltunkapan
authored
Merge branch 'master' into testing/DequeTest
2 parents 37de6e8 + 0e9be57 commit aeb7d4a

File tree

12 files changed

+464
-43
lines changed

12 files changed

+464
-43
lines changed

‎DIRECTORY.md

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
# Project Structure
22

3+
## src
4+
35
- 📁 **main**
46
- 📁 **java**
57
- 📁 **com**
@@ -165,12 +167,10 @@
165167
- 📄 [Kruskal](src/main/java/com/thealgorithms/datastructures/graphs/Kruskal.java)
166168
- 📄 [MatrixGraphs](src/main/java/com/thealgorithms/datastructures/graphs/MatrixGraphs.java)
167169
- 📄 [PrimMST](src/main/java/com/thealgorithms/datastructures/graphs/PrimMST.java)
168-
- 📄 [README](src/main/java/com/thealgorithms/datastructures/graphs/README.md)
169170
- 📄 [TarjansAlgorithm](src/main/java/com/thealgorithms/datastructures/graphs/TarjansAlgorithm.java)
170171
- 📄 [UndirectedAdjacencyListGraph](src/main/java/com/thealgorithms/datastructures/graphs/UndirectedAdjacencyListGraph.java)
171172
- 📄 [WelshPowell](src/main/java/com/thealgorithms/datastructures/graphs/WelshPowell.java)
172173
- 📁 **hashmap**
173-
- 📄 [Readme](src/main/java/com/thealgorithms/datastructures/hashmap/Readme.md)
174174
- 📁 **hashing**
175175
- 📄 [GenericHashMapUsingArray](src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArray.java)
176176
- 📄 [GenericHashMapUsingArrayList](src/main/java/com/thealgorithms/datastructures/hashmap/hashing/GenericHashMapUsingArrayList.java)
@@ -194,7 +194,6 @@
194194
- 📄 [MergeKSortedArrays](src/main/java/com/thealgorithms/datastructures/heaps/MergeKSortedArrays.java)
195195
- 📄 [MinHeap](src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java)
196196
- 📄 [MinPriorityQueue](src/main/java/com/thealgorithms/datastructures/heaps/MinPriorityQueue.java)
197-
- 📄 [Readme](src/main/java/com/thealgorithms/datastructures/heaps/Readme.md)
198197
- 📁 **lists**
199198
- 📄 [CircleLinkedList](src/main/java/com/thealgorithms/datastructures/lists/CircleLinkedList.java)
200199
- 📄 [CountSinglyLinkedListRecursion](src/main/java/com/thealgorithms/datastructures/lists/CountSinglyLinkedListRecursion.java)
@@ -205,7 +204,6 @@
205204
- 📄 [MergeSortedArrayList](src/main/java/com/thealgorithms/datastructures/lists/MergeSortedArrayList.java)
206205
- 📄 [MergeSortedSinglyLinkedList](src/main/java/com/thealgorithms/datastructures/lists/MergeSortedSinglyLinkedList.java)
207206
- 📄 [QuickSortLinkedList](src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java)
208-
- 📄 [README](src/main/java/com/thealgorithms/datastructures/lists/README.md)
209207
- 📄 [RandomNode](src/main/java/com/thealgorithms/datastructures/lists/RandomNode.java)
210208
- 📄 [ReverseKGroup](src/main/java/com/thealgorithms/datastructures/lists/ReverseKGroup.java)
211209
- 📄 [RotateSinglyLinkedLists](src/main/java/com/thealgorithms/datastructures/lists/RotateSinglyLinkedLists.java)
@@ -222,12 +220,10 @@
222220
- 📄 [PriorityQueues](src/main/java/com/thealgorithms/datastructures/queues/PriorityQueues.java)
223221
- 📄 [Queue](src/main/java/com/thealgorithms/datastructures/queues/Queue.java)
224222
- 📄 [QueueByTwoStacks](src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java)
225-
- 📄 [README](src/main/java/com/thealgorithms/datastructures/queues/README.md)
226223
- 📄 [SlidingWindowMaximum](src/main/java/com/thealgorithms/datastructures/queues/SlidingWindowMaximum.java)
227224
- 📄 [TokenBucket](src/main/java/com/thealgorithms/datastructures/queues/TokenBucket.java)
228225
- 📁 **stacks**
229226
- 📄 [NodeStack](src/main/java/com/thealgorithms/datastructures/stacks/NodeStack.java)
230-
- 📄 [README](src/main/java/com/thealgorithms/datastructures/stacks/README.md)
231227
- 📄 [ReverseStack](src/main/java/com/thealgorithms/datastructures/stacks/ReverseStack.java)
232228
- 📄 [Stack](src/main/java/com/thealgorithms/datastructures/stacks/Stack.java)
233229
- 📄 [StackArray](src/main/java/com/thealgorithms/datastructures/stacks/StackArray.java)
@@ -259,7 +255,6 @@
259255
- 📄 [PreOrderTraversal](src/main/java/com/thealgorithms/datastructures/trees/PreOrderTraversal.java)
260256
- 📄 [PrintTopViewofTree](src/main/java/com/thealgorithms/datastructures/trees/PrintTopViewofTree.java)
261257
- 📄 [QuadTree](src/main/java/com/thealgorithms/datastructures/trees/QuadTree.java)
262-
- 📄 [README](src/main/java/com/thealgorithms/datastructures/trees/README.md)
263258
- 📄 [RedBlackBST](src/main/java/com/thealgorithms/datastructures/trees/RedBlackBST.java)
264259
- 📄 [SameTreesCheck](src/main/java/com/thealgorithms/datastructures/trees/SameTreesCheck.java)
265260
- 📄 [SegmentTree](src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java)
@@ -749,7 +744,6 @@
749744
- 📄 [ValidParentheses](src/main/java/com/thealgorithms/strings/ValidParentheses.java)
750745
- 📄 [WordLadder](src/main/java/com/thealgorithms/strings/WordLadder.java)
751746
- 📁 **zigZagPattern**
752-
- 📄 [README](src/main/java/com/thealgorithms/strings/zigZagPattern/README.md)
753747
- 📄 [ZigZagPattern](src/main/java/com/thealgorithms/strings/zigZagPattern/ZigZagPattern.java)
754748
- 📁 **tree**
755749
- 📄 [HeavyLightDecomposition](src/main/java/com/thealgorithms/tree/HeavyLightDecomposition.java)
@@ -1048,6 +1042,7 @@
10481042
- 📄 [GrahamScanTest](src/test/java/com/thealgorithms/geometry/GrahamScanTest.java)
10491043
- 📄 [MidpointCircleTest](src/test/java/com/thealgorithms/geometry/MidpointCircleTest.java)
10501044
- 📄 [MidpointEllipseTest](src/test/java/com/thealgorithms/geometry/MidpointEllipseTest.java)
1045+
- 📄 [PointTest](src/test/java/com/thealgorithms/geometry/PointTest.java)
10511046
- 📁 **graph**
10521047
- 📄 [ConstrainedShortestPathTest](src/test/java/com/thealgorithms/graph/ConstrainedShortestPathTest.java)
10531048
- 📄 [StronglyConnectedComponentOptimizedTest](src/test/java/com/thealgorithms/graph/StronglyConnectedComponentOptimizedTest.java)
@@ -1416,4 +1411,4 @@
14161411
- 📁 **zigZagPattern**
14171412
- 📄 [ZigZagPatternTest](src/test/java/com/thealgorithms/strings/zigZagPattern/ZigZagPatternTest.java)
14181413
- 📁 **tree**
1419-
- 📄 [HeavyLightDecompositionTest](src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java)
1414+
- 📄 [HeavyLightDecompositionTest](src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java)

‎src/main/java/com/thealgorithms/maths/Median.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,13 @@ private Median() {
1313
* Calculate average median
1414
* @param values sorted numbers to find median of
1515
* @return median of given {@code values}
16+
* @throws IllegalArgumentException If the input array is empty or null.
1617
*/
1718
public static double median(int[] values) {
19+
if (values == null || values.length == 0) {
20+
throw new IllegalArgumentException("Values array cannot be empty or null");
21+
}
22+
1823
Arrays.sort(values);
1924
int length = values.length;
2025
return length % 2 == 0 ? (values[length / 2] + values[length / 2 - 1]) / 2.0 : values[length / 2];

‎src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java

Lines changed: 88 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
package com.thealgorithms.datastructures.disjointsetunion;
22

3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertNotEquals;
35
import static org.junit.jupiter.api.Assertions.assertNotNull;
46

5-
import org.junit.jupiter.api.Assertions;
67
import org.junit.jupiter.api.Test;
78

89
public class DisjointSetUnionTest {
@@ -12,7 +13,7 @@ public void testMakeSet() {
1213
DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
1314
Node<Integer> node = dsu.makeSet(1);
1415
assertNotNull(node);
15-
Assertions.assertEquals(node, node.parent);
16+
assertEquals(node, node.parent);
1617
}
1718

1819
@Test
@@ -33,19 +34,92 @@ public void testUnionFindSet() {
3334
Node<Integer> root3 = dsu.findSet(node3);
3435
Node<Integer> root4 = dsu.findSet(node4);
3536

36-
Assertions.assertEquals(node1, node1.parent);
37-
Assertions.assertEquals(node1, node2.parent);
38-
Assertions.assertEquals(node1, node3.parent);
39-
Assertions.assertEquals(node1, node4.parent);
37+
assertEquals(node1, node1.parent);
38+
assertEquals(node1, node2.parent);
39+
assertEquals(node1, node3.parent);
40+
assertEquals(node1, node4.parent);
4041

41-
Assertions.assertEquals(node1, root1);
42-
Assertions.assertEquals(node1, root2);
43-
Assertions.assertEquals(node1, root3);
44-
Assertions.assertEquals(node1, root4);
42+
assertEquals(node1, root1);
43+
assertEquals(node1, root2);
44+
assertEquals(node1, root3);
45+
assertEquals(node1, root4);
4546

46-
Assertions.assertEquals(1, node1.rank);
47-
Assertions.assertEquals(0, node2.rank);
48-
Assertions.assertEquals(0, node3.rank);
49-
Assertions.assertEquals(0, node4.rank);
47+
assertEquals(1, node1.rank);
48+
assertEquals(0, node2.rank);
49+
assertEquals(0, node3.rank);
50+
assertEquals(0, node4.rank);
51+
}
52+
53+
@Test
54+
public void testFindSetOnSingleNode() {
55+
DisjointSetUnion<String> dsu = new DisjointSetUnion<>();
56+
Node<String> node = dsu.makeSet("A");
57+
assertEquals(node, dsu.findSet(node));
58+
}
59+
60+
@Test
61+
public void testUnionAlreadyConnectedNodes() {
62+
DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
63+
Node<Integer> node1 = dsu.makeSet(1);
64+
Node<Integer> node2 = dsu.makeSet(2);
65+
Node<Integer> node3 = dsu.makeSet(3);
66+
67+
dsu.unionSets(node1, node2);
68+
dsu.unionSets(node2, node3);
69+
70+
// Union nodes that are already connected
71+
dsu.unionSets(node1, node3);
72+
73+
// All should have the same root
74+
Node<Integer> root = dsu.findSet(node1);
75+
assertEquals(root, dsu.findSet(node2));
76+
assertEquals(root, dsu.findSet(node3));
77+
}
78+
79+
@Test
80+
public void testRankIncrease() {
81+
DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
82+
Node<Integer> node1 = dsu.makeSet(1);
83+
Node<Integer> node2 = dsu.makeSet(2);
84+
Node<Integer> node3 = dsu.makeSet(3);
85+
Node<Integer> node4 = dsu.makeSet(4);
86+
87+
dsu.unionSets(node1, node2); // rank of node1 should increase
88+
dsu.unionSets(node3, node4); // rank of node3 should increase
89+
dsu.unionSets(node1, node3); // union two trees of same rank -> rank increases
90+
91+
assertEquals(2, dsu.findSet(node1).rank);
92+
}
93+
94+
@Test
95+
public void testMultipleMakeSets() {
96+
DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
97+
Node<Integer> node1 = dsu.makeSet(1);
98+
Node<Integer> node2 = dsu.makeSet(2);
99+
Node<Integer> node3 = dsu.makeSet(3);
100+
101+
assertNotEquals(node1, node2);
102+
assertNotEquals(node2, node3);
103+
assertNotEquals(node1, node3);
104+
105+
assertEquals(node1, node1.parent);
106+
assertEquals(node2, node2.parent);
107+
assertEquals(node3, node3.parent);
108+
}
109+
110+
@Test
111+
public void testPathCompression() {
112+
DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
113+
Node<Integer> node1 = dsu.makeSet(1);
114+
Node<Integer> node2 = dsu.makeSet(2);
115+
Node<Integer> node3 = dsu.makeSet(3);
116+
117+
dsu.unionSets(node1, node2);
118+
dsu.unionSets(node2, node3);
119+
120+
// After findSet, path compression should update parent to root directly
121+
Node<Integer> root = dsu.findSet(node3);
122+
assertEquals(root, node1);
123+
assertEquals(node1, node3.parent);
50124
}
51125
}

‎src/test/java/com/thealgorithms/datastructures/queues/PriorityQueuesTest.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,4 +55,60 @@ void testPQExtra() {
5555
Assertions.assertEquals(myQueue.peek(), 2);
5656
Assertions.assertEquals(myQueue.getSize(), 1);
5757
}
58+
59+
@Test
60+
void testInsertUntilFull() {
61+
PriorityQueue pq = new PriorityQueue(3);
62+
pq.insert(1);
63+
pq.insert(4);
64+
pq.insert(2);
65+
Assertions.assertTrue(pq.isFull());
66+
Assertions.assertEquals(4, pq.peek());
67+
}
68+
69+
@Test
70+
void testRemoveFromEmpty() {
71+
PriorityQueue pq = new PriorityQueue(3);
72+
Assertions.assertThrows(RuntimeException.class, pq::remove);
73+
}
74+
75+
@Test
76+
void testInsertDuplicateValues() {
77+
PriorityQueue pq = new PriorityQueue(5);
78+
pq.insert(5);
79+
pq.insert(5);
80+
pq.insert(3);
81+
Assertions.assertEquals(5, pq.peek());
82+
pq.remove();
83+
Assertions.assertEquals(5, pq.peek());
84+
pq.remove();
85+
Assertions.assertEquals(3, pq.peek());
86+
}
87+
88+
@Test
89+
void testSizeAfterInsertAndRemove() {
90+
PriorityQueue pq = new PriorityQueue(4);
91+
Assertions.assertEquals(0, pq.getSize());
92+
pq.insert(2);
93+
Assertions.assertEquals(1, pq.getSize());
94+
pq.insert(10);
95+
Assertions.assertEquals(2, pq.getSize());
96+
pq.remove();
97+
Assertions.assertEquals(1, pq.getSize());
98+
pq.remove();
99+
Assertions.assertEquals(0, pq.getSize());
100+
}
101+
102+
@Test
103+
void testInsertAndRemoveAll() {
104+
PriorityQueue pq = new PriorityQueue(3);
105+
pq.insert(8);
106+
pq.insert(1);
107+
pq.insert(6);
108+
Assertions.assertTrue(pq.isFull());
109+
pq.remove();
110+
pq.remove();
111+
pq.remove();
112+
Assertions.assertTrue(pq.isEmpty());
113+
}
58114
}

‎src/test/java/com/thealgorithms/divideandconquer/CountingInversionsTest.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,4 +29,35 @@ public void testAllInversions() {
2929
int[] arr = {5, 4, 3, 2, 1};
3030
assertEquals(10, CountingInversions.countInversions(arr));
3131
}
32+
33+
@Test
34+
public void testEmptyArray() {
35+
int[] arr = {};
36+
assertEquals(0, CountingInversions.countInversions(arr));
37+
}
38+
39+
@Test
40+
public void testArrayWithDuplicates() {
41+
int[] arr = {1, 3, 2, 3, 1};
42+
// Inversions: (3,2), (3,1), (3,1), (2,1)
43+
assertEquals(4, CountingInversions.countInversions(arr));
44+
}
45+
46+
@Test
47+
public void testLargeArray() {
48+
int n = 1000;
49+
int[] arr = new int[n];
50+
for (int i = 0; i < n; i++) {
51+
arr[i] = n - i; // descending order -> max inversions = n*(n-1)/2
52+
}
53+
int expected = n * (n - 1) / 2;
54+
assertEquals(expected, CountingInversions.countInversions(arr));
55+
}
56+
57+
@Test
58+
public void testArrayWithAllSameElements() {
59+
int[] arr = {7, 7, 7, 7};
60+
// No inversions since all elements are equal
61+
assertEquals(0, CountingInversions.countInversions(arr));
62+
}
3263
}

0 commit comments

Comments
 (0)








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/alxkm/TheAlgorithmsJava/commit/aeb7d4ad08f8db11ff86b9bb49c3514c92611375

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy