Compact a list based on a value

Question

Having a simple class such as:

public class Label {
    public String id;
    public double amount;
}

And having a list with the following values (list is sorted in amount ascending order):

id        amount
----------------
1742      10
1742      11
1647      12
4217      13
1647      14
1742      15

Is there a simple way to compact the list so that only the lowest amount for an id remains. So, after compaction, the list should look like this:

id        amount
----------------
1742      10
1647      12
4217      13

Answer 1

If i understood correctly you want to remove the doubles from a list of Label objects. There are some simple ways such as creating a custom comparator for the list:

Docs:https://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html Stack Overflow post: Collections sort(List<T>,Comparator<? super T>) method example

Another way is to use a map since as far as i can tell you use two values, so using like a TreeMap with a custom comparator ^ may also be a solution. Otherwise you can develop your own sorting algorythm that also compares the objects one with the other while sorting and skips the doubles based on your critera, Buble sorting for example can be tweaked to do that, and so do most sorting techniques.

Answer 2

Many ways to do this. How about (totally untested, likely won't compile):

public static List<Label> deduped(List<Label> yourSortedList) {
    List<Label> output = new LinkedList<>();
    assert yourSortedList.size() > 0;
    Label lastVal = yourSortedList.get(0);
    for (Label l : yourSortedList) {
        if (!lastVal.id.equals(l.id)) {
            output.add(lastVal);
            lastVal = l;
         }
    }
    output.add(lastVal);
    return output;
}

I'd be pretty surprised if there wasn't at least one bug in the above, but hopefully you get the general idea.

Answer 3

Here is one way of doing it. The method makeUnique() will keep only those labels that have minimum amounts.

public class Label {
    public String id;
    public double amount;

    public Label(String id, double amount) {
        super();
        this.id = id;
        this.amount = amount;
    }

    public static Map<String, Label> makeUnique(List<Label> list) {
        Map<String, Label> map = new HashMap<String, Label>();

        for (Label label : list) {
            if(!map.containsKey(label.id)) map.put(label.id, label);
        }
        return map;
    }

    public static void main(String[] args) {
        List<Label> list = new ArrayList<Label>();
        list.add(new Label("1742", 10));
        list.add(new Label("1742", 11));
        list.add(new Label("1647", 12));
        list.add(new Label("1647", 14));
        Map<String, Label> map = makeUnique(list);
    }

}

Answer 4

Almost everyone is correct but when it comes to simple way

simply use a java.util.Set

and Override the equals() and hashCode() methods for Label class.

Apart from that There are so many ways.

One of the way of doing This

List<Label> originalList = new ArrayList<Label>();
            // above conatins your original List

            List<Label> result = new ArrayList<Label>();
            Set<String> label = new HashSet<String>();

            for( Label item : originalList ) {
                if( label.add( item.getId() ) {
                    result.add( item );
                }
            }

you need to have a Getter method of getId() in your class

Answer 5

Since the list is already sorted on amount, you just need to include the object Label in the list for the first time it appears. You can generate a new list with the exact elements if you use a dictionary to store the ids of the elements already entered. Like this:

    public static List<Label> compact(List<Label> l)
    {
        Set<String> ids = new HashSet<>();
        List<Label> toret = new ArrayList<>();

        for(Label label: l) {
            if ( !ids.contains( label.id ) ) {
                ids.add( label.id );
                toret.add( label );
            }
        }

        return toret;
    }

Antoher possibility, since we are using lists, would be to do the compaction "in place", i.e., using the same list. Take into account that this possibility uses less memory, but is slower (since it has to look for element 'i' for each time in loop, which can be expensive in a LinkedList).

public static void compactInPlace(List<Label> l)
{
    Set<String> ids = new HashSet<>();

    for(int i = 0; i < l.size(); ++i) {
        if ( !ids.contains( l.get( i ).id ) ) {
            ids.add( l.get( i ).id );
        } else {
            l.remove( i );
            --i;
        }
    }

    return;
}

Find the code here: http://ideone.com/B4Gggt

Hope this helps.

Answer 6

Using Java 8 Streams you could do:

import java.util.Optional;
import java.util.List;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public static List<Label> getDistinctMinLabels(List<Label> labels) {
    return labels
        .stream()
        .collect(
            // group by label id
            // and of each group get the label with the minimum amount
            Collectors.groupingBy(
                label -> label.id, 
                Collectors.minBy((l1, l2) -> Double.compare(l1.amount, l2.amount)) 
            )
        )
        .entrySet()
        .stream()
        .map(Entry::getValue)
        .map(optional -> optional.get()) // Collectors.minBy returns an Optional<Label>
        .collect(Collectors.toList());   
}

This function will not be the most efficient, but also works when the labels are not sorted.