Skip to content

Commit d3a3213

Browse files
govardhanshah456govardhanshah456
authored
Make MedianOfRunningArray Generic (TheAlgorithms#4392)
1 parent 8803b1e commit d3a3213

7 files changed

Lines changed: 124 additions & 44 deletions

File tree

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java‎

Lines changed: 13 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -6,10 +6,10 @@
66
/**
77
* @author shrutisheoran
88
*/
9-
public class MedianOfRunningArray {
9+
public abstract class MedianOfRunningArray<T extends Number & Comparable<T>> {
1010

11-
private PriorityQueue<Integer> maxHeap;
12-
private PriorityQueue<Integer> minHeap;
11+
private PriorityQueue<T> maxHeap;
12+
private PriorityQueue<T> minHeap;
1313

1414
// Constructor
1515
public MedianOfRunningArray() {
@@ -21,8 +21,8 @@ public MedianOfRunningArray() {
2121
Inserting lower half of array to max Heap
2222
and upper half to min heap
2323
*/
24-
public void insert(Integer e) {
25-
if (!minHeap.isEmpty() && e < minHeap.peek()) {
24+
public void insert(final T e) {
25+
if (!minHeap.isEmpty() && e.compareTo(minHeap.peek()) < 0) {
2626
maxHeap.offer(e);
2727
if (maxHeap.size() > minHeap.size() + 1) {
2828
minHeap.offer(maxHeap.poll());
@@ -38,14 +38,16 @@ public void insert(Integer e) {
3838
/*
3939
Returns median at any given point
4040
*/
41-
public double median() {
41+
public T median() {
4242
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
4343
throw new IllegalArgumentException("Enter at least 1 element, Median of empty list is not defined!");
44+
} else if (maxHeap.size() == minHeap.size()) {
45+
T maxHeapTop = maxHeap.peek();
46+
T minHeapTop = minHeap.peek();
47+
return calculateAverage(maxHeapTop, minHeapTop);
4448
}
45-
46-
if (maxHeap.size() == minHeap.size()) {
47-
return (maxHeap.peek() + minHeap.peek()) / 2.0;
48-
}
49-
return maxHeap.size() > minHeap.size() ? maxHeap.peek() * 1.0 : minHeap.peek() * 1.0;
49+
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
5050
}
51+
52+
public abstract T calculateAverage(T a, T b);
5153
}

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArrayByte.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.thealgorithms.misc;
2+
3+
public final class MedianOfRunningArrayByte extends MedianOfRunningArray<Byte> {
4+
@Override
5+
public Byte calculateAverage(final Byte a, final Byte b) {
6+
return (byte) ((a + b) / 2);
7+
}
8+
}

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArrayDouble.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.thealgorithms.misc;
2+
3+
public final class MedianOfRunningArrayDouble extends MedianOfRunningArray<Double> {
4+
@Override
5+
public Double calculateAverage(final Double a, final Double b) {
6+
return (a + b) / 2.0d;
7+
}
8+
}

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArrayFloat.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.thealgorithms.misc;
2+
3+
public final class MedianOfRunningArrayFloat extends MedianOfRunningArray<Float> {
4+
@Override
5+
public Float calculateAverage(final Float a, final Float b) {
6+
return (a + b) / 2.0f;
7+
}
8+
}

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArrayInteger.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.thealgorithms.misc;
2+
3+
public final class MedianOfRunningArrayInteger extends MedianOfRunningArray<Integer> {
4+
@Override
5+
public Integer calculateAverage(final Integer a, final Integer b) {
6+
return (a + b) / 2;
7+
}
8+
}

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArrayLong.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.thealgorithms.misc;
2+
3+
public final class MedianOfRunningArrayLong extends MedianOfRunningArray<Long> {
4+
@Override
5+
public Long calculateAverage(final Long a, final Long b) {
6+
return (a + b) / 2L;
7+
}
8+
}

‎src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java‎

Lines changed: 71 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,87 +1,85 @@
11
package com.thealgorithms.misc;
22

33
import static org.junit.jupiter.api.Assertions.assertEquals;
4-
import static org.junit.jupiter.api.Assertions.assertFalse;
54
import static org.junit.jupiter.api.Assertions.assertThrows;
65

7-
import org.apache.commons.lang3.tuple.Pair;
86
import org.junit.jupiter.api.Test;
97

108
/**
11-
* Test case for Two sum Problem.
12-
* @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
9+
* Test case for Median Of Running Array Problem.
10+
* @author Ansh Shah (https://github.com/govardhanshah456)
1311
*/
1412

1513
public class MedianOfRunningArrayTest {
1614
private static final String EXCEPTION_MESSAGE = "Enter at least 1 element, Median of empty list is not defined!";
1715

1816
@Test
1917
public void testWhenInvalidInoutProvidedShouldThrowException() {
20-
MedianOfRunningArray stream = new MedianOfRunningArray();
18+
var stream = new MedianOfRunningArrayInteger();
2119
IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> stream.median());
2220
assertEquals(exception.getMessage(), EXCEPTION_MESSAGE);
2321
}
2422

2523
@Test
2624
public void testWithNegativeValues() {
27-
MedianOfRunningArray stream = new MedianOfRunningArray();
25+
var stream = new MedianOfRunningArrayInteger();
2826
stream.insert(-1);
2927
assertEquals(-1, stream.median());
3028
stream.insert(-2);
31-
assertEquals(-1.5, stream.median());
29+
assertEquals(-1, stream.median());
3230
stream.insert(-3);
3331
assertEquals(-2, stream.median());
3432
}
3533

3634
@Test
3735
public void testWithSingleValues() {
38-
MedianOfRunningArray stream = new MedianOfRunningArray();
36+
var stream = new MedianOfRunningArrayInteger();
3937
stream.insert(-1);
4038
assertEquals(-1, stream.median());
4139
}
4240

4341
@Test
4442
public void testWithRandomValues() {
45-
MedianOfRunningArray stream = new MedianOfRunningArray();
43+
var stream = new MedianOfRunningArrayInteger();
4644
stream.insert(10);
47-
assertEquals(10.0, stream.median());
45+
assertEquals(10, stream.median());
4846

4947
stream.insert(5);
50-
assertEquals(7.5, stream.median());
48+
assertEquals(7, stream.median());
5149

5250
stream.insert(20);
53-
assertEquals(10.0, stream.median());
51+
assertEquals(10, stream.median());
5452

5553
stream.insert(15);
56-
assertEquals(12.5, stream.median());
54+
assertEquals(12, stream.median());
5755

5856
stream.insert(25);
59-
assertEquals(15.0, stream.median());
57+
assertEquals(15, stream.median());
6058

6159
stream.insert(30);
62-
assertEquals(17.5, stream.median());
60+
assertEquals(17, stream.median());
6361

6462
stream.insert(35);
65-
assertEquals(20.0, stream.median());
63+
assertEquals(20, stream.median());
6664

6765
stream.insert(1);
68-
assertEquals(17.5, stream.median());
66+
assertEquals(17, stream.median());
6967
}
7068

7169
@Test
7270
public void testWithNegativeAndPositiveValues() {
73-
MedianOfRunningArray stream = new MedianOfRunningArray();
71+
var stream = new MedianOfRunningArrayInteger();
7472
stream.insert(-1);
7573
assertEquals(-1, stream.median());
7674
stream.insert(2);
77-
assertEquals(0.5, stream.median());
75+
assertEquals(0, stream.median());
7876
stream.insert(-3);
7977
assertEquals(-1, stream.median());
8078
}
8179

8280
@Test
8381
public void testWithDuplicateValues() {
84-
MedianOfRunningArray stream = new MedianOfRunningArray();
82+
var stream = new MedianOfRunningArrayInteger();
8583
stream.insert(-1);
8684
assertEquals(-1, stream.median());
8785
stream.insert(-1);
@@ -92,7 +90,7 @@ public void testWithDuplicateValues() {
9290

9391
@Test
9492
public void testWithDuplicateValuesB() {
95-
MedianOfRunningArray stream = new MedianOfRunningArray();
93+
var stream = new MedianOfRunningArrayInteger();
9694
stream.insert(10);
9795
stream.insert(20);
9896
stream.insert(10);
@@ -105,57 +103,97 @@ public void testWithDuplicateValuesB() {
105103

106104
@Test
107105
public void testWithLargeValues() {
108-
MedianOfRunningArray stream = new MedianOfRunningArray();
106+
var stream = new MedianOfRunningArrayInteger();
109107
stream.insert(1000000);
110108
assertEquals(1000000, stream.median());
111109
stream.insert(12000);
112110
assertEquals(506000, stream.median());
113111
stream.insert(15000000);
114112
assertEquals(1000000, stream.median());
115113
stream.insert(2300000);
116-
assertEquals(1650000.00, stream.median());
114+
assertEquals(1650000, stream.median());
117115
}
118116

119117
@Test
120118
public void testWithLargeCountOfValues() {
121-
MedianOfRunningArray stream = new MedianOfRunningArray();
119+
var stream = new MedianOfRunningArrayInteger();
122120
for (int i = 1; i <= 1000; i++) stream.insert(i);
123-
assertEquals(500.5, stream.median());
121+
assertEquals(500, stream.median());
124122
}
125123

126124
@Test
127125
public void testWithThreeValuesInDescendingOrder() {
128-
MedianOfRunningArray stream = new MedianOfRunningArray();
126+
var stream = new MedianOfRunningArrayInteger();
129127
stream.insert(30);
130128
stream.insert(20);
131129
stream.insert(10);
132-
assertEquals(20.0, stream.median());
130+
assertEquals(20, stream.median());
133131
}
134132

135133
@Test
136134
public void testWithThreeValuesInOrder() {
137-
MedianOfRunningArray stream = new MedianOfRunningArray();
135+
var stream = new MedianOfRunningArrayInteger();
138136
stream.insert(10);
139137
stream.insert(20);
140138
stream.insert(30);
141-
assertEquals(20.0, stream.median());
139+
assertEquals(20, stream.median());
142140
}
143141

144142
@Test
145143
public void testWithThreeValuesNotInOrderA() {
146-
MedianOfRunningArray stream = new MedianOfRunningArray();
144+
var stream = new MedianOfRunningArrayInteger();
147145
stream.insert(30);
148146
stream.insert(10);
149147
stream.insert(20);
150-
assertEquals(20.0, stream.median());
148+
assertEquals(20, stream.median());
151149
}
152150

153151
@Test
154152
public void testWithThreeValuesNotInOrderB() {
155-
MedianOfRunningArray stream = new MedianOfRunningArray();
153+
var stream = new MedianOfRunningArrayInteger();
156154
stream.insert(20);
157155
stream.insert(10);
158156
stream.insert(30);
159-
assertEquals(20.0, stream.median());
157+
assertEquals(20, stream.median());
158+
}
159+
160+
@Test
161+
public void testWithFloatValues() {
162+
var stream = new MedianOfRunningArrayFloat();
163+
stream.insert(20.0f);
164+
assertEquals(20.0f, stream.median());
165+
stream.insert(10.5f);
166+
assertEquals(15.25f, stream.median());
167+
stream.insert(30.0f);
168+
assertEquals(20.0f, stream.median());
169+
}
170+
171+
@Test
172+
public void testWithByteValues() {
173+
var stream = new MedianOfRunningArrayByte();
174+
stream.insert((byte) 120);
175+
assertEquals((byte) 120, stream.median());
176+
stream.insert((byte) -120);
177+
assertEquals((byte) 0, stream.median());
178+
stream.insert((byte) 127);
179+
assertEquals((byte) 120, stream.median());
180+
}
181+
182+
@Test
183+
public void testWithLongValues() {
184+
var stream = new MedianOfRunningArrayLong();
185+
stream.insert(120000000L);
186+
assertEquals(120000000L, stream.median());
187+
stream.insert(92233720368547757L);
188+
assertEquals(46116860244273878L, stream.median());
189+
}
190+
191+
@Test
192+
public void testWithDoubleValues() {
193+
var stream = new MedianOfRunningArrayDouble();
194+
stream.insert(12345.67891);
195+
assertEquals(12345.67891, stream.median());
196+
stream.insert(23456789.98);
197+
assertEquals(Double.valueOf(11734567.83), stream.median(), .01);
160198
}
161199
}

0 commit comments

Comments
 (0)