CMappedList.hpp

/* This file is part of sUtil, a random collection of utilities.

sUtil is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 3 of the License, or (at your option) any later version.

Alternatively, 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 2 of
the License, or (at your option) any later version.

sUtil 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 Lesser General Public
License and a copy of the GNU General Public License along with
sUtil. If not, see <http://www.gnu.org/licenses/>.
 */
/* \file CMappedList.hpp
 *
 *  Created on: Jul 12, 2010
 *
 *  Copyright (C) 2010, Samir Menon <smenon@stanford.edu>
 */

#ifndef CMAPPEDLIST_HPP_
#define CMAPPEDLIST_HPP_

#include <map>
#include <cstddef>
#include <vector>

#ifdef DEBUG
#include <iostream>
#include <cassert>
#endif

namespace sutil
{

  template <typename IdxS, typename TS>
  class SMLNode
  {
  public:
    TS* data_;
    IdxS* id_;

    //For the linked list
    SMLNode<IdxS,TS> *next_,*prev_;

    SMLNode()
    {
      data_=NULL;
      id_=NULL;
      next_=NULL;
      prev_=NULL;
    }
  };

  template <typename Idx, typename T>
  class CMappedList
  {
  public:
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef T*       pointer;
    typedef const T* const_pointer;
    typedef T&       reference;
    typedef const T& const_reference;
    typedef T        value_type;

    class iterator; //Forward declaration
    class const_iterator;

    CMappedList() : front_(NULL), back_(NULL), size_(0), flag_is_sorted_(false) {}

  protected:
    virtual bool deepCopy(const CMappedList<Idx,T>* const arg_pmap);

  public:
    explicit CMappedList(const CMappedList<Idx,T>& arg_pm)
    {
      front_ = NULL; back_ = NULL; null_.prev_ = NULL; size_ = 0;
      deepCopy(&arg_pm);
    }

    virtual CMappedList<Idx,T>& operator = (const CMappedList<Idx,T>& arg_rhs)
    {
      deepCopy(&arg_rhs);
      return *this;
    }

    virtual ~CMappedList();

    bool operator == (const CMappedList<Idx,T>& rhs);

    bool operator != (const CMappedList<Idx,T>& rhs);

    void swap(CMappedList<Idx,T>& arg_swap_obj);

//    /** Example usage:
//     *   first.assign (7,100);                      // 7 ints with value 100
//     *   second.assign (first.begin(),first.end()); // a copy of first */
//    void assign ( iterator first, iterator last );
//    void assign ( size_type n, const T& u );

  public:

    virtual T* create(const Idx & arg_idx, const bool insert_at_start=true);

    virtual T* create(const Idx & arg_idx, const T& arg_t, const bool insert_at_start=true);

    virtual T* insert(const Idx & arg_idx, T* arg_t, const bool insert_at_start=true);

    virtual T* at(const std::size_t arg_idx);

    virtual T* at(const Idx & arg_idx);

    virtual const Idx* getIndexAt(const std::size_t arg_idx) const;

    virtual int getIndexNumericAt(const Idx& arg_idx) const;

    virtual int getIndexNumericAt(const T* const arg_node) const;

    virtual const T* at_const(const std::size_t arg_idx) const;

    virtual const T* at_const(const Idx & arg_idx) const;

    virtual bool erase(T* arg_t);

    virtual bool erase(const Idx& arg_idx);

    virtual std::size_t size() const
    { return size_; }

    virtual bool empty() const
    { return (size_ == 0);  }

    virtual bool clear();

    virtual T* operator[](const std::size_t arg_idx)
    { return at(arg_idx); }

  protected:

    SMLNode<Idx,T> *front_;

    SMLNode<Idx,T> *back_;

    SMLNode<Idx,T> null_;

    std::map<Idx, SMLNode<Idx,T>*> map_;

    std::size_t size_;

  public:
    class iterator : public std::iterator<std::forward_iterator_tag, T>
    {
      //To allow : const_iterator x = iterator();
      friend class const_iterator;

      SMLNode<Idx,T> *pos_;
    public:
      explicit iterator(): pos_(NULL){}

      iterator(const iterator& other)
      { pos_ = other.pos_; }

      explicit iterator(SMLNode<Idx,T>* node_ptr)
      { pos_ = node_ptr; }

      iterator&
      operator = (const iterator& other)
      { pos_ = other.pos_; return (*this);  }

      bool
      operator == (const iterator& other)
      { return (pos_ == other.pos_);  }

      bool
      operator != (const iterator& other)
      { return (pos_ != other.pos_);  }

      T&
      operator * ()
      { return *(pos_->data_);  }

      T*
      operator -> ()
      { return pos_->data_;  }

      Idx&
      operator ! ()
      { return *(pos_->id_);  }

      iterator&
      operator ++(int unused)
      {
        if(NULL!= pos_->next_)
        { pos_ = pos_->next_; }
        return *this;
      }

      iterator&
      operator ++()
      {
        if(NULL!= pos_->next_)
        { pos_ = pos_->next_; }
        return *this;
      }

      iterator
      operator +(int offset)
      {
        SMLNode<Idx,T> *ptr = this->pos_;
        for(int i=0; i <offset; ++i)
        {
          if(NULL== ptr->next_) { break; }
          ptr = ptr->next_;
        }

        return iterator(ptr);
      }

      iterator&
      operator --(int unused)
      {
        if(NULL!= pos_)
        { pos_ = pos_->prev_; }
        return *this;
      }

      iterator&
      operator --()
      {
        if(NULL!= pos_)
        { pos_ = pos_->prev_; }
        return *this;
      }

      iterator
      operator -(int offset)
      {
        SMLNode<Idx,T> *ptr = this->pos_;
        for(int i=0; i < offset; ++i)
        {
          if(NULL== ptr->prev_) { break; }
          ptr = ptr->prev_;
        }

        return iterator(ptr);
      }
    };

    class const_iterator : public std::iterator<std::forward_iterator_tag, T>
    {
      const SMLNode<Idx,T> *pos_;
    public:
      explicit const_iterator(): pos_(NULL){}

      const_iterator(const const_iterator& other)
      { pos_ = other.pos_; }

      explicit const_iterator(const SMLNode<Idx,T>* node_ptr)
      { pos_ = node_ptr; }

      const const_iterator& operator = (const const_iterator& other)
      { pos_ = other.pos_; return (*this);  }

      const const_iterator& operator = (const iterator& other)
      { pos_ = static_cast<const SMLNode<Idx,T> *>(other.pos_); return (*this);  }

      bool
      operator == (const const_iterator& other)
      { return (pos_ == other.pos_);  }

      bool
      operator != (const const_iterator& other)
      { return (pos_ != other.pos_);  }

      const T&
      operator * ()
      { return *(pos_->data_);  }

      const T*
      operator -> ()
      { return pos_->data_;  }

      const Idx&
      operator ! ()
      { return *(pos_->id_);  }

      const_iterator&
      operator ++(int unused)
      {
        if(NULL!= pos_->next_)
        { pos_ = pos_->next_; }
        return *this;
      }

      const_iterator&
      operator ++()
      {
        if(NULL!= pos_->next_)
        { pos_ = pos_->next_; }
        return *this;
      }

      const_iterator
      operator +(int offset)
      {
        const SMLNode<Idx,T> *ptr = this->pos_;
        for(int i=0; i <offset; ++i)
        {
          if(NULL== ptr->next_) { break; }
          ptr = ptr->next_;
        }

        return const_iterator(ptr);
      }

      const_iterator&
      operator --(int unused)
      {
        if(NULL!= pos_)
        { pos_ = pos_->prev_; }
        return *this;
      }

      const_iterator&
      operator --()
      {
        if(NULL!= pos_)
        { pos_ = pos_->prev_; }
        return *this;
      }

      const_iterator
      operator -(int offset)
      {
        const SMLNode<Idx,T> *ptr = this->pos_;
        for(int i=0; i <offset; --i)
        {
          if(NULL== ptr) { break; }
          ptr = ptr->prev_;
        }

        return const_iterator(ptr);
      }
    };

    iterator begin()
    {
      if(NULL!=front_){ return iterator(front_);  }
      else{ return iterator(&null_);  }
    }

    const_iterator begin() const
    {
      if(NULL!=front_){ return const_iterator(front_);  }
      else{ return const_iterator(&null_);  }
    }

    iterator end()
    { return iterator(&null_); }

    const_iterator end() const
    { return const_iterator(&null_); }

  public:
    virtual bool sort(const std::vector<Idx> &arg_order);

    virtual bool sort_get_order(std::vector<Idx>& ret_order) const
    {
      if(flag_is_sorted_)
      { ret_order = sorting_order_; return true;  }
      else
      { return false; }
    }

    virtual bool isSorted() const
    { return flag_is_sorted_;  }

  protected:
    std::vector<Idx> sorting_order_;

    bool flag_is_sorted_;
  }; //End of class.

  template <typename Idx, typename T, bool ManageMemory>
  class CMappedPointerList : public CMappedList<Idx,T*>
  {
  public:
    typedef typename CMappedList<Idx,T*>::iterator iterator;
    typedef typename CMappedList<Idx,T*>::const_iterator const_iterator;

    virtual ~CMappedPointerList()
    {
      if(ManageMemory)
      {
        typename CMappedList<Idx,T*>::iterator it,ite;
        for(it = this->begin(), ite = this->end();
            it!=ite; ++it)
        {
          T*& tmp = *it;
          delete tmp;
          tmp = NULL;
        }
      }
    }
  };

  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::deepCopy(const CMappedList<Idx,T>* const arg_pmap)
  {//Deep copy.
    //No need if both are identical
    if(this == arg_pmap)
    { return true;  }

    this->~CMappedList(); //Delete everything in the mappedlist

    if(0 == arg_pmap->size_)
    {
      front_ = NULL; back_ = NULL; null_.prev_ = NULL;
      map_.clear();
      size_ = 0;
    }
    else
    {
      CMappedList<Idx,T>::const_iterator it,ite;
      for(it = arg_pmap->begin(), ite = arg_pmap->end(); it!=ite; ++it)
      {
        T* tmp = CMappedList<Idx,T>::create(!it,*it,false);
        if(NULL == tmp)
        {
#ifdef DEBUG
          std::cerr<<"\nCMappedList<Idx,T>::CMappedList(const CMappedList<Idx,T>& arg_pmap) : ";
          std::cerr<<"ERROR : Deep copy failed to duplicate a node. Resetting mappedlist.";
#endif
          this->~CMappedList();//Reset the mappedlist.
          return false;
        }
      }
    }
    return true;
  }

  template <typename Idx, typename T>
  CMappedList<Idx,T>::~CMappedList()
  {
    SMLNode<Idx,T> *t;

    //Nothing to do if already empty
    if(0==size_) {  return; }

    //Terminate the end (just in case)
    null_.next_ = NULL;

    //Now start deleting everything
    t = front_->next_;
    while(NULL!=t)
    {
      if(NULL!=t->prev_->data_)
      { delete t->prev_->data_;  }
      if(NULL!=t->prev_->id_)
      { delete t->prev_->id_;  }
      delete t->prev_;

      t = t->next_;
    }

    front_ = NULL; back_ = NULL; null_.prev_ = NULL;
    map_.clear();
    size_ = 0;
    flag_is_sorted_ = false;
  }

  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::operator == (const CMappedList<Idx,T>& rhs)
  {
    CMappedList<Idx,T>::const_iterator it, ite, it2, it2e;
    for(it = begin(), ite = end(),
        it2 = rhs.begin(), it2e = rhs.end();
        it!=ite && it2!=it2e; ++it, ++it2)
    {
      if(*it != *it2)
      { return false; }
    }
    //Would exit loop if atleast one was at the end.
    //If both are at the end then the two mapped lists are equal
    if((it == ite) && (it2 == it2e))
    { return true;  }
    //If both aren't at the end, return false;
    else
    { return false; }
  }

  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::operator != (const CMappedList<Idx,T>& rhs)
  { return !(*this == rhs);}


  template <typename Idx, typename T>
  void CMappedList<Idx,T>::swap(CMappedList<Idx,T>& arg_swap_obj)
  {
    //Be lazy
    CMappedList<Idx,T> *lhs, *rhs;
    if(size_ >= arg_swap_obj.size_)
    { lhs = this; rhs = &arg_swap_obj;  }
    else
    { lhs = &arg_swap_obj; rhs = this;  }

    //List status.
    SMLNode<Idx,T> *tf = lhs->front_;
    SMLNode<Idx,T> *tb = lhs->back_;
    std::map<Idx, SMLNode<Idx,T>*> tmap(lhs->map_);
    size_t ts = lhs->size_;

    //Sorting status
    bool tmp_lhs_sorted = lhs->flag_is_sorted_;
    std::vector<Idx> tmp_lhs_sorting_order;
    if(lhs->flag_is_sorted_)
    { tmp_lhs_sorting_order = lhs->sorting_order_;  }

    //Copy list status
    lhs->front_ = rhs->front_;
    lhs->back_ = rhs->back_;
    lhs->map_ = rhs->map_;
    lhs->size_ = rhs->size_;
    lhs->null_.prev_ = lhs->back_;
    if(0 < lhs->size_) {  lhs->back_->next_ = &(lhs->null_);  }

    //Copy sorting status
    lhs->flag_is_sorted_ = rhs->flag_is_sorted_;
    if(lhs->flag_is_sorted_)
    { lhs->sorting_order_ = rhs->sorting_order_;  }
    else { lhs->sorting_order_.clear();  }

    //Copy list status from tmp
    rhs->front_ = tf;
    rhs->back_ = tb;
    rhs->map_ = tmap;
    rhs->size_ = ts;
    rhs->null_.prev_ = rhs->back_;
    if(0 < rhs->size_) {  rhs->back_->next_ = &(rhs->null_);  }

    //Copy sorting status from tmp
    rhs->flag_is_sorted_ = tmp_lhs_sorted;
    if(rhs->flag_is_sorted_)
    { rhs->sorting_order_ = tmp_lhs_sorting_order;  }
    else { rhs->sorting_order_.clear();  }
  }

  template <typename Idx, typename T>
  T* CMappedList<Idx,T>::create(const Idx & arg_idx, const bool insert_at_start)
  { return CMappedList<Idx,T>::create(arg_idx,T(),insert_at_start); }

  template <typename Idx, typename T>
  T* CMappedList<Idx,T>::create(const Idx & arg_idx, const T& arg_t, const bool insert_at_start)
  {
    SMLNode<Idx,T> * tmp = new SMLNode<Idx,T>();

    if(NULL==tmp) //Memory not allocated
    { return NULL; }

    //Make sure the idx hasn't already been registered.
    if(map_.find(arg_idx) != map_.end())
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedList<Idx,T>::create() ERROR : Idx exists. Tried to add duplicate entry";
#endif
      return NULL;
    }

    tmp->data_ = new T(arg_t);
    tmp->id_ = new Idx(arg_idx);

    if(0 == size_)
    {
      back_ = tmp;
      front_ = tmp;
      front_->prev_ = NULL;
      front_->next_ = &null_;
      null_.prev_ = back_;
      tmp = NULL;
    }
    else if(insert_at_start)
    {
      tmp->next_ = front_;
      front_->prev_ = tmp;
      front_ = tmp;
      front_->prev_ = NULL;
      tmp = NULL;
    }
    else
    {
      back_->next_ = tmp;
      tmp->next_ = &null_;
      tmp->prev_ = back_;
      back_ = tmp;
      null_.prev_ = back_;
      back_->next_ = &null_;
      tmp = NULL;
    }

    size_++;

    map_.insert( std::pair<Idx, SMLNode<Idx,T> *>(arg_idx, front_) );
    flag_is_sorted_ = false;

    return front_->data_;
  }

  template <typename Idx, typename T>
  T* CMappedList<Idx,T>::insert(const Idx & arg_idx, T* arg_t, const bool insert_at_start)
  {
    SMLNode<Idx,T> * tmp = new SMLNode<Idx,T>();

    if(NULL==tmp) //Memory not allocated
    { return NULL; }

    //Make sure the idx hasn't already been registered.
    if(map_.find(arg_idx) != map_.end())
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedList<Idx,T>::create() ERROR : Idx exists. Tried to add duplicate entry";
#endif
      return NULL;
    }

    tmp->data_ = arg_t;
    tmp->id_ = new Idx(arg_idx);

    if(0 == size_)
    {
      back_ = tmp;
      front_ = tmp;
      front_->prev_ = NULL;
      front_->next_ = &null_;
      null_.prev_ = back_;
      tmp = NULL;
    }
    else if(insert_at_start)
    {
      tmp->next_ = front_;
      front_->prev_ = tmp;
      front_ = tmp;
      front_->prev_ = NULL;
      tmp = NULL;
    }
    else
    {
      back_->next_ = tmp;
      tmp->next_ = &null_;
      tmp->prev_ = back_;
      back_ = tmp;
      null_.prev_ = back_;
      back_->next_ = &null_;
      tmp = NULL;
    }

    size_++;

    map_.insert( std::pair<Idx, SMLNode<Idx,T> *>(arg_idx, front_) );
    flag_is_sorted_ = false;

    return front_->data_;
  }

  template <typename Idx, typename T>
  T* CMappedList<Idx,T>::at(const std::size_t arg_idx)
  {
    if(NULL==front_)
    { return NULL;  }
    else
    {
      if(arg_idx > size_)
      { return NULL; }
      SMLNode<Idx,T> * t = front_;

      for(std::size_t i=0; i<arg_idx; ++i)
      {
#ifdef DEBUG
        assert(i<=size_);
#endif

        if(NULL==t)
        { return NULL;  }
        t = t->next_;
      }
      if(NULL==t)
      { return NULL;  }

      return t->data_;
    }
  }

  template <typename Idx, typename T>
  T* CMappedList<Idx,T>::at(const Idx & arg_idx)
  {
    if(NULL==front_)
    { return NULL;  }
    else
    {
      if(map_.find(arg_idx) == map_.end())
      {
        return NULL;
      }

      SMLNode<Idx,T> * t = map_[arg_idx];

      if(NULL==t)
      { return NULL;  }
      else
      { return t->data_;  }
    }
  }

  template <typename Idx, typename T>
  const Idx* CMappedList<Idx,T>::getIndexAt(const std::size_t arg_idx) const
  {
    if(NULL==front_)
    { return NULL;  }
    else
    {
      if(arg_idx > size_)
      { return NULL; }
      SMLNode<Idx,T> * t = front_;

      for(std::size_t i=0; i<arg_idx; ++i)
      {
#ifdef DEBUG
        assert(i<=size_);
#endif

        if(NULL==t)
        { return NULL;  }
        t = t->next_;
      }
      if(NULL==t)
      { return NULL;  }

      return t->id_;
    }
  }

  template <typename Idx, typename T>
  int CMappedList<Idx,T>::getIndexNumericAt(const Idx& arg_idx) const
  {
    const T *tdes = at_const(arg_idx);
    return getIndexNumericAt(tdes);
  }

  template <typename Idx, typename T>
  int CMappedList<Idx,T>::getIndexNumericAt(const T* const arg_node) const
  {
    if(NULL == arg_node) { return -1; }

    SMLNode<Idx,T> *t = front_;

    int idx = 0;
    while(t->data_ != arg_node && NULL!=t)
    { t = t->next_; idx++;  }

    if(NULL == t){idx = -1;}

    return idx;
  }


  template <typename Idx, typename T>
  const T* CMappedList<Idx,T>::at_const(const std::size_t arg_idx) const
  {
    if(NULL==front_)
    { return NULL;  }
    else
    {
      if(arg_idx > size_)
      { return NULL; }
      const SMLNode<Idx,T> * t = front_;

      for(std::size_t i=0; i<arg_idx; ++i)
      {
#ifdef DEBUG
        assert(i<=size_);
#endif

        if(NULL==t)
        { return NULL;  }
        t = t->next_;
      }
      if(NULL==t)
      { return NULL;  }

      return (const T*) t->data_;
    }
  }

  template <typename Idx, typename T>
  const T* CMappedList<Idx,T>::at_const(const Idx & arg_idx) const
  {
    if(NULL==front_)
    { return NULL;  }
    else
    {
      if(map_.find(arg_idx) == map_.end())
      {
        return NULL;
      }

      const SMLNode<Idx,T> * t = map_.at(arg_idx);

      if(NULL==t)
      { return NULL;  }
      else
      { return (const T*) t->data_;  }
    }
  }


  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::erase(T* arg_t)
  {
    if((NULL==front_) || (NULL==arg_t))
    { return false;  }

    SMLNode<Idx,T> * t, *tpre;

    //Head is a special case
    if(front_->data_ == arg_t)
    {
      t = front_;
      front_ = front_->next_;

      if(NULL!= t->data_)
      {
        delete t->data_;
        if(NULL!= t->id_)
        {
          map_.erase(*(t->id_));
          delete t->id_;
        }
        delete t;
        size_--;

        if(0 == size_)
        { back_ = NULL; null_.prev_=NULL; }

        flag_is_sorted_ = false;

        return true; // Deleted head.
      }

      return false;//Head was NULL --> Error condition.
    }
    else
    {
      //The head doesn't match.
      tpre = front_;
      t = front_->next_;

      //Find the node
      while(NULL!=t)
      {
        if(t->data_ == arg_t)
        {
          tpre->next_ = t->next_;
          if(NULL!= t->data_)
          {
            delete t->data_;
            if(NULL!= t->id_)
            {
              map_.erase(*(t->id_));
              delete t->id_;
            }
            delete t;
            size_--;

            if(0 == size_)
            { back_ = NULL; null_.prev_=NULL; }

            flag_is_sorted_ = false;

            return true; // Deleted node.
          }
          else
          { return false; }//Node to delete was NULL --> Error condition.
        }
        tpre = t;
        t = t->next_;
      }
      return false; // Didn't delete anything.
    }//End of if/else
  }



  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::erase(const Idx& arg_idx)
  {
    if(0>=size_)
    { return false;  }

    //Make sure the node exists
    if(map_.find(arg_idx) == map_.end())
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedList<Idx,T>::erase() WARNING : Tried to erase a nonexistent entry";
#endif
      return false;
    }

    SMLNode<Idx,T> * node = map_[arg_idx];

    if(1==size_)
    {
      if(front_!=node) { return false; } //This should never happen when Size 1 + idx exists.

      if(NULL!= front_->data_)
      { delete front_->data_; }
      if(NULL!= front_->id_)
      { delete front_->id_;  }
      delete front_;

      front_ = NULL; back_ = NULL; null_.prev_ = NULL;
      node = NULL;
    }
    else
    {//At least two nodes. Remove the node
      if(NULL!= node->data_)
      { delete node->data_; }
      if(NULL!= node->id_)
      { delete node->id_;  }

      if(front_ == node)
      {
        front_ = front_->next_;
        front_->prev_ = NULL;
      }
      else if(back_ == node)
      {
        back_ = back_->prev_;
        back_->next_ = &null_;
        null_.prev_ = back_;
      }
      else
      {
        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;
      }

      delete node;
      node = NULL;
    }

    size_--;
    map_.erase(arg_idx);
    flag_is_sorted_ = false;

    return true; // Deleted head.
  }

  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::clear()
  {
    SMLNode<Idx,T> *tpre;
    tpre = front_;

    if(tpre == NULL)
    {
      size_=0;
      flag_is_sorted_ = false;
      return true;
    } //Nothing in the list.

    front_ = front_->next_;

    while(&null_ != tpre)
    {
      if(NULL!=tpre->data_)
      { delete tpre->data_; }
      if(NULL!=tpre->id_)
      { delete tpre->id_; }
      delete tpre;

      tpre = front_;
      if(&null_ == tpre)//Reached the end.
      { break; }
      front_ = front_->next_;
    }

    size_=0;
    front_ = NULL; back_ = NULL; null_.prev_ = NULL;
    map_.clear(); // Clear the map.
    flag_is_sorted_ = false; //Not ordered anymore
    return true;
  }

  template <typename Idx, typename T>
  bool CMappedList<Idx,T>::sort(const std::vector<Idx> &arg_order)
  {
    if(1>=size_)
    {//Already sorted.
      flag_is_sorted_ = true;
      sorting_order_ = arg_order;
      return true;
    }//Now we know for sure that there are atleast 2 elements, and that front, and back are set.

    // Check that size matches the passed order
    if(arg_order.size() != size_)
    {
#ifdef DEBUG
      std::cout<<"\nCMappedList<Idx,T>::sort() ERROR : Number of indices in passed order doesn't match mapped list.";
#endif
      return false;
    }

    //First check all the indices actually appear in the list.
    typename std::vector<Idx>::const_iterator it,ite;
    for(it = arg_order.begin(), ite = arg_order.end(); it!=ite; ++it)
    {
      T* ptr = this->at(*it);
      if(NULL == ptr)
      {
#ifdef DEBUG
      std::cout<<"\nCMappedList<Idx,T>::sort() ERROR : Passed order contains invalid index element.";
#endif
        return false;
      }
    }

    // Verified that all the elements are in the mapped list
    // So proceed to insertion sort.
    for(it = arg_order.begin(), ite = arg_order.end(); it!=ite; ++it)
    {
      // Find the node, starting from idx 0 to end.
      SMLNode<Idx,T>* node = map_[*it]; //Idx is already tested to exist in the map.

      if(node==back_) { continue;   } //Nothing to do. Node is already in the right place.

      // Detach the node from the list.
      if(node==front_)
      {
        node->next_->prev_ = NULL;
        front_ = node->next_;
      }
      else
      {
        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;
      }

      // Re-add the node at the end.
      back_->next_ = node;
      node->prev_ = back_;
      back_ = node;
      null_.prev_ = node;
      node->next_ = &null_;
    }

    flag_is_sorted_ = true;
    sorting_order_ = arg_order;
    return true;
  }
}

#endif /* CMAPPEDLIST_HPP_ */