htlist.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# 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>
# include <ah-errors.H>
# include <ah-dry.H>
 
# define NEXT(p) (p->get_next())
 
namespace Aleph {
 
template <typename T> class Snodenc; // forward declaration
 
class Slinknc
{
  Slinknc * next = nullptr;
 
public:
 
  virtual ~Slinknc() = default;
 
  [[nodiscard]] constexpr 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() noexcept
    {
      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
    {
      ah_overflow_error_if(not has_curr())
        << "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()
    {
      ah_overflow_error_if(not has_curr())
        << "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()
  {
    static_assert(std::is_default_constructible<T>::value,
                  "No default constructor for T");
  }
 
  Snodenc(const T & item) : data(item)
  {
    static_assert(std::is_copy_constructible<T>::value,
                  "No copy constructor for T");
  }
 
  Snodenc(T && item)
    : data(std::forward<T>(item))
  {
    static_assert(std::is_move_constructible<T>::value,
                  "No move constructor for T");
  }
 
  Snodenc * remove_next() noexcept
  {
    return static_cast<Snodenc *>(Slinknc::remove_next());
  }
 
  Snodenc *& get_next() noexcept
  {
    // STRICT ALIASING WARNING: This reinterpret_cast violates C++ strict
    // aliasing rules. Requires -fno-strict-aliasing compiler flag.
    return reinterpret_cast<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() noexcept
  {
    head = tail = nullptr;
  }
 
  [[nodiscard]] constexpr 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
  {
    if (list.is_empty())
      return;
 
    Slinknc * link_next = NEXT(link); // save what was after link
    NEXT(link) = list.head;           // link now points to list's head
    NEXT(list.tail) = link_next;      // list's tail points to what was after link
 
    if (link == tail)                 // if link was the tail, update tail
      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()
  {
    ah_underflow_error_if(is_empty())
      << "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)
  {
    ah_underflow_error_if(is_empty())
      << "Removing from a empty list";
 
    if (link == head)
      {
        head = NEXT(head);
        if (head == nullptr)
          tail = nullptr;
        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()
  {
    ah_underflow_error_if(is_empty())
      << "HTList as stack is empty";
    return remove_head();
  }
 
  Slinknc * top() const
  {
    ah_underflow_error_if(is_empty())
      << "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;
      }
 
    Slinknc * r_head = NEXT(p);
 
    l.head = head;
    l.tail = p;
 
    r.head = r_head;
    r.tail = r_head == nullptr ? nullptr : tail;
 
    NEXT(l.tail) = nullptr;
 
    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 = list.head == nullptr ? nullptr : 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() noexcept = default;
 
    Iterator(const HTList & list) noexcept
      : lptr(& const_cast<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;
        pos  = it.pos;
        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
    {
      ah_overflow_error_if(curr == nullptr)
        << "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()
    {
      ah_overflow_error_if(not has_curr())
        << "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()
    {
      ah_overflow_error_if(not has_curr())
        << "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;
        ah_domain_error() << "List is empty";
        return; // unreachable, silences -Wreturn-type
      }
 
    for (size_t i = 0; i < n; ++i)
      append(remove_first());
  }
};
 
    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;
 
  Slinknc * get_head() const noexcept = delete;
  Slinknc * get_tail() const noexcept = delete;
 
  DynList & swap(DynList & l) noexcept
  {
    return static_cast<DynList &>(HTList::swap(l));
  }
 
  DynList() { /* empty */ }
 
  DynList(const DynList & l) : HTList(), CtorBase(l) {}
 
private:
 
  T & __insert(Snodenc<T> * p) noexcept
  {
    static_assert(std::is_copy_constructible_v<T> or
                  std::is_move_constructible_v<T>,
                  "No copy assign for T");
    HTList::insert(p);
    return p->get_data();
  }
 
  T & __append(Snodenc<T> * p) noexcept
  {
    static_assert(std::is_copy_constructible_v<T> or
                  std::is_move_constructible_v<T>,
                  "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)
  {
    return push(item);
  }
 
  T & put(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();
    auto * 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();
    auto * 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
  {
    auto * 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
  {
    ah_underflow_error_if(is_empty())
      << "List is empty";
    return get_last_ne();
  }
 
  T & get_first() const
  {
    ah_underflow_error_if(is_empty())
      << "List is empty";
    return get_first_ne();
  }
 
  T & top() const
  {
    return get_first();
  }
 
  void empty() noexcept
  {
    if (is_empty())
      return;
 
        // a very fast deletion
    auto * last = static_cast<Snodenc<T>*> (this->HTList::get_last());
    auto * 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 = default;
 
    Iterator(const DynList & list) noexcept
      : HTList::Iterator(list) { /* empty */ }
 
    T & get_curr_ne() const noexcept
    {
      return static_cast<Snodenc<T> *>(HTList::Iterator::get_curr_ne())->get_data();
    }
 
    T & get_curr() const
    {
      return static_cast<Snodenc<T> *>(HTList::Iterator::get_curr())->get_data();
    }
 
    T del()
    {
      auto * p = static_cast<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); it.has_curr(); it.next_ne())
      {
        const T & item = it.get_curr_ne();
        if (not eq(item))
          continue;
        T ret = item; // performs a copy
        auto * removed = static_cast<Snodenc<T> *>(it.del_ne());
        delete removed;
        return ret;
      }
    return T(); // not found, return default constructed T
  }
 
  template <class Equal = std::equal_to<T>> T remove(Equal eq)
    {
      for (Iterator it(*this); it.has_curr(); it.next_ne())
          if (const T & item = it.get_curr(); eq(item))
            {
              T ret = item; // performs a copy
              auto * removed = static_cast<Snodenc<T> *>(it.HTList::Iterator::del());
              delete removed;
              return ret;
            }
 
      ah_domain_error() << "DynList::remove(Equal &): item not found";
      return T(); // unreachable, silences -Wreturn-type
    }
 
  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());
 
    return *this;
  }
 
  DynList & operator = (DynList && l) noexcept
  {
    return static_cast<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)
  {
    DynList copy = list;
    HTList::append(copy);
    return *this;
  }
 
  DynList & insert(const 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();
  }
 
  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