|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
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
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 java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public java.lang.reflect.Method predicate
public int fillPointer
Constructor Detail |
---|
public Heap()
Method Detail |
---|
public static Heap newHeap(java.lang.reflect.Method predicate, int arraySize)
public Vector sort(java.lang.reflect.Method predicate)
self
according to predicate
(in
ascending order if predicate
has L
semantics). If predicate
is NULL simply use self
s internal predicate (the normal case).
If it is different from self
s 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.
sort
in class Vector
predicate
-
public void heapify()
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.
public void insertIfBetter(Stella_Object value)
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 self
s 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.
value
- public void replaceHeapRoot(Stella_Object value)
self
with value
and restore
the heap property. Signal an error if self
is empty. Maintains self
as
a Min-heap if self
s predicate
has L
semantics; otherwise as a Max-heap.
value
- public void insert(Stella_Object value)
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 self
s predicate
has L
semantics; otherwise as a Max-heap.
insert
in class Collection
value
- public Stella_Object fastHeapRoot()
self
which is assumed to be non-empty.
public Stella_Object heapRoot()
self
(NULL if self
is empty).
public boolean emptyP()
self
is empty.
emptyP
in class Vector
public int length()
self
.
length
in class Vector
public void clear()
self
by setting its active length to zero.
clear
in class Vector
public void initializeHeap()
public static Stella_Object accessHeapSlotValue(Heap self, Symbol slotname, Stella_Object value, boolean setvalueP)
public Surrogate primaryType()
Stella_Object
self
.
Gets defined automatically for every non-abstract subclass of OBJECT.
primaryType
in class Vector
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |