I want to store in a queue, datastructure does not matter, only the elements that I have inserted within say last 5 minutes from current time. Anything older should get removed - so that any time I get the size of the queue it will give count of the objects inserted in last 5 minutes.
Basically all I have to know is how many times my app has made a http call to a sever in last 5 minutes before making the next call.
If anyone knows of some existing library that may have this implementation please share.
Typical stacks and queues are technically types of priority queues. The highest priority element in a stack is the most recently inserted one (LIFO), while the highest priority element in a queue is the least recently inserted one (FIFO).
Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served (i.e., the order in which they are removed).
Check if Queue Contains Element You can check if a Java Queue contains a certain element via its contains() method. The contains() method will return true if the Queue contains the given element, and false if not.
The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. In the below priority queue, an element with a maximum ASCII value will have the highest priority.
You can use a Priority Queue with timestamps as your keys. So that when you call Peek() you always get the oldest timestamp still in the queue. Then each time you go to query for the number of items inside your window size: you cleanup the items outside your window and return the number of items still in the Priority queue.
For example:
public class CountInWindow {
/**
* Adding a main just for testing
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException {
System.out.println("test started");
CountInWindow test = new CountInWindow(5000); //5 seconds for testing
test.debug = true;
test.insertTimeStamp(System.currentTimeMillis());
Thread.sleep(100);//sleep
test.insertTimeStamp(System.currentTimeMillis());
Thread.sleep(100);//sleep
test.insertTimeStamp(System.currentTimeMillis());
Thread.sleep(100);//sleep
test.insertTimeStamp(System.currentTimeMillis());
Thread.sleep(5040);//sleep 5 secs
test.insertTimeStamp(System.currentTimeMillis());
Thread.sleep(100);//sleep
test.insertTimeStamp(System.currentTimeMillis());
System.out.println(test.getWindowCount()); //Should be 2 not 6.
System.out.println("test done");
}
java.util.PriorityQueue<Long> window;
public static final long FIVE_MINS_IN_MS = 300000l;
public final long WINDOW_SIZE;
public boolean debug = false;
//Constructor which defaults to 5mins
public CountInWindow(){
WINDOW_SIZE = FIVE_MINS_IN_MS;
window = new java.util.PriorityQueue<Long>();
}
//Constructor for any size window
public CountInWindow(long windowSize){
WINDOW_SIZE = windowSize;
window = new java.util.PriorityQueue<Long>();
}
/**
* Add a new timestamp to the window's queue
* @param ts
*/
public void insertTimeStamp(long ts){
window.add(ts);
}
/**
* Clean up items outside the window size and then return the count of times still in the window.
* @return A count of timestamps still inside the 5 mins window.
*/
public int getWindowCount(){
long currTime = System.currentTimeMillis();
//Clean out old Timestamps
while((currTime - window.peek().longValue()) > WINDOW_SIZE){
long drop = window.remove().longValue();
if(debug)System.out.println("dropping item:" + drop);
}
return window.size();
}
}
In what language? Is the queue persistent or in-memory?
If you need this behavior in Java, you can use a DelayedQueue, and have a separate thread calling queue.take()
continuously in a tight loop to drain out expired items. queue.size()
will then give you the size of remaining unexpired items in the queue. This requires that the items you put in the DelayedQueue implement the Delayed interface and return the value 5 minutes to the .getDelay()
method.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With