Welcome to Programming and Data Structures

module;

#include <iomanip>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>

export module MaxHeap;

export template<typename T>
class MaxHeap {
  // Would normally be private - public to allow intrusive unit tests
public:
  T* data;      // array containing the heap
  int capacity; // maximum size
  int heapSize; // current logical size

  // Double the size of the underlying array
  void grow();

  // Gets the index of the largest child of the specified location
  //  Returns -1 if there are no children
  int largestChildIndex(int current) const;

public:
  // Get a copy of the top item
  T getMax();

  // Rmove the top item and return it
  T removeMax();

  // Add the given value to the heap
  void add(const T& value);

  // Construct a max heap with initial space for 32 items
  MaxHeap();

  // Destroy the max heap and release memory
  ~MaxHeap();

  // Copy ctor declared, not implemented unless needed
  MaxHeap(const MaxHeap& other) = delete;
  MaxHeap& operator=(const MaxHeap& other) = delete;

  // Convert to a string representation
  std::string toString() const;
};

template<typename T>
MaxHeap<T>::MaxHeap() {
  heapSize = 0;
  capacity = 32;
  data = new T[capacity];
}

template<typename T>
MaxHeap<T>::~MaxHeap() {
  delete[] data;
}

template<typename T>
void MaxHeap<T>::grow() {
  T* temp = data;
  capacity *= 2;
  data = new T[capacity * 2];
  for (int i = 0; i < heapSize; i++)
    data[i] = temp[i];

  delete[] temp;
}

template<typename T>
std::string MaxHeap<T>::toString() const {
  std::stringstream out;
  out << "[";
  for (int i = 0; i < heapSize - 1; ++i) {
    out << " " << data[i];
  }
  out << "]";
  return out.str();
}

template<typename T>
T MaxHeap<T>::getMax() {
  if (heapSize == 0)
    throw std::logic_error("getMax in empty heap");

  return data[0];
}

//-----------Other functions to be built------------------