archeap.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  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.
*/
 
 
# ifndef ARCHEAP_H
# define ARCHEAP_H
 
# include <tpl_binHeap.H>
# include <tpl_fibonacci_heap.H>
# include <tpl_graph_utils.H>
 
template <class GT,
          class Distance,
          class Access_Heap_Node>
class ArcHeap
    : public BinHeap<typename GT::Arc *, Distance_Compare<GT, Distance>>
{
  Distance dist;
  Access_Heap_Node access_node;
  Distance_Compare<GT, Distance> dist_cmp;
 
public:
  Distance &get_distance() { return dist; }
 
  ArcHeap(Distance __dist = Distance(),
          Access_Heap_Node acc = Access_Heap_Node())
    : dist(__dist), access_node(acc), dist_cmp(dist)
  {
    // empty
  }
 
  ArcHeap(const ArcHeap &) = delete;
  ArcHeap & operator=(const ArcHeap &) = delete;
 
  ArcHeap(ArcHeap && other) noexcept
    : Heap(std::move(other)), dist(std::move(other.dist)),
      access_node(std::move(other.access_node)), dist_cmp(dist)
  {}
 
  ArcHeap & operator=(ArcHeap && other) noexcept
  {
    if (this != &other)
      {
        empty();
        Heap::operator=(std::move(other));
        dist = std::move(other.dist);
        access_node = std::move(other.access_node);
        dist_cmp = Distance_Compare<GT, Distance>(dist);
      }
    return *this;
  }
 
  typedef
  BinHeap<typename GT::Arc *, Distance_Compare<GT, Distance>> Heap;
 
  typedef typename Heap::Node Node;
 
  using handle_type = Node *;
 
  void put_arc(typename GT::Arc *arc, typename GT::Node *tgt)
  {
    auto & handle_storage = access_node(tgt);
    handle_type & heap_node =
      reinterpret_cast<handle_type &>(handle_storage);
 
    if (heap_node == nullptr) // Is there already an arc inserted into the heap?
      { // No ==> create a new heap node and assign the arc
        heap_node = new Node;
        heap_node->get_key() = arc;
        this->insert(heap_node);
 
        return;
      }
 
    // two arcs with the same target ==> keep the smaller; discard the larger
    typename GT::Arc *& arc_in_heap = heap_node->get_key();
 
    // Does arc_in_heap have a shorter distance than arc?
    if (dist_cmp(arc_in_heap, arc))
      return; // old arc remains in the heap; new one is ignored
 
    // arc_in_heap will be the newly inserted arc
    arc_in_heap = arc;
    this->update(heap_node);
  }
 
  typename GT::Arc * get_min_arc()
  {
    Node *heap_node = this->getMin();
    typename GT::Arc *arc = heap_node->get_key();
 
    // Select the node that the access functor maps to this heap node
    auto *p = static_cast<typename GT::Node *>(arc->src_node);
    auto & handle_src =
      reinterpret_cast<handle_type &>(access_node(p));
    if (handle_src != heap_node)
      p = static_cast<typename GT::Node *>(arc->tgt_node);
 
    auto & handle_ref =
      reinterpret_cast<handle_type &>(access_node(p));
    assert(handle_ref == heap_node);
 
    handle_ref = nullptr;
 
    delete heap_node;
 
    return arc;
  }
 
  void empty()
  {
    this->remove_all_and_delete();
  }
 
  void clear() { empty(); }
 
  ~ArcHeap()
  {
    empty();
  }
};
 
 
 
template <class GT,
          class Distance,
          class Access_Heap_Node>
class ArcFibonacciHeap
{
  using Compare = Distance_Compare<GT, Distance>;
  using Heap = Fibonacci_Heap<typename GT::Arc *, Compare>;
 
public:
  using handle_type = typename Heap::handle_type;
 
private:
  Distance dist;
  Access_Heap_Node access_node;
  Compare dist_cmp;
  Heap heap;
 
  handle_type & handle_ref(typename GT::Node *p)
  {
    return reinterpret_cast<handle_type &>(access_node(p));
  }
 
public:
  Distance &get_distance() { return dist; }
 
  ArcFibonacciHeap(Distance __dist = Distance(),
                   Access_Heap_Node acc = Access_Heap_Node())
    : dist(__dist), access_node(acc), dist_cmp(dist), heap(dist_cmp)
  {
    // empty
  }
 
  ArcFibonacciHeap(const ArcFibonacciHeap &) = delete;
  ArcFibonacciHeap & operator=(const ArcFibonacciHeap &) = delete;
 
  ArcFibonacciHeap(ArcFibonacciHeap && other) noexcept
    : dist(std::move(other.dist)), access_node(std::move(other.access_node)),
      dist_cmp(dist), heap(std::move(other.heap))
  {}
 
  ArcFibonacciHeap & operator=(ArcFibonacciHeap && other) noexcept
  {
    if (this != &other)
      {
        dist = std::move(other.dist);
        access_node = std::move(other.access_node);
        dist_cmp = Compare(dist);
        heap = std::move(other.heap);
      }
    return *this;
  }
 
  void put_arc(typename GT::Arc *arc, typename GT::Node *tgt)
  {
    auto & heap_node = handle_ref(tgt);
 
    if (heap_node == nullptr) // Is there already an arc inserted into the heap?
      { // No ==> create a new heap node and assign the arc
        heap_node = heap.insert(arc);
        return;
      }
 
    // two arcs with the same target ==> keep the smaller; discard the larger
    typename GT::Arc *arc_in_heap = heap_node->data;
 
    // Does arc_in_heap have a shorter distance than arc?
    if (dist_cmp(arc_in_heap, arc))
      return; // old arc remains in the heap; new one is ignored
 
    heap.decrease_key(heap_node, arc);
  }
 
  typename GT::Arc * get_min_arc()
  {
    ah_underflow_error_if(heap.is_empty()) << "ArcFibonacciHeap is empty";
 
    auto *heap_node = heap.get_min_node();
    auto *arc = heap_node->data;
 
    // Select the node that the access functor maps to this heap node
    auto *p = static_cast<typename GT::Node *>(arc->src_node);
    auto & handle_src = handle_ref(p);
    if (handle_src != heap_node)
      p = static_cast<typename GT::Node *>(arc->tgt_node);
 
    auto & handle_entry = handle_ref(p);
    assert(handle_entry == heap_node);
 
    handle_entry = nullptr;
 
    (void) heap.extract_min();
 
    return arc;
  }
 
  bool is_empty() const noexcept { return heap.is_empty(); }
 
  void empty()
  {
    heap.clear();
  }
 
  void clear() { empty(); }
 
  ~ArcFibonacciHeap()
  {
    empty();
  }
};
 
# endif // ARCHEAP_H