How to return N consecutive elements from a Collection?

Question

I am passed a collection of objects (some Contact class in my case) and need to return a page from that collection. My code feels much longer than it needs to be. Am I missing some libraries that could perform that more elegantly than iterating over each element one at a time like I do below?

protected Collection<Contact> getPageOfContacts(
  Collection<Contact> contacts, int pageIndex, int pageSize) {
  if (pageIndex < 0 || pageSize <= 0
    || pageSize > contacts.size()) {
    return contacts;
  }
  int firstElement = pageIndex * pageSize;
  int lastElement = (pageIndex + 1) * pageSize - 1;
  Collection<Contact> pagedContacts = new ArrayList<Contact>();
  int index = -1;
  for (Contact contact : contacts) {
    index++;
    if (index < firstElement) {
      continue;
    }
    if (index > lastElement) {
      break;
    }
    pagedContacts.add(contact);
  }
  return pagedContacts;
}

Methenamine

How is the collection consumed? what methods are you using on it/plan to use on it? – Boilermaker

Answer 1

You could use Guava Iterables.partition:

protected <T> Collection<T> getPageOfContacts(
        Collection<T> contacts, int pageIndex, int pageSize) {
    return Lists.newArrayList(
        Iterables.partition(contacts, pageSize)).get(pageIndex);
}

A more complex version does not create all pages to pick the right one, but stops when the right page is found.

protected <T> Collection<T> getPageOfContacts(
        Collection<T> contacts, int pageIndex, int pageSize) {
    Iterator<List<T>> partitions = Iterators.partition(contacts.iterator(), pageSize);

    for(int page = 0; page<pageSize && partitions.hasNext(); page++){
        List<T> partition = partitions.next();
        if(page == pageIndex) return partition;
    }
    return Collections. <T> emptyList(); //or fail
}

Update:

Thanks to ColinD to point out that:

Iterables.get(Iterables.partition(contacts, pageSize), pageIndex)

is a simpler implementation.

Alaric

If x is already a List, it'd be a lot better to use Lists.partition instead. With the parameter being a Collection as in the OP, it'd still be worth checking if the collection is a List and using Lists if possible. – Hypoglycemia

I would implement a method for Lists. Only if the static type information is missing and performance is critical I would add the check in the method above. Depending on the situation it may be better to do the cast in the caller and call the list version directly. – Alaric

Yeah, it would make sense to just use an overload that takes a List instead. – Hypoglycemia

@Hypoglycemia See my comment below. #5516455 – Alaric

Thanks Thomas. I had heard about the Guava lib doing wonders with collections. Looks like a much better, cleaner code. Follow up question to anyone: many people have commented here that it would be wiser/better to use, possibly return, a List. Given that I am getting my contacts from a TreeSet and don't want to presume the user of my page will want a TreeSet, or a List for that matter, is there a consensus here that my using a Collection as input and output is the right way to proceed? Ideally, there would be a collection interface called "OrderedCollection" in Java. – Methenamine

Iterables.get(Iterables.partition(contacts, pageSize), pageIndex) does essentially what your second version does but more compactly. No need for the first version at all. – Hypoglycemia

@double07: One interesting Guava thing that relates to your question is ImmutableCollection... all subtypes of ImmutableCollection have a fixed order (insertion order or comparison order) and as such can be viewed as an ImmutableList using asList(). – Hypoglycemia

Answer 2

If you can require the data to be paged to be a List, you can get a sublist view of a single page easily using Guava:

public <T> List<T> getPage(List<T> list, int pageIndex, int pageSize) {
  return Lists.partition(list, pageSize).get(pageIndex);
}

This involves no copying or iteration (it uses sublist views of the original list) and handles a final page that has fewer than pageSize elements transparently.

For an arbitrary Iterable or Collection, I'd do this:

public <T> List<T> getPage(Iterable<T> iterable, int pageIndex, int pageSize) {
  return Iterables.get(Iterables.partition(iterable, pageSize), pageIndex);
}

By providing both these methods, you'd be able to handle objects that are known to be lists at compile-time efficiently and any other type of Iterable as efficiently as you can.

Hypoglycemia

I think this version is slower for LinkedLists than the Iterable version. The subList implementation for LinkedLists is O(n) (it uses get(int) which is O(n)). You should add a check that the List implements RandomAccess and add an Iterable version for Lists that don't. – Alaric

@Thomas: It depends on how you're going to be using the page List that's returned. If you're going to be doing index-based access, you might be better off using the Iterable version... or copying the partition in to a RandomAccess list before using it. I think in a lot of cases the page list might just be iterated over, in which case it should be fine as-is. – Hypoglycemia

Answer 3

If you want a defined order to your elements, you should be using a List, not a collection. The basic difference between List and Collection is that List has a fixed order to the elements. It also defines the very convenient method subList(int start, int end) which creates a sub-list which is an alias of the original list containing just the elements you want without the overhead of copying them to a new list.

Halfwitted

The intention may however to be able to work with any kind of collection, in particular with both lists and sets. Sets seem a reasonable candidate here as the contacts are likely to be ordered with a need to eliminate duplicates. – Escharotic

@iainmcgin, Sets are not ordered or indexed. If you want to page over a Set you could take a copy of it into a List. – Drought

@Peter TreeSet (and more generally, SortedSet implementations) are sorted based on elements implementing Comparable or a provided Comparator instance, and LinkedHashSet has an order based on the order in which things are added to the set. The indices of elements are then implicit based on this order, so it is still reasonable to expect to be able to page through them. These were the cases I was thinking of specifically, apologies for not stating this up front. – Escharotic

@Escharotic - Peter's point (I think) and mine is not that collections (including Set objects) cannot be ordered. It is that the abstract notion of "collection" (or "set") does not include any notion of order. It does not make sense to talk about "page n of the results" unless you first impose an order on the collection. There are certainly implementations of Collection and Set that also define a particular order to the elements. (TreeSet, for example, implements not only Collection but also SortedSet.) – Halfwitted

@iainmcgin: List is still a far more appropriate structure for this sort of thing. Sublists starting at specific indices are what paging is about, and only lists provide this type of access. You could page another data structure, but you'd be better off putting data to be paged in a List to begin with. – Hypoglycemia

The collection I am passed will be a set (TreeSet implementation allowing me to order the contacts) but I'd rather not make any assumption on the implementation if possible. I understand that the Collection abstraction does not define an order, but if one passes an ordered implementation to me, the code above will return an ordered collection, independent of whether the underlying implementation is a TreeSet, an ArrayList, or some other ordered implementation. It would just not make sense for someone to call my code if they had a non-ordered collection and the result would be undefined. – Methenamine

@double07: Will the same collection instance be passed to this method multiple times for paging or will it be a fresh instance each time? If the same instance will be used multiple times, it would probably be worth it to copy in to a List first and then use that list repeatedly with an implementation that returns sublist views. Then paging doesn't have to involve iteration and copying each time. – Hypoglycemia

@ColinD: I don't have a guarantee that I will be passed the same collection. I get my list of contacts from an addessbook that may change at any point in time, and I need the page returned to remain up to date with the latest addressbook content. I see your point about performance though. – Methenamine

Answer 4

The List interface provides a subList method, that takes a start index and an end index. See http://download.oracle.com/javase/6/docs/api/java/util/List.html#subList(int,%20int). The returned sublist is backed by the original list, so you probably want to do something like

protected Collection<Contact> getPageOfContacts(...) {
    return new ArrayList<Contact>(original.subList(start,end));
}

Fishbein

Answer 5

return new ArrayList<Contact>(new ArrayList<Contact>(contacts).subList(firstElement, lastElement));

Note: this will return the sublist exclusive lastElement

Note 2: The result are copied to another list for the reasons mentioned by Kevin.

Tenement

Answer 6

Iterables.partition(contacts, pageSize).forEachRemaining(paginatedContacts->{/*Operation here*/});

Anabolite