Java Collections: How to divide a sorted list into sub lists

Let's say I have a list (EG: LinkedList<SomeObject>that contains elements ordered by a certain attribute (EG: SomeObject.someValue()). This attribute can and usually does repeat often/it isn't unique, BUT is never null.

Is there a convenient way to divide this into multiple Lists, each list containing only its equal in cardinal order? Also, can this be done with only once iteration of the list? For example, the original list:

1, 1, 1, 2, 2, 3开发者_JS百科, 3, 3

The desired lists from this:

1, 1, 1
2, 2,
3, 3, 3

---

Not too convenient, but:

• start a loop. Store the previous item, and compare it to the current.
• if the previous is different from the current (using equals(..), and be careful with null), then create a new List, or use list.subList(groupStart, currentIdx)

---

You could use Apache CollectionUtils to do this, where "list" is the original list, and "value" is the current value of the objects you want to extract a sublist for:

Collection<SomeObject> selectedObjects = CollectionUtils
    .select(list,
            new Predicate() {
                boolean evaluate(Object input) {
                    return ((SomeObject) input).someValue().equals(value);    
                }
            });

This approach means using a well known and well tested library (which always is a good thing), but the downside is that you will loop through the list once for each sublist you need.

---

Pretty sure there isn't a java API method for this. However you can write:

 // This assumes your list is sorted according to someValue()
 // SomeValueType is the type of SomeObject.someValue()
 public Map<SomeValueType, List<SomeObject>> partition(List<SomeObject> list) {
    Object currValue = null;
    HashMap<SomeValueType, LinkedList<SomeObject>> result = new HashMap<SomeValueType, LinkedList<SomeObject>>();
    LinkedList<SomeObject> currList = null;

    for (SomeObject obj : list) {
        if (!obj.someValue().equals(currValue()) {
            currValue = obj.someValue();
            currList = new LinkedList<SomeObject>();
            result.put(currValue, currList);
        }
        currList.add(obj);
    }
}

This will return you an HashMap of sublists, where the key is the someValue and the value is the partitioned list associated to it. Note, I didn't test this, so don't just copy the code.

EDIT: made this return hashmap instead of arraylist.

---

If you would use Google Guava-libaries:

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Lists;

public class Example {
    public static void main(String[] args) {
        HashMultiset<Integer> ints = HashMultiset.create();
        ints.addAll(Lists.newArrayList(1, 1, 1, 2, 2, 3, 3, 3));
        System.out.println(ints);
    }
}

Output:

[1 x 3, 2 x 2, 3 x 3]

If you need to count how many elements of x you have use ints.count(x);, if you have value types you do not need to have more then just count.

---

With Guava, use Multimaps.index(Iterable<V>, Function<? super V, K>).

---

This should work (untested, but I am pretty sure everything is ok, This also assumes that the contents of the list are sortable):

public static List[] getEquivalentSubLists( List parent )
{

    List cloneList = parent.clone();
    Collections.sort(cloneList);

    ArrayList<List> returnLists;
    int end;
    while (cloneList.size() > 0)
    {
        end = cloneList.lastIndexOf(cloneList.get(0));

        returnLists.add(cloneList.subList(0, end));
        cloneList.removeAll(cloneList.subList(0, end));
    }

    return returnList.toArray();
}