/* Copyright 2003-2005 Joaquín M López Muñoz.

 * Distributed under the Boost Software License, Version 1.0.

 * (See accompanying file LICENSE_1_0.txt or copy at

 * http://www.boost.org/LICENSE_1_0.txt)

 *

 * See http://www.boost.org/libs/multi_index for library home page.

 */

#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP

#define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)

#pragma once

#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */

#include <boost/multi_index/detail/index_matcher.hpp>

#include <boost/noncopyable.hpp>

#include <boost/serialization/nvp.hpp>

#include <cstddef>

namespace boost{

namespace multi_index{

namespace detail{

/* index_saver accepts a base sequence of previously saved elements

 * and saves a possibly reordered subsequence in an efficient manner,

 * serializing only the information needed to rearrange the subsequence

 * based on the original order of the base.

 * multi_index_container is in charge of supplying the info about the

 * base sequence, and each index can subsequently save itself using the

 * const interface of index_saver.

 */

template<typename Node,typename Allocator>

class index_saver:private noncopyable

{

public:

  index_saver(const Allocator& al,std::size_t size):alg(al,size){}

  template<class Archive>

  void add(Node* node,Archive& ar,const unsigned int)

  {

    ar<<serialization::make_nvp("position",*node);

    alg.add(node);

  }

  template<class Archive>

  void add_track(Node* node,Archive& ar,const unsigned int)

  {

    ar<<serialization::make_nvp("position",*node);

  }

  template<typename IndexIterator,class Archive>

  void save(

    IndexIterator first,IndexIterator last,Archive& ar,

    const unsigned int)const

  {

    /* calculate ordered positions */

    alg.execute(first,last);

    /* Given a consecutive subsequence of displaced elements

     * x1,...,xn, the following information is serialized:

     *

     *   p0,p1,...,pn,0

     *

     * where pi is a pointer to xi and p0 is a pointer to the element

     * preceding x1. Crealy, from this information is possible to

     * restore the original order on loading time. If x1 is the first

     * element in the sequence, the following is serialized instead:

     *

     *   p1,p1,...,pn,0

     *

     * For each subsequence of n elements, n+2 pointers are serialized.

     * An optimization policy is applied: consider for instance the

     * sequence

     *

     *   a,B,c,D

     * 

     * where B and D are displaced, but c is in its correct position.

     * Applying the schema described above we would serialize 6 pointers:

     *

     *  p(a),p(B),0

     *  p(c),p(D),0

     * 

     * but this can be reduced to 5 pointers by treating c as a displaced

     * element:

     *

     *  p(a),p(B),p(c),p(D),0

     */

    std::size_t last_saved=3; /* distance to last pointer saved */

    for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){

      if(!alg.is_ordered(get_node(it))){

        if(last_saved>1)save_node(get_node(prev),ar);

        save_node(get_node(it),ar);

        last_saved=0;

      }

      else if(last_saved==2)save_node(null_node(),ar);

    }

    if(last_saved<=2)save_node(null_node(),ar);

    /* marks the end of the serialization info for [first,last) */

    save_node(null_node(),ar);

  }

private:

  template<typename IndexIterator>

  static Node* get_node(IndexIterator it)

  {

    return it.get_node();

  }

  static Node* null_node(){return 0;}

  template<typename Archive>

  static void save_node(Node* node,Archive& ar)

  {

    ar<<serialization::make_nvp("pointer",node);

  }

  index_matcher::algorithm<Node,Allocator> alg;

};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif