- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Utils/Containers/DynamicHeap.cpp

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00009 // Organization:        Model-based Embedded and Robotic Systems Group
    00010 //                                      Massachusetts Institute of Technology
    00011 //
    00013
    00014 #include "DynamicHeap.h"
    00015 #include <stdio.h>
    00016
    00017 using Mers::Utils::Containers::DynamicHeap;
    00018
    00020 // Construction/Destruction
    00022
    00023 DynamicHeap::DynamicHeap(bool myLargestFirstHeap, DynamicArray::DynamicArrayType myHeapType,
    00024                 bool myOwnershipStatus)
    00025 : DynamicArray(myHeapType, myOwnershipStatus)
    00026 {
    00027         largestFirst = myLargestFirstHeap;
    00028 }
    00029
    00031
    00032 DynamicHeap::~DynamicHeap()
    00033 {
    00034
    00035 }
    00036
    00038
    00039 DynamicHeap::DynamicHeap(DynamicHeap const &other)
    00040 : DynamicArray(other)
    00041 {
    00042         largestFirst = other.largestFirst;
    00043 }
    00044
    00046
    00047 DynamicHeap::DynamicHeap(DynamicHeap const * other)
    00048 : DynamicArray(*other)
    00049 {
    00050         largestFirst = other->largestFirst;
    00051 }
    00052
    00054
    00055 void DynamicHeap::heapify(unsigned int elementIndex)
    00056 {
    00057         unsigned int left, right, largest;
    00058
    00059         left = (elementIndex << 1) + 1;
    00060         right = left + 1;
    00061         if(left < mSize &&
    00062                 ((largestFirst && greaterThan(array[left], array[elementIndex])) ||
    00063                 (!largestFirst && lessThan(array[left], array[elementIndex])))){
    00064                 largest = left;
    00065         }else{
    00066                 largest = elementIndex;
    00067         }
    00068         if(right < mSize &&
    00069                 ((largestFirst && greaterThan(array[right], array[largest])) ||
    00070                 (!largestFirst && lessThan(array[right], array[largest])))){
    00071                 largest = right;
    00072         }
    00073         if(largest != elementIndex){
    00074                 void * tmp = array[elementIndex];
    00075                 array[elementIndex] = array[largest];
    00076                 array[largest] = tmp;
    00077                 heapify(largest);
    00078         }
    00079 }
    00080
    00082
    00083 int DynamicHeap::insert(void * element)
    00084 {
    00085         unsigned int i, parent;
    00086
    00087         if(FAILED(pushBack(element))){
    00088                 fprintf(stderr, "Unable to add a new element to this heap: %s\n",
    00089                         DynamicArray::dynamicArrayTypeToString(getDynamicArrayType()));
    00090                 return 1;
    00091         }
    00092
    00093         // i is 0 indexed
    00094         i = mSize - 1;
    00095         // parent is 0 indexed
    00096         parent = ((i + 1) / 2) - 1;
    00097         // find our insertion point
    00098         while(i > 0 &&
    00099                 ((largestFirst && greaterThan(element, array[parent])) ||
    00100                 (!largestFirst && lessThan(element, array[parent])))){
    00101                 array[i] = array[parent];
    00102                 i = parent;
    00103                 parent = ((i + 1) / 2) - 1;
    00104         }
    00105         // insert the new element
    00106         array[i] = element;
    00107         return 0;
    00108 }
    00109
    00111
    00112 int DynamicHeap::peekFirst(void * &element)
    00113 {
    00114         if(mSize == 0){
    00115                 fprintf(stderr, "Error, accessing an element from an empty heap\n");
    00116                 element = NULL;
    00117                 return 1;
    00118         }
    00119
    00120         element = array[0];
    00121         return 0;
    00122 }
    00123
    00125
    00126 int DynamicHeap::getFirst(void * &element)
    00127 {
    00128         void * tmp;
    00129
    00130         if(mSize == 0){
    00131                 fprintf(stderr, "Error, accessing an element from an empty heap\n");
    00132                 element = NULL;
    00133                 return 1;
    00134         }
    00135
    00136         element = array[0];
    00137         tmp = popBack();
    00138         array[0] = tmp;
    00139         heapify(0);
    00140         return 0;
    00141 }
    00142
    00144