Line data    Source code

       1              : /**
       2              :  * @file ADTPQueue.cpp
       3              :  * @author Konstantinos Chousos
       4              :  * @version 0.1
       5              :  * @date 2023-10-30
       6              :  *
       7              :  * @brief An ADT Priority Queue implemented using a heap.
       8              :  *
       9              :  * @copyright Copyright (c) 2023
      10              :  *
      11              :  */
      12              : #include "cppdescent/ADTPQueue.hpp"
      13              : #include <iostream>
      14              : 
      15              : // Helper functions for abstraction when accessing nodes.
      16              : 
      17       483082 : Pointer PQueue::nodeValue(int nodeId) {
      18       483082 :   return this->vector->getAt(nodeId - 1);
      19              : }
      20              : 
      21       113268 : void PQueue::nodeSwap(int nodeId1, int nodeId2) {
      22       113268 :   Pointer v1 = nodeValue(nodeId1);
      23       113268 :   Pointer v2 = nodeValue(nodeId2);
      24              : 
      25       113268 :   this->vector->setAt(nodeId1 - 1, v2);
      26       113268 :   this->vector->setAt(nodeId2 - 1, v1);
      27       113268 : }
      28              : 
      29              : // Keeps the heap property.
      30       129150 : void PQueue::bubbleUp(int nodeId) {
      31       129150 :   if (nodeId == 1)
      32        15288 :     return;
      33              : 
      34       113862 :   int parent = nodeId / 2;
      35              : 
      36       113862 :   if (this->compare(nodeValue(parent), nodeValue(nodeId)) < 0) {
      37       112564 :     nodeSwap(parent, nodeId);
      38       112564 :     bubbleUp(parent);
      39              :   }
      40              : }
      41              : 
      42              : // Keeps the heap property.
      43          704 : void PQueue::bubbleDown(int nodeId) {
      44          704 :   int lchild = 2 * nodeId;
      45          704 :   int rchild = lchild + 1;
      46              : 
      47          704 :   int size = this->getSize();
      48          704 :   if (lchild > size)
      49          412 :     return;
      50              : 
      51          292 :   int maxChild = lchild;
      52          292 :   if (rchild <= size && this->compare(nodeValue(lchild), nodeValue(rchild)) < 0)
      53           98 :     maxChild = rchild;
      54              : 
      55          292 :   if (this->compare(nodeValue(nodeId), nodeValue(maxChild)) < 0) {
      56          244 :     nodeSwap(nodeId, maxChild);
      57          244 :     bubbleDown(maxChild);
      58              :   }
      59              : }
      60              : 
      61              : // Initializes the queue with the vector values.
      62           14 : void PQueue::naiveHeapify(Vector* values) {
      63              :   // TODO: there is a more optimal way
      64           14 :   int size = values->getSize();
      65           70 :   for (int i = 0; i < size; i++)
      66           56 :     this->insert(values->getAt(i));
      67           14 : }
      68              : 
      69              : // Priority Queue functionsr
      70              : 
      71         3784 : PQueue::PQueue(CompareFunc compare, DestroyFunc destroyValue, Vector* values)
      72         3784 :     : compare(compare), destroyValue(destroyValue) {
      73              :   // LCOV_EXCL_START
      74              :   if (compare == nullptr) {
      75              :     std::cerr << "`compare` function cannot be NULL. Exiting...\n";
      76              :     return;
      77              :   }
      78              :   // LCOV_EXCL_STOP
      79              : 
      80         3784 :   this->vector = new Vector(0, nullptr);
      81              : 
      82         3784 :   if (values != nullptr)
      83           14 :     naiveHeapify(values);
      84              : }
      85              : 
      86         2992 : PQueue::~PQueue() {
      87         2992 :   this->vector->setDestroyValue(this->destroyValue);
      88         2992 :   delete vector;
      89         2992 : }
      90              : 
      91        46848 : int PQueue::getSize() {
      92        46848 :   return this->vector->getSize();
      93              : }
      94              : 
      95        15190 : Pointer PQueue::getMax() {
      96        15190 :   return nodeValue(1);
      97              : }
      98              : 
      99          714 : Pointer PQueue::getMin() {
     100          714 :   int firstLeaf = this->getSize() / 2 + 1;
     101          714 :   Pointer min = this->getMax();
     102              : 
     103         9842 :   for (int i = firstLeaf; i < this->getSize() + 1; i++) {
     104         9128 :     Pointer value = nodeValue(i);
     105         9128 :     if (compare(min, value) > 0)
     106         9100 :       min = value;
     107              :   }
     108              : 
     109          714 :   return min;
     110              : }
     111              : 
     112        16586 : void PQueue::insert(Pointer value) {
     113        16586 :   this->vector->insertLast(value);
     114              :   // The newly added element might not adhere to the heap property, when
     115              :   // it is placed at the last position. So we call `bubbleUp` to reestablish
     116              :   // this property on the queue.
     117        16586 :   bubbleUp(this->getSize());
     118        16586 : }
     119              : 
     120          154 : void PQueue::removeMax() {
     121              :   // LCOV_EXCL_START
     122              :   int lastNode = this->getSize();
     123              :   if (lastNode == 0) {
     124              :     std::cerr << "removeMax: Queue is empty. Exiting...\n";
     125              :     return;
     126              :   }
     127              :   // LCOV_EXCL_STOP
     128              : 
     129          154 :   if (this->destroyValue != nullptr)
     130          154 :     this->destroyValue(this->getMax());
     131              : 
     132          154 :   nodeSwap(1, lastNode);
     133          154 :   this->vector->removeLast();
     134              : 
     135              :   // Reestablish the heap property.
     136          154 :   bubbleDown(1);
     137              : }
     138              : 
     139           14 : DestroyFunc PQueue::setDestroyValue(DestroyFunc destroyValue) {
     140           14 :   DestroyFunc old = this->destroyValue;
     141           14 :   this->destroyValue = destroyValue;
     142           14 :   return old;
     143              : }
     144              : 
     145          334 : void PQueue::remove(Pointer value, CompareFunc compare) {
     146          334 :   int lastNode = this->getSize();
     147          334 :   if (lastNode == 0) {
     148           14 :     std::cerr << "remove: Queue is empty. Exiting...\n";
     149           14 :     return;
     150              :   }
     151              : 
     152          320 :   int tbr = this->find(value, compare);
     153              : 
     154          320 :   if (tbr == -1) {
     155           14 :     std::cerr << "remove: Given value not found. Exiting..." << std::endl;
     156           14 :     return;
     157              :   }
     158              : 
     159          306 :   if (this->destroyValue != nullptr)
     160          153 :     this->destroyValue(this->nodeValue(tbr));
     161              : 
     162          306 :   this->nodeSwap(tbr, lastNode);
     163          306 :   this->vector->removeLast();
     164              : 
     165              :   // Reestablish the heap property.
     166          306 :   this->bubbleDown(tbr);
     167              : }
     168              : 
     169         1299 : int PQueue::find(Pointer value, CompareFunc compare) {
     170         4159 :   for (int i = 1; i <= this->getSize(); i++)
     171         3307 :     if (compare(value, this->nodeValue(i)) == 0)
     172          447 :       return i;
     173              : 
     174          852 :   return -1;
     175              : }