Class AbstractArrayWeakHeap<K>

  • Type Parameters:
    K - the type of keys maintained by this heap
    All Implemented Interfaces:
    java.io.Serializable, Heap<K>
    Direct Known Subclasses:
    AbstractArrayHeap, BinaryArrayWeakHeap

    abstract class AbstractArrayWeakHeap<K>
    extends java.lang.Object
    implements Heap<K>, java.io.Serializable
    An abstract weak heap with an array representation.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected K[] array
      The array used for representing the heap.
      protected java.util.Comparator<? super K> comparator
      The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.
      protected static int DOWNSIZING_MIN_HEAP_CAPACITY
      Limit for the heap capacity when down-sizing.
      protected static int MAX_HEAP_CAPACITY
      The maximum heap capacity.
      protected static int MIN_HEAP_CAPACITY
      The minimum heap capacity.
      protected int minCapacity
      Minimum capacity due to initially requested capacity.
      private static long serialVersionUID  
      protected int size
      Number of elements in the heap.
    • Constructor Summary

      Constructors 
      Constructor Description
      AbstractArrayWeakHeap​(java.util.Comparator<? super K> comparator, int capacity)
      Constructor
    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected void checkCapacity​(int capacity)
      Check that a capacity is valid.
      void clear()
      Clear all the elements of this heap.
      java.util.Comparator<? super K> comparator()
      Returns the comparator used to order the keys in this heap, or null if this heap uses the natural ordering of its keys.
      protected abstract void ensureCapacity​(int capacity)
      Make sure the array representation can hold a certain number of elements.
      protected abstract void fixdown​(int k)
      Downwards fix starting from a particular element
      protected abstract void fixdownWithComparator​(int k)
      Downwards fix starting from a particular element.
      protected abstract void fixup​(int k)
      Upwards fix starting from a particular element
      protected abstract void fixupWithComparator​(int k)
      Upwards fix starting from a particular element.
      protected abstract void initCapacity​(int capacity)
      Initialize array representation.
      boolean isEmpty()
      Returns true if this heap is empty.
      long size()
      Returns the number of elements in this heap.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • MAX_HEAP_CAPACITY

        protected static final int MAX_HEAP_CAPACITY
        The maximum heap capacity.
        See Also:
        Constant Field Values
      • MIN_HEAP_CAPACITY

        protected static final int MIN_HEAP_CAPACITY
        The minimum heap capacity.
        See Also:
        Constant Field Values
      • DOWNSIZING_MIN_HEAP_CAPACITY

        protected static final int DOWNSIZING_MIN_HEAP_CAPACITY
        Limit for the heap capacity when down-sizing.
        See Also:
        Constant Field Values
      • comparator

        protected final java.util.Comparator<? super K> comparator
        The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.
      • array

        protected K[] array
        The array used for representing the heap.
      • size

        protected int size
        Number of elements in the heap.
      • minCapacity

        protected final int minCapacity
        Minimum capacity due to initially requested capacity.
    • Constructor Detail

      • AbstractArrayWeakHeap

        public AbstractArrayWeakHeap​(java.util.Comparator<? super K> comparator,
                                     int capacity)
        Constructor
        Parameters:
        comparator - the comparator to use
        capacity - the requested capacity
    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Returns true if this heap is empty.
        Specified by:
        isEmpty in interface Heap<K>
        Returns:
        true if this heap is empty, false otherwise
      • size

        public long size()
        Returns the number of elements in this heap.
        Specified by:
        size in interface Heap<K>
        Returns:
        the number of elements in this heap
      • comparator

        public java.util.Comparator<? super K> comparator()
        Returns the comparator used to order the keys in this heap, or null if this heap uses the natural ordering of its keys.
        Specified by:
        comparator in interface Heap<K>
        Returns:
        the comparator used to order the keys in this heap, or null if this heap uses the natural ordering of its keys
      • clear

        public void clear()
        Clear all the elements of this heap.
        Specified by:
        clear in interface Heap<K>
      • checkCapacity

        protected final void checkCapacity​(int capacity)
        Check that a capacity is valid.
        Parameters:
        capacity - the capacity
        Throws:
        java.lang.IllegalArgumentException - if the capacity is negative or more than the maximum array size
      • initCapacity

        protected abstract void initCapacity​(int capacity)
        Initialize array representation.
        Parameters:
        capacity - the capacity
      • ensureCapacity

        protected abstract void ensureCapacity​(int capacity)
        Make sure the array representation can hold a certain number of elements.
        Parameters:
        capacity - the capacity
      • fixup

        protected abstract void fixup​(int k)
        Upwards fix starting from a particular element
        Parameters:
        k - the index of the starting element
      • fixupWithComparator

        protected abstract void fixupWithComparator​(int k)
        Upwards fix starting from a particular element. Performs comparisons using the comparator.
        Parameters:
        k - the index of the starting element
      • fixdown

        protected abstract void fixdown​(int k)
        Downwards fix starting from a particular element
        Parameters:
        k - the index of the starting element
      • fixdownWithComparator

        protected abstract void fixdownWithComparator​(int k)
        Downwards fix starting from a particular element. Performs comparisons using the comparator.
        Parameters:
        k - the index of the starting element