List.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/>.
*/

/*
        Aleph implementation of list C++ standard container
*/

# ifndef ALEPH_LIST_H
# define ALEPH_LIST_H

# include <ah_stdc++_utils.H>
# include <tpl_sort_utils.H>

namespace Aleph
{

    template <class T>
class list
{
  mutable Dnode<T> dlist;

  typedef Dnode<T> Node;

public:

  typedef T value_type;

  typedef typename list::value_type & reference;

  typedef const typename list::value_type & const_reference;

  typedef size_t size_type;

private:

  mutable size_type num_elem;

  mutable bool num_elem_is_updated;

  void reset_num_elem(const size_type & num = 0)
  {
    num_elem = num;
    num_elem_is_updated = true;
  }

  void update_num_elem()
  {
    assert(not num_elem_is_updated);

    size_type counter = 0;

    for (typename Dnode<T>::Iterator it(dlist); it.has_curr(); it.next_ne())
      ++counter;

    num_elem = counter;
    num_elem_is_updated = true;
  }

public:

  class iterator
  {
    friend class list<T>;

    typedef typename Dnode<T>::Iterator Iterator;
    
    Iterator itor;

    bool underflow;
    bool overflow;

    void init_flags()
    {
      if (itor.has_curr())
        underflow = overflow = false;
      else
        underflow = overflow = true;
    }

    iterator(Dnode<T> & __list) : itor(__list)
    {
      init_flags();
    }

    void goto_begin()
    {
      itor.reset_first();
      init_flags();
    }

    void goto_last()
    {
      itor.reset_last();
      init_flags();
    }

    void goto_end()
    {
      itor.reset_last();
      init_flags();
      if (not overflow)
        itor.next();
      overflow = true;
    }

    void forward()
    {
      if (underflow)
        {
          goto_begin();
          return;
        }
      
      itor.next();

      if (not itor.has_curr())
        overflow = true;
    }

    void backward()
    {
      if (overflow)
        {
          goto_last();
          return;
        }
      
      itor.prev();

      if (not itor.has_curr())
        underflow = true;
    }

  public:

    typedef typename list::value_type   value_type;

    typedef int                         difference_type;

    typedef typename list::value_type * pointer;

    typedef typename list::reference    reference;

    iterator() : underflow(false), overflow(false) { /* empty */ }

    T & operator *()
    {
      return itor.get_curr()->get_data();
    }

    T * operator ->()
    {
      return & itor.get_curr()->get_data();
    }

    iterator operator ++()
    {
      forward();
      return *this;
    }

    iterator operator ++ (int)
    {
      iterator return_value = *this;
      forward();
      return return_value;
    }

    iterator operator --()
    {
      backward();
      return *this;
    }

    iterator operator -- (int)
    {
      iterator return_value = *this;
      backward();
      return return_value;
    }
    
    iterator operator += (const size_type & n)
    {
      for (int i = 0; i < n; ++i)
        forward();

      return *this;
    } 

    iterator operator -= (const size_type & n)
    {
      for (int i = 0; i < n; ++i)
        backward();

      return *this;
    } 

    bool operator == (const iterator & __itor)
    {
      return itor == __itor.itor;
    }

    bool operator != (const iterator& __itor)
    {
      return itor != __itor.itor;
    }

    bool verify (const list<T> & list) const
    {
      return itor.verify((Dlink*)(&list.dlist));
    }

    bool verify(const iterator & it) const
    {
      return itor.verify(it.itor);
    }
  }; // end class iterator

private:

  void copy(const list& _list)
  {
    assert(dlist.is_empty());
    assert(num_elem == 0);

    for (typename Dnode<T>::Iterator it(_list.dlist); 
         it.has_curr(); it.next_ne())
      {
        Node * node = new Node(it.get_curr_ne()->get_data());

        dlist.append(node);
        ++num_elem;
      }
  }

public:

  list() : num_elem(0), num_elem_is_updated(true) { /* empty */ }

  list(const list & c) : num_elem(0), num_elem_is_updated(true)
  {
    copy(c);
  }

  list(const size_type & num) : num_elem(0), num_elem_is_updated(true)
  {
    for (/* nothing */; num_elem < num; ++num_elem)
      dlist.append(new Node);
   }

  list(const size_type & num, const T & value) 
    : num_elem(0), num_elem_is_updated(true)
  {
    for (/* nothing */; num_elem < num; ++num_elem)
      dlist.append(new Node(value));
  }

      template <class Itor>
  list(Itor beg, const Itor & end) 
    : num_elem(0), num_elem_is_updated(true)
  {
    Aleph::verify_iterators(beg, end);

    while (beg != end)
      {
        dlist.append(new Node(*beg++));
        ++num_elem;
      }
  }

  ~list() 
  {
    clear();
  }

  size_type size() 
  {
    if (not num_elem_is_updated)
      update_num_elem();

    return num_elem;
  }

  bool empty() const
  {
    return dlist.is_empty();
  }

  bool operator == (const list & c) const
  {
    if (this == &c)
      return true;

    if (num_elem_is_updated and c.num_elem_is_updated)
      if (num_elem != c.num_elem)
        return false;

    typename Dnode<T>::Iterator it_l(*this), it_r(c.dlist);

    while (it_l.has_curr() and it_r.has_curr())
      {
        if (it_l.get_curr_ne()->get_data() != it_r.get_curr_ne()->get_data())
          return false;

        it_l.next_ne();
        it_r.next_ne();
      }

    if (it_l.is_empty() and it_r.is_empty())
      return true;
    
    return false;
  }

  bool operator != (const list & c) const
  {
    return not (*this == c);
  }

  bool operator < (const list & c) const
  {
    if (this == &c)
      return false;

    typename Dnode<T>::Iterator it_l(*this);
    typename Dnode<T>::Iterator it_r(c);

    while (it_l.has_curr() and it_r.has_curr())
      {
        if (it_l.get_curr_ne()->get_data() < it_r.get_curr_ne()->get_data())
          return true;
        else if (it_r.get_curr()->get_data() < 
                 it_l.get_curr()->get_data())
          return false; // no son iguales

        it_l.next_ne();
        it_r.next_ne();
      }

    return it_l.is_empty();
  }

  bool operator > (const list & c) const
  {
    return c < *this;
  }

  bool operator <= (const list & c) const
  {
    return not (c > *this );
  }

  bool operator >= (const list & c) const
  {
    return not (*this < c);
  }

  list & operator = (const list & c)
  {
    if (this == &c)
      return *this;

    clear();
    copy(c);
  }

  void assign(const size_type & num, const T & value)
  {
    clear();
    
    for (int n = 0; n < num; ++n)
      push_back(value);
  }

      template <typename Itor>
  void assign (Itor beg, const Itor & end)
  {
    Aleph::verify_iterators(beg, end);

    clear();
    
    while (beg != end)
      push_back(*beg++);
  }
    
  void swap(list & c)
  {
    dlist.swap(c.dlist);
    std::swap(num_elem, c.num_elem);
    std::swap(num_elem_is_updated, c.num_elem_is_updated);
  }

  reference front() const
  {
    return dlist.get_next()->get_data();
  }

  reference back() const
  {
    return dlist.get_prev()->get_data();
  }

  iterator begin() const
  {
    return iterator(dlist);
  }
  
  iterator end() const
  {
    iterator _itor(dlist);
    _itor.goto_end();

    return _itor;
  }
 
  iterator insert(const iterator & pos, const T & value)
  {
    Aleph::verify_container_and_iterator(*this, pos);

    Node * new_node = new Node(value);

    Node * current_node = pos.itor.get_curr();

    current_node->append(new_node);

    pos.itor.set(new_node);

    ++num_elem;

    return pos;
  }

  void insert(iterator pos, const size_type & num, const T & value)
  {
    Aleph::verify_container_and_iterator(*this, pos);

    Node new_list;

    try
      {
        for (int i = 0; i < num; ++i)
          new_list.append (new Node(value));

        Node * current_node = pos.itor.get_curr();
        current_node->insert_list(&new_list);
        num_elem += num;
      }
    catch (...)
      {
        new_list.remove_all_and_delete();
        throw;
      }
  }

      template <class Itor>
  void insert(iterator pos, Itor beg, const Itor & end)
  {
    Aleph::verify_container_and_iterator(*this, pos);
    Aleph::verify_iterators(beg, end);

    Node new_list;
    try
      {
        while (beg != end)
          {
            new_list.append(new Node(*beg++));
            ++num_elem;
          }

        Node * current_node = pos.itor.get_curr();
        current_node->insert_list(&new_list);
      }
    catch (...)
      {
        new_list.remove_all_and_delete();
        throw;
      }
  }

  void push_front(const T & value)
  {
    dlist.insert(new Node(value));
    ++num_elem;
  }

  void push_back(const T & value)
  {
    dlist.append(new Node(value));
    ++num_elem;
  }

  void remove(const T & value)
  {
    for (typename Dnode<T>::Iterator it(dlist); it.has_curr(); /* nothing */)
      if (it.get_curr_ne()->get_data() == value)
        {
          delete it.del();
          --num_elem;
        }
      else
        it.next_ne();
  }

  iterator erase(iterator pos)
  {
    Aleph::verify_container_and_iterator(*this, pos);

    delete pos.itor.del();
    --num_elem;

    return pos;
  }

  iterator erase(iterator beg, const iterator & end)
  {
    Aleph::verify_container_and_iterator(*this, beg);
    Aleph::verify_iterators(beg, end);

    while (beg != end)
      {
        delete  beg.itor.del();
        --num_elem;
      }

    return beg;
  }

  void pop_front()
  {
    delete dlist.remove_next();
    num_elem--;
  }

  void pop_back()
  {
    delete dlist.remove_prev();
    --num_elem;
  }

  void clear()
  {
    dlist.remove_all_and_delete();
    reset_num_elem();
  }

  void resize(size_type num, const T & t = T())
  {
    if (num == size())
      return;
    
    if (num < num_elem)
      {
        while (num_elem > num)
          {
            delete dlist.remove_prev();
            --num_elem;
          }

        return;
      }

    iterator itor(end());
    --itor;
    insert(itor, num - num_elem, t);
  }

      template <class Op>
  void unique(const Op & op) 
  {
    reset_num_elem(); // recordar que coloca num_elem = 0
    
    for (typename Dnode<T>::Iterator it1(dlist); it1.has_curr(); 
         it1.next_ne(), ++num_elem)
      {
        typename Dnode<T>::Iterator it2(it1); it2.next_ne();

        while (it2.has_curr())
          if (op(it1.get_curr_ne()->get_data(), it2.get_curr_ne()->get_data()))
            delete it2.del();
          else
            break;
      }
  }

  void unique()  
  {
    unique(Aleph::equal_to<T>());
  }

  void splice(iterator pos, list & l)
  {
    Aleph::verify_container_and_iterator(*this, pos);

    pos.itor.get_curr()->insert_list(&l.dlist);

    num_elem_is_updated = l.num_elem_is_updated;
    num_elem += l.num_elem;

    l.reset_num_elem();

    assert(l.dlist.is_empty());
  }

  void splice(iterator pos, list & src_list, iterator src_pos)
  {
    Aleph::verify_container_and_iterator(*this, pos);
    Aleph::verify_container_and_iterator(src_list, src_pos);

    pos.itor.get_curr()->insert(src_pos.itor.del());
    --src_list.num_elem;
    ++num_elem;
  }

  void splice(iterator pos, list & src_list, 
              iterator src_beg, const iterator & src_end)
  {
    Aleph::verify_container_and_iterator(*this, pos);
    Aleph::verify_container_and_iterator(src_list, src_beg);
    Aleph::verify_iterators(src_beg, src_end);    

    Dlink list_to_insert;
    src_list.dlist.cut_list(src_beg.itor.get_curr(), &list_to_insert);

    Dlink remaining_list;
    list_to_insert.cut_list(src_end.itor.get_curr(), &remaining_list);
    
    pos.itor.get_curr()->insert_list(&list_to_insert);
    num_elem_is_updated = false;

    src_list.dlist.concat_list(&remaining_list);
    src_list.num_elem_is_updated = false;
  }

      template <class Cmp>
  void sort(const Cmp &)
  {
    quicksort<T, Cmp>(dlist);   
  }

  void sort()
  {
    sort(Aleph::less<T>()); 
  }

      template <class Cmp>
  void merge(list & l, const Cmp &)
  {
    Dnode<T> result;

    Aleph::merge_lists<T, Cmp>(dlist, l.dlist, result);

    dlist.swap(result);

    num_elem += l.num_elem;

    l.reset_num_elem();

    assert(l.dlist.is_empty());
  }

  void merge(list & l)
  {
    merge(l, Aleph::less<T>());
  }

  void reverse()
  {
    reset_num_elem(dlist.reverse_list());
  }
};


    template <typename T>
typename list<T>::size_type distance(typename list<T>::iterator it1, 
                                     typename list<T>::iterator it2)
{
  typename list<T>::size_type counter = 0;

  while (it1 != it2)
    {
      counter++;
      it1++;
    }

  return counter;
}

} // end namespace Aleph

# endif // ALEPH_LIST_H