Write pre and post conditions for functions #include<string> #include<cstring> #

Question

Write pre and post conditions for functions

#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

template<class ItemType>
class ArrayMaxHeap
{
private:
   static const int ROOT_INDEX = 0;        // Helps with readability
   static const int DEFAULT_CAPACITY = 21; // Small capacity to test for a full heap
   ItemType* items;                        // Array of heap items
   int itemCount;                          // Current count of heap items
   int maxItems;                           // Maximum capacity of the heap

   // ---------------------------------------------------------------------
   // Most of the private utility methods use an array index as a parameter
   // and in calculations. This should be safe, even though the array is an
   // implementation detail, since the methods are private.
   // ---------------------------------------------------------------------

   // Returns the array index of the left child (if it exists).
   int getLeftChildIndex(const int nodeIndex) const;

   // Returns the array index of the right child (if it exists).
   int getRightChildIndex(int nodeIndex) const;

   // Returns the array index of the parent node.
   int getParentIndex(int nodeIndex) const;

   // Tests whether this node is a leaf.
   bool isLeaf(int nodeIndex) const;

   // Converts a semiheap to a heap.
   void heapRebuild(int subTreeRootIndex);

   // Creates a heap from an unordered array.
   void heapCreate();
   
public:
   ArrayMaxHeap();
   ArrayMaxHeap(const ItemType someArray[], const int arraySize);
   virtual ~ArrayMaxHeap();

   // HeapInterface Public Methods:
   bool isEmpty() const;
   int getNumberOfNodes() const;
   int getHeight() const;
   ItemType peekTop() const;
   bool add(const ItemType& newData);
   // Adds a new node containing the given data to this heap.
   bool remove();
   // Removes the root node from this heap.
   void clear();
   // Removes all nodes from this heap.
   void display(string& anItem);
};
template<class ItemType>
int ArrayMaxHeap<ItemType>::getLeftChildIndex(const int nodeIndex) const
{
   return (2 * nodeIndex) + 1;
} // end getLeftChildIndex

template<class ItemType>
int ArrayMaxHeap<ItemType>::getRightChildIndex(const int nodeIndex) const
{
   return (2 * nodeIndex) + 2;
} // end getRightChildIndex

template<class ItemType>
int ArrayMaxHeap<ItemType>::getParentIndex(const int nodeIndex) const
{
   return (nodeIndex - 1) / 2;
} // end getParentIndex

template<class ItemType>
bool ArrayMaxHeap<ItemType>::isLeaf(const int nodeIndex) const
{
   return (getLeftChildIndex(nodeIndex) >= itemCount);
} // end isLeaf

template<class ItemType>
void ArrayMaxHeap<ItemType>::heapRebuild(const int subTreeNodeIndex)
{
   if (!isLeaf(subTreeNodeIndex))
   {
      // Find larger child
      int leftChildIndex = getLeftChildIndex(subTreeNodeIndex);   // A left child must exist
      int largerChildIndex = leftChildIndex;                   // Make assumption about larger child
      int rightChildIndex = getRightChildIndex(subTreeNodeIndex); // A right child might not exist
    
      // Check to see whether a right child exists
      if (rightChildIndex < itemCount)
      {
         // A right child exists; check whether it is larger
         if (items[rightChildIndex] > items[largerChildIndex])
            largerChildIndex = rightChildIndex; // Asssumption was wrong
      } // end if
    
      // If root value is smaller that the value in the larger child, swap values
      if (items[subTreeNodeIndex] < items[largerChildIndex])
      {
         swap(items[largerChildIndex], items[subTreeNodeIndex]);
       
         // Continue with the recursion at that child
         heapRebuild(largerChildIndex);
      } // end if
   } // end if
} // end heapRebuild

template<class ItemType>
void ArrayMaxHeap<ItemType>::heapCreate()
{
   for (int index = itemCount / 2; index >= 0; index--)
   {
      heapRebuild(index);
   } // end for
} // end heapCreate

template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap(): itemCount(0), maxItems(DEFAULT_CAPACITY)
{
   items = new ItemType[DEFAULT_CAPACITY];
} // end default constructor

template<class ItemType>
ArrayMaxHeap<ItemType>::
ArrayMaxHeap(const ItemType someArray[], const int arraySize):
             itemCount(arraySize), maxItems(2 * arraySize)
{
   // Allocate the array
   items = new ItemType[2 * arraySize];

   // Copy given values into the array
   for (int i = 0; i < itemCount; i++)
      items[i] = someArray[i];

   // Reorganize the array into a heap
   heapCreate();
} // end constructor

template<class ItemType>
ArrayMaxHeap<ItemType>::~ArrayMaxHeap()
{
   delete[] items;
} // end destructor

template<class ItemType>
bool ArrayMaxHeap<ItemType>::isEmpty() const
{
   return itemCount == 0;
} // end isEmpty

template<class ItemType>
int ArrayMaxHeap<ItemType>::getHeight() const
{
   return static_cast<int>(ceil((log(itemCount + 1) / log(2))));

} // end getHeight

template<class ItemType>
int ArrayMaxHeap<ItemType>::getNumberOfNodes() const
{
   return itemCount;
} // end getNumberOfNodes

template<class ItemType>
void ArrayMaxHeap<ItemType>::clear()
{
   itemCount = 0;
} // end clear

template<class ItemType>
ItemType ArrayMaxHeap<ItemType>::peekTop() const
{
   if (isEmpty())
   {
       cout << "Attempted peek into an empty heap. Program termiated";
       exit(1);
   }
   else
        return items[0];
} // end peekTop

template<class ItemType>
bool ArrayMaxHeap<ItemType>::add(const ItemType& newData)
{
   bool isSuccessful = false;
   if (itemCount < maxItems)
   {
      items[itemCount] = newData;

      bool inPlace = false;
      int newDataIndex = itemCount;
      while ((newDataIndex > 0) && !inPlace)
      {
         int parentIndex = getParentIndex(newDataIndex);
         if (items[newDataIndex] < items[parentIndex])
         {
            inPlace = true;
         }
         else
         {
            swap(items[newDataIndex], items[parentIndex]);
            newDataIndex = parentIndex;
         } // end if
      } // end while

      itemCount++;
      isSuccessful = true;
   } // end if

   return isSuccessful;
} // end add

template<class ItemType>
bool ArrayMaxHeap<ItemType>::remove()
{
   bool isSuccessful = false;
   if (!isEmpty())
   {
      items[ROOT_INDEX] = items[itemCount - 1];
      itemCount--;
      heapRebuild(ROOT_INDEX);
      isSuccessful = true;
   } // end if

   return isSuccessful;
} // end remove

void display(string& anItem)
{
   cout << "Displaying item - " << anItem << endl;
}

int main()
{
   ArrayMaxHeap<string>* heap1Ptr = new ArrayMaxHeap<string>();
   heap1Ptr->add("10");
   heap1Ptr->add("20");
   heap1Ptr->add("30");
   heap1Ptr->add("40");
   heap1Ptr->add("50");
   heap1Ptr->add("60");
   heap1Ptr->add("70");
   heap1Ptr->add("80");


   cout << "Heap 1: " << endl;
   while (!heap1Ptr->isEmpty())
   {
      cout << "# of nodes: " << heap1Ptr->getNumberOfNodes() << endl;
      cout << "Height: "     << heap1Ptr->getHeight() << endl;
      cout << "max value: " << heap1Ptr->peekTop() << endl;
      cout << "remove: "     << heap1Ptr->remove() << endl << endl;
   } // end while

   ArrayMaxHeap<string>* heap2Ptr = new ArrayMaxHeap<string>();
   heap2Ptr->add("50");
   heap2Ptr->add("30");
   heap2Ptr->add("70");
   heap2Ptr->add("20");
   heap2Ptr->add("60");
   heap2Ptr->add("40");
   heap2Ptr->add("10");
   heap2Ptr->add("80");

   cout << "-------------" << endl;
   cout << "Heap 2: " << endl;
   while (!heap2Ptr->isEmpty())
   {
      cout << "# of nodes: " << heap2Ptr->getNumberOfNodes() << endl;
      cout << "Height: "     << heap2Ptr->getHeight() << endl;
      cout << "max value: " << heap2Ptr->peekTop() << endl;
      cout << "remove: "     << heap2Ptr->remove() << endl << endl;
   } // end while

   return 0;
} // end main

Explanation / Answer

1) int getLeftChildIndex(const int nodeIndex) const;

//Precondition: nodelIndex >= 0

//PostCondition: Returns the array index of the left child if it exists.

2) int getRightChildIndex(int nodeIndex) const;

//Precondition: nodelIndex >= 0

//Postcondition: Returns the array index of the right child if it exists.

3) int getParentIndex(int nodeIndex) const;

//Precondition: nodelIndex > 0

//Postcondition: Returns the array index of the parent node.

4) bool isLeaf(int nodeIndex) const;

//Precondition: nodelIndex >= 0

//Postcondition: The value returned by the function is True if the left child is a leaf. Otherwise the value returned by the function is false.

5) void heapRebuild(int subTreeRootIndex);

//Precondition: subTreeRootIndex >= 0

//Postcondition: Arranges the nodes with values in decending order

void heapCreate();

//Precondition: Unordered array

//Postcondition: Creates a heap from an unordered array.

bool isEmpty() const;

//Postcondition: The value returned by the function is True if the heap is not empty. Otherwise the value is false.

int getNumberOfNodes() const;

//Precondition: Create heap.

//Postcondition: Returns the number of nodes in a heap

int getHeight() const;

//Postcondition: Returns the heigh of heap

bool add(const ItemType& newData);

//Precondition: newData should be of type ItemType

//Postcondition: Adds a new node containing the given data to this heap.

bool remove();

//Precondition: Heap should have root node

//Postcondition: The value returned from the function is true if the root node is removed from this heap, otherwise the value is false.

void clear();

//Precondition: Heap should have nodes

//Postcondition: Removes all nodes from this heap.

void display(string& anItem);

//Precondition: Heap should have nodes

//Postcondition: Displays the nodes

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.