PriorityQueue.h

Go to the documentation of this file.

/*
 * Deskflow -- mouse and keyboard sharing utility
 * SPDX-FileCopyrightText: (C) 2012 - 2016 Symless Ltd.
 * SPDX-FileCopyrightText: (C) 2003 Chris Schoeneman
 * SPDX-License-Identifier: GPL-2.0-only WITH LicenseRef-OpenSSL-Exception
 */
 
#pragma once
 
#include <algorithm>
#include <vector>


template <
    class T, class Container = std::vector<T>,
#if defined(_MSC_VER)
    class Compare = std::greater<Container::value_type>>
#else
    class Compare = std::greater<typename Container::value_type>>
#endif
class PriorityQueue
{
public:
  using value_type = Container::value_type;
  using size_type = Container::size_type;
  using iterator = Container::iterator;
  using const_iterator = Container::const_iterator;
  using container_type = Container;
 
  PriorityQueue() = default;
  explicit PriorityQueue(Container &swappedIn)
  {
    swap(swappedIn);
  }
  ~PriorityQueue() = default;



  void push(const value_type &v)
  {
    c.push_back(v);
    std::push_heap(c.begin(), c.end(), comp);
  }

  void pop()
  {
    std::pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
  }

  void erase(iterator i)
  {
    c.erase(i);
    std::make_heap(c.begin(), c.end(), comp);
  }

  iterator begin()
  {
    return c.begin();
  }

  iterator end()
  {
    return c.end();
  }

  void swap(PriorityQueue<T, Container, Compare> &q) noexcept
  {
    c.swap(q.c);
  }

  void swap(Container &c2) noexcept
  {
    c.swap(c2);
    std::make_heap(c.begin(), c.end(), comp);
  }



  bool empty() const
  {
    return c.empty();
  }

  size_type size() const
  {
    return c.size();
  }

  const value_type &top() const
  {
    return c.front();
  }

  const_iterator begin() const
  {
    return c.begin();
  }

  const_iterator end() const
  {
    return c.end();
  }

 
private:
  Container c;
  Compare comp;
};