priority_queue.hpp

Go to the documentation of this file.

/******************************************************************************
 * # License
 * <b>Copyright 2021 Silicon Laboratories Inc. www.silabs.com</b>
 ******************************************************************************
 * The licensor of this software is Silicon Laboratories Inc. Your use of this
 * software is governed by the terms of Silicon Labs Master Software License
 * Agreement (MSLA) available at
 * www.silabs.com/about-us/legal/master-software-license-agreement. This
 * software is distributed to you in Source Code format and is governed by the
 * sections of the MSLA applicable to Source Code.
 *
 *****************************************************************************/
#ifndef PRIORITY_QUEUE_HPP
#define PRIORITY_QUEUE_HPP
 
// disable out of bound subscript warning. on every index there should be a test
// for out of bounds
#pragma GCC diagnostic ignored "-Warray-bounds"
 
#include <type_traits>
#include <functional>
#include <algorithm>
#include <cassert>
 
#include "sl_log.h"
 
template<class T, int Size, class KeyGreater = std::greater<T>>
class priority_queue
{
  public:
  using value_type     = typename std::decay<T>::type;
  using iterator       = value_type *;
  using const_iterator = const value_type *;
  using size_type      = int;
 
  constexpr priority_queue() = default;
 
  bool insert(value_type &&item) noexcept
  {
    // since we have a fixed memory size on the buffer. we cannot exceed `Size`
    // panic if we do.
    if (size() >= max_size()) {
      sl_log_error("priority_queue",
                   "Cannot insert a new item since the "
                   "max capacity of %d is reached!",
                   max_size());
      return false;
    }
 
    // if there is only one item in the queue, we dont have to `heapify`
    // anything.
    if (size() == 0) {
      init_iterators();
      *last = item;
      return true;
    }
 
    // assign item to the next slot. first increase `last` then assign.
    *(++last) = item;
 
    // validate the binary heap by moving up the tree. stop when there is a
    // parent which has not a higher priority.
    size_type current = size() - 1;
    size_type parent  = parent_index(current);
 
    KeyGreater greater;
    while (current != 0 && greater(elements[current], elements[parent])) {
      std::iter_swap(elements + parent, elements + current);
      current = parent;
      parent  = parent_index(current);
    }
    return true;
  }
 
  value_type pop_front() noexcept
  {
    assert(!empty());
 
    // erase returns the iterator following the erased iterator. if that element
    // is the last in the queue, it will point to `nullptr`. since we know that
    // the value is still at spot `elements[0]` return it!.
    if (const auto it = erase(begin()); it == nullptr) {
      return *elements;
    }
 
    // The first element was swapped to the last postition. Even though from
    // outside of this class, reading `end()` is invalid. we know for sure it
    // contains the previous element. we can safely create a copy of it here.
    return *end();
  }
 
  iterator erase(const_iterator iterator)
  {
    assert(!empty());
    if (size() > 1) {
      std::iter_swap(const_cast<T *>(iterator), last--);
 
      size_type current = iterator - begin();
      size_type child   = biggest_child(current);
 
      while (child < size()
             && KeyGreater()(elements[child], elements[current])) {
        std::iter_swap(elements + current, elements + child);
        current = child;
        child   = biggest_child(current);
      }
    } else {
      clear();
      // if there is no item anymore in the queue, begin and end point to
      // nullptr.
      return end();
    }
 
    // we need to return the next iterator here. because we deleted the current
    // iterator in the tree, the next node collapsed onto the same spot.
    // therefore return the same iterator again.
    return const_cast<priority_queue::iterator>(iterator);
  }
 
  constexpr size_type size() const noexcept
  {
    return end() - begin();
  }
 
  constexpr size_type max_size() const noexcept
  {
    return Size;
  }
 
  constexpr bool empty() const noexcept
  {
    return last == nullptr;
  }
 
  constexpr iterator begin() noexcept
  {
    return first;
  }
 
  constexpr iterator end() noexcept
  {
    if (!last) {
      return last;
    }
    return last + 1;
  }
 
  constexpr const_iterator begin() const noexcept
  {
    return first;
  }
 
  constexpr const_iterator end() const noexcept
  {
    if (!last) {
      return last;
    }
 
    return last + 1;
  }
 
  constexpr void clear() noexcept
  {
    first = nullptr;
    last  = nullptr;
  }
 
  private:
  constexpr size_type parent_index(size_type i) const
  {
    return (i - 1) / 2;
  }
 
  constexpr size_type left_index(size_type i) const
  {
    return 2 * i + 1;
  }
 
  constexpr size_type right_index(size_type i) const
  {
    return 2 * i + 2;
  }
 
  inline constexpr size_type biggest_child(size_type current) const
  {
    size_type left  = left_index(current);
    size_type right = right_index(current);
 
    if (right < size() && KeyGreater()(elements[right], elements[left])) {
      return right;
    }
    return left;
  }
 
  inline void init_iterators()
  {
    first = elements;
    last  = elements;
  }
 
  value_type elements[Size];
  iterator last  = nullptr;
  iterator first = nullptr;
};
 
#endif  // PRIORITY_QUEUE_HPP