3

Python's collections.deque has a maxlen argument, such that

[...] the deque is bounded to the specified maximum length. Once a bounded length deque is full, when new items are added, a corresponding number of items are discarded from the opposite end. [...]

I have been looking for a class that implements the Deque interface in Java, that does the same.

public ArrayDeque(int numElements) looks like numElements only initializes the deque to that size, but doesn't enforce it as a max length.

Chris Wesseling
  • 6,226
  • 2
  • 36
  • 72

1 Answers1

1

Probably not. LinkedHashMap has some facilities to build a cache with eviction policies, but that might be overkill for what you want. Just extend the Deque and add your custom logic ;-)

Edit:

class MyFixedSizeDeque<T> extends ArrayDeque<T>
{
   private int maxSize;
   public MyDeque(int size)
   {
      this.maxSize = size; 
   }

   @Override
   public void addLast(T e)
   {
      this.addLast(e);
      if(this.size() > maxSize)
         this.removeFirst();
   } 
}

My Java is a little rusty, and you might want to overload a few more methods (or switch to composition rather than inheritance) but I hope you get the idea...

Daniel Langdon
  • 5,899
  • 4
  • 28
  • 48
  • Basically I want something with O(1) `add` and a fixed length. – Chris Wesseling May 15 '15 at 13:20
  • The `addLast()` should indeed be O(1). But isn't the `removeFirst()` O(n), because all elements get moved? [Aparently](http://stackoverflow.com/a/16777926/383793), still fast, because System.arraycopy can do a native memcpy ([depending on the contents](http://stackoverflow.com/questions/2772152/why-is-system-arraycopy-native-in-java#comment2806033_2772176)). The same code could extend LinkedList for the O(1) time complexity. I guess composition caters both, [whichever one may need](http://stackoverflow.com/a/322742/383793). – Chris Wesseling May 18 '15 at 11:17
  • Oh, sorry, my bad. I was actually thinking of a LinkedList indeed, as the base class, for which access to first and last is always O(1), but typed ArrayDequeue because ... no idea... – Daniel Langdon May 18 '15 at 15:02