edu.isi.stella
Class Heap

java.lang.Object
  extended by edu.isi.stella.Stella_Object
      extended by edu.isi.stella.StandardObject
          extended by edu.isi.stella.AbstractCollection
              extended by edu.isi.stella.Collection
                  extended by edu.isi.stella.Sequence
                      extended by edu.isi.stella.Vector
                          extended by 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