Package org.drip.graph.heap

Class TimedCollection<ITEM>

java.lang.Object
org.drip.graph.heap.TimedCollection<ITEM>
public class TimedCollection<ITEM>
extends java.lang.Object
TimedCollection implements a Collection where each Item is stored with a Time Stamp (in nanoseconds). Retrieval Order can be LIFO or FIFO, depending on whether the underlying Priority Queue is a Max or a Min Queue. The References are:

  • Brodal, G. S. (1996): Priority Queue on Parallel Machines Scandinavian Workshop on Algorithm Theory – SWAT ’96 416-427
  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Sanders, P., K. Mehlhorn, M. Dietzfelbinger, and R. Dementiev (2019): Sequential and Parallel Algorithms and Data Structures – A Basic Toolbox Springer
  • Sundell, H., and P. Tsigas (2005): Fast and Lock-free Concurrent Priority Queues for Multi-threaded Systems Journal of Parallel and Distributed Computing 65 (5) 609-627
  • Wikipedia (2020): Priority Queue https://en.wikipedia.org/wiki/Priority_queue




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • TimedCollection

      public TimedCollection​(PriorityQueue<java.lang.Long,​ITEM> priorityQueue) throws java.lang.Exception
      TimedCollection Constructor
      Parameters:
      priorityQueue - Underlying Priority Queue
      Throws:
      java.lang.Exception - Thown if the Inputs are Invalid

  • Method Details

    • FIFOBinomial

      public static <ITEM> TimedCollection<ITEM> FIFOBinomial()
      Construct a Binomial FIFO (i.e, Queue) Version of TimedCollection
      Type Parameters:
      ITEM - The Item Type
      Returns:
      Binomial FIFO (i.e, Queue) Version of TimedCollection

    • FIFOBinary

      public static <ITEM> TimedCollection<ITEM> FIFOBinary()
      Construct a Binary FIFO (i.e, Queue) Version of TimedCollection
      Type Parameters:
      ITEM - The Item Type
      Returns:
      Binary FIFO (i.e, Queue) Version of TimedCollection

    • LIFOBinomial

      public static <ITEM> TimedCollection<ITEM> LIFOBinomial()
      Construct a Binomial LIFO (i.e, Stack) Version of TimedCollection
      Type Parameters:
      ITEM - The Item Type
      Returns:
      Binomial LIFO (i.e, Stack) Version of TimedCollection

    • LIFOBinary

      public static <ITEM> TimedCollection<ITEM> LIFOBinary()
      Construct a Binary LIFO (i.e, Stack) Version of TimedCollection
      Type Parameters:
      ITEM - The Item Type
      Returns:
      Binary LIFO (i.e, Stack) Version of TimedCollection

    • priorityQueue

      public PriorityQueue<java.lang.Long,​ITEM> priorityQueue()
      Retrieve the Underlying Priority Queue
      Returns:
      The Underlying Priority Queue

    • insert

      public boolean insert​(ITEM item)
      Insert an Item into the Queue with its Time Stamp
      Parameters:
      item - The Item
      Returns:
      TRUE - The Item is successfully inserted into the Queue with its Time Stamp

    • extractExtremum

      public PriorityQueueEntry<java.lang.Long,​ITEM> extractExtremum()
      Extract the Extremum Item
      Returns:
      The Extremum Item

    • peek

      public PriorityQueueEntry<java.lang.Long,​ITEM> peek()
      Peek the Extremum Item
      Returns:
      The Extremum Item