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.

Two things here: learn about floating point math. Your assumption that you can easily use equality for double numbers isn't correct. Floating point numbers should always be compared as delta against some epsilon threshold. And: your exact requirements are unclear, would you go for example if you had 7,3 as pair in there for example? — GhostCat, Sep 26 '19 at 18:38
"I'm trying to reduce the map for all of the consecutive duplicated values." what does that mean? — GitPhilter, Sep 26 '19 at 18:39
If it's really the consecutive duplicated numbers, shouldn't either the `(1, 1)` or `(4, 1)` be removed too? — M. Prokhorov, Sep 26 '19 at 18:40
It's like, between numbers. This looks like a time series where he wants the endpoints of each time series at a certain value. So, value 1 lasts from times (1 to 4), 2 last from times (5 to 7), etc. — Avi, Sep 26 '19 at 18:42
Double as a key is an odd choice, use Integer there. Also you can't preserve an order, use index or next/previous elements using streams. Especially parallel streams. And for your solution you are going to need that, so use "for" instead. — Horatiu Jeflea, Sep 26 '19 at 18:49
@Avi, if there is `(1, 1)`, then `(4, 1)` is missing and then there's `(5, 2)`, the logical meaning is exactly the same - that the series contains `([1;5), 1), ([5;inf), 2)`. — M. Prokhorov, Sep 27 '19 at 11:47

lczapski · Accepted Answer · 2019-09-27T10:52:49.560

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<>())));

Thank you. This is exactly what I was looking for. – lemming622 Sep 27 '19 at 15:49 — lemming622, Sep 27 '19 at 15:49

score 0 · Answer 2 · answered Sep 27 '19 at 06:57

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));

Bentaye · Answer 3 · 2019-09-27T10:57:29.360

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}

Deduplication of repeated numbers in java

3 Answers3

For loop version

Lambda version

Output