(See the next iteration.)
This question is an elaboration of my question. Just like the previous implementation, all operations (except clear) run in exact or amortized constant time.
I have taken into account all points made by @Emily L., and my data structure looks like this:
StatisticsNumberSet.java
package net.coderodde.stat;
import java.util.HashMap;
import java.util.Map;
/**
* This class aims for providing the user insertion, removal and statistics
* query operations, all in exact or amortized constant time. While adding a
* number runs in amortized constant time, deletion and query operations run in
* exact constant time. The query operations are size of the set, its average
* value, and its standard deviation.
* <p>
* The name <i>set</i> is a bit misleading: this data structure allows
* duplicate values and keeps track of them via a histogram (this is a
* multiset).
*
* @author Rodion "rodde" Efremov
* @version 1.61 (Mar 27, 2017)
*/
public class StatisticsNumberSet {
private double sum;
private double squareSum;
private int numberOfElements;
private final Map<Double, Integer> histogramMap = new HashMap<>();
/**
* Adds a new {@code double} value to this set.
*
* @param number the value to add to this set.
*/
public void add(double number) {
checkNumberIsNotNaN(number);
checkNumberIsNotInfinite(number);
histogramMap.put(number, histogramMap.getOrDefault(number, 0) + 1);
sum += number;
squareSum += number * number;
numberOfElements++;
}
/**
* Adds a new arbitrary number to this set.
*
* @param number the number to add to this set.
*/
public void add(Number number) {
add(number.doubleValue());
}
/**
* Attempts to remove the input {@code double} number, and does so if it is
* present in this set.
*
* @param number the value to remove.
* @return {@code true} only if the input value is present in this set prior
* to this operation, {@code false} otherwise.
*/
public boolean remove(double number) {
if (histogramMap.containsKey(number)) {
int oldCount = histogramMap.put(number,
histogramMap.get(number) - 1);
if (oldCount == 1) {
histogramMap.remove(number);
}
sum -= number;
squareSum -= number * number;
numberOfElements--;
return true;
} else {
return false;
}
}
/**
* Attempts to remove the input number, and does so if it is present in this
* set.
*
* @param number the number to remove.
* @return {@code true} only if the input number is present in this set
* prior to this operation, {@code false} otherwise.
*/
public boolean remove(Number number) {
return remove(number.doubleValue());
}
/**
* Removes all the values from this set.
*/
public void clear() {
histogramMap.clear();
sum = 0.0;
squareSum = 0.0;
numberOfElements = 0;
}
/**
* Returns the number of values stored in this set.
*
* @return the number of values stored.
*/
public int size() {
return numberOfElements;
}
/**
* Returns the current average value of this set.
*
* @return the average of this set.
*/
public double getAverage() {
if (numberOfElements == 0) {
return Double.NaN;
}
return sum / numberOfElements;
}
/**
* Returns the current standard deviation of this set.
*
* @return the standard deviation of this set.
*/
public double getStandardDeviation() {
switch (numberOfElements) {
case 1:
case 0:
return Double.NaN;
}
double step1 = squareSum - sum * sum / numberOfElements;
double step2 = step1 / (numberOfElements - 1);
return Math.sqrt(step2);
}
/**
* Returns a textual representation of this set.
*
* @return a textual representation.
*/
@Override
public String toString() {
return "[Size = " + numberOfElements + ", average = " + getAverage() +
", s.d. = " + getStandardDeviation() + "]";
}
public static void main(String[] args) {
StatisticsNumberSet set = new StatisticsNumberSet();
set.add(1);
set.add(1);
set.add(3);
System.out.println(set);
set.remove(1);
System.out.println(set);
}
private void checkNumberIsNotNaN(double number) {
if (Double.isNaN(number)) {
throw new IllegalArgumentException("The input number is NaN.");
}
}
private void checkNumberIsNotInfinite(double number) {
if (Double.isInfinite(number)) {
throw new IllegalArgumentException(
"The input number is infite: " + number);
}
}
}
StatisticsNumberSetTest.java
package net.coderodde.stat;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;
public class StatisticsNumberSetTest {
private static final double DELTA = 0.001;
private final StatisticsNumberSet set = new StatisticsNumberSet();
@Before
public void setUp() {
set.clear();
}
@Test
public void testAdd_double() {
set.add(1.0);
set.add(2.0);
assertEquals(2, set.size());
set.add(1.0);
assertEquals(3, set.size());
set.add(2.0);
assertEquals(4, set.size());
assertEquals(1.5, set.getAverage(), DELTA);
}
@Test
public void testAdd_Number() {
set.add(1);
set.add(2.0f);
assertEquals(2, set.size());
set.add(1L);
assertEquals(3, set.size());
set.add((short) 2);
assertEquals(4, set.size());
assertEquals(1.5, set.getAverage(), DELTA);
}
@Test
public void testRemove_double() {
set.add(10.0);
set.remove(10.0);
set.add(11);
set.remove(11.0);
assertEquals(0, set.size());
}
@Test
public void testRemove_Number() {
set.add(10.0);
set.remove(10);
set.add((short) 11);
set.remove(11L);
assertEquals(0, set.size());
}
@Test
public void testSize() {
for (int i = 0; i < 10; ++i) {
assertEquals(i, set.size());
set.add(i);
assertEquals(i + 1, set.size());
}
for (int i = 9; i > -3; --i) {
assertEquals(Math.max(i + 1, 0), set.size());
set.remove(i);
assertEquals(Math.max(i, 0), set.size());
}
}
@Test
public void testGetAverage() {
set.add(1);
set.add(2L);
set.add((short) 3);
set.add((byte) 4);
set.add(5.0f);
set.add(6.0);
assertEquals(3.5, set.getAverage(), DELTA);
}
@Test
public void testGetStandardDeviation() {
set.add(1);
set.add(2L);
set.add((short) 3);
set.add((byte) 4);
set.add(5.0f);
set.add(6.0);
assertEquals(1.8708, set.getStandardDeviation(), DELTA);
}
}
As always, any critique is much appreciated.
