dlink.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph 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.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# 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() : prev(this), next(this) { /* empty */ }
  Dlink(const Dlink &) { reset(); } 

  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;
  }      
  void reset() 
  {

    I(this != NULL);

    next = prev = this; 
  }
  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;
      }

    Aleph::swap(prev->next, link->prev->next);
    Aleph::swap(next->prev, link->next->prev);
    Aleph::swap(prev, link->prev);
    Aleph::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 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 *& get_prev()
  {

    I((this != NULL) and (next != NULL) and (prev != NULL));

    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 del() 
  {

    I((this != NULL) and (next != NULL) and (prev != NULL));

    prev->next = next;
    next->prev = prev;
    reset();
  } 
  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;
  }
  int reverse_list() 
  {
    if (is_empty())
      return 0;

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

    int counter = 0; 

        // recorrer toda la lista this, eliminar primero e insertar en tmp_head
    while (not is_empty())
      {
        Dlink * current = remove_next(); // eliminar primero de la lista

        tmp_head.insert(current); // insertarlo de primero en tmp_head

        counter++;
      }  

        // tmp_head contiene la lista invertida y this está vacía ==> swap
    swap(&tmp_head);

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

    I(list->is_empty()); // list debe estar vacía

        // enlazar list a list
    list->prev = prev; // último nodo
    list->next = link; // primer nodo que es link

        // quitar de this todo lo que está a partir de link
    prev = link->prev; 
    link->prev->next = this;

    link->prev = list;
    list->prev->next = list;
  }
  class Iterator 
  {

  private:

    Dlink * head;
    Dlink * curr;

  public:

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

    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(const Iterator &  itor) : head(itor.head), curr(itor.curr)
    {
      // Empty
    }

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

    Iterator & operator = (const Iterator & itor)
    {

      if (this == &itor)
        return *this;

      head = itor.head;
      curr = itor.curr;

      return *this;
    }

    Iterator & operator = (Dlink * head_ptr)
    {
      head = head_ptr;
      curr = head->get_next();

      return *this;
    }

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

    Dlink * get_current() const
    {

      I(curr != NULL and head != NULL);

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

      return curr;
    }

    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() 
  {
    Dlink * node;
    Iterator itor(this);
    
        // recorrer y eliminar los nodos
    while (itor.has_current())
      {
        node = itor.get_current();
        itor.next();
        node->del();
        delete node;
      }
  }
  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); \
} 

}
# endif /* DLINK_H */ 

---