sortedPriorityQueue.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2026 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - the GNU Lesser General Public License as published by               *
 *      the Free Software Foundation, either version 3 of the License,      *
 *      or (at your option) any later version,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2026                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
 

 
#ifndef GUM_SORTED_PRIORITY_QUEUE_H
#define GUM_SORTED_PRIORITY_QUEUE_H
 
#include <cstddef>
#include <functional>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/priorityQueue.h>
#include <agrum/base/core/sharedAVLTree.h>
 
#include <initializer_list>
#include <type_traits>
 
namespace gum {
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  template < typename Val, typename Priority, typename Cmp >
  class SortedPriorityQueueIterator;
  template < typename Val, typename Priority, typename Cmp >
  class SortedPriorityQueueIteratorSafe;
 
  template < typename Val, typename Priority, typename Cmp >
  class SortedPriorityQueueReverseIterator;
  template < typename Val, typename Priority, typename Cmp >
  class SortedPriorityQueueReverseIteratorSafe;
 
  // we declare this class to enable getNodeFromExternalValue_ optimizations
  class GraphChange;
 
#endif   // DOXYGEN_SHOULD_SKIP_THIS

  template < typename Val, typename Priority = int, typename Cmp = std::less< Priority > >
  class SortedPriorityQueue {
    public:
    using value_type            = Val;
    using reference             = Val&;
    using const_reference       = const Val&;
    using pointer               = Val*;
    using const_pointer         = const Val*;
    using difference_type       = std::ptrdiff_t;
    using iterator              = SortedPriorityQueueIterator< Val, Priority, Cmp >;
    using iterator_safe         = SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >;
    using reverse_iterator      = SortedPriorityQueueReverseIterator< Val, Priority, Cmp >;
    using reverse_iterator_safe = SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >;
 
 
    // ============================================================================
    // ============================================================================

    explicit SortedPriorityQueue(Cmp  compare  = Cmp(),
                                 Size capacity = GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY);

    explicit SortedPriorityQueue(std::initializer_list< std::pair< Val, Priority > > list);

    SortedPriorityQueue(const SortedPriorityQueue< Val, Priority, Cmp >& from);

    SortedPriorityQueue(SortedPriorityQueue< Val, Priority, Cmp >&& from) noexcept;

    ~SortedPriorityQueue();

 
    public:
    // ============================================================================
    // ============================================================================

    SortedPriorityQueue< Val, Priority, Cmp >&
        operator=(const SortedPriorityQueue< Val, Priority, Cmp >& from);

    SortedPriorityQueue< Val, Priority, Cmp >&
        operator=(SortedPriorityQueue< Val, Priority, Cmp >&& from) noexcept;

    const_reference operator[](const Val& val) const;

 
    // ============================================================================
    // ============================================================================

    Size size() const noexcept;

    bool empty() const noexcept;

    bool contains(const Val& val) const noexcept;

    [[nodiscard]] optional_ref< const value_type > tryGet(const Val& key) const;


    const Val& top() const;


    const Val& bottom() const;

    const Priority& topPriority() const;

    const Priority& bottomPriority() const;

    value_type pop();

    value_type popTop();

    value_type popBottom();

    const_reference insert(const Val& val, const Priority& priority);

    const_reference insert(Val&& val, Priority&& priority);

    template < typename... Args >
    const_reference emplace(Args&&... args);

    void eraseTop();

    void eraseBottom();

    void erase(const Val& val, bool internal_val = false);

    void setPriority(const Val& elt, const Priority& new_priority, bool internal_val = false);

    void setPriority(const Val& elt, Priority&& new_priority, bool internal_val = false);

    const Priority& priority(const Val& elt, bool internal_val = false) const;

    void clear();

    std::string toString() const;

 
    // ============================================================================
    // ============================================================================

    iterator begin() const;

    constexpr const iterator& end() const;

    reverse_iterator rbegin() const;

    constexpr const reverse_iterator& rend() const;

    iterator_safe beginSafe();

    constexpr const iterator_safe& endSafe() const;

    reverse_iterator_safe rbeginSafe();

    constexpr const reverse_iterator_safe& rendSafe() const;

 
    // ============================================================================
    // ============================================================================

    Size capacity() const noexcept;

    void resize(Size new_size);

 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    using AVLNode = AVLTreeNode< Val >;

    using HashElt = typename std::pair< const AVLTreeNode< Val >, Priority >;

    struct TreeCmp {
      TreeCmp() = default;
 
      TreeCmp(const Cmp& cmp);
 
      TreeCmp(Cmp&& cmp);
 
      // get the priority associated with a given AVLTreeNode value. It turns out
      // that the elements stored into the HashTable are of type HashElt defined
      // above. Now, the constexpr offset defined below contains precisely the
      // offset in bytes between Value v and its priority. Function getPriority
      // therefore just computes the location of the priority and returns it.
      const Priority& getPriority(const Val& v) const;
 
      // from a Val instance stored into memory, get the address of the start of
      // the AVLNode structure that would have contained it. This is useful for
      // comparing elements in the hashTable without having to create dummy AVLNodes
      AVLTreeNode< Val >* getNode(const Val& v) const;
 
      // the comparison function between two contents of two nodes of the AVL tree:
      // the nodes should be sorted according to their priority
      bool operator()(const Val& x, const Val& y) const;
 
      Cmp _cmp_;
 
      // compute the offset in bytes between the location of Val and Priority in
      // the elements stored into the hash table
      static constexpr std::size_t offset_to_priority = offsetof(HashElt, second);
      static constexpr std::size_t offset_to_value    = offsetof(AVLTreeNode< Val >, value);
      static constexpr std::size_t offset_from_value_to_priority
          = offset_to_priority - offset_to_value;
    };
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
    private:
    SharedAVLTree< Val, TreeCmp > _tree_;

    HashTable< AVLTreeNode< Val >, Priority > _nodes_{HashTableConst::default_size, true, true};

    TreeCmp _tree_cmp_;

    AVLNode& getNodeFromInternalValue_(const Val& val) const;

    AVLNode& getNodeFromExternalValue_(const Val& val) const;

    optional_ref< AVLNode > tryGetNodeFromExternalValue_(const Val& val) const;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // the TreeCmp getnode function induces some warning on some compilers when Val
    // is a string because some optimizations are made by the compiler in this case.
    // to avoid this, the getNode_ function above executes different codes depending
    // on whether Val is different from a string or not. The structs below allow
    // to make this discrimination at compile time.
    template < typename T >
    struct is_basic_string: std::false_type {};
 
    template < typename T1, typename T2, typename T3 >
    struct is_basic_string< std::basic_string< T1, T2, T3 > >: std::true_type {};
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    friend iterator;
    friend reverse_iterator;
    friend iterator_safe;
    friend reverse_iterator_safe;
  };

  template < typename Val, typename Priority = int, typename Cmp = std::less< Priority > >
  class SortedPriorityQueueIterator:
      protected SharedAVLTreeReverseIterator<
          Val,
          typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using TreeCmp           = typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp;
 
 
    // ============================================================================
    // ============================================================================

    explicit SortedPriorityQueueIterator(const SortedPriorityQueue< Val, Priority, Cmp >& queue,
                                         const bool begin = true) noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static end iterator
    // only sortedPriorityQueue.cpp should use this constructor
    explicit consteval SortedPriorityQueueIterator(StaticInitializer init) noexcept :
        SharedAVLTreeReverseIterator< Val, TreeCmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    SortedPriorityQueueIterator(
        const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) noexcept;

    SortedPriorityQueueIterator(SortedPriorityQueueIterator< Val, Priority, Cmp >&& from) noexcept;

    ~SortedPriorityQueueIterator() noexcept;

 
 
    // ============================================================================
    // ============================================================================

    SortedPriorityQueueIterator< Val, Priority, Cmp >&
        operator=(const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) noexcept;

    SortedPriorityQueueIterator< Val, Priority, Cmp >&
        operator=(SortedPriorityQueueIterator< Val, Priority, Cmp >&& from) noexcept;

    bool operator==(const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) const;

    bool operator!=(const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) const;


    SortedPriorityQueueIterator< Val, Priority, Cmp >& operator++() noexcept;


    SortedPriorityQueueIterator< Val, Priority, Cmp >& operator+=(const Size k) noexcept;


    SortedPriorityQueueIterator< Val, Priority, Cmp >& operator--() noexcept;


    SortedPriorityQueueIterator< Val, Priority, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;

 
    // ============================================================================
    // ============================================================================


    [[nodiscard]] const_reference value() const;


    [[nodiscard]] const Priority& priority() const;


    friend SortedPriorityQueue< Val, Priority, Cmp >;
 
    using TreeIterator = SharedAVLTreeReverseIterator<
        Val,
        typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp >;
  };

  template < typename Val, typename Priority = int, typename Cmp = std::less< Val > >
  class SortedPriorityQueueIteratorSafe:
      protected SharedAVLTreeReverseIteratorSafe<
          Val,
          typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using TreeCmp           = typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp;
 
 
    // ============================================================================
    // ============================================================================

    explicit SortedPriorityQueueIteratorSafe(SortedPriorityQueue< Val, Priority, Cmp >& queue,
                                             const bool rbegin = true);
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static endSafe iterator
    // only sortedPriorityQueue.cpp should use this constructor
    explicit consteval SortedPriorityQueueIteratorSafe(StaticInitializer init) noexcept :
        SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    SortedPriorityQueueIteratorSafe(
        const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from);

    SortedPriorityQueueIteratorSafe(SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&& from);

    ~SortedPriorityQueueIteratorSafe() noexcept;

 
    // ============================================================================
    // ============================================================================

    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
        operator=(const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from);

    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
        operator=(SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&& from);

    bool operator==(const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) const;

    bool operator!=(const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) const;


    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& operator++() noexcept;


    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& operator+=(const Size k) noexcept;


    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& operator--() noexcept;


    SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;

 
    // ============================================================================
    // ============================================================================


    [[nodiscard]] const_reference value() const;


    [[nodiscard]] const Priority& priority() const;

 
    protected:
    friend SortedPriorityQueue< Val, Cmp >;
 
    using TreeIterator = SharedAVLTreeReverseIteratorSafe<
        Val,
        typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp >;
  };

  template < typename Val, typename Priority = int, typename Cmp = std::less< Val > >
  class SortedPriorityQueueReverseIterator:
      protected SharedAVLTreeIterator<
          Val,
          typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using TreeCmp           = typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp;
 
 
    // ============================================================================
    // ============================================================================

    explicit SortedPriorityQueueReverseIterator(
        const SortedPriorityQueue< Val, Priority, Cmp >& queue,
        const bool                                       rbegin = true) noexcept;
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static rend iterator
    // only sortedPriorityQueue.cpp should use this constructor
    explicit consteval SortedPriorityQueueReverseIterator(StaticInitializer init) noexcept :
        SharedAVLTreeIterator< Val, TreeCmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    SortedPriorityQueueReverseIterator(
        const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) noexcept;

    SortedPriorityQueueReverseIterator(
        SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&& from) noexcept;

    ~SortedPriorityQueueReverseIterator() noexcept;

 
    // ============================================================================
    // ============================================================================

    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
        operator=(const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) noexcept;

    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
        operator=(SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&& from) noexcept;

    bool operator==(const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) const;

    bool operator!=(const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) const;


    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& operator++() noexcept;


    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& operator+=(const Size k) noexcept;


    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& operator--() noexcept;


    SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;

 
    // ============================================================================
    // ============================================================================


    [[nodiscard]] const_reference value() const;


    [[nodiscard]] const Priority& priority() const;

 
    protected:
    friend SortedPriorityQueue< Val, Priority, Cmp >;
 
    using TreeIterator
        = SharedAVLTreeIterator< Val, typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp >;
  };

  template < typename Val, typename Priority = int, typename Cmp = std::less< Val > >
  class SortedPriorityQueueReverseIteratorSafe:
      protected SharedAVLTreeIteratorSafe<
          Val,
          typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp > {
    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = Val;
    using reference         = value_type&;
    using const_reference   = const value_type&;
    using pointer           = value_type*;
    using const_pointer     = const value_type*;
    using TreeCmp           = typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp;
 
 
    // ============================================================================
    // ============================================================================

    explicit SortedPriorityQueueReverseIteratorSafe(
        SortedPriorityQueue< Val, Priority, Cmp >& queue,
        const bool                                 rbegin = true);
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // constructor for the static rendSafe iterator
    // only sortedPriorityQueue.cpp should use this constructor
    explicit consteval SortedPriorityQueueReverseIteratorSafe(StaticInitializer init) noexcept :
        SharedAVLTreeIteratorSafe< Val, TreeCmp >(init) {}
#endif   // DOXYGEN_SHOULD_SKIP_THIS

    SortedPriorityQueueReverseIteratorSafe(
        const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from);

    SortedPriorityQueueReverseIteratorSafe(
        SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&& from);

    ~SortedPriorityQueueReverseIteratorSafe() noexcept;

 
    // ============================================================================
    // ============================================================================

    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
        operator=(const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from);

    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
        operator=(SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&& from);

    bool operator==(const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) const;

    bool operator!=(const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) const;


    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& operator++() noexcept;


    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& operator+=(const Size k) noexcept;


    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& operator--() noexcept;


    SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& operator-=(const Size k) noexcept;

    const_reference operator*() const;

    const_pointer operator->() const;

 
    // ============================================================================
    // ============================================================================


    [[nodiscard]] const_reference value() const;


    [[nodiscard]] const Priority& priority() const;

 
    protected:
    friend AVLTree< Val, Cmp >;
    friend SortedPriorityQueue< Val, Cmp >;
 
    using TreeIterator
        = SharedAVLTreeIteratorSafe< Val,
                                     typename SortedPriorityQueue< Val, Priority, Cmp >::TreeCmp >;
  };

  template < typename Val, typename Priority, typename Cmp >
  std::ostream& operator<<(std::ostream&                                    stream,
                           const SortedPriorityQueue< Val, Priority, Cmp >& queue);
 
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // _static_SortedPriorityQueue_end_ is a 'constant' iterator initialized at
  // compile time that represents the end iterators for all the sorted priority
  // queues (whatever their type). This global variable avoids creating the same
  // iterators within every sorted priority queue instance (this would be quite
  // inefficient as end is precisely identical for all these queues). The same hold
  // for reverse and safe end iterators.
  // The type of _SortedPriorityQueue_end_ is a pointer to void because C++ allows
  // pointers to void to be cast into pointers to other types (and conversely).
  // This avoids the painful strict-aliasing rule warning
  extern const SortedPriorityQueueIterator< int, std::less< int > >
      _static_SortedPriorityQueue_end_;
  extern const SortedPriorityQueueReverseIterator< int, std::less< int > >
      _static_SortedPriorityQueue_rend_;
  extern const SortedPriorityQueueIteratorSafe< int, std::less< int > >
      _static_SortedPriorityQueue_end_safe_;
  extern const SortedPriorityQueueReverseIteratorSafe< int, std::less< int > >
      _static_SortedPriorityQueue_rend_safe_;
 
  inline constexpr void* const _SortedPriorityQueue_end_
      = (void* const)&_static_SortedPriorityQueue_end_;
  inline constexpr void* const _SortedPriorityQueue_rend_
      = (void* const)&_static_SortedPriorityQueue_rend_;
  inline constexpr void* const _SortedPriorityQueue_end_safe_
      = (void* const)&_static_SortedPriorityQueue_end_safe_;
  inline constexpr void* const _SortedPriorityQueue_rend_safe_
      = (void* const)&_static_SortedPriorityQueue_rend_safe_;
#endif   // DOXYGEN_SHOULD_SKIP_THIS
 
} /* namespace gum */
 
// always include the implementation of the templates
#include <agrum/base/core/sortedPriorityQueue_tpl.h>
 
#endif /* GUM_SORTED_PRIORITY_QUEUE_H */