Index: lang/cplusplus/boost-supplement/trunk/boost_supplement/random/discrete_distribution.hpp
===================================================================
--- lang/cplusplus/boost-supplement/trunk/boost_supplement/random/discrete_distribution.hpp (revision 5902)
+++ lang/cplusplus/boost-supplement/trunk/boost_supplement/random/discrete_distribution.hpp (revision 5902)
@@ -0,0 +1,182 @@
+/* boost-supplement random/discrete_distribution.hpp header file
+ *
+ * Copyright (C) 2008 Kenta Murata.
+ * 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)
+ *
+ * $Id$
+ * 
+ */
+
+#ifndef BOOST_SUPPLEMENT_DISCRETE_DISTRIBUTION_HPP
+#define BOOST_SUPPLEMENT_DISCRETE_DISTRIBUTION_HPP 1
+
+#include <boost/random/uniform_real.hpp>
+#include <boost/concept_check.hpp>
+
+#include <iterator>
+#include <utility>
+#include <vector>
+
+namespace boost_supplement {
+template<class IntType = long, class RealType = double>
+class discrete_distribution
+{
+public:
+  typedef RealType input_type;
+  typedef IntType result_type;
+
+  typedef typename std::vector<input_type>::const_iterator probability_iterator;
+  typedef typename std::vector<input_type>::const_reverse_iterator probability_reverse_iterator;
+
+  typedef typename std::vector<result_type>::const_iterator alias_iterator;
+  typedef typename std::vector<result_type>::const_reverse_iterator alias_reverse_iterator;
+
+#if !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300)
+  BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer);
+  BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer);
+#endif
+
+private:
+  std::vector<input_type> probabilities_;
+  std::vector<result_type> aliases_;
+
+  template<class RandomAccessIterator>
+  void make_table(RandomAccessIterator first, RandomAccessIterator last,
+                  std::random_access_iterator_tag)
+    {
+      boost::function_requires
+        <boost::RandomAccessIteratorConcept<RandomAccessIterator> >();
+
+      result_type n = std::distance(first, last);
+      aliases_.resize(n, n);
+
+      while (first != last) {
+        probabilities_.push_back(*first - input_type(1.0/n));
+        ++first;
+      }
+
+      BOOST_ASSERT(n == probabilities_.size());
+
+      for (result_type i = 0; i < n; ++i) {
+        result_type j = 0;
+        while (j < n && aliases_[j] < n) ++j;
+
+        result_type min_i(j);
+        result_type max_i(j);
+        input_type min_v(probabilities_[min_i]);
+        input_type max_v(probabilities_[max_i]);
+
+        for (++j; j < n; ++j) {
+          if (aliases_[j] < n) continue;
+          if (probabilities_[j] < min_v) {
+            min_i = j;
+            min_v = probabilities_[j];
+          }
+          else if (probabilities_[j] > max_v) {
+            max_i = j;
+            max_v = probabilities_[j];
+          }
+        }
+
+        if (min_i != max_i) {
+          aliases_[min_i] = max_i;
+          probabilities_[min_i] = input_type(1.0) + min_v*n;
+          probabilities_[max_i] = min_v + max_v;
+        }
+        else {
+          probabilities_[min_i] = 1.0;
+        }
+      }
+    }
+
+  template<class InputIterator>
+  void make_table(InputIterator first, InputIterator last,
+                  std::input_iterator_tag)
+    {
+      boost::function_requires
+        <boost::InputIteratorConcept<InputIterator> >();
+
+      std::vector<input_type> dist(first, last);
+      make_table<typename std::vector<input_type>::iterator>(
+        dist.begin(), dist.end(), std::random_access_iterator_tag());
+    }
+
+  template<class InputIterator>
+  void make_normalized_table(InputIterator first, InputIterator last)
+    {
+      boost::function_requires
+        <boost::InputIteratorConcept<InputIterator> >();
+
+      std::vector<input_type> dist;
+      input_type sum = *first;
+      dist.push_back(*first);
+      while (++first != last) {
+        sum += *first;
+        dist.push_back(*first);
+      }
+      for (typename std::vector<input_type>::iterator i = dist.begin();
+           i != dist.end(); ++i) {
+        *i /= sum;
+      }
+      make_table(dist.begin(), dist.end(),
+                 std::random_access_iterator_tag());
+    }
+
+public:
+  template<class InputIterator>
+  discrete_distribution(InputIterator first, InputIterator last,
+                        bool normalized=false)
+    : probabilities_(), aliases_()
+    {
+      typename std::iterator_traits<InputIterator>::iterator_category ic;
+      if (normalized)
+        make_table(first, last, ic);
+      else
+        make_normalized_table(first, last);
+    }
+
+  result_type num() const { return result_type(probabilities_.size()); }
+
+  // accessor for probabiliies_
+  std::pair<probability_iterator, probability_iterator>
+  probabilities() const {
+    return std::make_pair(probabilities_.begin(), probabilities_.end()); }
+
+  std::pair<probability_reverse_iterator, probability_reverse_iterator>
+  reverse_probabilities() const {
+    return std::make_pair(probabilities_.rbegin(), probabilities_.rend()); }
+
+  // accessor for aliases_
+  std::pair<alias_iterator, alias_iterator>
+  aliases() const {
+    return std::make_pair(aliases_.begin(), aliases_.end()); }
+  std::pair<alias_reverse_iterator, alias_reverse_iterator>
+  reverse_aliases() const {
+    return std::make_pair(aliases_.rbegin(), aliases_.rend()); }
+
+  template<class Engine>
+  result_type operator()(Engine& eng)
+    {
+      boost::uniform_real<input_type> ud;
+      input_type u = ud(eng);
+      result_type x = result_type(u);
+      u -= x;
+      if (probabilities_[x] < u) return x;
+      return aliases_[x];
+    }
+};
+
+}
+
+#endif // ifndef BOOST_SUPPLEMENT_DISCRETE_DISTRIBUTION_HPP
+
+/*
+ * Local Variables:
+ * coding: utf-8
+ * mode: c++
+ * c-basic-offset: 2
+ * indent-tabs-mode: nil
+ * End:
+ */