FM / detail

/usr/include/boost/multi_index/detail

Name	Size	Mode	Actions
access_specifier.hpp	2115	0644	edit dl rm
adl_swap.hpp	858	0644	edit dl rm
allocator_traits.hpp	4957	0644	edit dl rm
archive_constructed.hpp	1991	0644	edit dl rm
auto_space.hpp	2907	0644	edit dl rm
base_type.hpp	1981	0644	edit dl rm
bidir_node_iterator.hpp	2584	0644	edit dl rm
bucket_array.hpp	7730	0644	edit dl rm
cons_stdtuple.hpp	2206	0644	edit dl rm
converter.hpp	1372	0644	edit dl rm
copy_map.hpp	4713	0644	edit dl rm
define_if_constexpr_macro.hpp	876	0644	edit dl rm
do_not_copy_elements_tag.hpp	762	0644	edit dl rm
duplicates_iterator.hpp	2574	0644	edit dl rm
hash_index_args.hpp	3066	0644	edit dl rm
hash_index_iterator.hpp	4407	0644	edit dl rm
hash_index_node.hpp	23170	0644	edit dl rm
has_tag.hpp	915	0644	edit dl rm
header_holder.hpp	1296	0644	edit dl rm
ignore_wstrict_aliasing.hpp	548	0644	edit dl rm
index_base.hpp	9189	0644	edit dl rm
index_loader.hpp	3472	0644	edit dl rm
index_matcher.hpp	6134	0644	edit dl rm
index_node_base.hpp	3500	0644	edit dl rm
index_saver.hpp	3787	0644	edit dl rm
invariant_assert.hpp	578	0644	edit dl rm
is_function.hpp	1439	0644	edit dl rm
is_index_list.hpp	978	0644	edit dl rm
is_transparent.hpp	3616	0644	edit dl rm
iter_adaptor.hpp	7591	0644	edit dl rm
modify_key_adaptor.hpp	1066	0644	edit dl rm
node_handle.hpp	6249	0644	edit dl rm
node_type.hpp	1783	0644	edit dl rm
no_duplicate_tags.hpp	2213	0644	edit dl rm
ord_index_args.hpp	2363	0644	edit dl rm
ord_index_impl.hpp	49850	0644	edit dl rm
ord_index_impl_fwd.hpp	4024	0644	edit dl rm
ord_index_node.hpp	20137	0644	edit dl rm
ord_index_ops.hpp	7629	0644	edit dl rm
promotes_arg.hpp	1886	0644	edit dl rm
raw_ptr.hpp	1187	0644	edit dl rm
restore_wstrict_aliasing.hpp	457	0644	edit dl rm
rnd_index_loader.hpp	4886	0644	edit dl rm
rnd_index_node.hpp	6453	0644	edit dl rm
rnd_index_ops.hpp	6003	0644	edit dl rm
rnd_index_ptr_array.hpp	3499	0644	edit dl rm
rnd_node_iterator.hpp	3135	0644	edit dl rm
rnk_index_ops.hpp	8621	0644	edit dl rm
safe_mode.hpp	18103	0644	edit dl rm
scope_guard.hpp	13703	0644	edit dl rm
seq_index_node.hpp	5455	0644	edit dl rm
seq_index_ops.hpp	6152	0644	edit dl rm
serialization_version.hpp	1801	0644	edit dl rm
uintptr_type.hpp	2446	0644	edit dl rm
unbounded.hpp	1556	0644	edit dl rm
undef_if_constexpr_macro.hpp	459	0644	edit dl rm
value_compare.hpp	1240	0644	edit dl rm
vartempl_support.hpp	10965	0644	edit dl rm

Edit: /usr/include/boost/multi_index/detail/index_matcher.hpp (6134B)

/* Copyright 2003-2015 Joaquin M Lopez Munoz.
 * 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)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/noncopyable.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/raw_ptr.hpp>
#include <cstddef>
#include <functional>

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<void*>()(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<y.pile_top;
    }
  };
};

/* common code operating on void *'s */

template<typename Allocator>
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 raw_ptr<entry*>(spc.data());}

auto_space<entry,Allocator> 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<typename Node,typename Allocator>
class algorithm:private algorithm_base<Allocator>
{
  typedef algorithm_base<Allocator> super;

public:
  algorithm(const Allocator& al,std::size_t size):super(al,size){}

void add(Node* node)
  {
    super::add(node);
  }

template<typename IndexIterator>
  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<typename IndexIterator>
  static Node* get_node(IndexIterator it)
  {
    return static_cast<Node*>(it.get_node());
  }
};

} /* namespace multi_index::detail::index_matcher */

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif

cmd: