dlink.H

# ifndef DLINK_H
# define DLINK_H

# include <aleph.H>

using namespace Aleph;

namespace Aleph {

class Dlink 
{
protected: 

  mutable Dlink * prev; 
  mutable Dlink * next;

public:

  Dlink & swap(Dlink & l)
  {
    std::swap(prev, l.prev);
    std::swap(next, l.next);

    return *this;
  }
   
  Dlink() : prev(this), next(this) { /* empty */ }

  Dlink(const Dlink &) { reset(); } 

  Dlink(Dlink && l) : prev(this), next(this) 
  {
    swap(l);
  }

  Dlink & operator = (const Dlink & l) 
  {
    if (this == &l) 
      return *this;

    if (not is_empty())
      throw std::invalid_argument ("left list must be empty");

    reset();

    return *this;
  }   

  Dlink & operator = (Dlink && l) 
  {
    return swap(l);
  }

  void reset() 
  {
    I(this != NULL);
    next = prev = this; 
  }

  void init() 
  {
    reset();
  }

  void swap(Dlink * link) 
  {
    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);
  }

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

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

  bool is_unitarian_or_empty() const { return next == prev; }

  void insert(Dlink * node) 
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    I(node != NULL); 
    I(node->is_empty());

    node->prev = this;
    node->next = next;
    next->prev = node;
    next       = node;
  }

  void push(Dlink * node) 
  {
    insert(node);
  }

  void append(Dlink * node) 
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    I(node != NULL);
    I(node->is_empty());

    node->next = this;
    node->prev = prev;
    prev->next = node;
    prev       = node;
  }

  Dlink *& get_next()
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    return next; 
  }

  Dlink * top() { return get_next(); }

  Dlink *& get_prev()
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    return prev; 
  }

  Dlink *& get_first() { return next; }

  Dlink *& get_last() { return prev; } 

  void insert_list(Dlink * head)
  {
    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)
  {
    if (head->is_empty()) 
      return;

    head->next->prev = prev;
    head->prev->next = this;
    prev->next       = head->next;
    prev             = head->prev;
    head->reset();
  }

  void concat_list(Dlink * head) 
  { 
    I(head != NULL);

    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) 
  { 
    concat_list(&head);
  }

  void del() 
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));

    prev->next = next;
    next->prev = prev;
    reset();
  }

  void erase() { del(); }

  Dlink * remove_prev() 
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    I(prev != this); 
    I(next != this); 

    Dlink* retValue = prev;
    retValue->del();

    return retValue;
  }

  Dlink * remove_next() 
  {
    I((this != NULL) and (next != NULL) and (prev != NULL));
    I(prev != this); 
    I(next != this); 

    Dlink* retValue = next;
    retValue->del();

    return retValue;
  }

  Dlink * remove_last() 
  {
    return remove_prev();
  }

  Dlink * remove_first() 
  {
    return remove_next();
  }

  Dlink * pop() 
  {
    return remove_next();
  }

  size_t reverse_list() 
  {
    if (is_empty()) 
      return 0;

    Dlink tmp; // cabecera temporal donde se guarda lista invertida

      // recorrer lista this, eliminar primero e insertar en tmp
    size_t counter = 0; 
    for (/* nada */; not is_empty(); counter++)
      tmp.insert(remove_next()); // eliminar e insertar en tmp

    swap(&tmp); // tmp == lista invertida; this vacía ==> swap

    return counter;
  }

  size_t split_list(Dlink & l, Dlink & r) 
  {
    I(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;
  }

  Dlink cut_list(Dlink * link) 
  {
    I(not is_empty() and not link->is_empty() and link != this);

    Dlink list;
    if (link == this->prev) // es link el último de la lista?
      {
        link->del();
        list.append(link);
        return list;
      }

    if (link == this->next) // es link el primero de la lista
      {
        list.swap(this);
        I(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;
    mutable Dlink * curr;

  public:

    typedef Dlink Set_Type;

    typedef Dlink * Item_Type;

    Iterator(Dlink * head_ptr) : head(head_ptr), curr(head->get_next()) {}

    Iterator(Dlink & _head) : head(&_head), curr(head->get_next())
    {
      // Empty
    }

    Iterator(Dlink * head_ptr, Dlink * curr_ptr) 
      : head(head_ptr), curr(curr_ptr)
    {
      // Empty
    }

    Iterator() : head(NULL), curr(NULL) { /* Empty */ }

    void reset_first() 
    {
      I(curr != NULL and head != NULL);

      curr = head->get_next();
    }

    void reset_last() 
    {
      I(curr != NULL and head != NULL);
      curr = head->get_prev();
    }

    void set(Dlink * new_curr) 
    {
      I(curr != NULL and head != NULL);
      curr = new_curr;
    }

    void reset(Dlink * new_head, Dlink * new_curr)
    {
      head = new_head;
      curr = new_curr;
    }

    void reset(Dlink * new_head)
    {
      head = new_head;
      curr = head->get_next();;
    }

    bool has_current() const 
    {
      I(curr != NULL and head != NULL);
      return curr != head;
    }

       // sinónimo de has_current()
    bool has_curr() const { return has_current(); }

    Dlink * get_current() const
    {
      I(curr != NULL and head != NULL);

      if (not has_current())
        throw std::overflow_error("Not element in list");

      return curr;
    }

       // sinónimo de get_current()
    Dlink * get_curr() const { return get_current(); }

    bool is_in_first() const { return curr == head->next; }

    bool is_in_last() const { return curr == head->prev; }

    void prev() throw(std::exception, std::underflow_error)
    {
      if (not has_current())
        throw std::underflow_error("Not previous element in list");

      curr = curr->get_prev();
    }

    void next() throw(std::exception, std::overflow_error)
    {
      if (not has_current())
        throw std::overflow_error("Not next element in list");

      curr = curr->get_next();
    }

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

    bool operator != (const Iterator & it) const { return curr != it.curr; }
    
    Dlink * del() 
    {
      I(curr != NULL and head != NULL);
      I(has_current());

      Dlink * current = get_current(); // obtener nodo actual
      next(); // 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() 
  {
    for (Iterator itor(this); itor.has_current(); delete itor.del()) ;
  }

  bool check()
  {
    Iterator itor(this);
    Dlink* node;

    for (/* nothing */; itor.has_current(); itor.next())
      {
        node = itor.get_current();

        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_current(); itor.prev())
      {
        node = itor.get_current();

        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) \
{ \
  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) \
{ \
  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)                 \
  {                                                                     \
    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 */