1 files changed, 248 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp
new file mode 100644
index 0000000..5828137
--- /dev/null
+++ b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp
@@ -0,0 +1,248 @@
+/* Copyright 2003-2008 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)&&(_MSC_VER>=1200)
+#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 <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 &*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