edu.isi.stella
Class Heap

java.lang.Object
  edu.isi.stella.Stella_Object
      edu.isi.stella.StandardObject
          edu.isi.stella.AbstractCollection
              edu.isi.stella.Collection
                  edu.isi.stella.Sequence
                      edu.isi.stella.Vector
                          edu.isi.stella.Heap

public class Heap
extends Vector

Implements a Min or Max heap depending on the semantics of predicate (Min if predicate has a L semantics). This is useful for in-place sorting (even though we have specialzed sort routines for that) or to maintain top-N lists with log(N) insertion time. We place this under VECTOR instead of VECTOR-SEQUENCE for now, since sequential order isn't really maintained or accessible until we sort the heap.

Field Summary

int	fillPointer
java.lang.reflect.Method	predicate

Fields inherited from class edu.isi.stella.Vector

arraySize, theArray

Constructor Summary

Heap()

Method Summary

static Stella_Object	accessHeapSlotValue(Heap self, Symbol slotname, Stella_Object value, boolean setvalueP)
void	clear() Clear self by setting its active length to zero.
boolean	emptyP() Return TRUE if self is empty.
Stella_Object	fastHeapRoot() Return the root of self which is assumed to be non-empty.
void	heapify() Restore the heap property of self according to its predicate.
Stella_Object	heapRoot() Return the root of self (NULL if self is empty).
void	initializeHeap()
void	insert(Stella_Object value) Insert value into self and restore the heap property.
void	insertIfBetter(Stella_Object value) Insert value into self and restore the heap property.
int	length() Return the length of the currently filled portion of self.
static Heap	newHeap(java.lang.reflect.Method predicate, int arraySize)
Surrogate	primaryType() Returns the primary type of self.
void	replaceHeapRoot(Stella_Object value) Replace the current root of self with value and restore the heap property.
Vector	sort(java.lang.reflect.Method predicate) Sort the heap self according to predicate (in ascending order if predicate has L semantics).

Methods inherited from class edu.isi.stella.Vector

accessVectorSlotValue, allocateIterator, butLast, consify, copy, equalHashCode, fifth, fifthSetter, first, firstSetter, fourth, fourthSetter, initializeVector, insertAt, last, lastPosition, lastSetter, listify, memberP, newVector, nonEmptyP, nth, nthSetter, objectEqualP, position, printObject, printVector, resizeVector, second, secondSetter, third, thirdSetter

Methods inherited from class edu.isi.stella.Sequence

orderedP, sequence, yieldConsListFromSequence

Methods inherited from class edu.isi.stella.Collection

noDuplicatesP, remove

Methods inherited from class edu.isi.stella.StandardObject

arrayTypeSpecifierP, baseTypeToTypeSpec, cantOverwriteActiveCollectionSlot, compatibleParameterTypesP, computeAnchoredTypeSpec, computeRelativeTypeSpec, conformingTypeSpecP, copyWrappedLiteral, cppNonPointerTypeP, cppReferenceTypeP, cppReferencizeType, cppTranslateAndPointerizeTypeSpec, cppTranslateAndReferencizeTypeSpec, cppTranslateTypeSpec, cppTypeWithoutInteriorPointersP, dropSlotValue, extractParameterType, extractRequiredArgumentValues, getSlot, hashCode_, idlTranslateTypeSpec, inverseSlotDemon, javaLiteralP, javaNativeLiteralWrapperNames, javaSpecialSetterName, javaTranslateArrayOfTypeSpec, javaTranslateTypeSpec, javaTranslateTypeSpecForFunction, javaTranslateTypeSpecHelper, javaYieldClassObjectArrayExpression, javaYieldClassObjectExpression, javaYieldFullyQualifiedTypeName, javaYieldTranslatedClassAndMethodNames, listifyTypeSpec, lookupClTypeFromStellaType, objectEqlP, putSlotValue, readSlotValue, runConstructorDemons, runDestructorDemons, runSlotDemons, runSlotGuardDemonsP, standardObjectP, subTypeSpecOfP, twoArgumentLeastCommonSupertype, typeSpecToBaseType, typeSpecToClass, typeToWalkedNullValueTree, validateTypeSpecifier, voidP, walkTypeSpecIsNativeTypeP, writeSlotValue, yieldTypeSpecTree

Methods inherited from class edu.isi.stella.Stella_Object

_, accessInContext, addPropertyValue, amPm, anchoredTypeSpecifierP, andOrNotTreeP, applyCoercionMethod, atomicExpressionP, bindToSurrogateP, booleanP, bootstrapIsaP, bquotify, cast, characterP, chooseSortPredicate, clConditionalizeTypeDeclarationTree, clTranslateAtomicTree, clTranslateATree, clTranslateBooleanTest, clTranslatePlainBooleanTest, clTranslateVerbatimBodySymbols, clYieldTypedExpressionTree, coerceATree, coerceEvaluatedTree, coerceMvTree, coerceOptionValue, coerceToBoolean, coerceToFloat, coerceToHashSet, coerceToModule, coerceToModuleName, coerceToString, coerceToSymbol, coerceToXmlElement, coerceValueToBoolean, coerceValueToFloat, coerceValueToString, coerceValueToType, coercibleP, collectFeatureList, collectKeyValueList, commonLispSymbolP, computeExpressionType, consifyListsAndIterators, consP, consTreeMatchP, convertToLiteral, copyConsTree, cppArgumentIsStreamP, cppBinaryOperatorP, cppBlockP, cppMaybeOutputStatementWithParentheses, cppOperatorP, cppOutputAtomicExpression, cppOutputLiteral, cppOutputOneActualParameter, cppOutputStatement, cppOutputTypedEntity, cppPrognifyStatement, cppPrognP, cppStatementToList, cppStreamIsStandardOutputP, cpptrans, cppTranslateAtomicTree, cppTranslateATree, cppTranslatedArrayTypeP, csValueP, dateDivider, dateTimeDivider, day, dealWithAmPm, dealWithEra, dealWithNoonMidn, decrementReferenceCount, defaultOptionHandler, defineSystem, defmodule, deletedP, describe, describeObject, describeTersely, destructureMethodNameTree, deUglifyParseTree, either, eqlP, eqlToBooleanP, eqlToCharacterP, eqlToFloatP, eqlToIntegerP, eqlToLongIntegerP, eqlToStringP, equalConsTreesP, equalP, era, estimatedEvaluationCost, evaluate, evaluateArgumentTree, evaluateAtomicTree, evaluateCommand, expandBquoteTree, filterModuleP, floatP, free, get, getObject, getProperty, hashlist, hashMemoizedArguments, helpBquotify, helpClTranslateATree, helpCoerceATree, helpLptrans, helpPrintOutline, helpTransformBooleanProceduralExpression, helpWalkATree, homeModule, hour, idlOutputAtomicExpression, idlOutputLiteral, idlOutputStatement, idlTranslateAtomicTree, idlTranslateATree, illegalTreeP, implodePathname, incrementallyTranslate, incrementReferenceCount, inlineUnwrapBoolean, inlineWrapBoolean, inModule, integerP, isaP, javaBinaryOperatorP, javaBlockP, javaEndOfLineTokenP, javaHelpOutputPrintStream, javaMaybeOutputStatementWithParentheses, javaOperatorP, javaOutputLiteral, javaOutputStatement, javaPrognP, javaStreamIsStandardOutputP, javaSymbolCaseP, javaTranslateAtomicTree, javaTranslateATree, javaTranslateWithNativeWrapper, jptrans, keywordP, legalTokenizerFromStateP, legalTokenizerStateP, legalTokenizerToStateP, literalEqlP, logLevelLE, longIntegerP, lptrans, makeEvaluatableBquoteTree, makeFileNameFromRelativePath, makeMemoizedValueEntry, makeMemoizedValueEntryn, matchConsTree, methodSlotP, minute, month, nameToString, nilP, noonMidn, numberWrapperToFloat, objectHashCode, one, oneI, onlyIf, parametricTypeSpecifierP, parseArrayDimensionsSpec, parseOptions, parseTokenizerCharacterSpec, parseTokenizerStateModifiers, permanentCopy, permanentify, permanentifyForm, po, prettyPrintLiteral, primaryClass, printOutline, printStellaCode, printStellaDefinition, printUndefinedSuperClasses, proceduralExpressionP, ptrans, publicSlots, registerRecycledItem, runOptionHandlerP, safeEqualHashCode, safeHashCode, safePrimaryType, safeYieldTypeSpecifier, searchConsTreeP, searchConsTreeWithFilterP, searchForObject, secondp, setProperty, sideEffectFreeExpressionP, simplifyBquoteTree, specialp, stella_Increment, stellaClassP, stellaCollectionP, stellaNeedToCompileP, stellaNeedToTranslateP, stellaObjectP, stellify, storageSlotP, stringifyInModule, stringP, substituteConsTree, substituteOnce, surrogateP, surrogatify, sweep, symbolCaseP, symbolP, sysTree, targetLanguageType, taxonomyIsaP, timeDivider, timeMultiply, tokenizerIncludeSpecP, tokenizerToStateAlias, tokenizerToStateName, toString, traceIf, traceKeywordP, transientifyForm, transientObjectP, transientSymbolP, translateWalkedTree, treeSize, treeToTrees, trueOptionP, tryToEvaluate, typeP, typify, unmake, unregisterRecycledItem, updateInContext, valuesTreeP, variableExpressionP, verbatimStringP, verbatimTreeP, vetOptions, vrletExpressionP, walkAtomicTree, walkATree, walkCollectionTree, walkDontCallMeTree, walkedExpressionExpression, walkedExpressionType, walkExpressionTree, walkMvExpressionTree, walkMvTree, walkStatement, walkTopLevelExpression, walkWithoutTypeTree, warnAboutUnknownSourceType, weekday, withinContext, withinModule, withinWorld, withStellaTokenizer, withSystemDefinition, withTokenizer, wrapperP, wrapWhereTest, xmlAttributeP, xmlBaseAttributeP, xmlCdataFormP, xmlCdataP, xmlDeclarationFormP, xmlDeclarationP, xmlDoctypeFormP, xmlElementFormP, xmlElementP, xmlGlobalAttributeP, xmlLocalAttributeP, xmlnsAttributeP, xmlProcessingInstructionFormP, xmlProcessingInstructionP, xmlTagCase, year, yieldCondTest, yieldCondTestOrTests, yieldHardcodedCaseSymbolIdOrIds, yieldInCursorClausesForArgumentList, yieldInCursorClausesForGeneralCollection, yieldInCursorClausesForVector, yieldTypeSpecifier, zone, zoneMinute

Methods inherited from class java.lang.Object

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

Field Detail

predicate

public java.lang.reflect.Method predicate

fillPointer

public int fillPointer

Constructor Detail

Heap

public Heap()

Method Detail

newHeap

public static Heap newHeap(java.lang.reflect.Method predicate,
                           int arraySize)

sort

public Vector sort(java.lang.reflect.Method predicate)

Sort the heap self according to predicate (in ascending order if predicate has L semantics). If predicate is NULL simply use selfs internal predicate (the normal case). If it is different from selfs internal predicate, heapify self first according to the new predicate, store the new predicate in self and then sort the heap. Note that a sorted array automatically satisfies the heap property. This is slightly different than a regular heap sort due to the way HEAP's are maintained; however, the complexity is the same.

Overrides:

sort in class Vector

Parameters:

predicate -

Returns:

Vector

heapify

public void heapify()

Restore the heap property of self according to its predicate. Normally, this is not needed, since insert operations preserve the heap property. However, this can be useful after bulk insertion of values or if predicate has been changed.

insertIfBetter

public void insertIfBetter(Stella_Object value)

Insert value into self and restore the heap property. If self has available room, simply insert value. If the heap is full, only insert value if it is better than the current root (i.e., the minimum of self if selfs predicate has L semantics). In that case, replace the root of self and restore the heap property. This is useful to build and maintain a heap with some top-N elements (relative to predicate) where the root (or minimum) of self is the currently weakest element at the end of the list.

Parameters:

value -

replaceHeapRoot

public void replaceHeapRoot(Stella_Object value)

Replace the current root of self with value and restore the heap property. Signal an error if self is empty. Maintains self as a Min-heap if selfs predicate has L semantics; otherwise as a Max-heap.

Parameters:

value -

insert

public void insert(Stella_Object value)

Insert value into self and restore the heap property. Signal an error if there is no more room in self. Maintains self as a Min-heap if selfs predicate has L semantics; otherwise as a Max-heap.

Overrides:

insert in class Collection

Parameters:

value -

fastHeapRoot

public Stella_Object fastHeapRoot()

Return the root of self which is assumed to be non-empty.

Returns:

Stella_Object

heapRoot

public Stella_Object heapRoot()

Return the root of self (NULL if self is empty).

Returns:

Stella_Object

emptyP

public boolean emptyP()

Return TRUE if self is empty.

Overrides:

emptyP in class Vector

Returns:

boolean

length

public int length()

Return the length of the currently filled portion of self.

Overrides:

length in class Vector

Returns:

int

clear

public void clear()

Clear self by setting its active length to zero.

Overrides:

clear in class Vector

initializeHeap

public void initializeHeap()

accessHeapSlotValue

public static Stella_Object accessHeapSlotValue(Heap self,
                                                Symbol slotname,
                                                Stella_Object value,
                                                boolean setvalueP)

primaryType

public Surrogate primaryType()

Description copied from class: Stella_Object

Returns the primary type of self. Gets defined automatically for every non-abstract subclass of OBJECT.

Overrides:

primaryType in class Vector

Returns:

Surrogate