williamr@2: /* Copyright 2003-2005 Joaquín M López Muñoz.
williamr@2:  * Distributed under the Boost Software License, Version 1.0.
williamr@2:  * (See accompanying file LICENSE_1_0.txt or copy at
williamr@2:  * http://www.boost.org/LICENSE_1_0.txt)
williamr@2:  *
williamr@2:  * See http://www.boost.org/libs/multi_index for library home page.
williamr@2:  */
williamr@2: 
williamr@2: #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP
williamr@2: #define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP
williamr@2: 
williamr@2: #if defined(_MSC_VER)&&(_MSC_VER>=1200)
williamr@2: #pragma once
williamr@2: #endif
williamr@2: 
williamr@2: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
williamr@2: #include <boost/multi_index/detail/index_matcher.hpp>
williamr@2: #include <boost/noncopyable.hpp>
williamr@2: #include <boost/serialization/nvp.hpp>
williamr@2: #include <cstddef>
williamr@2: 
williamr@2: namespace boost{
williamr@2: 
williamr@2: namespace multi_index{
williamr@2: 
williamr@2: namespace detail{
williamr@2: 
williamr@2: /* index_saver accepts a base sequence of previously saved elements
williamr@2:  * and saves a possibly reordered subsequence in an efficient manner,
williamr@2:  * serializing only the information needed to rearrange the subsequence
williamr@2:  * based on the original order of the base.
williamr@2:  * multi_index_container is in charge of supplying the info about the
williamr@2:  * base sequence, and each index can subsequently save itself using the
williamr@2:  * const interface of index_saver.
williamr@2:  */
williamr@2: 
williamr@2: template<typename Node,typename Allocator>
williamr@2: class index_saver:private noncopyable
williamr@2: {
williamr@2: public:
williamr@2:   index_saver(const Allocator& al,std::size_t size):alg(al,size){}
williamr@2: 
williamr@2:   template<class Archive>
williamr@2:   void add(Node* node,Archive& ar,const unsigned int)
williamr@2:   {
williamr@2:     ar<<serialization::make_nvp("position",*node);
williamr@2:     alg.add(node);
williamr@2:   }
williamr@2: 
williamr@2:   template<class Archive>
williamr@2:   void add_track(Node* node,Archive& ar,const unsigned int)
williamr@2:   {
williamr@2:     ar<<serialization::make_nvp("position",*node);
williamr@2:   }
williamr@2: 
williamr@2:   template<typename IndexIterator,class Archive>
williamr@2:   void save(
williamr@2:     IndexIterator first,IndexIterator last,Archive& ar,
williamr@2:     const unsigned int)const
williamr@2:   {
williamr@2:     /* calculate ordered positions */
williamr@2: 
williamr@2:     alg.execute(first,last);
williamr@2: 
williamr@2:     /* Given a consecutive subsequence of displaced elements
williamr@2:      * x1,...,xn, the following information is serialized:
williamr@2:      *
williamr@2:      *   p0,p1,...,pn,0
williamr@2:      *
williamr@2:      * where pi is a pointer to xi and p0 is a pointer to the element
williamr@2:      * preceding x1. Crealy, from this information is possible to
williamr@2:      * restore the original order on loading time. If x1 is the first
williamr@2:      * element in the sequence, the following is serialized instead:
williamr@2:      *
williamr@2:      *   p1,p1,...,pn,0
williamr@2:      *
williamr@2:      * For each subsequence of n elements, n+2 pointers are serialized.
williamr@2:      * An optimization policy is applied: consider for instance the
williamr@2:      * sequence
williamr@2:      *
williamr@2:      *   a,B,c,D
williamr@2:      * 
williamr@2:      * where B and D are displaced, but c is in its correct position.
williamr@2:      * Applying the schema described above we would serialize 6 pointers:
williamr@2:      *
williamr@2:      *  p(a),p(B),0
williamr@2:      *  p(c),p(D),0
williamr@2:      * 
williamr@2:      * but this can be reduced to 5 pointers by treating c as a displaced
williamr@2:      * element:
williamr@2:      *
williamr@2:      *  p(a),p(B),p(c),p(D),0
williamr@2:      */
williamr@2: 
williamr@2:     std::size_t last_saved=3; /* distance to last pointer saved */
williamr@2:     for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){
williamr@2:       if(!alg.is_ordered(get_node(it))){
williamr@2:         if(last_saved>1)save_node(get_node(prev),ar);
williamr@2:         save_node(get_node(it),ar);
williamr@2:         last_saved=0;
williamr@2:       }
williamr@2:       else if(last_saved==2)save_node(null_node(),ar);
williamr@2:     }
williamr@2:     if(last_saved<=2)save_node(null_node(),ar);
williamr@2: 
williamr@2:     /* marks the end of the serialization info for [first,last) */
williamr@2: 
williamr@2:     save_node(null_node(),ar);
williamr@2:   }
williamr@2: 
williamr@2: private:
williamr@2:   template<typename IndexIterator>
williamr@2:   static Node* get_node(IndexIterator it)
williamr@2:   {
williamr@2:     return it.get_node();
williamr@2:   }
williamr@2: 
williamr@2:   static Node* null_node(){return 0;}
williamr@2: 
williamr@2:   template<typename Archive>
williamr@2:   static void save_node(Node* node,Archive& ar)
williamr@2:   {
williamr@2:     ar<<serialization::make_nvp("pointer",node);
williamr@2:   }
williamr@2: 
williamr@2:   index_matcher::algorithm<Node,Allocator> alg;
williamr@2: };
williamr@2: 
williamr@2: } /* namespace multi_index::detail */
williamr@2: 
williamr@2: } /* namespace multi_index */
williamr@2: 
williamr@2: } /* namespace boost */
williamr@2: 
williamr@2: #endif