dlink.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

# ifndef DLINK_H
# define DLINK_H

# include <aleph.H>

using namespace Aleph;

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> inline Dnode<T> * to_dnode() noexcept;
  template <typename T> inline const Dnode<T> * to_dnode() const noexcept;
  template <typename T> inline T& to_data() noexcept;
  template <typename T> inline 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();
  }

  bool is_empty() const noexcept { return this == next and this == prev; }

  bool is_unitarian() const noexcept { return this != next and next == prev; }

  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;
  }

  Dlink *& get_next() const noexcept
  {
    assert(next != nullptr and prev != nullptr);
    return next;
  }

  Dlink *& get_prev() const noexcept
  {
    assert(next != nullptr and prev != nullptr);
    return prev;
  }

  Dlink *& get_first_ne() const noexcept { return next; }

  Dlink *& get_last_ne() const noexcept { return prev; }

  Dlink *& get_first() const noexcept { return next; }

  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()
  {
    if (is_empty())
      throw std::underflow_error("Dlink as stack is not empty");
    return get_next();
  }

  Dlink * pop() 
  {
    if (is_empty())
      throw std::underflow_error("Dlink as stack is not 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);
    }

    bool has_curr() const noexcept
    {
      assert(curr != nullptr and head != nullptr);
      return curr != head;
    }

    bool is_last() const noexcept
    {
      return head->is_empty() ? false : curr == head->prev;
    }

    Dlink * get_curr_ne() const noexcept
    {
      assert(curr != nullptr and head != nullptr);
      return curr;
    }

    Dlink * get_curr() const
    {
      if (not has_curr())
        throw std::overflow_error("Not element in list");

      return get_curr_ne();
    }

    bool is_in_first() const noexcept
    {
      return head->is_empty() ? false : curr == head->next;
    }

    bool is_in_last() const noexcept { return is_last(); }

    void prev_ne() noexcept { curr = curr->get_prev(); }

    void prev()
    {
      if (not has_curr())
        throw std::underflow_error("Not previous element in list");
      prev_ne();
    }

    void next_ne() noexcept { curr = curr->get_next(); }

    void next()
    {
      if (not has_curr())
        throw std::overflow_error("Not next element in list");
      next_ne();
    }

    bool operator == (const Iterator & it) const noexcept
    { return curr == it.curr; }

    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_ne(); // obtener nodo actual
      next_ne(); // avanzar al siguiente nodo
      current->del(); // eliminar de la lista antiguo nodo actual
      return current;
    }

    bool verify(Dlink * l) const { return head == l; }

    bool verify(const Iterator & it) const { 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;
      else
        throw std::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;
      else
        throw std::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_ne();

        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 */