001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.lib;
032:
033: /**
034: * Provides the base HSQLDB interface for Heap ADT implementations. <p>
035: *
036: * In this context, a Heap is simply a collection-like ADT that allows addition
037: * of elements and provides a way to remove the least element, given some
038: * implementation-dependent strategy for imposing an order over its
039: * elements. <p>
040: *
041: * Typically, an HsqlHeap will be implemented as a tree-like structure that
042: * recursively guarantees a <i>Heap Invariant</i>, such that all nodes below
043: * the root are greater than the root, given some comparison stragegy. <p>
044:
045: * This in turn provides the basis for an efficient implementation of ADTs such
046: * PriorityQueue, since Heap operations using the typical implementation are,
047: * in theory, guaranteed to be O(log n).
048: *
049: * @author boucherb@users
050: * @version 1.7.2
051: * @since 1.7.2
052: */
053: public interface HsqlHeap {
054:
055: /**
056: * Removes all of the elements from this Heap.
057: */
058: void clear();
059:
060: /**
061: * Retrieves whether this Heap is empty.
062: */
063: boolean isEmpty();
064:
065: /**
066: * Retrieves whether this Heap is full.
067: */
068: boolean isFull();
069:
070: /**
071: * Adds the specified element to this Heap.
072: *
073: * @param o The element to add
074: * @throws IllegalArgumentException if the implementation does
075: * not accept elements of the supplied type (optional)
076: * throws RuntimeException if the implementation
077: * dictates that this Heap is not currently accepting additions
078: * or that this Heap is currently full (optional)
079: */
080: void add(Object o) throws IllegalArgumentException,
081: RuntimeException;
082:
083: /**
084: * Retrieves the least element from this Heap, without removing it.
085: *
086: * @return the least element from this Heap
087: */
088: Object peek();
089:
090: /**
091: * Retrieves the least element from this Heap, removing it in the process.
092: *
093: * @return the least element from this Heap
094: */
095: Object remove();
096:
097: /**
098: * Retrieves the number of elements currently in this Heap.
099: *
100: * @return the number of elements currently in this Heap
101: */
102: int size();
103: }
|