Deduplication of repeated numbers in java

Question

I have a TreeMap of <Double,Double>. I'm trying to reduce the map for all of the consecutive duplicated values.
I.e. key, values of

 (1.0, 1.0)
 (2.0, 1.0)
 (3.0, 1.0)
 (4.0, 1.0)
 (5.0, 2.0)
 (6.0, 2.0)
 (7.0, 2.0)
 (8.0, 1.0)
 (9.0, 1.0)
(10.0, 1.0)

reduced to

 (1.0, 1.0)
 (4.0, 1.0)
 (5.0, 2.0)
 (7.0, 2.0)
 (8.0, 1.0)
(10.0, 1.0)

I can get the unique values with

List<Double> uniqueValues = test.values().parallelStream().distinct()
    .collect(Collectors.toList());

And I can iterate over those values to get the keys to the values

List<Integer> uniqueKeys = test.entrySet().stream()
    .filter(entry -> Objects.equals(entry.getValue(), uniqueValue))
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

But now I am a loss on getting the the start and end points of each set of duplicated values.

What is a good solution for this? I have though about getting the provided keys but the issues come up with the example above where the repeated number comes back.

Answer 1

First I'll start by saying that you should not use Double for the key in a Map. More details here: Double in HashMap

Then, here is an example with a Map<Integer, Integer> to simplify the logic. You will need to adapt it for Map<Double, Double>

The logic is that the first and last map entries will always be in the result map. So you just have to filter out the ones in the middle (index 1 to map size -1). Just skipping the ones that have the same value as the previous or next one

For loop version

// get the sorted list of keys
List<Integer> keys = new ArrayList<>(map.keySet());
Collections.sort(keys);

List<Integer> resultKeys = new ArrayList<>();
// first key will always be in the result map, add it
resultKeys.add(keys.get(0));
// for each following key, add if the value is different from both previous or next
for (int i = 1; i < keys.size()-1; i++) {
    Integer key = keys.get(i);
    Integer value = map.get(key);

    Integer previousKey = keys.get(i-1);
    Integer previousValue = map.get(previousKey);

    Integer nextKey = keys.get(i+1);
    Integer nextValue = map.get(nextKey);

    if(previousValue.intValue() != value.intValue() || nextValue.intValue() != value.intValue()) {
        resultKeys.add(key);
    }
}

// last key will always be in the result map, add it
resultKeys.add(keys.get(keys.size()-1));

// make a map out of you list
Map<Integer, Integer> resultMap = resultKeys.stream()
        .collect(Collectors.toMap(k -> k, map::get));

Map<Integer, Integer> resultTreeMap = new TreeMap<>();
resultTreeMap.putAll(resultMap);

Lambda version

// get the sorted list of keys
List<Integer> keys = new ArrayList<>(map.keySet());
Collections.sort(keys);

Map<Integer, Integer> resultMap = 
        IntStream.range(1, keys.size()-1)
        .boxed()
        .map(i -> setToNullIfNotKept(keys, i))
        .filter(Objects::nonNull)
        .collect(Collectors.toMap(k -> k, map::get));

// first key will always be in the result map, add it
resultMap.put(keys.get(0), map.get(keys.get(0)));
// last key will always be in the result map, add it
Integer lastKey = keys.get(keys.size() - 1);
resultMap.put(lastKey, map.get(lastKey));

Map<Integer, Integer> resultTreeMap = new TreeMap<>();
resultTreeMap.putAll(resultMap);

The utility method to nullify not wanted indexes:

private static Integer setToNullIfNotKept(List<Integer> keys, Integer i) {
    Integer key = keys.get(i);
    Integer value = map.get(key);

    Integer previousKey = keys.get(i-1);
    Integer previousValue = map.get(previousKey);

    Integer nextKey = keys.get(i+1);
    Integer nextValue = map.get(nextKey);

    if(previousValue.intValue() != value.intValue() || nextValue.intValue() != value.intValue()) {
        return key;
    }
    return null;
}

Output

Given that input map:

Map<Integer, Integer> map = new TreeMap<>();
map.put(1, 1);
map.put(2, 1);
map.put(3, 1);
map.put(4, 1);
map.put(5, 2);
map.put(6, 2);
map.put(7, 2);
map.put(8, 1);
map.put(9, 1);
map.put(10, 1);

They both output the following Map:

{1=1, 4=1, 5=2, 7=2, 8=1, 10=1}

Answer 2

You can collect every series to separated list. Thanks to LinkedList you have easy access to last element and to check is it still the same value. If value change then new LinkedList is created to collect next entries.

LinkedList<LinkedList<Map.Entry<Double,Double>>> linkedLists = new LinkedList<>();

test.entrySet().stream().forEach(e -> {
    if (linkedLists.isEmpty() || 
        ! linkedLists.getLast().getLast().getValue().equals(e.getValue())) {
        linkedLists.add(new LinkedList<>());
    }
    linkedLists.getLast().add(e);
});

System.out.println(linkedLists);

After that you can change this to final list

System.out.println(linkedLists.stream()
    .flatMap(ll -> Arrays.asList(ll.getFirst(), ll.getLast()).stream())
    .collect(Collectors.toList()));

or map with preserved order

System.out.println(linkedLists.stream()
    .flatMap(ll -> Arrays.asList(ll.getFirst(), ll.getLast()).stream())
    .collect( Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
        (a1, a2) -> a1, () -> new LinkedHashMap<>())));

Answer 3

An implementation using a list instead of a map of input values:

    final List<Double> input = getInputList();

    final Map<Integer, Double> result = new LinkedHashMap<>();
    if (input.isEmpty()) {
        return result;
    }

    boolean firstOccurrence = true;
    for (int i = 0; i < input.size() - 1; i++) {
        final Double current = input.get(i);
        final Double next = input.get(i + 1);
        if (firstOccurrence || !current.equals(next)) {
            result.put(i, current);
        }
        firstOccurrence = !current.equals(next);
    }
    result.put(input.size() - 1, input.get(input.size() - 1));