x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
index_matcher.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\multi_index\detail\index_matcher.hpp
Girar
Efecto
Propiedad
Historial
/* Copyright 2003-2007 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_MATCHER_HPP #define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP #if defined(_MSC_VER)&&(_MSC_VER>=1200) #pragma once #endif #include
/* keep it first to prevent nasty warns in MSVC */ #include
#include
#include
#include
#include
namespace boost{ namespace multi_index{ namespace detail{ /* index_matcher compares a sequence of elements against a * base sequence, identifying those elements that belong to the * longest subsequence which is ordered with respect to the base. * For instance, if the base sequence is: * * 0 1 2 3 4 5 6 7 8 9 * * and the compared sequence (not necesarilly the same length): * * 1 4 2 3 0 7 8 9 * * the elements of the longest ordered subsequence are: * * 1 2 3 7 8 9 * * The algorithm for obtaining such a subsequence is called * Patience Sorting, described in ch. 1 of: * Aldous, D., Diaconis, P.: "Longest increasing subsequences: from * patience sorting to the Baik-Deift-Johansson Theorem", Bulletin * of the American Mathematical Society, vol. 36, no 4, pp. 413-432, * July 1999. * http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/ * S0273-0979-99-00796-X.pdf * * This implementation is not fully generic since it assumes that * the sequences given are pointed to by index iterators (having a * get_node() memfun.) */ namespace index_matcher{ /* The algorithm stores the nodes of the base sequence and a number * of "piles" that are dynamically updated during the calculation * stage. From a logical point of view, nodes form an independent * sequence from piles. They are stored together so as to minimize * allocated memory. */ struct entry { entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){} /* node stuff */ void* node; std::size_t pos; entry* previous; bool ordered; struct less_by_node { bool operator()( const entry& x,const entry& y)const { return std::less
()(x.node,y.node); } }; /* pile stuff */ std::size_t pile_top; entry* pile_top_entry; struct less_by_pile_top { bool operator()( const entry& x,const entry& y)const { return x.pile_top
class algorithm_base:private noncopyable { protected: algorithm_base(const Allocator& al,std::size_t size): spc(al,size),size_(size),n(0),sorted(false) { } void add(void* node) { entries()[n]=entry(node,n); ++n; } void begin_algorithm()const { if(!sorted){ std::sort(entries(),entries()+size_,entry::less_by_node()); sorted=true; } num_piles=0; } void add_node_to_algorithm(void* node)const { entry* ent= std::lower_bound( entries(),entries()+size_, entry(node),entry::less_by_node()); /* localize entry */ ent->ordered=false; std::size_t n=ent->pos; /* get its position */ entry dummy(0); dummy.pile_top=n; entry* pile_ent= /* find the first available pile */ std::lower_bound( /* to stack the entry */ entries(),entries()+num_piles, dummy,entry::less_by_pile_top()); pile_ent->pile_top=n; /* stack the entry */ pile_ent->pile_top_entry=ent; /* if not the first pile, link entry to top of the preceding pile */ if(pile_ent>&entries()[0]){ ent->previous=(pile_ent-1)->pile_top_entry; } if(pile_ent==&entries()[num_piles]){ /* new pile? */ ++num_piles; } } void finish_algorithm()const { if(num_piles>0){ /* Mark those elements which are in their correct position, i.e. those * belonging to the longest increasing subsequence. These are those * elements linked from the top of the last pile. */ entry* ent=entries()[num_piles-1].pile_top_entry; for(std::size_t n=num_piles;n--;){ ent->ordered=true; ent=ent->previous; } } } bool is_ordered(void * node)const { return std::lower_bound( entries(),entries()+size_, entry(node),entry::less_by_node())->ordered; } private: entry* entries()const{return &*spc.data();} auto_space
spc; std::size_t size_; std::size_t n; mutable bool sorted; mutable std::size_t num_piles; }; /* The algorithm has three phases: * - Initialization, during which the nodes of the base sequence are added. * - Execution. * - Results querying, through the is_ordered memfun. */ template
class algorithm:private algorithm_base
{ typedef algorithm_base
super; public: algorithm(const Allocator& al,std::size_t size):super(al,size){} void add(Node* node) { super::add(node); } template
void execute(IndexIterator first,IndexIterator last)const { super::begin_algorithm(); for(IndexIterator it=first;it!=last;++it){ add_node_to_algorithm(get_node(it)); } super::finish_algorithm(); } bool is_ordered(Node* node)const { return super::is_ordered(node); } private: void add_node_to_algorithm(Node* node)const { super::add_node_to_algorithm(node); } template
static Node* get_node(IndexIterator it) { return static_cast
(it.get_node()); } }; } /* namespace multi_index::detail::index_matcher */ } /* namespace multi_index::detail */ } /* namespace multi_index */ } /* namespace boost */ #endif
index_matcher.hpp
Dirección de la página
Dirección del archivo
Anterior
18/44
Siguiente
Descargar
( 6 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.