name: SysHeap

synopsis:

g++ [flags ...] file ... -l /isip/tools/lib/$ISIP_BINARY/lib_system.a

#include <SysHeap.h>

boolean insert(void* ptr);
boolean extractMax(void*& ptr);
boolean extract(void* ptr);
boolean build();

quick start:

// declare a heap object
//
SysHeap heap;

// set the length of heap
//
heap.setLength(10);

// give values to heap
//
heap.data_d[0] = (void*)8;
heap.data_d[1] = (void*)14;
heap.data_d[2] = (void*)7;
heap.data_d[3] = (void*)11;
heap.data_d[4] = (void*)10;
heap.data_d[5] = (void*)1;
heap.data_d[6] = (void*)4;
heap.data_d[7] = (void*)2;
heap.data_d[8] = (void*)3;
heap.data_d[9] = (void*)9;

// declare a pointer
//
void* ptr_ins;

// insert this pointer into heap
//
ptr_ins = (void*)12;
heap.insert(ptr_ins);

description:

The SysHeap class implements a heap for pointers. The insert and extract methods are the most useful methods. The insert method adds a pointer to the heap and the extract method removes a pointer from the heap. The extractMax method, on the other hand, removes and returns the largest pointer from the heap.

The binary heap data structure is an array that can be viewed as a complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

If an array A is used to represents a heap, A[0] is the root of the tree. Also, given the index i of a node the following indices can be found:

Parent (i)      = i / 2     

Left Child (i)  = 2 * i + 1 

Right Child (i) = 2 * i + 2

A good tutorial on heaps can be found at :

Introduction to Algorithms

dependencies:

public constants:

define the class name:

static const unichar CLASS_NAME[] = L"SysHeap";

define the default value(s) of the class data:

static const long DEF_NUM_ELEMENTS = 0;

static const long DEF_CAPACITY = 0;

static const long DEF_GROW_FACTOR = 2;

error codes:

error code indicating SysHeap class general error:
```
static const long ERR = 1700;
```
error code indicating that heap is empty:
```
static const long ERR_HEMPTY = 1701;
```
error code indicating attemp to extract pointer which is not on heap:
```
static const long ERR_INVPTR = 1702;
```

protected data:

array of void pointers:

void** data_d;

capacity of heap:

long capacity_d;

number of elements in heap:

long num_elements_d;

growth factor of heap:

long grow_factor_d;

declare a static debug level for all class instantiations:
```
Integral::DEBUG debug_level_d;
```

required public methods:

static methods:

static const SysString& name();

static boolean diagnose(Integral::DEBUG debug_level);

debug methods:

static boolean setDebug(Integral::DEBUG debug_level);

boolean debug(const unichar* message);

destructor/constructor(s):
```
~SysHeap();
```
```
SysHeap();
```

assign methods:

these methods are omitted because SysHeap cannot be duplicated

operator= methods:

these methods are omitted because SysHeap cannot be duplicated

i/o methods:

these methods are omitted because SysHeap can not write itself to an sof file

equality methods:
```
boolean eq(const SysHeap& arg);
```

memory management methods:

new and delete are omitted because memory for SysHeap objects is not managed by the MemoryManager class

boolean clear(Integral::CMODE ctype_a = Integral::DEF_CMODE);

class-specific public methods:

heap specific property methods: these methods are used to build heaps, get the length of the heap and test if the heap is empty
```
boolean build();
```
```
boolean isEmpty() const;
```
```
long length() const;
```

data manipulation methods: these methods are used to add, find and remove pointers to/from the heap as well as set the heap properties

boolean insert(void* ptr);

long find(void* ptr, long start_index = 0) const;

boolean extractMax(void*& ptr);

boolean extract(void* ptr);

boolean extract(void* ptr, long pos);

boolean setLength(long len);

boolean setCapacity(long cap);

boolean setGrow(long grow_factor);

private methods:

copy constructor: this is declared private so it cannot be called for the SysHeap class

SysHeap(const SysHeap& arg);

heapify methods:
```
boolean heapify(long index);
```
bubble up methods:
```
boolean bubbleUp(long index);
```
parent methods:
```
boolean parent(long index) const;
```

left and right child methods:

boolean left(long index) const;

boolean right(long index) const;

examples:

This example shows how to build the heap:

// declare heap object
//
SysHeap heap;

// set the length of the heap
//
heap.setLength(5);

// give values to heap
//
heap.data_d[0] = (void*)8;
heap.data_d[1] = (void*)14;
heap.data_d[2] = (void*)7;
heap.data_d[3] = (void*)11;
heap.data_d[4] = (void*)10;

// build the heap
//
heap.build();

This example shows how to insert and delete a pointer from the heap, and also, how to extract the maximum pointer from the heap:

// insertion of a pointer in the heap
//
void* ptr0;
ptr0 = (void*)15;
heap.insert(ptr0);

// extract the maximum pointer from the heap
//
void* ptr_ext_max;
heap.extractMax(ptr_ext_max);

// extract a pointer from the heap
//
void* ptr1;
ptr1 = (void*)11;
heap.extract(ptr1);

notes:

none.