dlink.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 DLINK_H
# define DLINK_H
 
# include <aleph.H>
# include <ah-errors.H>
 
namespace Aleph {
 
  template <typename T> class Dnode; // Forward declaration of derived class
 
  class Dlink
  {
  protected:
 
    mutable Dlink * prev;
    mutable Dlink * next;
 
  public:
 
    template <typename T>
    Dnode<T> * to_dnode() noexcept;
    template <typename T>
    const Dnode<T> * to_dnode() const noexcept;
    template <typename T>
    T& to_data() noexcept;
    template <typename T>
    const T& to_data() const noexcept;
 
    Dlink() noexcept : prev(this), next(this) { assert(is_empty()); }
 
    Dlink(const Dlink & l) noexcept
      : prev(l.prev), next(l.next)
    {
      if (l.is_empty())
        reset();
    }
 
    void swap(Dlink * link) noexcept
    {
      if (is_empty() and link->is_empty())
        return;
 
      if (is_empty())
        {
          link->next->prev = this;
          link->prev->next = this;
          next = link->next;
          prev = link->prev;
          link->reset();
          return;
        }
 
      if (link->is_empty())
        {
          next->prev = link;
          prev->next = link;
          link->next = next;
          link->prev = prev;
          reset();
          return;
        }
 
      std::swap(prev->next, link->prev->next);
      std::swap(next->prev, link->next->prev);
      std::swap(prev, link->prev);
      std::swap(next, link->next);
    }
 
    void swap(Dlink & l) noexcept
    {
      swap(&l);
    }
 
    Dlink(Dlink && l) noexcept : Dlink()
    {
      swap(l);
    }
 
    Dlink & operator = (const Dlink & l) noexcept
    {
      if (l.is_empty())
        return *this;
 
      assert(is_empty());
      prev = l.prev;
      next = l.next;
      return *this;
    }
 
    Dlink & operator = (Dlink && l) noexcept
    {
      swap(l);
      return *this;
    }
 
    void reset() noexcept
    {
      next = prev = this;
    }
 
    void init() noexcept
    {
      reset();
    }
 
    [[nodiscard]] constexpr bool is_empty() const noexcept { return this == next and this == prev; }
 
    [[nodiscard]] constexpr bool is_unitarian() const noexcept { return this != next and next == prev; }
 
    [[nodiscard]] constexpr bool is_unitarian_or_empty() const noexcept { return next == prev; }
 
    void insert(Dlink * node) noexcept
    {
      assert(next != nullptr and prev != nullptr);
      assert(node != nullptr);
      assert(node->is_empty());
 
      node->prev = this;
      node->next = next;
      next->prev = node;
      next       = node;
    }
 
    void push(Dlink * node) noexcept
    {
      insert(node);
    }
 
    void append(Dlink * node) noexcept
    {
      assert(next != nullptr and prev != nullptr);
      assert(node != nullptr);
      assert(node->is_empty());
 
      node->next = this;
      node->prev = prev;
      prev->next = node;
      prev       = node;
    }
 
    [[nodiscard]] Dlink *& get_next() const noexcept
    {
      assert(next != nullptr and prev != nullptr);
      return next;
    }
 
    [[nodiscard]] Dlink *& get_prev() const noexcept
    {
      assert(next != nullptr and prev != nullptr);
      return prev;
    }
 
    [[nodiscard]] constexpr Dlink *& get_first_ne() const noexcept { return next; }
 
    [[nodiscard]] constexpr Dlink *& get_last_ne() const noexcept { return prev; }
 
    [[nodiscard]] constexpr Dlink *& get_first() const noexcept { return next; }
 
    [[nodiscard]] constexpr Dlink *& get_last() const noexcept { return prev; }
 
    void wrap_header(Dlink * l) noexcept
    {
      assert(is_empty());
      l->append(this);
    }
 
    void insert_list(Dlink * head) noexcept
    {
      if (head->is_empty())
        return;
 
      head->prev->next = next;
      head->next->prev = this;
      next->prev       = head->prev;
      next             = head->next;
      head->reset();
    }
 
    void append_list(Dlink * head) noexcept
    {
      if (head->is_empty())
        return;
 
      head->next->prev = prev;
      head->prev->next = this;
      prev->next       = head->next;
      prev             = head->prev;
      head->reset();
    }
 
    void splice(Dlink * l) noexcept
    {
      Dlink head;
      head.wrap_header(l);
      insert_list(&head);
      assert(head.is_empty());
    }
 
    void concat_list(Dlink * head) noexcept
    {
      assert(head != nullptr);
 
      if (head->is_empty())
        return;
 
      if (this->is_empty())
        {
          swap(head);
          return;
        }
 
      prev->next       = head->next;
      head->next->prev = prev;
      prev             = head->prev;
      head->prev->next = this;
      head->reset();
    }
 
    void concat_list(Dlink & head) noexcept
    {
      concat_list(&head);
    }
 
    Dlink * del() noexcept
    {
      assert(next != nullptr and prev != nullptr);
 
      prev->next = next;
      next->prev = prev;
      reset();
      return this;
    }
 
    void erase() noexcept { del(); }
 
    Dlink * remove_prev() noexcept
    {
      assert(not is_empty());
 
      Dlink* retValue = prev;
      retValue->del();
 
      return retValue;
    }
 
    Dlink * remove_next() noexcept
    {
      assert(not is_empty());
 
      Dlink* retValue = next;
      retValue->del();
 
      return retValue;
    }
 
    Dlink * remove_last_ne() noexcept
    {
      return remove_prev();
    }
 
    Dlink * remove_first_ne() noexcept
    {
      return remove_next();
    }
 
    Dlink * remove_last() noexcept
    {
      return remove_prev();
    }
 
    Dlink * remove_first() noexcept
    {
      return remove_next();
    }
 
    Dlink * top() const
    {
      ah_underflow_error_if(is_empty()) << "Dlink as stack is empty";
      return get_next();
    }
 
    Dlink * pop()
    {
      ah_underflow_error_if(is_empty()) << "Dlink as stack is empty";
      return remove_next();
    }
 
    size_t reverse_list() noexcept
    {
      if (is_empty())
        return 0;
 
      Dlink tmp;
      size_t counter = 0;
      for (; not is_empty(); counter++)
        tmp.insert(remove_next());
 
      swap(&tmp);
 
      return counter;
    }
 
    size_t reverse() noexcept { return reverse_list(); }
 
    size_t split_list_ne(Dlink & l, Dlink & r) noexcept
    {
      assert(l.is_empty() and r.is_empty()); // l y r deben estar vacías
 
      size_t count = 0;
      while (not is_empty())
        {
          l.append(remove_next()); ++count;
 
          if (is_empty())
            break;
 
          r.insert(remove_prev()); ++count;
        }
 
      return count;
    }
 
    size_t split_list(Dlink & l, Dlink & r) noexcept
    {
      return split_list_ne(l, r);
    }
 
    Dlink cut_list(Dlink * link) noexcept
    {
      assert(not is_empty() and not link->is_empty() and link != this);
 
      Dlink list;
      if (link == this->prev) // is link the last item?
        {
          link->del();
          list.append(link);
          return list;
        }
 
      if (link == this->next) // is link the first item?
        {
          list.swap(this);
          assert(this->is_empty());
          return list;
        }
 
      list.prev = this->prev;       // enlazar list a link (punto de corte)
      list.next = link;
      this->prev = link->prev;       // quitar de this todo a partir de link
      link->prev->next = this;
      link->prev = &list;       // colocar el corte en list
      list.prev->next = &list;
 
      return list;
    }
 
    class Iterator
    {
    private:
 
      mutable Dlink * head = nullptr;
      mutable Dlink * curr = nullptr;
 
    public:
 
      using Set_Type = Dlink;
 
      using Item_Type = Dlink *;
 
      Iterator(Dlink * head_ptr) noexcept
        : head(head_ptr), curr(head->get_next()) { /* */ }
 
      Iterator(const Dlink & list) noexcept
        : head(&const_cast<Dlink&>(list)), curr(head->get_next())
      {
        // Empty
      }
 
      void set(Dlink * new_curr) noexcept
      {
        assert(curr != nullptr and head != nullptr);
        curr = new_curr;
      }
 
      Iterator() noexcept : head(nullptr), curr(nullptr) { /* Empty */ }
 
      void reset_first() noexcept
      {
        assert(curr != nullptr and head != nullptr);
        curr = head->get_next();
      }
 
      void reset_last() noexcept
      {
        assert(curr != nullptr and head != nullptr);
        curr = head->get_prev();
      }
 
      void end() noexcept
      {
        put_itor_at_the_end(*this);
      }
 
      [[nodiscard]] bool has_curr() const noexcept
      {
        assert(curr != nullptr and head != nullptr);
        return curr != head;
      }
 
      [[nodiscard]] bool is_last() const noexcept
      {
        return head->is_empty() ? false : curr == head->prev;
      }
 
      [[nodiscard]] Dlink * get_curr_ne() const noexcept
      {
        assert(curr != nullptr and head != nullptr);
        return curr;
      }
 
      [[nodiscard]] Dlink * get_curr() const
      {
        ah_overflow_error_if(not has_curr()) << "Not element in list";
 
        return get_curr_ne();
      }
 
      [[nodiscard]] constexpr bool is_in_first() const noexcept
      {
        return head->is_empty() ? false : curr == head->next;
      }
 
      [[nodiscard]] bool is_in_last() const noexcept { return is_last(); }
 
      void prev_ne() noexcept { curr = curr->get_prev(); }
 
      void prev()
      {
        ah_underflow_error_if(not has_curr()) << "Not previous element in list";
        prev_ne();
      }
 
      void next_ne() noexcept { curr = curr->get_next(); }
 
      void next()
      {
        ah_overflow_error_if(not has_curr()) << "Not next element in list";
        next_ne();
      }
 
      [[nodiscard]] constexpr bool operator == (const Iterator & it) const noexcept
      { return curr == it.curr; }
 
      [[nodiscard]] constexpr bool operator != (const Iterator & it) const noexcept
      { return curr != it.curr; }
 
      Dlink * del()
      {
        assert(curr != nullptr and head != nullptr);
        assert(has_curr());
 
        Dlink * current = get_curr(); // obtener nodo actual
        next(); // avanzar al siguiente nodo
        current->del(); // eliminar de la lista antiguo nodo actual
        return current;
      }
 
      Dlink * del_ne() noexcept
      {
        assert(curr != nullptr and head != nullptr);
        assert(has_curr());
 
        Dlink * current = get_curr(); // obtener nodo actual
        next_ne(); // avanzar al siguiente nodo
        current->del(); // eliminar de la lista antiguo nodo actual
        return current;
      }
 
      [[nodiscard]] constexpr bool verify(Dlink * l) const noexcept { return head == l; }
 
      [[nodiscard]] constexpr bool verify(const Iterator & it) const noexcept { return head == it.head; }
    };
 
    void remove_all_and_delete() noexcept
    {
      while (not is_empty())
        delete remove_next();
    }
 
    void rotate_left(size_t n)
    {
      if (is_empty())
        {
          if (n == 0)
            return;
          ah_domain_error() << "List is empty";
        }
 
      for (size_t i = 0; i < n; ++i)
        append(remove_first());
    }
 
    void rotate_right(size_t n)
    {
      if (is_empty())
        {
          if (n == 0)
            return;
          ah_domain_error() << "List is empty";
        }
 
      for (size_t i = 0; i < n; ++i)
        insert(remove_last());
    }
 
    bool check()
    {
      Iterator itor(this);
      Dlink* node;
 
      for (/* nothing */; itor.has_curr(); itor.next_ne())
        {
          node = itor.get_curr();
 
          if (not (node->get_next()->get_prev() == node))
            return false;
 
          if (not (node->get_prev()->get_next() == node))
            return false;
        }
 
      for (itor.reset_last(); itor.has_curr(); itor.prev())
        {
          node = itor.get_curr();
 
          if (not (node->get_next()->get_prev() == node))
            return false;
 
          if (not (node->get_prev()->get_next() == node))
            return false;
        }
 
      return true;
    }
  };
 
# define DLINK_TO_TYPE(type_name, link_name)                            \
  inline static type_name * dlink_to_##type_name(Dlink * link) noexcept \
  {                                                                     \
    type_name * ptr_zero = 0;                                           \
    size_t offset_link = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
    char * address_type = reinterpret_cast<char*>(link) - offset_link;  \
    return reinterpret_cast<type_name *>(address_type);                 \
  }
 
# define LINKNAME_TO_TYPE(type_name, link_name)                         \
  inline static type_name * link_name##_to_##type_name(Dlink * link) noexcept \
  {                                                                     \
    type_name * ptr_zero = 0;                                           \
    size_t offset_link = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
    char * address_type = reinterpret_cast<char*>(link) - offset_link;  \
    return reinterpret_cast<type_name *>(address_type);                 \
  }
 
 
# define DLINK_TO_BASE(type_name, link_name)                            \
  inline static type_name * dlink_to_base(Dlink * link) noexcept        \
  {                                                                     \
    type_name * ptr_zero = 0;                                           \
    size_t offset_link = reinterpret_cast<size_t>(&(ptr_zero->link_name)); \
    char * address_type = reinterpret_cast<char*>(link) - offset_link;  \
    return reinterpret_cast<type_name *>(address_type);                 \
  }
 
}
 
# endif /* DLINK_H */