heaps.mapping
Class ArrayBackedMappingHeap<K,V>

java.lang.Object
  heaps.mapping.MappingHeap<K,V>
      heaps.mapping.ArrayBackedMappingHeap<K,V>

Type Parameters:

K - the type of all keys

V - the type of all values

All Implemented Interfaces:

Heap<MappingHeapEntry<K,V>>

public class ArrayBackedMappingHeap<K,V>
extends MappingHeap<K,V>

A implementation of the MappingHeap interface that is only backed by an array. For an array of N elements, this class executes the methods of MappingHeap that depend on the implementation in O(N) time. These methods are slower than their counterparts implemented in FastMappingHeap because existing mappings must be searched for in the backing array.

Author:

Michael Parker

Constructor Summary

ArrayBackedMappingHeap()
Creates a new heap with the backing array having an initial size of 16.

ArrayBackedMappingHeap(java.util.Comparator<? super K> _comp)
Creates a new heap with the backing array having an initial size of 16.

ArrayBackedMappingHeap(java.util.Comparator<? super K> _comp, int _init_capacity)
Creates a new heap with the backing array having the specified initial size.

ArrayBackedMappingHeap(int _init_capacity)
Creates a new heap with the backing array having the specified initial size.

Method Summary

void	clear() Removes all elements from the heap.
boolean	contains(K key) Returns whether a value is mapped to by the given key.
MappingHeapEntry<K,V>	extract() Extracts the next element from the heap.
V	get(K key) Returns the value that is mapped to by the given key.
int	getSize() Returns the number of elements in the heap.
boolean	isEmpty() Returns true if the heap is empty, false otherwise.
V	put(K key, V value) Creates a mapping from the given key to the given value.
V	remove(K key) Removes the mapping for the given key if one exists.
MappingHeapEntry<K,V>	top() Returns the next object element to be extracted from the heap without actually removing it from the heap.

Methods inherited from class heaps.mapping.MappingHeap

getComparator

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayBackedMappingHeap

public ArrayBackedMappingHeap()

Creates a new heap with the backing array having an initial size of 16. Elements are sorted by the natural ordering of the keys, which must implement the Comparable interface and be mutually comparable.

ArrayBackedMappingHeap

public ArrayBackedMappingHeap(int _init_capacity)

Creates a new heap with the backing array having the specified initial size. The constructed heap relies on the natural ordering of the keys, which must implement the Comparable interface and be mutually comparable.

Parameters:

_init_capacity - the initial size of the backing array

ArrayBackedMappingHeap

public ArrayBackedMappingHeap(java.util.Comparator<? super K> _comp)

Creates a new heap with the backing array having an initial size of 16. Keys are sorted by the provided comparator, and must be mutually comparable under it.

Parameters:

_comp - the comparator used to order keys

ArrayBackedMappingHeap

public ArrayBackedMappingHeap(java.util.Comparator<? super K> _comp,
                              int _init_capacity)

Creates a new heap with the backing array having the specified initial size. Keys are sorted by the provided comparator, and must be mutually comparable under it.

Parameters:

_comp - the comparator used to order heap elements

_init_capacity - the initial size of the backing array

Method Detail

put

public V put(K key,
             V value)

Description copied from class: MappingHeap

Creates a mapping from the given key to the given value. If the given key already maps to a value, this value is returned and the heap is modified so that the key now maps to the provided value parameter.

Specified by:

put in class MappingHeap<K,V>

Parameters:

key - the key to map to the given value

value - the value to be mapped to by the key

Returns:

the previous value associated with the given key, or null if no value existed

get

public V get(K key)

Description copied from class: MappingHeap

Returns the value that is mapped to by the given key. This this key does not map to any value, this method returns null.

Specified by:

get in class MappingHeap<K,V>

Parameters:

key - the key whose associated value is to be returned

Returns:

the value mapped to by the given key

contains

public boolean contains(K key)

Description copied from class: MappingHeap

Returns whether a value is mapped to by the given key.

Specified by:

contains in class MappingHeap<K,V>

Parameters:

key - the key to query for membership of in the heap

Returns:

true if the given key maps to a value, false otherwise

remove

public V remove(K key)

Description copied from class: MappingHeap

Removes the mapping for the given key if one exists. The value that was mapped to is returned; if no mapping exited, this method returns null and has no effect.

Specified by:

remove in class MappingHeap<K,V>

Parameters:

key - the key to remove a mapping under

Returns:

the value mapped to by the given key, or null if the key maps to no value

clear

public void clear()

Description copied from interface: Heap

Removes all elements from the heap.

top

public MappingHeapEntry<K,V> top()

Description copied from interface: Heap

Returns the next object element to be extracted from the heap without actually removing it from the heap. If the heap is non-empty, this value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Returns:

the top element in the heap

extract

public MappingHeapEntry<K,V> extract()

Description copied from interface: Heap

Extracts the next element from the heap. If the heap is non-empty, the value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Returns:

the top element removed from the heap

getSize

public int getSize()

Description copied from interface: Heap

Returns the number of elements in the heap.

Returns:

the number of heap elements

isEmpty

public boolean isEmpty()

Description copied from interface: Heap

Returns true if the heap is empty, false otherwise. This is equivalent to returning true if and only if getSize returns 0.

Returns:

true if the heap is empty, false otherwise