Module org.bzdev.base
Package org.bzdev.util

Class CachedSkewHeap<E extends CachedSkewHeap.Entry<E>>

java.lang.Object
org.bzdev.util.CachedSkewHeap<E>
Type Parameters:
E - the type of a heap entry
public abstract class CachedSkewHeap<E extends CachedSkewHeap.Entry<E>> extends Object
Priority queue based on skew heaps. This class maintains two skew heaps: a 'main' one and a soldiery one for recently added entries. The subsidiary heap is merged into the main heap when the heap is polled, or when some size limit is reached, leaving an emu subsidiary heap. Since the subsidiary heap is typically much smaller than the main heap, this speeds up insertions because the time complexity to merge a heap of size n with a heap of size m is log n + log m. whereas the time complexity to add m entries to a heap of size m << n is approximately m log n. There is also a cache - a pointer to an entry to which new entries can be safely appended when it can appear after the cache. The cache, if not null, is an entry in the subsidiary heap.

To use this class, one should first create a subclass of CachedSkewHeap.Entry as described in the documentation for that class. If this subclass is named HeapEntry, one then uses that subclass as the type parameter for CachedSkewHeap. For example, 


 public class OurHeap extends CachedSkewHeap<HeapEntry> {
      protected int compareEntries(HeapEntry e1, HeapEntry e2)) {
        // now compare he1 and he2.
        ...
      }
 }

While some methods are similar to ones provided by PriorityQueue, the usage for this class is more restrictive, and in particular it does not provide all the methods one would expect from a class in the Java collections framework.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    CachedSkewHeap.Entry<E extends CachedSkewHeap.Entry<E>>
    CachedSkewHeap entry.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CachedSkewHeap()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(E entry)
    Add an entry to this heap.
    protected abstract int
    compareEntries(E entry1, E entry2)
    Compare two entries for order.
    boolean
    isEmpty()
    Check if this heap is empty.
    void
    merge()
    Merge events on the event queue.
    E
    peek()
    Find the entry in this heap with the lowest order
    E
    poll()
    Find the entry with the lowest order and remove it from the queue.
    boolean
    remove(E entry)
    Remove an entry from the heap.
    long
    size()
    Find the number of entries in this heap.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CachedSkewHeap

      public CachedSkewHeap()

  • Method Details

    • compareEntries

      protected abstract int compareEntries(E entry1, E entry2)
      Compare two entries for order. The heap will return entries with the lowest order first.
      Returns:
      less than 0, 0, or greater than 0 when entry1's order is lower than, equal to, or greater than entry2's order respectively.

    • isEmpty

      public boolean isEmpty()
      Check if this heap is empty.
      Returns:
      true if it is empty; false otherwise

    • merge

      public void merge()
      Merge events on the event queue. This method will modify the event queue so that new entries can be added quickly. It is useful in special cases such as when a potentially large number of new events will be scheduled in order of increasing or decreasing priority level and before the heap is polled. It has no effect immediately after an event was removed from the event queue, either by calling poll() or remove(Entry).

    • size

      public long size()
      Find the number of entries in this heap.
      Returns:
      the number of entries

    • peek

      public E peek()
      Find the entry in this heap with the lowest order
      Returns:
      the entry with the lowest priority.

    • poll

      public E poll()
      Find the entry with the lowest order and remove it from the queue.
      Returns:
      the heap entry with the lowest order

    • add

      public boolean add(E entry)
      Add an entry to this heap.
      Parameters:
      entry - the entry to add
      Returns:
      true if the entry was added; false otherwise.

    • remove

      public boolean remove(E entry)
      Remove an entry from the heap.

      The entry must not be one in a different heap.

      Parameters:
      entry - the entry
      Returns:
      true on success; false otherwise