How to properly abuse a prioirty queue

2014-10-20 21:16 by Ian

My collection of C++ classes has grown to include a priority queue template. Here is that template, and an example of how to make it do something it wasn't written to do: Calculate statistical mode.

PriorityQueue.h

/*
File:   PriorityQueue.h
Author: J. Ian Lindsay
Date:   2014.06.30

Copyright (C) 2014 J. Ian Lindsay

Everyone is permitted to copy and distribute verbatim or modified 
copies of this license document, and changing it is allowed as long 
as the name is changed. 

         DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE 
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 

0. You just DO WHAT THE FUCK YOU WANT TO.

http://www.wtfpl.net


Template for a priority queue implemented on top of a linked-list.
Highest-priority nodes are stored closest to the beginning of the list.
*/

#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <inttypes.h>
#ifdef ARDUINO
  #include "Arduino.h"
#else
  #include <stdlib.h>
#endif

using namespace std;

/* This is the class that holds a datum in the list. */
template <class T> class PriorityNode{
  public:
    PriorityNode<T> *next;
    T data;
    int priority;
    bool reap;
};


/*
* The class that should be instantiated.
*/
template <class T> class PriorityQueue {
  public:
    PriorityQueue(void);
    ~PriorityQueue(void);

    int insert(T, int priority);  // Returns the ID of the data, or -1 on failure. Makes only a reference to the payload.
    int insert(T);                // Same as above, but assumes lowest priority.
    
    int size(void);               // Returns the number of elements in this list.

    T dequeue(void);              // Removes the first element of the list. Return the node's data on success, or NULL on empty queue.
    bool remove(int position);    // Removes the element at the given position of the list. Return true on success.

    T get(void);                  // Returns the data from the first element.
    T get(int position);          // Returns the data from the element at the given position.
    int getPosition(T);           // Returns the position in the queue for the given element.
    int getPriority(T);           // Returns the priority in the queue for the given element.

    bool hasNext(void);           // Returns false if this list is empty. True otherwise.
    bool contains(T);             // Returns true if this list contains the given data. False if not.

    bool incrementPriority(T);    // Finds the given T and increments its priority by one.
    bool decrementPriority(T);    // Finds the given T and decrements its priority by one.


  private:
    PriorityNode<T> *root;        // The root of the queue. Is also the highest-priority.
    int element_count;
    
    /*
    * Returns the last element in the list. 
    * Returns the WHOLE element, not just the data it holds.
    */
    PriorityNode<T>* getLast(void);
    
    /* 
    * Returns the last element in the list with the given priority, or the highest priority
    *   item in the list if the argument is greater than all nodes. 
    */
    PriorityNode<T>* getLastWithPriority(int);

    PriorityNode<T>* get_node_by_element(T);    // Return a priority node by the element it contains.
    int insert(PriorityNode<T>*);    // Returns the ID of the data, or -1 on failure.
    void enforce_priorities(void);   // Need to call this after changing a priority to ensure position reflects priority.
    int count(void);                 // Counts the elements in the list without reliance on stored value. Slower...
};


template <class T> PriorityQueue<T>::PriorityQueue() {
  root = NULL;
  element_count = 0;
}

template <class T> PriorityQueue<T>::~PriorityQueue() {
  while (root != NULL) {
    dequeue();
  }
}


/*
* Returns the position in the list that the data was inserted, or -1 on failure.
*/
template <class T> int PriorityQueue<T>::insert(T d) {
  return insert(d, 0);
}


/*
* Returns the position in the list that the data was inserted, or -1 on failure.
* Inserts at the first position that has a lower priority than the one given.
*/
template <class T> int PriorityQueue<T>::insert(T d, int nu_pri) {
  int return_value = -1;
  PriorityNode<T> *nu = (PriorityNode<T>*) malloc(sizeof(PriorityNode<T>));
  if (nu == NULL) {
    return return_value;      // Failed to allocate memory.
  }
  nu->reap     = false;
  nu->data     = d;
  nu->priority = nu_pri;

  return_value = insert(nu);
  element_count++;
  return 1;
}


template <class T> int PriorityQueue<T>::insert(PriorityNode<T>* nu) {
  if (nu == NULL) {
    return -1;
  }

  PriorityNode<T> *current = getLastWithPriority(nu->priority);

  if (current == NULL) {
    nu->next = root;
    root     = nu;
  }
  else {
    nu->next      = current->next;
    current->next = nu;
  }
  return 1;
}



template <class T> int PriorityQueue<T>::size() {
  return element_count;
}


template <class T> int PriorityQueue<T>::count() {
  PriorityNode<T>* current = root;
  int return_value = 0;
  while (current != NULL) {
    current = current->next;
    return_value++;
  }
  element_count = return_value;
  return return_value;
}


/*
* Returns a pointer to the last PriorityNode in this linked list.
*/
template <class T> PriorityNode<T>* PriorityQueue<T>::getLast() {
  PriorityNode<T>* return_value = root;
  while ((return_value != NULL) && (return_value->next != NULL)) {
    return_value = return_value->next;
  }
  return return_value;
}


/*
* Returns a pointer to the first PriorityNode in this linked list with a matching element.
*/
template <class T> PriorityNode<T>* PriorityQueue<T>::get_node_by_element(T test_data) {
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (current->data == test_data) {
      return current;
    }
    current = current->next;
  }
  return NULL;
}


/*
* Returns a pointer to the last PriorityNode in this linked list.
* Returns NULL if there is not a node that has a priority at-least matching what we provided.
*/
template <class T> PriorityNode<T>* PriorityQueue<T>::getLastWithPriority(int nu_pri) {
  PriorityNode<T>* current      = root;
  PriorityNode<T>* last         = NULL;
  while (current != NULL) {
    if (nu_pri > current->priority) {
      return last;
    }
    last    = current;
    current = current->next;
  }
  return last;
}


template <class T> void PriorityQueue<T>::enforce_priorities(void) {
  PriorityNode<T>* current  = root;
  PriorityNode<T>* prior    = NULL;
  while (current != NULL) {
    if (prior == NULL) {              // If current is the root node...
      if (current->next != NULL) {  // ...and there are at least two items in the queue...
        if (current->next->priority > current->priority) {  // ...and they are out of order...
          root = current->next;         // Swap them.
          current->next = root->next;
          root->next = current;
          
          current = root;               // Restart the test.
        }
      }
    }
    else {
      if (prior->priority < current->priority) {
        // We need to promote current to come before prior in the queue.
        // We won't bother juggling this here. Instead, we'll simply remove
        // current and re-insert it.
        prior->next = current->next;   // Effectively removes current.
        insert(current);
        
        // Restart the test.
        current = root;
      }
    }
    
    prior = current;
    current = current->next;
  }
}


template <class T> bool PriorityQueue<T>::incrementPriority(T test_data) {
  PriorityNode<T>* current = get_node_by_element(test_data);
  if (current != NULL) {
    current->priority++;
    enforce_priorities();
    return true;
  }
  return false;
}

template <class T> bool PriorityQueue<T>::decrementPriority(T test_data) {
  PriorityNode<T>* current = get_node_by_element(test_data);
  if (current != NULL) {
    current->priority--;
    enforce_priorities();
    return true;
  }
  return false;
}


template <class T> T PriorityQueue<T>::dequeue() {
  PriorityNode<T>* current = root;
  if (current != NULL) {
    // This is safe because we only store references. Not the actual data.
    T return_value = current->data;
    root = current->next;
    free(current);
    element_count--;
    return return_value;
  }
  return NULL;
}


template <class T> bool PriorityQueue<T>::remove(int pos) {
  int i = 0;
  PriorityNode<T>* prior   = NULL;
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (i == pos) {
      if (prior != NULL) {
        prior->next = current->next;
      }
      else {
        root = current->next;
      }
      if (current->data != NULL) {
        if (current->reap) {
          free(current->data);
        }
      }
      free(current);
      element_count--;
      return true;
    }
    i++;
    prior = current;
    current = current->next;
  }
  return false;
}


template <class T> T PriorityQueue<T>::get() {
  PriorityNode<T>* current = root;
  if (current != NULL) {
    return current->data;
  }
  return NULL;
}


template <class T> T PriorityQueue<T>::get(int pos) {
  int i = 0;
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (i == pos) {
      return current->data;
    }
    i++;
    current = current->next;
  }
  return NULL;
}


template <class T> bool PriorityQueue<T>::contains(T test_data) {
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (current->data == test_data) {
      return true;
    }
    current = current->next;
  }
  return false;
}


template <class T> int PriorityQueue<T>::getPosition(T test_data) {
  int i = 0;
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (current->data == test_data) {
      return i;
    }
    i++;
    current = current->next;
  }
  return -1;
}


template <class T> int PriorityQueue<T>::getPriority(T test_data) {
  PriorityNode<T>* current = root;
  while (current != NULL) {
    if (current->data == test_data) {
      return current->priority;
    }
    current = current->next;
  }
  return -1;
}


template <class T> bool PriorityQueue<T>::hasNext() {
  return (root != NULL);
}

#endif

Now we need a test driver of some sort.... This one just throws a bunch of doubles into the template (it was meant to take pointers to things). Doing so generates lots of warnings that we will ignore. The compiler thinks we might be making a mistake, but we're not.

#include "../DataStructures/PriorityQueue.h"
#include <stdlib.h>
#include <stdio.h>


int main(void) {
  PriorityQueue<double> mode_bins;
  double dubs[20] = {0.54, 0.10, 0.68, 0.54, 0.54, \
                     0.10, 0.17, 0.67, 0.54, 0.09, \
                     0.57, 0.15, 0.68, 0.54, 0.67, \
                     0.11, 0.10, 0.64, 0.54, 0.09};
   
    
  for (int i = 0; i < 20; i++) {
      if (mode_bins.contains(dubs[i])) {
        mode_bins.incrementPriority(dubs[i]);
      }
      else {
        mode_bins.insert(dubs[i], 1);
      }
  }
  
  double temp_double = 0;  
  double most_common = mode_bins.get();
  int stat_mode      = mode_bins.getPriority(most_common);
  printf("Most common:  %lf\n", most_common);
  printf("Mode:         %d\n\n",  stat_mode);
  
  // Now let's print a simple histogram...
  while (mode_bins.hasNext()) {
    temp_double = mode_bins.get();
    stat_mode = mode_bins.getPriority(temp_double);
    printf("%lf\t", temp_double);
    for (int n = 0; n < stat_mode; n++) {
      printf("*");
    }
    printf("  (%d)\n", stat_mode);
    mode_bins.dequeue();
  }
}

Code above should be compilable with....

gcc -o PriorityQueueTest PriorityQueueTest.cpp -lstdc++

And when run, should produce something like this....

joshl@JOSH-DEV ~/working-copies/tests $ ./PriorityQueueTest Most common:  0.540000
Mode:         6

0.540000        ******  (6)
0.100000        ***  (3)
0.680000        **  (2)
0.670000        **  (2)
0.090000        **  (2)
0.170000        *  (1)
0.570000        *  (1)
0.150000        *  (1)
0.110000        *  (1)
0.640000        *  (1)



Previous:
Next: