htlist.H

# ifndef HTLIST_H
# define HTLIST_H

# include <stdexcept>
# include <utility>
# include <initializer_list>
# include <ahFunction.H>
# include <ahFunctional.H>
# include <ahDry.H>

# include <nana.h>

# define NEXT(p) (p->get_next())

namespace Aleph {

class Slinknc
{
  Slinknc * next;

public:

  Slinknc() : next(NULL) { /* empty */ }

  Slinknc(const Slinknc &) : next(NULL) { /* empty */ }

  void reset()
  {
    I(this not_eq NULL);
    next = NULL;
  }
  
  bool is_empty() const
  {
    I(this != NULL);
    return next == NULL;
  }

  Slinknc & operator = (const Slinknc & link)
  {
    if (&link == this)
      return *this;
    
    if (not is_empty())
      throw std::invalid_argument("link is not empty");

    next = NULL; 

    return *this;
  }

  Slinknc *& get_next()
  {
    I(this not_eq NULL);
    return next;
  }

  void insert(Slinknc * p)
  {
    I(this not_eq NULL);
    I(p not_eq NULL);
    I(p->is_empty());
    p->next = next;
    next = p;
  }

  Slinknc * remove_next()
  {
    I(this not_eq NULL);
    Slinknc * ret_val = next;
    next = ret_val->next;
    ret_val->reset();
    return ret_val;
  }

  class Iterator
  {
    Slinknc * head;
    Slinknc * curr;

  public:

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

    Iterator(Slinknc & list)
      : head(&list), curr(head)
    {
      // Empty
    }

    Iterator(Slinknc * _head, Slinknc * _curr)
      : head(_head), curr(_curr)
    {
      // Empty
    }

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

    bool has_curr() const
    {
      return has_current();
    }

    Slinknc * get_current() const
    {
      if (not has_current())
        throw std::overflow_error("Iterator is at the end of the list");
      return curr;
    }

    Slinknc * get_curr() const
    {
      return get_current();
    }

    void next()
    {
      if (not has_current())
        throw std::overflow_error("Iterator is at the end of the list");
      curr = curr->next;
    }

    void reset_first()
    {
      curr = head;
    }
  };    
};


    template <typename T>
class Snodenc : public Slinknc
{
  T data;

public:

  T & get_data() { return data; }

  Snodenc() { /* empty*/ }

  Snodenc(const T & item) : data(item) 
  {
    // empty
  }

  Snodenc(T && item)
  {
    std::swap(data, item);
  }

  Snodenc * remove_next() { return (Snodenc*) Slinknc::remove_next(); }

  Snodenc *& get_next() { return (Snodenc*&) Slinknc::get_next(); }

  Snodenc * remove_first() { return Snodenc::remove_next(); }

  Snodenc *& get_first() const { return Snodenc::get_next(); }
};


class HTList
{
  Slinknc * head;
  Slinknc * tail;

public:

  HTList() : head(NULL), tail(NULL) { /* empty */ }

  HTList(Slinknc * l) : head(l), tail(l) { /* empty */ }

  bool is_empty() const { return head == NULL; }

  bool is_unitarian() const { return head != NULL and head == tail; }

  bool is_unitarian_or_empty() const { return head == tail; }

  Slinknc * get_head() { return head; }

  Slinknc * get_tail() { return tail; }

  Slinknc * get_first() { return get_head(); }

  Slinknc * get_last() { return get_tail(); }

  HTList & swap(HTList & l)
  {
    std::swap(head, l.head);
    std::swap(tail, l.tail);
    return *this;
  }

  void insert(Slinknc * link)
  {
    I(NEXT(link) == NULL);

    if (head == NULL)
      {
        I(tail == NULL);
        head = tail = link;
        return;
      }
    
    NEXT(link) = head;
    head = link;
  }

  void push(Slinknc * link) { insert(link); }

  void append(Slinknc * link)
  {
    I(link != NULL and NEXT(link) == NULL);

    if (head == NULL)
      {
        I(tail == NULL);
        head = tail = link;
        return;
      }

    NEXT(tail) = link;
    tail = link;
  }

  void append(HTList & l)
  {
    if (l.is_empty())
      return;

    if (this->is_empty())
      {
        this->swap(l);
        return;
      }
    
    NEXT(tail) = l.head;
    tail = l.tail;
    l.head = l.tail = NULL;
  }

  void put(Slinknc * link) { append(link); }

  void concat(HTList & l) { append(l); }

  void concat_list(HTList & l) { append(l); }

  void insert(HTList & l)
  {
    l.append(*this);
    this->swap(l);
  }

  void insert(Slinknc * link, HTList & list)
  {
    NEXT(link) = list.head;
    tail = list.tail;
    list.head = list.tail = NULL;
  }

  Slinknc * remove_head()
  {
    if (is_empty())
      throw std::underflow_error("HTList is empty");

    Slinknc * ret_val = head;
    if (head == tail)
      head = tail = NULL;
    else
      {
        head = NEXT(head);
        if (head == NULL)
          tail = NULL;
      }

    ret_val->reset();

    return ret_val;
  }
  
  Slinknc * remove_first() { return remove_head(); }

  bool remove(Slinknc * link)
  {
    if (is_empty())
      throw std::domain_error("Removing from a empty list");

    if (link == head)
      {
        head = NEXT(head);
        link->reset();
        return true;
      }

    for (Slinknc * prev = head, * p = NEXT(head); p != NULL; 
         prev = p, p = NEXT(p))
      if (p == link)
        {
          NEXT(prev) = NEXT(p);
          if (link == tail)
            tail = prev;
          link->reset();
          return true;  
        }

    return false;
  }

  Slinknc * pop() { return remove_head(); }

  size_t split_list(HTList & l, HTList & r)
  {
    I(l.is_empty() and r.is_empty()); // l y r deben estar vacías

    if (is_empty())
      return 0;

    if (is_unitarian())
      {
        swap(l);
        return 1;
      }

    size_t count = 0;
    Slinknc * p = head;
    Slinknc * q = head;
    while (true)
      {
        q = NEXT(q); ++count;

        if (q == tail or q == NULL)
          break;

        p = NEXT(p); 
        q = NEXT(q); ++count;
        if (q == tail or q == NULL)
          break;
      }

    l.head = head;
    l.tail = p;

    r.head = NEXT(p);
    r.tail = tail;

    head = tail = NULL;

    return count;
  }

  size_t split(HTList & l, HTList & r)
  {
    return split_list(l, r);
  }

  size_t reverse()
  {
    HTList tmp;

    size_t count = 0;
    while (not is_empty())
      {
        tmp.insert(remove_first());
        ++count;
      }

    swap(tmp);

    return count;
  }

  size_t reverse_list()
  {
    return reverse();
  }
  
  void cut(Slinknc * link, HTList & list)
  {
    I(list.is_empty());

    list.head = NEXT(link);
    list.tail = tail;

    tail = link;
    NEXT(link) = NULL;
  }

  void cut_list(Slinknc * link, HTList & list) { cut(link, list); }

  void remove_all_and_delete() 
  {
    while (not is_empty())
      delete remove_head();
  }

  class Iterator
  {
    HTList * lptr;
    Slinknc * curr;
    Slinknc * prev;
 
  public:

    Iterator(const Iterator & it) 
      : lptr(it.lptr), curr(it.curr), prev(it.prev) { /* empty */ }
    
    Iterator() : lptr(NULL), curr(NULL), prev(NULL) { /* empty */ }

    Iterator(const HTList & list) 
      : lptr(& (HTList&) list), curr(lptr->head), prev(curr)
    { /* empty */ }

    void reset() 
    {
      prev = curr = lptr->head;
    }

    void reset_first() { reset(); }

    Iterator & operator = (const Iterator & it)
    {
      lptr = it.lptr;
      curr = it.curr;
      prev = it.prev;
      return *this;
    }

    bool has_curr() const { return curr != NULL; }

    bool has_current() const { return has_curr(); }

    Slinknc * get_curr() const
    {
      if (curr == NULL)
        throw std::overflow_error("Iterator overflow");

      return curr;
    }

    Slinknc * get_current() const { return get_curr(); }

    void next() 
    {
      if (curr == lptr->head)
        {
          I(prev == lptr->head);
          curr = NEXT(curr);
        }
      else if (curr == lptr->tail)
        {
          I(NEXT(prev) == curr);
          curr = NULL;
        }
      else
        {
          I(NEXT(prev) == curr);
          prev = curr;
          curr = NEXT(curr);
          I(NEXT(prev) == curr);
        }
    }

    Slinknc * del()
    {
      if (not has_curr())
        throw std::overflow_error("Iterator overflow");

      Slinknc * ret_val = NULL;
      if (curr == lptr->head) // first item removal
        {
          ret_val = lptr->remove_first();
          prev = curr = lptr->head;
        }
      else if (curr == lptr->tail) // last item removal
        {
          I(NEXT(prev) == curr);
          ret_val = curr;
          NEXT(prev) = NEXT(curr);
          lptr->tail = prev;
          curr = NULL; // put in overflow
        }
      else
        {
          I(NEXT(prev) == curr);
          ret_val = curr;
          NEXT(prev) = NEXT(curr);
          curr = NEXT(curr);
        }
      
      ret_val->reset();
      return ret_val;
    }
  };

  void insert(const Iterator & it, HTList & list) 
  { 
    insert(it.get_curr(), list);
  }

  void cut_list(const Iterator & it, HTList & list) 
  {
    cut(it.get_curr(), list); 
  }

  size_t size() const
  {
    size_t count = 0;

    for (Iterator it(*this); it.has_curr(); it.next())
      ++count;

    return count;
  }
};


    template <typename T = int>
class DynList : public HTList
{
public:

  DynList & swap(DynList & l) { return (DynList&) HTList::swap(l); }

  DynList() { /* empty */ }

  typedef T Item_Type;

  typedef T Key_Type;

private:

  T & __insert(Snodenc<T> * p)
  {
    HTList::insert(p);
    return p->get_data();
  }

  T & __append(Snodenc<T> * p)
  {
    HTList::append(p);
    return p->get_data();
  }

public:

  T & insert(const T & item)
  {
    return __insert(new Snodenc<T> (item));
  }

  T & insert(T && item)
  {
    return __insert(new Snodenc<T> (std::move(item)));
  }

  T & append(const T & item)
  {
    return __append(new Snodenc<T> (item));
  }

  T & append(T && item)
  {
    return __append(new Snodenc<T> (std::move(item)));
  } 

  DynList(const T & item)
  {
    insert(item);
  }

  DynList(T && item)
  {
    insert(std::move(item));
  }

  T remove()
  {
    Slinknc * l = this->HTList::remove_head();
    Snodenc<T> * p = static_cast<Snodenc<T>*> (l);
    T ret_val = std::move(p->get_data());
    delete p;

    return ret_val;
  }
  
  T remove_first() { return remove(); }

  T & get() 
  {
    if (is_empty())
      throw std::underflow_error("List is empty");

    Snodenc<T> * p = static_cast<Snodenc<T>*> (this->HTList::get_first());
    return p->get_data();
  }

  T & get_last() 
  {
    if (is_empty())
      throw std::underflow_error("List is empty");

    Snodenc<T> * p = static_cast<Snodenc<T>*> (this->HTList::get_last());
    return p->get_data();
  }

  const T & get_last() const 
  {
    return const_cast<DynList*>(this)->get_last();
  }

  T & get_first() { return get(); }

  const T & get_first() const { return get(); }

  T & get() const 
  { 
    DynList * ptr = const_cast<DynList*>(this);
    return ptr->get(); 
  }

  void empty()
  {
    while (not is_empty())
      remove();

    I(this->is_empty());
  }

  ~DynList() { empty(); }
  
  class Iterator : public HTList::Iterator
  {
  public:

    typedef T Item_Type;

    typedef Iterator Iterator_Type;

    Iterator() { /* empty */ }

    Iterator(const DynList & list) : HTList::Iterator(list) { /* empty */ }

    T & get_curr() const
    {
      return ((Snodenc<T>*) (HTList::Iterator::get_curr()))->get_data();
    }

    T & get_current() const
    {
      return get_curr();
    }

    T del() 
    {
      Snodenc<T> * p = (Snodenc<T> *) this->HTList::Iterator::del();
      T ret_val = std::move(p->get_data());
      delete p;
      return ret_val;
    }
  };

      template <class Equal = Aleph::equal_to<T>>
  bool remove(const T & item)
  {
    for (Iterator it(*this); it.has_curr(); it.next())
      if (Equal () (it.get_curr(), item))
        {
          it.del();
          return true;
        }

    return false;
  }

  DynList(const DynList & l)
  {
    for (typename DynList::Iterator it(l); it.has_curr(); it.next())
      append(it.get_curr());
  }

  DynList(DynList && l)
  {
    swap(l);
  }

  DynList(std::initializer_list<T> l)
  {
    std::for_each(l.begin(), l.end(), /* Lambda */ [this] (const T & item)
                  {
                    append(item); 
                  });
  }
  
  DynList & operator = (const DynList & l)
  {
    if (&l == this)
      return *this;

    empty();

    for (typename DynList::Iterator it(l); it.has_curr(); it.next())
      append(it.get_curr());
    
    return *this;
  }

  DynList & operator = (DynList && l)
  {
    return (DynList&) this->swap(l);
  }

  void append(DynList && list)
  {
    HTList::append(list);
  }

  void insert(DynList && list)
  {
    HTList::insert(list);
  }

  void append(const DynList & list)
  {
    if (&list == this)
      return;

    DynList copy = list;
    HTList::append(copy);
  }

  void insert(const DynList & list)
  {
    if (&list == this)
      return;

    DynList tmp = list;
    HTList::insert(tmp);
  }

  T & get(const size_t & i)
  {
    Iterator it(*this);

    for (size_t __i = 0 ; it.has_current() and __i < i; it.next(), ++__i);

    return it.get_current();
  }

  T & operator [] (const size_t & i)
  {
    return get(i);
  }

  Generic_Traverse(T);

  Functional_Methods(T);
};


# undef NEXT

} // end namespace Aleph


# endif // HTLIST_H