tpl_dynDlist.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 TPL_DYNDLIST_H
# define TPL_DYNDLIST_H

# include <ahFunctional.H>
# include <ahDry.H>
# include <ah-args-ctor.H>
# include <ahIterator.H>
# include <ah-iterator.H>
# include <tpl_dnode.H>

using namespace Aleph;

namespace Aleph {

# include <ah-dry.H>

    template <typename T = int>
class DynDlist
      : public Dnode<T>,
        public GenericTraverse<DynDlist<T>>,
        public SpecialCtors<DynDlist<T>, T>,
        public LocateFunctions<DynDlist<T>, T>,
        public FunctionalMethods<DynDlist<T>, T>,
        public GenericItems<DynDlist<T>, T>,
        public StlAlephIterator<DynDlist<T>>
{
  size_t num_elem = 0;

public:

  using Set_Type = DynDlist;

  using Item_Type = T;

  using Key_Type = T;

  const size_t & size() const noexcept { return num_elem; }

  DynDlist() { /* Empty */ }

  // using CtorBase = SpecialCtors<DynDlist<T>, T>;
  // using CtorBase::CtorBase;

  // /** Construct a new list with copies of elements of list `l`

  //     \param[in] l list to be copied
  //     \throw bad_alloc if there is no enough memory
  // */
  // DynDlist(const DynList<T> & l) : Dnode<T>(), CtorBase(l) {}

  Special_Ctors(DynDlist, T);

  void empty() noexcept 
  {
    while (not this->is_empty())
      delete this->Dnode<T>::remove_next();

    num_elem = 0;
  }

  ~DynDlist() 
  {
    empty();
  }

private:

  T & __insert(Dnode<T> * p) noexcept
  {
    Dnode<T>::insert(p);
    ++num_elem;
    return p->get_data();
  }

  T & __append(Dnode<T> * p) noexcept
  {
    Dnode<T>::append(p);
    ++num_elem;
    return p->get_data();
  }

public:

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

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

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

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

 private:

  void __insert(DynDlist<T> & list) noexcept
  {
    Dlink::insert_list(&list);
    num_elem += list.num_elem;
    list.num_elem = 0;

    assert(list.is_empty());
  }

  void __append(DynDlist<T> & list) noexcept
  {
    Dlink::append_list(&list);
    num_elem += list.num_elem;
    list.num_elem = 0;

    assert(list.is_empty());
  }

 public:

  void insert(const DynDlist & list)
  {
    auto l = list; // perform a copy of list
    __insert(l);
  }

  void insert(DynDlist && list) noexcept
  {
    __insert(list);
  }

  void append(const DynDlist & list) noexcept
  {
    auto l = list; // perform a copy of list
    __append(l);
  }

  void append(DynDlist && list) noexcept
  {
    __append(list);
  }

  T & get_first_ne() const noexcept
  {
    return this->get_next()->get_data();
  }

  T & get_last_ne() const noexcept
  {
    return this->get_prev()->get_data();
  }

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

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

  T remove_first_ne() noexcept
  {
    Dnode<T> * ptr = this->remove_next();
    T retVal = ptr->get_data();
    delete ptr;
    --num_elem;

    return retVal;
  }

  T remove_last_ne() noexcept
  {
    Dnode<T> * ptr = this->remove_prev();
    T retVal = ptr->get_data();
    delete ptr;
    --num_elem;

    return retVal;
  }

  T remove_first()
  {
    if (this->is_empty())
      throw std::underflow_error("DynDlist is empty");
    return remove_first_ne();
  }

  T remove_last()
  {
    if (this->is_empty())
      throw std::underflow_error("DynDlist is empty");
    return remove_last_ne();
  }

  T & put(const T & item) { return append(item); }

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

  T get() { return remove_first(); }

  T & rear() { return get_last(); }

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

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

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

  T pop() { return remove_first(); }

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

  void remove(T & data) noexcept
  {
    Dnode<T> * p = Dnode<T>::data_to_node(data);
    p->del();
    delete p;
    --num_elem;
  }

  void erase(T & data) noexcept
  {
    remove(data);
  }

  void swap(DynDlist & l) noexcept
  {
    std::swap(num_elem, l.num_elem);
    this->Dlink::swap(&l);
  }

  void split_list_ne(DynDlist & l, DynDlist & r) noexcept
  {
    Dlink::split_list(l, r);
    l.num_elem = r.num_elem = num_elem/2;

    if (num_elem % 2 == 1) // ¿es num_elem impar?
      l.num_elem++;

    num_elem = 0;
  }

  void split_list(DynDlist & l, DynDlist & r)
  {
    if ((not l.is_empty()) or (not r.is_empty()))
      throw std::domain_error("lists are not empty");
    split_list_ne(l, r);
  }

  void split(DynDlist & l, DynDlist & r)
  {
    split_list(l, r);
  }

  class Iterator : public Dnode<T>::Iterator
  {
    DynDlist * list_ptr; // puntero a la lista
    long       pos;      // posición del elemento actual en la secuencia

    using Base = typename Dnode<T>::Iterator;

  public:

    using Set_Type = DynDlist;

    using Item_Type = T;

    long get_pos() const noexcept { return pos; }

    void next_ne() noexcept
    {
      Dnode<T>::Iterator::next_ne();
      pos++;
    }

    void next()
    {
      Dnode<T>::Iterator::next();
      pos++;
    }

    void prev()
    {
      Dnode<T>::Iterator::prev();
      pos--;
    }

    void reset_first() noexcept
    {
      Dnode<T>::Iterator::reset_first();
      pos = 0;
    }

    void reset_last() noexcept
    {
      Dnode<T>::Iterator::reset_last();
      pos = list_ptr->num_elem - 1;
    }

    void end() noexcept
    {
      put_itor_at_the_end(*this);
    }

    Iterator(const DynDlist<T> & list) noexcept
    : Base(list), list_ptr(&const_cast<DynDlist&>(list)), pos(0)
    {
      // empty
    }

    Iterator() noexcept : list_ptr(nullptr) { /* empty */ }

    Iterator & operator = (const Iterator & it) noexcept
    {
      Dnode<T>::Iterator::operator = (it);
      list_ptr = it.list_ptr;
      pos      = it.pos;

      return *this;
    }

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

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

    void insert(const T & item)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->insert(new Dnode<T>(item));
      ++list_ptr->num_elem;
    }

    void insert(T && item)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->
        insert(new Dnode<T>(std::forward<T>(item)));
      ++list_ptr->num_elem;
    }

    void append(const T & item)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->append(new Dnode<T>(item));
      ++list_ptr->num_elem;
    }

    void append(T && item)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->
        append(new Dnode<T>(std::forward<T>(item)));
      ++list_ptr->num_elem;
    }

    void insert_list(DynDlist & list)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->insert_list(&list);
      list_ptr->num_elem += list.num_elem;
      list.num_elem = 0;

      assert(list.is_empty());
    }

    void append_list(DynDlist & list)
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T>::Iterator::get_curr()->append_list(&list);
      list_ptr->num_elem += list.num_elem;
      list.num_elem = 0;

      assert(list.is_empty());
    }

    T del()
    {
      if (not this->has_curr())
        throw std::overflow_error ("DynDlist Iterator has not current");

      Dnode<T> * ptr = Dnode<T>::Iterator::get_curr();
      T ret_val      = ptr->get_data();
      Dnode<T>::Iterator::next();
      ptr->del();
      delete ptr;
      --list_ptr->num_elem;
      return ret_val;
    }
  };

  DynDlist<T> & operator = (const DynDlist & list)
  {
    if (this == &list)
      return *this;

    empty();

    for (typename DynDlist<T>::Iterator itor(const_cast<DynDlist&>(list));
         itor.has_curr(); itor.next_ne())
      this->append(itor.get_curr_ne());

    return *this;
  }

  DynDlist(const DynDlist & list) : DynDlist()
  {
    assert(this->is_empty());

    for (typename DynDlist<T>::Iterator itor(const_cast<DynDlist&>(list));
         itor.has_curr();itor.next_ne())
      this->append(itor.get_curr_ne());
  }

  DynDlist(DynDlist<T> && list) noexcept
    : DynDlist()
  {
    swap(list);
  }

  DynDlist<T> & operator = (DynDlist && list) noexcept
  {
    swap(list);
    return *this;
  }

  T & operator [] (const size_t & n) const
  {
    typename DynDlist<T>::Iterator it(*this);

    for (int i = 0; i < n and it.has_curr(); i++, it.next_ne()) ;

    return it.get_curr();
  }

  DynDlist & reverse() noexcept
  {
    Dlink::reverse();
    return *this;
  }

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

  DynDlist<T> reverse() const
  {
    DynDlist<T> ret;
    for (auto it = this->get_it(); it.has_curr(); it.next_ne())
      ret.insert(it.get_curr_ne());
    return ret;
  }

  DynDlist<T> rev() const { return reverse(); }
};

} // end namespace Aleph

# endif /* TPL_DYNDLIST_H */