htlist.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 HTLIST_H
# define HTLIST_H

# include <type_traits>
# include <cassert>
# include <stdexcept>
# include <utility>
# include <ahFunction.H>
# include <ahFunctional.H>
# include <ah-args-ctor.H>
# include <ah-iterator.H>

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

using namespace Aleph;

namespace Aleph {

template <typename T> class Snodenc; // forward declaration

class Slinknc
{
  Slinknc * next = nullptr;

public:

  bool is_empty() const noexcept { return next == nullptr; }

  Slinknc() noexcept : next(nullptr) { /* empty */ }

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

  void reset() noexcept
  {
    next = nullptr;
  }

  Slinknc & operator = (const Slinknc & ) noexcept
  {
    next = nullptr;
    return *this;
  }

  Slinknc *& get_next() noexcept
  {
    return next;
  }


  void insert(Slinknc * p) noexcept
  {
    assert(p != nullptr);
    p->next = next;
    next = p;
  }

  Slinknc * remove_next() noexcept
  {
    Slinknc * ret_val = next;
    next = ret_val->next;
    ret_val->reset();
    return ret_val;
  }

  template <typename T> inline
  Snodenc<T> * to_snodenc() noexcept;

  template <typename T> inline T & to_data() noexcept;

  template <typename T> inline
  const Snodenc<T> * to_snodenc() const noexcept;

  template <typename T> inline const T & to_data() const noexcept;

  class Iterator
  {
    Slinknc * head;
    Slinknc * curr;

    void init()
    {
      curr = head->is_empty() ? nullptr : head->next;
    }

  public:

    Iterator() noexcept : head(nullptr), curr(nullptr)
    {
      // Empty
    }

    Iterator(Slinknc & list) noexcept : head(&list)
    {
      init();
    }

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

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

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

    Slinknc * get_curr_ne() const noexcept { return curr; }

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

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

    void reset_first() noexcept
    {
      init();
    }
  };
};


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

public:

  T & get_data() noexcept { return data; }

  const T & get_data() const noexcept { return data; }

  Snodenc() noexcept(std::is_nothrow_constructible<T>::value)
  {
    static_assert(std::is_default_constructible<T>::value,
                  "No default constructor for T");
  }

  Snodenc(const T & item) noexcept(noexcept(T(item))) : data(item)
  {
    static_assert(std::is_copy_constructible<T>::value,
                  "No copy constructor for T");
  }

  Snodenc(T && item) noexcept(noexcept(std::swap(data, item)))
    : data(std::forward<T>(item))
  {
    static_assert(std::is_move_constructible<T>::value,
                  "No move constructor for T");
  }

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

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

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

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

  template <typename T> inline
Snodenc<T> * Slinknc::to_snodenc() noexcept
{
  return static_cast<Snodenc<T>*>(this);
}

    template <typename T> inline
const Snodenc<T> * Slinknc::to_snodenc() const noexcept
{
  return static_cast<const Snodenc<T>*>(this);
}

template <typename T> T & Slinknc::to_data() noexcept
{
  return this->to_snodenc<T>()->get_data();
}

template <typename T> const T & Slinknc::to_data() const noexcept
{
  return this->to_snodenc<T>()->get_data();
}

class HTList
{
  Slinknc * head;
  Slinknc * tail;

public:

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

  void reset()
  {
    head = tail = nullptr;
  }

  bool is_empty() const noexcept { return head == nullptr; }

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

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

  Slinknc * get_head() const noexcept { return head; }

  Slinknc * get_tail() const noexcept { return tail; }

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

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


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


  void insert(Slinknc * link) noexcept
  {
    assert(NEXT(link) == nullptr);

    if (head == nullptr)
      {
        assert(tail == nullptr);
        head  = tail = link;
        return;
      }

    NEXT(link) = head;
    head = link;
  }


  void append(Slinknc * link) noexcept
  {
    assert(link != nullptr and NEXT(link) == nullptr);

    if (head == nullptr)
      {
        assert(tail == nullptr);
        head = tail = link;
        return;
      }

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


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

    if (this->is_empty())
      {
        this->swap(l);
        return;
      }

    NEXT(tail) = l.head;
    tail = l.tail;
    l.head = l.tail = nullptr;
  }

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

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

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


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

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

  Slinknc * remove_head_ne() noexcept
  {
    Slinknc * ret_val = head;
    if (head == tail)
      head = tail = nullptr;
    else
      {
        head = NEXT(head);
        if (head == nullptr)
          tail = nullptr;
      }

    ret_val->reset();

    return ret_val;
  }

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

  Slinknc * remove_first_ne() noexcept { return remove_head_ne(); }

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

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

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

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

    return false;
  }

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

  Slinknc * pop()
  {
    if (is_empty())
      throw std::underflow_error("HTList as stack is empty");
    return remove_head();
  }

  Slinknc * top()
  {
    if (is_empty())
      throw std::underflow_error("HTList as stack is empty");
    return get_first();
  }


  size_t split_list(HTList & l, HTList & r) noexcept
  {
    assert(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 (q != tail and q != nullptr)
      {
        q = NEXT(q); ++count;
        if (q == tail or q == nullptr)
          break;

        p = NEXT(p);
        q = NEXT(q); ++count;
      }

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

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

    head = tail = nullptr;

    return count;
  }

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

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

  size_t reverse() noexcept
  {
    HTList tmp;

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

    swap(tmp);

    return count;
  }

  size_t reverse_list() noexcept
  {
    return reverse();
  }


  void cut(Slinknc * link, HTList & list) noexcept
  {
    assert(list.is_empty());

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

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

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

  void remove_all_and_delete() noexcept
  {
    while (not is_empty())
      delete remove_head_ne();
  }

  class Iterator
  {
    HTList * lptr = nullptr;
    Slinknc * curr = nullptr;
    Slinknc * prev = nullptr;

    long pos = 0;

  public:

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

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

    long get_pos() const noexcept { return pos; }

    void reset_first() noexcept { reset(); }

    void reset_last()
    {
      reset();
      if (lptr->is_empty())
        return;

      while (NEXT(curr))
        {
          prev = curr;
          curr = NEXT(curr);
          ++pos;
        }
    }

    void end() noexcept
    {
      curr = nullptr;
    }

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

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

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

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

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

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

      return curr;
    }

    Slinknc * get_curr_ne() const noexcept { return curr; }

    void next_ne() noexcept
    {
      if (curr == lptr->head) // on the first item?
        {
          assert(prev == lptr->head);
          curr = NEXT(curr);
        }
      else if (curr == lptr->tail) // on the last item?
        {
          assert(NEXT(prev) == curr);
          curr = nullptr;
        }
      else
        {
          assert(NEXT(prev) == curr);
          prev = curr;
          curr = NEXT(curr);
          assert(NEXT(prev) == curr);
        }
      pos++;
    }

    void next()
    {
      if (not has_curr())
        throw std::overflow_error("Iterator overflow");
      next_ne();
    }

    Slinknc * del_ne() noexcept
    {
      Slinknc * ret_val = nullptr;
      if (curr == lptr->head) // first item removal
        {
          ret_val = lptr->remove_first();
          prev = curr = lptr->head;
        }
      else if (curr == lptr->tail) // last item removal
        {
          assert(NEXT(prev) == curr);
          ret_val = curr;
          NEXT(prev) = NEXT(curr);
          lptr->tail = prev;
          curr = nullptr; // put in overflow
        }
      else
        {
          assert(NEXT(prev) == curr);
          ret_val = curr;
          NEXT(prev) = NEXT(curr);
          curr = NEXT(curr);
        }

      ret_val->reset();
      return ret_val;
    }

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

      return del_ne();
    }
  };

  size_t size() const noexcept
  {
    size_t count = 0;
    for (Iterator it(*this); it.has_curr(); it.next_ne())
      ++count;

    return count;
  }

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

# include <ah-dry.H>

    template <typename T = int>
class DynList : public HTList,
                public GenericTraverse<DynList<T>>,
                public LocateFunctions<DynList<T>, T>,
                public SpecialCtors<DynList<T>, T>,
                public FunctionalMethods<DynList<T>, T>,
                public GenericItems<DynList<T>, T>,
                public StlAlephIterator<DynList<T>>
{
  using CtorBase = SpecialCtors<DynList<T>, T>;

  using CtorBase::CtorBase;

 public:

  using Item_Type = T;

  using Key_Type = T;

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

  DynList() noexcept(std::is_nothrow_constructible<T>::value) { /* empty */ }

  DynList(const DynList & l) : HTList(), CtorBase(l) {}

private:

  T & __insert(Snodenc<T> * p) noexcept
  {
    static_assert(std::is_copy_constructible<T>::value or
                  std::is_move_constructible<T>::value,
                  "No copy assign for T");
    HTList::insert(p);
    return p->get_data();
  }

  T & __append(Snodenc<T> * p) noexcept
  {
    static_assert(std::is_copy_constructible<T>::value or
                  std::is_move_constructible<T>::value,
                  "No copy assign for T");
    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::forward<T>(item)));
  }

  T & push(const T & item)
  {
    return insert(item);
  }

  T & push(T && item) { return insert(std::forward<T>(item)); }

  T & put(const T & item) noexcept(noexcept(T(item)))
  {
    return push(item);
  }

  T & put(T && item) noexcept(noexcept(std::forward<T>(item)))
  {
    return push(std::forward<T>(item));
  }

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

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

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

    return ret_val;
  }

  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_ne() noexcept
  {
    return remove_ne();
  }

  T remove_first()
  {
    return remove();
  }

  T pop() { return remove_first(); }

  T get() { return remove(); }

  T & get_last_ne() const noexcept
  {
    Snodenc<T> * p = static_cast<Snodenc<T>*> (this->HTList::get_last());
    return p->get_data();
  }

  T & get_first_ne() const noexcept
  {
    return static_cast<Snodenc<T>*>(this->HTList::get_first())->get_data();
  }

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

  T & get_first() const
  {
    if (is_empty())
      throw std::underflow_error("List is empty");
    return get_first_ne();
  }

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

  void empty() noexcept
  {
    if (is_empty())
      return;

        // a very fast deletion
    Snodenc<T> * last = static_cast<Snodenc<T>*> (this->HTList::get_last());
    Snodenc<T> * p = static_cast<Snodenc<T>*> (this->HTList::get_first());
    while (p != last)
      {
        Snodenc<T> * q = p;
        p = p->get_next();
        delete q;
      }
    delete p;
    reset();
  }

  ~DynList() { empty(); }

  class Iterator : public HTList::Iterator
  {
  public:

    using Item_Type = T; 

    using Iterator_Type = Iterator;

    using Set_Type = DynList; 

    Iterator() noexcept { /* empty */ }

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

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

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

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

  DynList & reverse() noexcept
  {
    reverse_list();
    return *this;
  }

  DynList & rev() noexcept { return reverse(); }

  DynList reverse() const
  {
    DynList ret;
    for (auto it = this->get_it(); it.has_curr(); it.next())
      ret.insert(it.get_curr());

    return ret;
  }

  DynList rev() const { return reverse(); }

  template <class Equal = std::equal_to<T>>
  T remove_ne(Equal eq) noexcept
  {
    for (Iterator it(*this); true; it.next_ne())
      {
        const T & item = it.get_curr_ne();
        if (not eq(item))
          continue;
        T ret = item; // performs a copy
        it.del_ne();
        return ret;
      }
  }

  template <class Equal = std::equal_to<T>> T remove(Equal eq)
    {
      for (Iterator it(*this); it.has_curr(); it.next_ne())
        {
          const T & item = it.get_curr_ne();
          if (eq(item))
            {
              T ret = item; // performs a copy
              it.del();
              return ret;
            }
        }

      throw std::domain_error("DynList::remove(Equal &): item not found");
    }

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

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

    empty();

    for (typename DynList::Iterator it(l); it.has_curr(); it.next_ne())
      append(it.get_curr_ne());

    return *this;
  }

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

  DynList & append(DynList && list) noexcept
  {
    HTList::append(list);
    return *this;
  }

  DynList & insert(DynList && list) noexcept
  {
    HTList::insert(list);
    return *this;
  }

  DynList & append(const DynList & list) noexcept(noexcept(DynList(list)))
  {
    DynList copy = list;
    HTList::append(copy);
    return *this;
  }

  DynList & insert(const DynList & list) noexcept(noexcept(DynList(list)))
  {
    DynList tmp = list;
    HTList::insert(tmp);
    return *this;
  }

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

    for (size_t __i = 0 ; it.has_curr() and __i < i; it.next_ne(), ++__i);

    return it.get_curr_ne();
  }

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

template <class Container>
inline DynList<typename Container::Item_Type> to_dynlist(const Container & c)
{
  return c.template maps<typename Container::Item_Type>([] (const auto & d)
                                                        {
                                                          return d;
                                                        });
}

  template <typename T> inline
DynList<T> get_unitarian_DynList(const T & item)
{
  DynList<T> ret;
  ret.append(item);
  return ret;
}

    template <typename T> inline
DynList<T> unitarian_DynList(const T & item)
{
  return DynList<T>({item});
}

# undef NEXT

} // end namespace Aleph


# endif // HTLIST_H