0

I need to use a FIFO structure in my application. It needs to have at most 5 elements. I'd like to have something easy to use (I don't care for concurrency) that implements the Collection interface.

I've tried the LinkedList, that seems to come from Queue, but it doesn't seem to allow me to set it's maximum capacity. It feels as if I just want at max 5 elements but try to add 20, it will just keep increasing in size to fit it. I'd like something that'd work the following way:

XQueue<Integer> queue = new XQueue<Integer>(5); //where 5 is the maximum number of elements I want in my queue.
for (int i = 0; i < 10; ++i) {
    queue.offer(i);
}

for (int i = 0; i < 5; ++i) {
    System.out.println(queue.poll());
}

That'd print:

5
6
7
8
9

Thanks

Improve this question
3
  • Why should it print 5,6,..? why not 0,1,2,3,4? offer seems to suggest that it woud fail when max capacity is reached Commented Apr 17, 2010 at 18:00
  • Technically I'm actually interested what is the need for this kind of queue, usually ignoring data/tasks (that is, dropping them out due to some mundane reason) isn't a good thing. Other than that, this sounds like something I'd like to try coding just to see if I can get one to work. Commented Apr 17, 2010 at 18:06
  • 1
    It seems the interest is to keep track of the top 5 "recently used" elements. Since you only care about recent you need to discard the older ones. Commented Apr 17, 2010 at 18:12

7 Answers 7

Reset to default
3

Create your own subclass of the one you want, and override the add method so that it

  • checks if the new object will fit, and fails if not
  • calls super.add()

(and the constructors).

If you want it to block when inserting if full, it is a different matter.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Well, the idea would be to use something that comes with the framework.
doesn't that sort of defeat the purpose of being able to subclass? if the framework doesn't have an object, you can make one.
Well, maybe the framework HAS one, and subclassing would defeat the purpose of having a such rich framework.
I think your request is a kind of very specific, so subclassing as Thorbjørn suggests is the obvious solution. It's easy, keeps the code clean and works just perfect with your needs. Why not to do that then?!
I didn't say anywhere I wouldn't do that, I'm just waiting to see if anyone knows of any class that already does what I want without having to subclass it myself.
|
2

I haven't seen any limitation like that in the API. You can use ArrayList by changing the behavior of the add method with anonymous class feature:

new ArrayList<Object>(){
    public boolean add(Object o){ /*...*/ }
}
Improve this answer

Comments

2

Looks like what you want is a limited size FIFO structure, that evicts oldest items when new ones are added. I recommend a solution based on a cyclic array implementation, where you should track the index of the queue tail and queue head, and increase them (in cyclic manner) as needed.

EDIT: Here is my implementation (note that it IS a Collection). It works fine with your test scenario.

public class XQueue <T> extends AbstractQueue<T>{
    private T[] arr;
    private int headPos;
    private int tailPos;
    private int size;

    @SuppressWarnings("unchecked")
    public XQueue(int n){
        arr = (T[]) new Object[n];
    }

    private int nextPos(int pos){
        return (pos + 1) % arr.length;
    }

    @Override
    public T peek() {
        if (size == 0)
            return null;
        return arr[headPos];
    }

    public T poll(){
        if (size == 0)
            return null;
        size--;
        T res = arr[headPos];
        headPos = nextPos(headPos);     
        return res;
    }

    @Override
    public boolean offer(T e) {
        if (size < arr.length)
            size++;
        else
            if (headPos == tailPos)
                headPos = nextPos(headPos);
        arr[tailPos] = e;
        tailPos = nextPos(tailPos);
        return true;
    }

    @Override
    public Iterator<T> iterator() {
        return null; //TODO: Implement
    }

    @Override
    public int size() {
        return size;
    }
}
Improve this answer

Comments

1

Perhaps an ArrayBlockingQueue might do the trick. Look here. Try something like this:

BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(5);

for (int i = 0; i < 10; i++) {
  while (!queue.offer(i)) {
    queue.poll();        
  }
}

for (int i = 0; i < 5; i++) {   
  System.out.println(queue.poll());
}
Improve this answer

2 Comments

The problem is that after it's full it won't allow me to add new items. I'd want it to discard old ones.
That is what the while is for. If the offer returns false then it couldn't add the element therefore polling the queue to remove one element from the head. The next iteration of the while gets the offer to accept the element since there is space available from the previous poll.
1

You have three choices

1) Subclass an Abstract Collection

2) Limit the size to five and do the logic around the code where you are doing the insert.

3) Use LinkedListHashMap The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. (You would then use an Iterator to get the values - which will be returned in order of insertion)

Your best bet is #1 - It is real easy if you look at the link.

Improve this answer

Comments

1

Did you have a look at the Apache Commons Collections library? The BoundedFifoBuffer should exactly meet your needs.

Improve this answer

Comments

0

If I remember correctly, I've done exactly what you want using a LinkedList.

What you need to do is check the size of the List, if it's 5 and you want to add objects, just delete the first element and keep doing so if the size is 5.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.