Data structure limited by range

Question

For a utility class, I've created a particular implementation of a list where the list's items can be limited to a specific range, using the google guava Range utility. Items in the list must accordingly implement Comparable. When an item is added or retrieved from the list, they will be within the specified range.

Note: I'm using this class to store commits/revisions from git or svn repositories, then users can limit information to a specific range. I know I could simply filter out information, but I decided to go all out and see if I could turn it into a learning experience

I have two different implementations of this:

1. Accept any items, but hide them based on the range. The range could then be modified, and previously hidden items could be exposed.
2. Only accept items within the range, and when the range is updated, all items outside of the range are discarded.

I've tried to mimic the way that the native Java libraries organize and abstract out their list implementations.

The code is broken up into many different files, so I will post the relevant ones here, and leave a link to my GitHub where the others are located.

Here's my AbstractRangedArrayList implementation:

package com.pwhiting.collect;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import com.google.common.collect.Lists;
import com.google.common.collect.Range;
public abstract class AbstractRangedList<C extends Comparable<?>> implements RangedList<C >{
 protected final List<C> data;
 protected List<C> limitedData = Lists.newArrayList();
 protected Range<C> range = Range.all();
 public AbstractRangedList() {
 this(new ArrayList<C>());
 }
 public AbstractRangedList(final List<C> data) {
 this.data = data;
 includeAll();
 }
 public RangedArrayList<C> copy() {
 final RangedArrayList<C> theCopy = new RangedArrayList<C>(data);
 theCopy.range = range;
 theCopy.limitedData = Lists.newArrayList(limitedData);
 return theCopy;
 }
 @Override
 public C get(final int index) {
 return isLimited() ? limitedData.get(index) : data.get(index);
 }
 @Override
 public Range<C> getRange() {
 return range;
 }
 @Override
 public void includeAll() {
 limitedData = Lists.newArrayList();
 range = Range.all();
 }
 @Override
 public boolean isLimited() {
 return !this.range.equals(Range.all());
 }
 @Override
 public Iterator<C> iterator() {
 return isLimited() ? limitedData.iterator() : data.iterator();
 }
 @Override
 public void limitToRange(final Range<C> range) {
 includeAll();
 this.range = range;
 for (final C c : data) {
 if (range.contains(c)) {
 limitedData.add(c);
 }
 }
 }
 @Override
 public int size() {
 return isLimited() ? limitedData.size() : data.size();
 }
 /**
 * Called when data is added to check to add to limited data
 */
 protected void reassess() {
 limitToRange(getRange());
 }
 @Override
 public void clear() {
 data.clear();
 limitedData.clear();
 }
 @Override
 public boolean contains(Object o) {
 return isLimited() ? limitedData.contains(o) : data.contains(o);
 }
 @Override
 public boolean containsAll(Collection<?> c) {
 return isLimited() ? limitedData.containsAll(c) : data.containsAll(c);
 }
 @Override
 public int indexOf(Object o) {
 return isLimited() ? limitedData.indexOf(o) : data.indexOf(o);
 }
 @Override
 public boolean isEmpty() {
 return isLimited() ? limitedData.isEmpty() : data.isEmpty();
 }
 @Override
 public int lastIndexOf(Object o) {
 return isLimited() ? limitedData.lastIndexOf(o) : data.lastIndexOf(o);
 }
 @Override
 public ListIterator<C> listIterator() {
 return isLimited() ? limitedData.listIterator() : data.listIterator();
 }
 @Override
 public ListIterator<C> listIterator(int index) {
 return isLimited() ? limitedData.listIterator(index) : data.listIterator(index);
 }
 @Override
 public boolean remove(Object o) {
 boolean result = false;
 if (isLimited()){
 result = limitedData.remove(o);
 }
 result |= data.remove(o);
 return result;
 }
 @Override
 public C remove(int index) {
 C c = data.remove(index);
 reassess();
 return c;
 }
 @Override
 public boolean removeAll(Collection<?> c) {
 return data.removeAll(c) || limitedData.removeAll(c);
 }
 @Override
 public boolean retainAll(Collection<?> c) {
 boolean v = data.retainAll(c);
 reassess();
 return v;
 }
 @Override
 public List<C> subList(int fromIndex, int toIndex) {
 return isLimited() ? limitedData.subList(fromIndex, toIndex) : data.subList(fromIndex, toIndex);
 }
 @Override
 public Object[] toArray() {
 return isLimited() ? limitedData.toArray() : data.toArray();
 }
 @Override
 public <T> T[] toArray(T[] a) {
 return isLimited() ? limitedData.toArray(a) : data.toArray(a);
 }
}

And here's the actual RangedLimitedList implementation:

package com.pwhiting.collect;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
/**
 * Represents a data structure whose data entries can be restricted to a certain
 * range. New elements added to this list are kept, but also hidden if they do 
 * not fall into the range.
 *
 * @author phwhitin
 *
 * @param <T>
 * @param <C>
 */
public class RangedArrayList<C extends Comparable<?>> extends AbstractRangedList<C> {
 public RangedArrayList() {
 super(new ArrayList<C>());
 }
 public RangedArrayList(final List<C> data) {
 super(data);
 }
 @Override
 public boolean add(final C c) {
 return range.contains(c) ? data.add(c) && limitedData.add(c)
 : data.add(c);
 }
 @Override
 public void add(int index, C element) {
 data.add(index, element);
 reassess();
 }
 @Override
 public boolean addAll(Collection<? extends C> c) {
 boolean v = data.addAll(c);
 reassess();
 return v;
 }
 @Override
 public boolean addAll(int index, Collection<? extends C> c) {
 boolean v = data.addAll(index, c);
 reassess();
 return v;
 }
 @Override
 public C set(int index, C element) {
 C v = data.set(index, element);
 reassess();
 return v;
 }
}

Again, I've omitted some of the classes for brevity's sake, but they are on my GitHub at the link provided above, should you need to view them to pass judgement.

I want to know if there is a more efficient way I could have done this, or perhaps a better structure I could have chosen. I'm not necessarily concerned with whether or not something like this already exists, it's mostly a thought experiment.

• Simon Forsberg: How are using this? What do you need this class for?
• Himself12794: I'm using this to store commits/revisions from git or svn repositories, then users can limit information to a specific range. I know I could simply filter out information, but I decided to go all out and see if I could turn it into a learning experience.

Answer 1

Inefficient adds

 protected final List<C> data;
 protected List<C> limitedData = Lists.newArrayList();
 protected Range<C> range = Range.all();

When you use any of the four methods to add elements to the range, they end up \$\mathcal{O}(n)\$ where \$n\$ is the final number of elements in the list. This is because limitToRange always rebuilds limitedData from data.

 protected final NavigableSet<C> data = new TreeSet<>();
 protected Set<C> limitedData = data;
 protected Range<C> range = Range.all();

With this data structure, adding would be \$\mathcal{O}(\log n)\$ and the limiting operation would be only the efficiency of the subset operations.

 public void limitToRange(final Range<C> range) {
 includeAll();
 this.range = range;
 for (final C c : data) {
 if (range.contains(c)) {
 limitedData.add(c);
 }
 }
 }

becomes

 public void limitToRange(final Range<C> range) {
 this.range = range;
 if (range.hasLowerBound()) {
 boolean lowerClosed = range.lowerBoundType() == BoundType.Closed;
 if (range.hasUpperBound() {
 boolean upperClosed = range.upperBoundType() == BoundType.Closed;
 limitedData = data.subSet(range.lowerBound(), lowerClosed, range.upperBound(), upperClosed);
 } else {
 limitedData = data.tailSet(range.lowerBound(), lowerClosed);
 }
 } else if (range.hasUpperBound() {
 boolean upperClosed = range.upperBoundType() == BoundType.Closed;
 limitedData = data.headSet(range.upperBound(), upperClosed);
 } else {
 limitedData = data;
 }
 }

This is limited by the time it takes to do the Set limiting operations.

Now, you might reasonable argue that Set doesn't support all the List operations, but if they are important to you, you could implement your own tree type that did.

Note that your current implementation already breaks the contract that if you set something at position i and then get from position i, you get back the same item. So in a very real way, it's not a List either.

• Himself12794: Ah, I see. I wasn't aware of that particular specification of a list. In that case, I think it would be better to change this particular implementation to a set, and start a different list implementation with a tree type list.