Limited SortedSet

Question

i'm looking for an implementation of SortedSet with a limited number of elements. So if there are more elements added then the specified Maximum the comparator decides if to add the item and remove the last one from the Set.

SortedSet<Integer> t1 = new LimitedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
// [1,3,5]
t1.add(2);
// [1,2,3]
t1.add(9);
// [1,2,3]
t1.add(0);
// [0,1,2]

Is there an elegant way in the standard API to accomplish this?

I've wrote a JUnit Test for checking implementations:

@Test
public void testLimitedSortedSet() {
final LimitedSortedSet<Integer> t1 = new LimitedSortedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
System.out.println(t1);
// [1,3,5]
t1.add(2);
System.out.println(t1);
// [1,2,3]
t1.add(9);
System.out.println(t1);
// [1,2,3]
t1.add(0);
System.out.println(t1);
// [0,1,2]
Assert.assertTrue(3 == t1.size());
Assert.assertEquals(Integer.valueOf(0), t1.first());
}

Answer 1

With the standard API you'd have to do it yourself, i.e. extend one of the sorted set classes and add the logic you want to the add() and addAll() methods. Shouldn't be too hard.

Btw, I don't fully understand your example:

t1.add(9);
// [1,2,3]

Shouldn't the set contain [1,2,9] afterwards?

Edit: I think now I understand: you want to only keep the smallest 3 elements that were added to the set, right?

Edit 2: An example implementation (not optimised) could look like this:

class LimitedSortedSet<E> extends TreeSet<E> {

  private int maxSize;

  LimitedSortedSet( int maxSize ) {
    this.maxSize = maxSize;
  }

  @Override
  public boolean addAll( Collection<? extends E> c ) {
    boolean added = super.addAll( c );        
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }   
    return added;
  }

  @Override
  public boolean add( E o ) {    
    boolean added =  super.add( o );
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }
    return added;
  }
}

Note that tailSet() returns the subset including the parameter (if in the set). This means that if you can't calculate the next higher value (doesn't need to be in the set) you'll have to readd that element. This is done in the code above.

If you can calculate the next value, e.g. if you have a set of integers, doing something tailSet( lastElement + 1 ) would be sufficient and you'd not have to readd the last element.

Alternatively you can iterate over the set yourself and remove all elements that follow the last you want to keep.

Another alternative, although that might be more work, would be to check the size before inserting an element and remove accordingly.

Update: as msandiford correctly pointed out, the first element that should be removed is the one at index maxSize. Thus there's no need to readd (re-add?) the last wanted element.

Important note: As @DieterDP correctly pointed out, the implementation above violates the Collection#add() api contract which states that if a collection refuses to add an element for any reason other than it being a duplicate an excpetion must be thrown.

In the example above the element is first added but might be removed again due to size constraints or other elements might be removed, so this violates the contract.

To fix that you might want to change add() and addAll() to throw exceptions in those cases (or maybe in any case in order to make them unusable) and provide alterante methods to add elements which don't violate any existing api contract.

In any case the above example should be used with care since using it with code that isn't aware of the violations might result in unwanted and hard to debug errors.

Answer 2

I'd say this is a typical application for the decorator pattern, similar to the decorator collections exposed by the Collections class: unmodifiableXXX, synchronizedXXX, singletonXXX etc. I would take Guava's ForwardingSortedSet as base class, and write a class that decorates an existing SortedSet with your required functionality, something like this:

public final class SortedSets {

    public <T> SortedSet<T> maximumSize(
        final SortedSet<T> original, final int maximumSize){

        return new ForwardingSortedSet<T>() {

            @Override
            protected SortedSet<T> delegate() {
                return original;
            }

            @Override
            public boolean add(final T e) {
                if(original.size()<maximumSize){
                    return original.add(e);
                }else return false;
            }

            // implement other methods accordingly
        };
    }

}

Answer 3

No, there is nothing like that using existing Java Library.

But yes, you can build a one like below using composition. I believe it will be easy.

public class LimitedSet implements SortedSet {

    private TreeSet treeSet = new TreeSet();

    public boolean add(E e) {
        boolean result = treeSet.add(e);
        if(treeSet.size() >= expectedSize) {
            // remove the one you like ;)
        }
        return result;
    }

    // all other methods delegate to the "treeSet"

}

UPDATE After reading your comment

As you need to remove the last element always:

• you can consider maintaining a stack internally
• it will increase memory complexity with O(n)
• but possible to retrieve the last element with just O(1)... constant time

It should do the trick I believe