[boost-doc-zh] r406 committed - 升级至1.43.0，第5批，libs/目录r-s子目录
- From: boost-doc-zh@xxxxxxxxxxxxxx
- To: boost-doc-zh-notify@xxxxxxxxxxxxx
- Date: Mon, 31 May 2010 08:12:48 +0000
Revision: 406
Author: alai04
Date: Mon May 31 00:54:22 2010
Log: 升级至1.43.0，第5批，libs/目录r-s子目录
http://code.google.com/p/boost-doc-zh/source/detail?r=406
Added:
/trunk/libs/random/build
/trunk/libs/random/build/Jamfile.v2
/trunk/libs/random/doc
/trunk/libs/random/doc/Jamfile.v2
/trunk/libs/random/doc/concepts.qbk
/trunk/libs/random/doc/distribution_performance_linux.qbk
/trunk/libs/random/doc/distribution_performance_windows.qbk
/trunk/libs/random/doc/distributions.qbk
/trunk/libs/random/doc/generator_defs.qbk
/trunk/libs/random/doc/generator_performance_linux.qbk
/trunk/libs/random/doc/generator_performance_windows.qbk
/trunk/libs/random/doc/generators.qbk
/trunk/libs/random/doc/nondet_random.qbk
/trunk/libs/random/doc/performance.qbk
/trunk/libs/random/doc/performance_data.qbk
/trunk/libs/random/doc/random.qbk
/trunk/libs/random/doc/random_number_generator.qbk
/trunk/libs/random/doc/tutorial.qbk
/trunk/libs/random/example
/trunk/libs/random/example/Jamfile.v2
/trunk/libs/random/example/die.cpp
/trunk/libs/random/example/random_demo.cpp
/trunk/libs/random/example/weighted_die.cpp
/trunk/libs/random/extra
/trunk/libs/random/extra/Jamfile.v2
/trunk/libs/random/extra/haertel.hpp
/trunk/libs/random/extra/test_haertel.cpp
/trunk/libs/random/performance
/trunk/libs/random/performance/generate_table.cpp
/trunk/libs/random/performance/nondet_random_speed.cpp
/trunk/libs/random/performance/random_speed.cpp
/trunk/libs/random/src
/trunk/libs/random/src/random_device.cpp
/trunk/libs/random/test
/trunk/libs/random/test/Jamfile.v2
/trunk/libs/random/test/histogram.cpp
/trunk/libs/random/test/instantiate.cpp
/trunk/libs/random/test/integrate.hpp
/trunk/libs/random/test/random_test.cpp
/trunk/libs/random/test/statistic_tests.cpp
/trunk/libs/random/test/statistic_tests.hpp
/trunk/libs/random/test/validate.cpp
/trunk/libs/range/doc/Jamfile.v2
/trunk/libs/range/doc/boost_range.qbk
/trunk/libs/range/doc/concepts.qbk
/trunk/libs/range/doc/example.cpp
/trunk/libs/range/doc/examples.qbk
/trunk/libs/range/doc/faq.qbk
/trunk/libs/range/doc/headers.qbk
/trunk/libs/range/doc/history_ack.qbk
/trunk/libs/range/doc/html
/trunk/libs/range/doc/html/index.html
/trunk/libs/range/doc/html/quickbook_HTML.manifest
/trunk/libs/range/doc/html/range
/trunk/libs/range/doc/html/range/concepts
/trunk/libs/range/doc/html/range/concepts/bidirectional_range.html
/trunk/libs/range/doc/html/range/concepts/concept_checking.html
/trunk/libs/range/doc/html/range/concepts/forward_range.html
/trunk/libs/range/doc/html/range/concepts/overview.html
/trunk/libs/range/doc/html/range/concepts/random_access_range.html
/trunk/libs/range/doc/html/range/concepts/single_pass_range.html
/trunk/libs/range/doc/html/range/concepts.html
/trunk/libs/range/doc/html/range/examples.html
/trunk/libs/range/doc/html/range/faq.html
/trunk/libs/range/doc/html/range/history_ack
/trunk/libs/range/doc/html/range/history_ack.html
/trunk/libs/range/doc/html/range/introduction.html
/trunk/libs/range/doc/html/range/library_headers
/trunk/libs/range/doc/html/range/library_headers/adaptors.html
/trunk/libs/range/doc/html/range/library_headers/algorithm.html
/trunk/libs/range/doc/html/range/library_headers/algorithm_extensions.html
/trunk/libs/range/doc/html/range/library_headers/general.html
/trunk/libs/range/doc/html/range/library_headers.html
/trunk/libs/range/doc/html/range/mfc_atl
/trunk/libs/range/doc/html/range/mfc_atl/atl_ranges.html
/trunk/libs/range/doc/html/range/mfc_atl/const_ranges.html
/trunk/libs/range/doc/html/range/mfc_atl/mfc_ranges.html
/trunk/libs/range/doc/html/range/mfc_atl/references.html
/trunk/libs/range/doc/html/range/mfc_atl/requirements.html
/trunk/libs/range/doc/html/range/mfc_atl.html
/trunk/libs/range/doc/html/range/portability.html
/trunk/libs/range/doc/html/range/reference
/trunk/libs/range/doc/html/range/reference/adaptors
/trunk/libs/range/doc/html/range/reference/adaptors/adaptors_general_requirements.html
/trunk/libs/range/doc/html/range/reference/adaptors/adaptors_introduction.html
/trunk/libs/range/doc/html/range/reference/adaptors/adaptors_reference.html
/trunk/libs/range/doc/html/range/reference/adaptors/adaptors_synopsis.html
/trunk/libs/range/doc/html/range/reference/adaptors/general_requirements.html
/trunk/libs/range/doc/html/range/reference/adaptors/introduction.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference
/trunk/libs/range/doc/html/range/reference/adaptors/reference/adjacent_filtered.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/copied.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/filtered.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/indexed.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/indirected.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/map_keys.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/map_values.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/replaced.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/replaced_if.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/reversed.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/sliced.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/strided.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/tokenized.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/transformed.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference/uniqued.html
/trunk/libs/range/doc/html/range/reference/adaptors/reference.html
/trunk/libs/range/doc/html/range/reference/adaptors.html
/trunk/libs/range/doc/html/range/reference/algorithms
/trunk/libs/range/doc/html/range/reference/algorithms/heap
/trunk/libs/range/doc/html/range/reference/algorithms/heap/make_heap.html
/trunk/libs/range/doc/html/range/reference/algorithms/heap/pop_heap.html
/trunk/libs/range/doc/html/range/reference/algorithms/heap/push_heap.html
/trunk/libs/range/doc/html/range/reference/algorithms/heap/sort_heap.html
/trunk/libs/range/doc/html/range/reference/algorithms/heap.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/copy_backward.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/fill.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/fill_n.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/generate.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/inplace_merge.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/merge.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/nth_element.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/partial_sort.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/partition.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/random_shuffle.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/remove.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/remove_copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/remove_copy_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/remove_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/replace.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/replace_copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/replace_copy_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/replace_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/reverse.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/reverse_copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/rotate.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/rotate_copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/sort.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/stable_partition.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/stable_sort.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/swap_ranges.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/transform.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/unique.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating/unique_copy.html
/trunk/libs/range/doc/html/range/reference/algorithms/mutating.html
/trunk/libs/range/doc/html/range/reference/algorithms/new
/trunk/libs/range/doc/html/range/reference/algorithms/new/copy_n.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/erase.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/for_each.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/insert.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/iota.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/is_sorted.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/overwrite.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/push_back.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/push_front.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/remove_erase.html
/trunk/libs/range/doc/html/range/reference/algorithms/new/remove_erase_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/new.html
/trunk/libs/range/doc/html/range/reference/algorithms/non.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/adjacent_find.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/binary_search.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/count.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/count_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/equal.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/equal_range.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/find.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/find_end.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/find_first_of.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/find_if.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/for_each.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/lexicographical_compare.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/lower_bound.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/max_element.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/min_element.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/mismatch.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/search.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/search_n.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating/upper_bound.html
/trunk/libs/range/doc/html/range/reference/algorithms/non_mutating.html
/trunk/libs/range/doc/html/range/reference/algorithms/numeric
/trunk/libs/range/doc/html/range/reference/algorithms/numeric/accumulate.html
/trunk/libs/range/doc/html/range/reference/algorithms/numeric/adjacent_difference.html
/trunk/libs/range/doc/html/range/reference/algorithms/numeric/inner_product.html
/trunk/libs/range/doc/html/range/reference/algorithms/numeric/partial_sum.html
/trunk/libs/range/doc/html/range/reference/algorithms/numeric.html
/trunk/libs/range/doc/html/range/reference/algorithms/permutation
/trunk/libs/range/doc/html/range/reference/algorithms/permutation/next_permutation.html
/trunk/libs/range/doc/html/range/reference/algorithms/permutation/prev_permutation.html
/trunk/libs/range/doc/html/range/reference/algorithms/permutation.html
/trunk/libs/range/doc/html/range/reference/algorithms/set
/trunk/libs/range/doc/html/range/reference/algorithms/set/includes.html
/trunk/libs/range/doc/html/range/reference/algorithms/set/set_difference.html
/trunk/libs/range/doc/html/range/reference/algorithms/set/set_intersection.html
/trunk/libs/range/doc/html/range/reference/algorithms/set/set_symmetric_difference.html
/trunk/libs/range/doc/html/range/reference/algorithms/set/set_union.html
/trunk/libs/range/doc/html/range/reference/algorithms/set.html
/trunk/libs/range/doc/html/range/reference/algorithms.html
/trunk/libs/range/doc/html/range/reference/concept_implementation
/trunk/libs/range/doc/html/range/reference/concept_implementation/overview.html
/trunk/libs/range/doc/html/range/reference/concept_implementation/semantics
/trunk/libs/range/doc/html/range/reference/concept_implementation/semantics/functions.html
/trunk/libs/range/doc/html/range/reference/concept_implementation/semantics/metafunctions.html
/trunk/libs/range/doc/html/range/reference/concept_implementation/semantics.html
/trunk/libs/range/doc/html/range/reference/concept_implementation/synopsis.html
/trunk/libs/range/doc/html/range/reference/concept_implementation.html
/trunk/libs/range/doc/html/range/reference/extending
/trunk/libs/range/doc/html/range/reference/extending/method_1.html
/trunk/libs/range/doc/html/range/reference/extending/method_2.html
/trunk/libs/range/doc/html/range/reference/extending/method_3
/trunk/libs/range/doc/html/range/reference/extending/method_3/method_3_1.html
/trunk/libs/range/doc/html/range/reference/extending/method_3/method_3_2.html
/trunk/libs/range/doc/html/range/reference/extending/method_3.html
/trunk/libs/range/doc/html/range/reference/extending.html
/trunk/libs/range/doc/html/range/reference/range_algorithm.html
/trunk/libs/range/doc/html/range/reference/ranges
/trunk/libs/range/doc/html/range/reference/ranges/counting_range.html
/trunk/libs/range/doc/html/range/reference/ranges/introduction.html
/trunk/libs/range/doc/html/range/reference/ranges/irange.html
/trunk/libs/range/doc/html/range/reference/ranges/istream_range.html
/trunk/libs/range/doc/html/range/reference/ranges/reference
/trunk/libs/range/doc/html/range/reference/ranges/reference/counting_range.html
/trunk/libs/range/doc/html/range/reference/ranges/reference/irange.html
/trunk/libs/range/doc/html/range/reference/ranges/reference/istream_range.html
/trunk/libs/range/doc/html/range/reference/ranges/reference.html
/trunk/libs/range/doc/html/range/reference/ranges.html
/trunk/libs/range/doc/html/range/reference/semantics
/trunk/libs/range/doc/html/range/reference/semantics/functions.html
/trunk/libs/range/doc/html/range/reference/semantics/metafunctions.html
/trunk/libs/range/doc/html/range/reference/synopsis.html
/trunk/libs/range/doc/html/range/reference/utilities
/trunk/libs/range/doc/html/range/reference/utilities/iterator_range.html
/trunk/libs/range/doc/html/range/reference/utilities/join.html
/trunk/libs/range/doc/html/range/reference/utilities/sub_range.html
/trunk/libs/range/doc/html/range/reference/utilities.html
/trunk/libs/range/doc/html/range/reference.html
/trunk/libs/range/doc/html/range/style_guide.html
/trunk/libs/range/doc/html/range/upgrade
/trunk/libs/range/doc/html/range/upgrade/upgrade_1_34_to_1_35.html
/trunk/libs/range/doc/html/range/upgrade/upgrade_from_1_34.html
/trunk/libs/range/doc/html/range/upgrade/upgrade_from_1_42.html
/trunk/libs/range/doc/html/range/upgrade.html
/trunk/libs/range/doc/html/range/utilities
/trunk/libs/range/doc/html/range/utilities/iterator_range.html
/trunk/libs/range/doc/html/range/utilities/join.html
/trunk/libs/range/doc/html/range/utilities/sub_range.html
/trunk/libs/range/doc/html/standalone_HTML.manifest
/trunk/libs/range/doc/introduction.qbk
/trunk/libs/range/doc/mfc_atl.qbk
/trunk/libs/range/doc/mfc_atl.rst
/trunk/libs/range/doc/portability.qbk
/trunk/libs/range/doc/reference
/trunk/libs/range/doc/reference/adaptors
/trunk/libs/range/doc/reference/adaptors/adjacent_filtered.html
/trunk/libs/range/doc/reference/adaptors/adjacent_filtered.qbk
/trunk/libs/range/doc/reference/adaptors/copied.html
/trunk/libs/range/doc/reference/adaptors/copied.qbk
/trunk/libs/range/doc/reference/adaptors/examples
/trunk/libs/range/doc/reference/adaptors/examples/adjacent_filtered.cpp
/trunk/libs/range/doc/reference/adaptors/examples/copied.cpp
/trunk/libs/range/doc/reference/adaptors/examples/filtered.cpp
/trunk/libs/range/doc/reference/adaptors/examples/indexed.cpp
/trunk/libs/range/doc/reference/adaptors/examples/indirected.cpp
/trunk/libs/range/doc/reference/adaptors/examples/map_keys.cpp
/trunk/libs/range/doc/reference/adaptors/examples/map_values.cpp
/trunk/libs/range/doc/reference/adaptors/examples/replaced.cpp
/trunk/libs/range/doc/reference/adaptors/examples/replaced_if.cpp
/trunk/libs/range/doc/reference/adaptors/examples/reversed.cpp
/trunk/libs/range/doc/reference/adaptors/examples/sliced.cpp
/trunk/libs/range/doc/reference/adaptors/examples/strided.cpp
/trunk/libs/range/doc/reference/adaptors/examples/tokenized.cpp
/trunk/libs/range/doc/reference/adaptors/examples/transformed.cpp
/trunk/libs/range/doc/reference/adaptors/examples/uniqued.cpp
/trunk/libs/range/doc/reference/adaptors/filtered.html
/trunk/libs/range/doc/reference/adaptors/filtered.qbk
/trunk/libs/range/doc/reference/adaptors/indexed.html
/trunk/libs/range/doc/reference/adaptors/indexed.qbk
/trunk/libs/range/doc/reference/adaptors/indirected.html
/trunk/libs/range/doc/reference/adaptors/indirected.qbk
/trunk/libs/range/doc/reference/adaptors/map_keys.html
/trunk/libs/range/doc/reference/adaptors/map_keys.qbk
/trunk/libs/range/doc/reference/adaptors/map_values.html
/trunk/libs/range/doc/reference/adaptors/map_values.qbk
/trunk/libs/range/doc/reference/adaptors/replaced.html
/trunk/libs/range/doc/reference/adaptors/replaced.qbk
/trunk/libs/range/doc/reference/adaptors/replaced_if.html
/trunk/libs/range/doc/reference/adaptors/replaced_if.qbk
/trunk/libs/range/doc/reference/adaptors/reversed.html
/trunk/libs/range/doc/reference/adaptors/reversed.qbk
/trunk/libs/range/doc/reference/adaptors/sliced.html
/trunk/libs/range/doc/reference/adaptors/sliced.qbk
/trunk/libs/range/doc/reference/adaptors/strided.html
/trunk/libs/range/doc/reference/adaptors/strided.qbk
/trunk/libs/range/doc/reference/adaptors/tokenized.html
/trunk/libs/range/doc/reference/adaptors/tokenized.qbk
/trunk/libs/range/doc/reference/adaptors/transformed.html
/trunk/libs/range/doc/reference/adaptors/transformed.qbk
/trunk/libs/range/doc/reference/adaptors/uniqued.html
/trunk/libs/range/doc/reference/adaptors/uniqued.qbk
/trunk/libs/range/doc/reference/adaptors.qbk
/trunk/libs/range/doc/reference/algorithm
/trunk/libs/range/doc/reference/algorithm/adjacent_find.qbk
/trunk/libs/range/doc/reference/algorithm/binary_search.qbk
/trunk/libs/range/doc/reference/algorithm/copy.qbk
/trunk/libs/range/doc/reference/algorithm/copy_backward.qbk
/trunk/libs/range/doc/reference/algorithm/count.qbk
/trunk/libs/range/doc/reference/algorithm/count_if.qbk
/trunk/libs/range/doc/reference/algorithm/equal.qbk
/trunk/libs/range/doc/reference/algorithm/equal_range.qbk
/trunk/libs/range/doc/reference/algorithm/fill.qbk
/trunk/libs/range/doc/reference/algorithm/fill_n.qbk
/trunk/libs/range/doc/reference/algorithm/find.qbk
/trunk/libs/range/doc/reference/algorithm/find_end.qbk
/trunk/libs/range/doc/reference/algorithm/find_first_of.qbk
/trunk/libs/range/doc/reference/algorithm/find_if.qbk
/trunk/libs/range/doc/reference/algorithm/for_each.qbk
/trunk/libs/range/doc/reference/algorithm/generate.qbk
/trunk/libs/range/doc/reference/algorithm/includes.qbk
/trunk/libs/range/doc/reference/algorithm/inplace_merge.qbk
/trunk/libs/range/doc/reference/algorithm/lexicographical_compare.qbk
/trunk/libs/range/doc/reference/algorithm/lower_bound.qbk
/trunk/libs/range/doc/reference/algorithm/make_heap.qbk
/trunk/libs/range/doc/reference/algorithm/max_element.qbk
/trunk/libs/range/doc/reference/algorithm/merge.qbk
/trunk/libs/range/doc/reference/algorithm/min_element.qbk
/trunk/libs/range/doc/reference/algorithm/mismatch.qbk
/trunk/libs/range/doc/reference/algorithm/next_permutation.qbk
/trunk/libs/range/doc/reference/algorithm/nth_element.qbk
/trunk/libs/range/doc/reference/algorithm/partial_sort.qbk
/trunk/libs/range/doc/reference/algorithm/partition.qbk
/trunk/libs/range/doc/reference/algorithm/pop_heap.qbk
/trunk/libs/range/doc/reference/algorithm/prev_permutation.qbk
/trunk/libs/range/doc/reference/algorithm/push_heap.qbk
/trunk/libs/range/doc/reference/algorithm/random_shuffle.qbk
/trunk/libs/range/doc/reference/algorithm/remove.qbk
/trunk/libs/range/doc/reference/algorithm/remove_copy.qbk
/trunk/libs/range/doc/reference/algorithm/remove_copy_if.qbk
/trunk/libs/range/doc/reference/algorithm/remove_if.qbk
/trunk/libs/range/doc/reference/algorithm/replace.qbk
/trunk/libs/range/doc/reference/algorithm/replace_copy.qbk
/trunk/libs/range/doc/reference/algorithm/replace_copy_if.qbk
/trunk/libs/range/doc/reference/algorithm/replace_if.qbk
/trunk/libs/range/doc/reference/algorithm/reverse.qbk
/trunk/libs/range/doc/reference/algorithm/reverse_copy.qbk
/trunk/libs/range/doc/reference/algorithm/rotate.qbk
/trunk/libs/range/doc/reference/algorithm/rotate_copy.qbk
/trunk/libs/range/doc/reference/algorithm/search.qbk
/trunk/libs/range/doc/reference/algorithm/search_n.qbk
/trunk/libs/range/doc/reference/algorithm/set_difference.qbk
/trunk/libs/range/doc/reference/algorithm/set_intersection.qbk
/trunk/libs/range/doc/reference/algorithm/set_symmetric_difference.qbk
/trunk/libs/range/doc/reference/algorithm/set_union.qbk
/trunk/libs/range/doc/reference/algorithm/sort.qbk
/trunk/libs/range/doc/reference/algorithm/sort_heap.qbk
/trunk/libs/range/doc/reference/algorithm/stable_partition.qbk
/trunk/libs/range/doc/reference/algorithm/stable_sort.qbk
/trunk/libs/range/doc/reference/algorithm/swap_ranges.qbk
/trunk/libs/range/doc/reference/algorithm/transform.qbk
/trunk/libs/range/doc/reference/algorithm/unique.qbk
/trunk/libs/range/doc/reference/algorithm/unique_copy.qbk
/trunk/libs/range/doc/reference/algorithm/upper_bound.qbk
/trunk/libs/range/doc/reference/algorithm_ext
/trunk/libs/range/doc/reference/algorithm_ext/copy_n.qbk
/trunk/libs/range/doc/reference/algorithm_ext/erase.qbk
/trunk/libs/range/doc/reference/algorithm_ext/for_each.qbk
/trunk/libs/range/doc/reference/algorithm_ext/insert.qbk
/trunk/libs/range/doc/reference/algorithm_ext/iota.qbk
/trunk/libs/range/doc/reference/algorithm_ext/is_sorted.qbk
/trunk/libs/range/doc/reference/algorithm_ext/overwrite.qbk
/trunk/libs/range/doc/reference/algorithm_ext/push_back.qbk
/trunk/libs/range/doc/reference/algorithm_ext/push_front.qbk
/trunk/libs/range/doc/reference/algorithm_ext/remove_erase.qbk
/trunk/libs/range/doc/reference/algorithm_ext/remove_erase_if.qbk
/trunk/libs/range/doc/reference/algorithms.qbk
/trunk/libs/range/doc/reference/extending.qbk
/trunk/libs/range/doc/reference/numeric
/trunk/libs/range/doc/reference/numeric/accumulate.qbk
/trunk/libs/range/doc/reference/numeric/adjacent_difference.qbk
/trunk/libs/range/doc/reference/numeric/inner_product.qbk
/trunk/libs/range/doc/reference/numeric/partial_sum.qbk
/trunk/libs/range/doc/reference/overview.qbk
/trunk/libs/range/doc/reference/ranges
/trunk/libs/range/doc/reference/ranges/counting_range.qbk
/trunk/libs/range/doc/reference/ranges/irange.qbk
/trunk/libs/range/doc/reference/ranges/istream_range.qbk
/trunk/libs/range/doc/reference/ranges.qbk
/trunk/libs/range/doc/reference/semantics.qbk
/trunk/libs/range/doc/reference/synopsis.qbk
/trunk/libs/range/doc/reference/utilities.qbk
/trunk/libs/range/doc/reference.qbk
/trunk/libs/range/doc/style.qbk
/trunk/libs/range/doc/upgrade.qbk
/trunk/libs/range/test/Jamfile.v2
/trunk/libs/range/test/adaptor_test
/trunk/libs/range/test/adaptor_test/adjacent_filtered.cpp
/trunk/libs/range/test/adaptor_test/adjacent_filtered_example.cpp
/trunk/libs/range/test/adaptor_test/copied.cpp
/trunk/libs/range/test/adaptor_test/copied_example.cpp
/trunk/libs/range/test/adaptor_test/filtered.cpp
/trunk/libs/range/test/adaptor_test/filtered_example.cpp
/trunk/libs/range/test/adaptor_test/indexed.cpp
/trunk/libs/range/test/adaptor_test/indexed_example.cpp
/trunk/libs/range/test/adaptor_test/indirected.cpp
/trunk/libs/range/test/adaptor_test/indirected_example.cpp
/trunk/libs/range/test/adaptor_test/map.cpp
/trunk/libs/range/test/adaptor_test/map_keys_example.cpp
/trunk/libs/range/test/adaptor_test/map_values_example.cpp
/trunk/libs/range/test/adaptor_test/replaced.cpp
/trunk/libs/range/test/adaptor_test/replaced_example.cpp
/trunk/libs/range/test/adaptor_test/replaced_if.cpp
/trunk/libs/range/test/adaptor_test/replaced_if_example.cpp
/trunk/libs/range/test/adaptor_test/reversed.cpp
/trunk/libs/range/test/adaptor_test/reversed_example.cpp
/trunk/libs/range/test/adaptor_test/sliced.cpp
/trunk/libs/range/test/adaptor_test/sliced_example.cpp
/trunk/libs/range/test/adaptor_test/strided.cpp
/trunk/libs/range/test/adaptor_test/strided2.cpp
/trunk/libs/range/test/adaptor_test/strided_example.cpp
/trunk/libs/range/test/adaptor_test/tokenized.cpp
/trunk/libs/range/test/adaptor_test/transformed.cpp
/trunk/libs/range/test/adaptor_test/transformed_example.cpp
/trunk/libs/range/test/adaptor_test/uniqued.cpp
/trunk/libs/range/test/adaptor_test/uniqued_example.cpp
/trunk/libs/range/test/adaptors.cpp
/trunk/libs/range/test/algorithm.cpp
/trunk/libs/range/test/algorithm_ext_test
/trunk/libs/range/test/algorithm_ext_test/copy_n.cpp
/trunk/libs/range/test/algorithm_ext_test/erase.cpp
/trunk/libs/range/test/algorithm_ext_test/for_each_ext.cpp
/trunk/libs/range/test/algorithm_ext_test/insert.cpp
/trunk/libs/range/test/algorithm_ext_test/iota.cpp
/trunk/libs/range/test/algorithm_ext_test/is_sorted.cpp
/trunk/libs/range/test/algorithm_ext_test/overwrite.cpp
/trunk/libs/range/test/algorithm_ext_test/push_back.cpp
/trunk/libs/range/test/algorithm_ext_test/push_front.cpp
/trunk/libs/range/test/algorithm_test
/trunk/libs/range/test/algorithm_test/adjacent_find.cpp
/trunk/libs/range/test/algorithm_test/binary_search.cpp
/trunk/libs/range/test/algorithm_test/copy.cpp
/trunk/libs/range/test/algorithm_test/copy_backward.cpp
/trunk/libs/range/test/algorithm_test/count.cpp
/trunk/libs/range/test/algorithm_test/count_if.cpp
/trunk/libs/range/test/algorithm_test/equal.cpp
/trunk/libs/range/test/algorithm_test/equal_range.cpp
/trunk/libs/range/test/algorithm_test/fill.cpp
/trunk/libs/range/test/algorithm_test/find.cpp
/trunk/libs/range/test/algorithm_test/find_end.cpp
/trunk/libs/range/test/algorithm_test/find_first_of.cpp
/trunk/libs/range/test/algorithm_test/find_if.cpp
/trunk/libs/range/test/algorithm_test/for_each.cpp
/trunk/libs/range/test/algorithm_test/generate.cpp
/trunk/libs/range/test/algorithm_test/heap.cpp
/trunk/libs/range/test/algorithm_test/includes.cpp
/trunk/libs/range/test/algorithm_test/inplace_merge.cpp
/trunk/libs/range/test/algorithm_test/lexicographical_compare.cpp
/trunk/libs/range/test/algorithm_test/lower_bound.cpp
/trunk/libs/range/test/algorithm_test/max_element.cpp
/trunk/libs/range/test/algorithm_test/merge.cpp
/trunk/libs/range/test/algorithm_test/min_element.cpp
/trunk/libs/range/test/algorithm_test/mismatch.cpp
/trunk/libs/range/test/algorithm_test/next_permutation.cpp
/trunk/libs/range/test/algorithm_test/nth_element.cpp
/trunk/libs/range/test/algorithm_test/partial_sort.cpp
/trunk/libs/range/test/algorithm_test/partition.cpp
/trunk/libs/range/test/algorithm_test/prev_permutation.cpp
/trunk/libs/range/test/algorithm_test/random_shuffle.cpp
/trunk/libs/range/test/algorithm_test/remove.cpp
/trunk/libs/range/test/algorithm_test/remove_if.cpp
/trunk/libs/range/test/algorithm_test/replace.cpp
/trunk/libs/range/test/algorithm_test/replace_if.cpp
/trunk/libs/range/test/algorithm_test/reverse.cpp
/trunk/libs/range/test/algorithm_test/rotate.cpp
/trunk/libs/range/test/algorithm_test/search.cpp
/trunk/libs/range/test/algorithm_test/set_difference.cpp
/trunk/libs/range/test/algorithm_test/set_intersection.cpp
/trunk/libs/range/test/algorithm_test/set_symmetric_difference.cpp
/trunk/libs/range/test/algorithm_test/set_union.cpp
/trunk/libs/range/test/algorithm_test/sort.cpp
/trunk/libs/range/test/algorithm_test/stable_partition.cpp
/trunk/libs/range/test/algorithm_test/stable_sort.cpp
/trunk/libs/range/test/algorithm_test/transform.cpp
/trunk/libs/range/test/algorithm_test/unique.cpp
/trunk/libs/range/test/algorithm_test/upper_bound.cpp
/trunk/libs/range/test/combine.cpp
/trunk/libs/range/test/counting_range.cpp
/trunk/libs/range/test/irange.cpp
/trunk/libs/range/test/istream_range.cpp
/trunk/libs/range/test/join.cpp
/trunk/libs/range/test/pointer_as_iterator.cpp
/trunk/libs/range/test/test_driver
/trunk/libs/range/test/test_driver/range_return_test_driver.hpp
/trunk/libs/range/test/test_function
/trunk/libs/range/test/test_function/check_equal_fn.hpp
/trunk/libs/range/test/test_function/counted_function.hpp
/trunk/libs/range/test/test_function/equal_to_x.hpp
/trunk/libs/range/test/test_function/false_predicate.hpp
/trunk/libs/range/test/test_function/greater_than_x.hpp
/trunk/libs/range/test/test_function/multiply_by_x.hpp
/trunk/libs/serialization/doc/simple_log.html
/trunk/libs/serialization/example/demo_log.cpp
/trunk/libs/serialization/example/demo_simple_log.cpp
/trunk/libs/serialization/example/demo_trivial_archive.cpp
/trunk/libs/serialization/example/log_archive.cpp
/trunk/libs/serialization/example/log_archive.hpp
/trunk/libs/serialization/example/simple_log_archive.hpp
/trunk/libs/signals2/example/Jamfile.v2
/trunk/libs/spirit/doc/html/spirit/advanced/customize/auto
/trunk/libs/spirit/doc/html/spirit/advanced/customize/auto/create_generator.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/auto/create_parser.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/auto.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/auto.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auto.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/columns.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generate_api/create_generator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/string/symbols.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/karma_adapted_complex.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/auto.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auto.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/matches.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/no_skip.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parse_api/create_parser.html
/trunk/libs/spirit/doc/html/spirit/what_s_new
/trunk/libs/spirit/doc/html/spirit/what_s_new/spirit_1_x.html
/trunk/libs/spirit/doc/html/spirit/what_s_new/spirit_2_1.html
/trunk/libs/spirit/doc/html/spirit/what_s_new/spirit_2_2.html
/trunk/libs/spirit/doc/html/spirit/what_s_new/spirit_2_3.html
/trunk/libs/spirit/doc/karma_performance.xlsx
/trunk/libs/spirit/doc/outline.txt
/trunk/libs/spirit/example/karma
/trunk/libs/spirit/example/karma/Jamfile
/trunk/libs/spirit/example/karma/actions.cpp
/trunk/libs/spirit/example/karma/auto_facilities.cpp
/trunk/libs/spirit/example/karma/basic_facilities.cpp
/trunk/libs/spirit/example/karma/calc2_ast.hpp
/trunk/libs/spirit/example/karma/calc2_ast_dump.cpp
/trunk/libs/spirit/example/karma/calc2_ast_rpn.cpp
/trunk/libs/spirit/example/karma/calc2_ast_vm.cpp
/trunk/libs/spirit/example/karma/calc2_ast_vm.hpp
/trunk/libs/spirit/example/karma/classify_char.cpp
/trunk/libs/spirit/example/karma/complex_number.cpp
/trunk/libs/spirit/example/karma/complex_number_adapt.cpp
/trunk/libs/spirit/example/karma/complex_number_easier.cpp
/trunk/libs/spirit/example/karma/customize_counter.cpp
/trunk/libs/spirit/example/karma/customize_embedded_container.cpp
/trunk/libs/spirit/example/karma/customize_use_as_container.cpp
/trunk/libs/spirit/example/karma/escaped_string.cpp
/trunk/libs/spirit/example/karma/generate_code.cpp
/trunk/libs/spirit/example/karma/key_value_sequence.cpp
/trunk/libs/spirit/example/karma/mini_xml_karma.cpp
/trunk/libs/spirit/example/karma/num_list1.cpp
/trunk/libs/spirit/example/karma/num_list2.cpp
/trunk/libs/spirit/example/karma/num_list3.cpp
/trunk/libs/spirit/example/karma/num_matrix.cpp
/trunk/libs/spirit/example/karma/printf_style_double_format.cpp
/trunk/libs/spirit/example/karma/quick_start1.cpp
/trunk/libs/spirit/example/karma/quoted_strings.cpp
/trunk/libs/spirit/example/karma/reference.cpp
/trunk/libs/spirit/example/karma/reorder_struct.cpp
/trunk/libs/spirit/example/karma/simple_columns_directive.cpp
/trunk/libs/spirit/example/karma/simple_columns_directive.hpp
/trunk/libs/spirit/example/lex
/trunk/libs/spirit/example/lex/Jamfile
/trunk/libs/spirit/example/lex/custom_token_attribute.cpp
/trunk/libs/spirit/example/lex/example.hpp
/trunk/libs/spirit/example/lex/example1.cpp
/trunk/libs/spirit/example/lex/example1.input
/trunk/libs/spirit/example/lex/example2.cpp
/trunk/libs/spirit/example/lex/example2.input
/trunk/libs/spirit/example/lex/example3.cpp
/trunk/libs/spirit/example/lex/example3.input
/trunk/libs/spirit/example/lex/example4.cpp
/trunk/libs/spirit/example/lex/example4.input
/trunk/libs/spirit/example/lex/example5.cpp
/trunk/libs/spirit/example/lex/example5.input
/trunk/libs/spirit/example/lex/example6.cpp
/trunk/libs/spirit/example/lex/example6.input
/trunk/libs/spirit/example/lex/print_numbers.cpp
/trunk/libs/spirit/example/lex/print_numbers.input
/trunk/libs/spirit/example/lex/reference.cpp
/trunk/libs/spirit/example/lex/static_lexer
/trunk/libs/spirit/example/lex/static_lexer/Jamfile
/trunk/libs/spirit/example/lex/static_lexer/word_count.input
/trunk/libs/spirit/example/lex/static_lexer/word_count_generate.cpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_lexer_generate.cpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_lexer_static.cpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_lexer_static.hpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_lexer_tokens.hpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_static.cpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_static.hpp
/trunk/libs/spirit/example/lex/static_lexer/word_count_tokens.hpp
/trunk/libs/spirit/example/lex/strip_comments.cpp
/trunk/libs/spirit/example/lex/strip_comments.input
/trunk/libs/spirit/example/lex/strip_comments_lexer.cpp
/trunk/libs/spirit/example/lex/word_count.cpp
/trunk/libs/spirit/example/lex/word_count.input
/trunk/libs/spirit/example/lex/word_count_functor.cpp
/trunk/libs/spirit/example/lex/word_count_functor.flex
/trunk/libs/spirit/example/lex/word_count_functor_flex.cpp
/trunk/libs/spirit/example/lex/word_count_lexer.cpp
/trunk/libs/spirit/example/qi/Jamfile
/trunk/libs/spirit/example/qi/actions.cpp
/trunk/libs/spirit/example/qi/adapt_template_struct.cpp
/trunk/libs/spirit/example/qi/boost_array.cpp
/trunk/libs/spirit/example/qi/calc1.cpp
/trunk/libs/spirit/example/qi/calc2.cpp
/trunk/libs/spirit/example/qi/calc2_ast.cpp
/trunk/libs/spirit/example/qi/calc3.cpp
/trunk/libs/spirit/example/qi/calc4.cpp
/trunk/libs/spirit/example/qi/calc4_debug.cpp
/trunk/libs/spirit/example/qi/calc5.cpp
/trunk/libs/spirit/example/qi/calc6
/trunk/libs/spirit/example/qi/calc6/calc6.cpp
/trunk/libs/spirit/example/qi/calc6/calc6.hpp
/trunk/libs/spirit/example/qi/calc6/calc6a.cpp
/trunk/libs/spirit/example/qi/calc6/calc6b.cpp
/trunk/libs/spirit/example/qi/calc6/calc6b.hpp
/trunk/libs/spirit/example/qi/calc6/calc6c.cpp
/trunk/libs/spirit/example/qi/calc6/calc6c.hpp
/trunk/libs/spirit/example/qi/calc7
/trunk/libs/spirit/example/qi/calc7/calc7.cpp
/trunk/libs/spirit/example/qi/calc7/calc7.hpp
/trunk/libs/spirit/example/qi/calc7/calc7a.cpp
/trunk/libs/spirit/example/qi/calc7/calc7b.cpp
/trunk/libs/spirit/example/qi/calc7/calc7b.hpp
/trunk/libs/spirit/example/qi/calc7/calc7c.cpp
/trunk/libs/spirit/example/qi/calc7/calc7c.hpp
/trunk/libs/spirit/example/qi/complex_number.cpp
/trunk/libs/spirit/example/qi/display_attribute_type.cpp
/trunk/libs/spirit/example/qi/display_attribute_type.hpp
/trunk/libs/spirit/example/qi/employee.cpp
/trunk/libs/spirit/example/qi/iter_pos.hpp
/trunk/libs/spirit/example/qi/iter_pos_parser.cpp
/trunk/libs/spirit/example/qi/key_value_sequence.cpp
/trunk/libs/spirit/example/qi/key_value_sequence_empty_value.cpp
/trunk/libs/spirit/example/qi/key_value_sequence_ordered.cpp
/trunk/libs/spirit/example/qi/mini_c
/trunk/libs/spirit/example/qi/mini_c/mini_c.cpp
/trunk/libs/spirit/example/qi/mini_c/mini_c.hpp
/trunk/libs/spirit/example/qi/mini_c/mini_ca.cpp
/trunk/libs/spirit/example/qi/mini_c/mini_cb.cpp
/trunk/libs/spirit/example/qi/mini_c/mini_cb.hpp
/trunk/libs/spirit/example/qi/mini_c/mini_cc.cpp
/trunk/libs/spirit/example/qi/mini_c/mini_cc.hpp
/trunk/libs/spirit/example/qi/mini_c/mini_cd.cpp
/trunk/libs/spirit/example/qi/mini_c/mini_cd.hpp
/trunk/libs/spirit/example/qi/mini_c_samples
/trunk/libs/spirit/example/qi/mini_c_samples/1.mini
/trunk/libs/spirit/example/qi/mini_c_samples/2.mini
/trunk/libs/spirit/example/qi/mini_c_samples/3.mini
/trunk/libs/spirit/example/qi/mini_xml1.cpp
/trunk/libs/spirit/example/qi/mini_xml2.cpp
/trunk/libs/spirit/example/qi/mini_xml3.cpp
/trunk/libs/spirit/example/qi/nabialek.cpp
/trunk/libs/spirit/example/qi/num_list1.cpp
/trunk/libs/spirit/example/qi/num_list2.cpp
/trunk/libs/spirit/example/qi/num_list3.cpp
/trunk/libs/spirit/example/qi/num_list4.cpp
/trunk/libs/spirit/example/qi/parse_date.cpp
/trunk/libs/spirit/example/qi/porting_guide_classic.cpp
/trunk/libs/spirit/example/qi/porting_guide_qi.cpp
/trunk/libs/spirit/example/qi/reference.cpp
/trunk/libs/spirit/example/qi/reorder_struct.cpp
/trunk/libs/spirit/example/qi/roman.cpp
/trunk/libs/spirit/example/qi/sum.cpp
/trunk/libs/spirit/example/qi/typeof.cpp
/trunk/libs/spirit/example/support
/trunk/libs/spirit/example/support/Jamfile
/trunk/libs/spirit/example/support/multi_pass.cpp
/trunk/libs/spirit/example/support/multi_pass.txt
Deleted:
/trunk/libs/random/histogram.cpp
/trunk/libs/random/instantiate.cpp
/trunk/libs/random/integrate.hpp
/trunk/libs/random/nondet_random_speed.cpp
/trunk/libs/random/random_demo.cpp
/trunk/libs/random/random_device.cpp
/trunk/libs/random/random_speed.cpp
/trunk/libs/random/random_test.cpp
/trunk/libs/random/statistic_tests.cpp
/trunk/libs/random/statistic_tests.hpp
/trunk/libs/random/validate.cpp
/trunk/libs/random/wg21-proposal.html
/trunk/libs/range/doc/boost_range.html
/trunk/libs/range/doc/examples.html
/trunk/libs/range/doc/faq.html
/trunk/libs/range/doc/headers.html
/trunk/libs/range/doc/history_ack.html
/trunk/libs/range/doc/intro.html
/trunk/libs/range/doc/mfc_atl.html
/trunk/libs/range/doc/portability.html
/trunk/libs/range/doc/range.html
/trunk/libs/range/doc/style.html
/trunk/libs/range/doc/upgrading.html
/trunk/libs/range/doc/utility_class.html
Modified:
/trunk/libs/random/index.html
/trunk/libs/random/nondet_random.html
/trunk/libs/random/random-concepts.html
/trunk/libs/random/random-distributions.html
/trunk/libs/random/random-generators.html
/trunk/libs/random/random-misc.html
/trunk/libs/random/random-performance.html
/trunk/libs/random/random-variate.html
/trunk/libs/range/index.html
/trunk/libs/range/test/adl_conformance.cpp
/trunk/libs/range/test/compat2.cpp
/trunk/libs/range/test/const_ranges.cpp
/trunk/libs/range/test/iterator_pair.cpp
/trunk/libs/range/test/iterator_range.cpp
/trunk/libs/range/test/reversible_range.cpp
/trunk/libs/range/test/std_container.cpp
/trunk/libs/range/test/sub_range.cpp
/trunk/libs/serialization/doc/archive_reference.html
/trunk/libs/serialization/doc/archives.html
/trunk/libs/serialization/doc/class_diagram.html
/trunk/libs/serialization/doc/contents.html
/trunk/libs/serialization/doc/derivation.html
/trunk/libs/serialization/doc/extended_type_info.html
/trunk/libs/serialization/doc/headers.html
/trunk/libs/serialization/doc/overview.html
/trunk/libs/serialization/doc/release.html
/trunk/libs/serialization/doc/singleton.html
/trunk/libs/serialization/doc/special.html
/trunk/libs/serialization/example/Jamfile.v2
/trunk/libs/serialization/example/demo.cpp
/trunk/libs/serialization/example/demo_gps.hpp
/trunk/libs/serialization/example/demo_portable_archive.cpp
/trunk/libs/serialization/example/portable_binary_iarchive.cpp
/trunk/libs/serialization/src/basic_iarchive.cpp
/trunk/libs/serialization/src/basic_oarchive.cpp
/trunk/libs/serialization/src/basic_pointer_iserializer.cpp
/trunk/libs/serialization/src/basic_pointer_oserializer.cpp
/trunk/libs/serialization/src/basic_serializer_map.cpp
/trunk/libs/serialization/src/basic_text_iprimitive.cpp
/trunk/libs/serialization/src/basic_text_oprimitive.cpp
/trunk/libs/serialization/src/basic_text_wiprimitive.cpp
/trunk/libs/serialization/src/basic_text_woprimitive.cpp
/trunk/libs/serialization/src/shared_ptr_helper.cpp
/trunk/libs/serialization/src/utf8_codecvt_facet.cpp
/trunk/libs/serialization/src/void_cast.cpp
/trunk/libs/serialization/test/C.hpp
/trunk/libs/serialization/test/J.hpp
/trunk/libs/serialization/test/Jamfile.v2
/trunk/libs/serialization/test/binary_archive.hpp
/trunk/libs/serialization/test/binary_warchive.hpp
/trunk/libs/serialization/test/polymorphic_array_binary_archive.hpp
/trunk/libs/serialization/test/polymorphic_base.hpp
/trunk/libs/serialization/test/polymorphic_binary_archive.hpp
/trunk/libs/serialization/test/polymorphic_derived2.cpp
/trunk/libs/serialization/test/polymorphic_derived2.hpp
/trunk/libs/serialization/test/polymorphic_text_archive.hpp
/trunk/libs/serialization/test/polymorphic_xml_archive.hpp
/trunk/libs/serialization/test/polymorphic_xml_warchive.hpp
/trunk/libs/serialization/test/portable_binary_archive.hpp
/trunk/libs/serialization/test/test_array.cpp
/trunk/libs/serialization/test/test_check.cpp
/trunk/libs/serialization/test/test_class_info_load.cpp
/trunk/libs/serialization/test/test_codecvt_null.cpp
/trunk/libs/serialization/test/test_const_load_fail1.cpp
/trunk/libs/serialization/test/test_const_load_fail1_nvp.cpp
/trunk/libs/serialization/test/test_const_load_fail2.cpp
/trunk/libs/serialization/test/test_const_load_fail2_nvp.cpp
/trunk/libs/serialization/test/test_const_load_fail3.cpp
/trunk/libs/serialization/test/test_const_load_fail3_nvp.cpp
/trunk/libs/serialization/test/test_const_pass.cpp
/trunk/libs/serialization/test/test_const_save_warn1.cpp
/trunk/libs/serialization/test/test_const_save_warn1_nvp.cpp
/trunk/libs/serialization/test/test_const_save_warn2.cpp
/trunk/libs/serialization/test/test_const_save_warn2_nvp.cpp
/trunk/libs/serialization/test/test_const_save_warn3.cpp
/trunk/libs/serialization/test/test_const_save_warn3_nvp.cpp
/trunk/libs/serialization/test/test_const_save_warn4.cpp
/trunk/libs/serialization/test/test_const_save_warn4_nvp.cpp
/trunk/libs/serialization/test/test_dll_exported.cpp
/trunk/libs/serialization/test/test_dll_plugin.cpp
/trunk/libs/serialization/test/test_exported.cpp
/trunk/libs/serialization/test/test_no_rtti.cpp
/trunk/libs/serialization/test/test_not_serializable.cpp
/trunk/libs/serialization/test/test_pimpl.cpp
/trunk/libs/serialization/test/test_polymorphic2.cpp
/trunk/libs/serialization/test/test_polymorphic2.hpp
/trunk/libs/serialization/test/test_polymorphic2imp.cpp
/trunk/libs/serialization/test/test_polymorphic_A.cpp
/trunk/libs/serialization/test/test_polymorphic_A.hpp
/trunk/libs/serialization/test/test_set.cpp
/trunk/libs/serialization/test/test_singleton.cpp
/trunk/libs/serialization/test/test_traits_fail.cpp
/trunk/libs/serialization/test/test_traits_pass.cpp
/trunk/libs/serialization/test/text_archive.hpp
/trunk/libs/serialization/test/text_warchive.hpp
/trunk/libs/serialization/test/xml_archive.hpp
/trunk/libs/serialization/test/xml_warchive.hpp
/trunk/libs/signals2/example/disconnect_and_block.cpp
/trunk/libs/signals2/example/doc_view_acm.cpp
/trunk/libs/spirit/doc/Jamfile
/trunk/libs/spirit/doc/abstracts/attributes.qbk
/trunk/libs/spirit/doc/advanced/customization_points.qbk
/trunk/libs/spirit/doc/html/index.html
/trunk/libs/spirit/doc/html/spirit/abstracts/attributes/compound_attributes.html
/trunk/libs/spirit/doc/html/spirit/abstracts/attributes/more_compound_attributes.html
/trunk/libs/spirit/doc/html/spirit/abstracts/attributes/nonterminal_attributes.html
/trunk/libs/spirit/doc/html/spirit/abstracts/attributes/primitive_attributes.html
/trunk/libs/spirit/doc/html/spirit/abstracts/attributes.html
/trunk/libs/spirit/doc/html/spirit/abstracts/parsing_expression_grammar.html
/trunk/libs/spirit/doc/html/spirit/abstracts/syntax_diagram.html
/trunk/libs/spirit/doc/html/spirit/abstracts.html
/trunk/libs/spirit/doc/html/spirit/acknowledgments.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/assign_to/assign_to_attribute_from_iterators.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/assign_to/assign_to_attribute_from_value.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/assign_to.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/clear_value.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/extract_from.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/is_container.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/begin_container.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/compare_iterators.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/container_iterator.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/deref_iterator.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/end_container.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate/next_iterator.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/iterate.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/store_value/container_value.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/store_value/push_back.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/store_value.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize/transform.html
/trunk/libs/spirit/doc/html/spirit/advanced/customize.html
/trunk/libs/spirit/doc/html/spirit/advanced/indepth/parsers_indepth.html
/trunk/libs/spirit/doc/html/spirit/advanced/indepth.html
/trunk/libs/spirit/doc/html/spirit/advanced.html
/trunk/libs/spirit/doc/html/spirit/faq.html
/trunk/libs/spirit/doc/html/spirit/introduction.html
/trunk/libs/spirit/doc/html/spirit/karma/performance_measurements/numeric_performance/double_performance.html
/trunk/libs/spirit/doc/html/spirit/karma/performance_measurements/numeric_performance/format_performance.html
/trunk/libs/spirit/doc/html/spirit/karma/performance_measurements/numeric_performance/int_performance.html
/trunk/libs/spirit/doc/html/spirit/karma/performance_measurements/numeric_performance.html
/trunk/libs/spirit/doc/html/spirit/karma/performance_measurements.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/common_notation.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/compound_attribute_rules.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/non_terminals.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/phoenix.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/action.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/auxiliary.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/binary.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/boolean.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/char.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/directives.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/operators.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/real_number.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/signed_int.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/stream.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/string.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators/unsigned_int.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/primitive_generators.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference/semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/karma/quick_reference.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/action.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auxiliary/attr_cast.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auxiliary/eol.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auxiliary/eps.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auxiliary/lazy.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/auxiliary.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/binary/binary_big.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/binary/binary_little.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/binary/binary_native.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/binary.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/char/char_class.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/char/char_generator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/char.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/alignment.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/buffer.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/delimit.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/maxwidth.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/omit.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/repeat.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive/upperlower.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/directive.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generate_api/iterator_api.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generate_api/stream_api.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generate_api.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/binarygenerator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/generator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/narygenerator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/nonterminal.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/primitivegenerator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts/unarygenerator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/generator_concepts.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/karma_basics.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/nonterminal/grammar.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/nonterminal/rule.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/nonterminal.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/numeric/boolean.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/numeric/real_number.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/numeric/signed_int.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/numeric/unsigned_int.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/numeric.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/alternative.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/and_predicate.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/kleene.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/list.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/not_predicate.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/optional.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/plus.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator/sequence.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/operator.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/stream/stream.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/stream.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/string/string.html
/trunk/libs/spirit/doc/html/spirit/karma/reference/string.html
/trunk/libs/spirit/doc/html/spirit/karma/reference.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/karma_complex.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/karma_easier_complex.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/num_list.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/num_matrix.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/quick_start.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials/warming_up.html
/trunk/libs/spirit/doc/html/spirit/karma/tutorials.html
/trunk/libs/spirit/doc/html/spirit/karma.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts/lexer_primitives/lexer_token_values.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts/lexer_primitives.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts/lexer_semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts/lexer_static_model.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts/lexer_tokenizing.html
/trunk/libs/spirit/doc/html/spirit/lex/abstracts.html
/trunk/libs/spirit/doc/html/spirit/lex/lexer_introduction.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference/common_notation.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference/lexer.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference/lexers.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference/phoenix.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference/semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/lex/quick_reference.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lex_basics.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_api.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_concepts/lexer.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_concepts/narylexer.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_concepts/primitivelexer.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_concepts/unarylexer.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/lexer_concepts.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/primitives/char_tokendef.html
/trunk/libs/spirit/doc/html/spirit/lex/reference/primitives.html
/trunk/libs/spirit/doc/html/spirit/lex/reference.html
/trunk/libs/spirit/doc/html/spirit/lex/tutorials/lexer_quickstart1.html
/trunk/libs/spirit/doc/html/spirit/lex/tutorials/lexer_quickstart2.html
/trunk/libs/spirit/doc/html/spirit/lex/tutorials/lexer_quickstart3.html
/trunk/libs/spirit/doc/html/spirit/lex/tutorials/lexer_tutorials.html
/trunk/libs/spirit/doc/html/spirit/lex/tutorials.html
/trunk/libs/spirit/doc/html/spirit/lex.html
/trunk/libs/spirit/doc/html/spirit/notes/porting_from_spirit_1_8_x.html
/trunk/libs/spirit/doc/html/spirit/notes/style_guide.html
/trunk/libs/spirit/doc/html/spirit/notes.html
/trunk/libs/spirit/doc/html/spirit/preface.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/common_notation.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/compound_attribute_rules.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/non_terminals.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/phoenix.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/action.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/auxiliary.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/binary.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/char.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/directive.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/numeric.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/operator.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers/string.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/qi_parsers.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference/semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/qi/quick_reference.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/action.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/attr.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/attr_cast.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/eoi.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/eol.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/eps.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary/lazy.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/auxiliary.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/basics.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/binary/binary_big.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/binary/binary_little.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/binary/binary_native.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/binary.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/char/char.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/char/char_class.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/char.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/lexeme.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/no_case.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/omit.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/raw.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive/skip.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/directive.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/nonterminal/grammar.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/nonterminal/rule.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/nonterminal.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/numeric/boolean.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/numeric/int.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/numeric/real.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/numeric/uint.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/numeric.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/alternative.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/and_predicate.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/difference.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/expect.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/kleene.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/list.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/not_predicate.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/optional.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/permutation.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/plus.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/sequence.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator/sequential_or.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/operator.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parse_api/iterator_api.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parse_api/stream_api.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parse_api.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/binaryparser.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/naryparser.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/nonterminal.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/parser.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/primitiveparser.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts/unaryparser.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/parser_concepts.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/stream/stream.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/stream.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/string/string.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/string/symbols.html
/trunk/libs/spirit/doc/html/spirit/qi/reference/string.html
/trunk/libs/spirit/doc/html/spirit/qi/reference.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/complex___our_first_complex_parser.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/employee___parsing_into_structs.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/mini_xml___asts_.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/mini_xml___error_handling.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/number_list___stuffing_numbers_into_a_std__vector.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/number_list_attribute___one_more__with_style.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/number_list_redux___list_syntax.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/quick_start.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/roman_numerals.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/semantic_actions.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/sum___adding_numbers.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials/warming_up.html
/trunk/libs/spirit/doc/html/spirit/qi/tutorials.html
/trunk/libs/spirit/doc/html/spirit/qi.html
/trunk/libs/spirit/doc/html/spirit/references.html
/trunk/libs/spirit/doc/html/spirit/repository.html
/trunk/libs/spirit/doc/html/spirit/structure/include.html
/trunk/libs/spirit/doc/html/spirit/structure.html
/trunk/libs/spirit/doc/html/spirit/support/multi_pass.html
/trunk/libs/spirit/doc/html/spirit/support.html
/trunk/libs/spirit/doc/html/spirit/what_s_new.html
/trunk/libs/spirit/doc/karma/auto.qbk
/trunk/libs/spirit/doc/karma/complex.qbk
/trunk/libs/spirit/doc/karma/directive.qbk
/trunk/libs/spirit/doc/karma/numeric_performance.qbk
/trunk/libs/spirit/doc/karma/quick_reference.qbk
/trunk/libs/spirit/doc/lex/lexer_semantic_actions.qbk
/trunk/libs/spirit/doc/qi/actions.qbk
/trunk/libs/spirit/doc/qi/auto.qbk
/trunk/libs/spirit/doc/qi/complex.qbk
/trunk/libs/spirit/doc/qi/directive.qbk
/trunk/libs/spirit/doc/qi/employee.qbk
/trunk/libs/spirit/doc/qi/error_handling.qbk
/trunk/libs/spirit/doc/qi/mini_xml.qbk
/trunk/libs/spirit/doc/qi/nonterminal.qbk
/trunk/libs/spirit/doc/qi/num_list4.qbk
/trunk/libs/spirit/doc/qi/operator.qbk
/trunk/libs/spirit/doc/qi/quick_reference.qbk
/trunk/libs/spirit/doc/qi/roman.qbk
/trunk/libs/spirit/doc/spirit2.qbk
/trunk/libs/spirit/doc/support/multi_pass.qbk
/trunk/libs/spirit/doc/what_s_new.qbk
/trunk/libs/spirit/repository/doc/Jamfile
/trunk/libs/spirit/repository/doc/html/index.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/karma_components/directives/karma_confix_generator.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/karma_components/directives.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/karma_components/nonterminal/subrule.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/karma_components/nonterminal.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/karma_components.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/preface.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/directives/confix.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/directives/distinct.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/directives.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/nonterminal/subrule.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/nonterminal.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/primitive/flush_multi_pass.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components/primitive.html
/trunk/libs/spirit/repository/doc/html/spirit_repository/qi_components.html
/trunk/libs/spirit/repository/doc/qi/confix.qbk
/trunk/libs/statechart/doc/acknowledgments.html
/trunk/libs/statechart/doc/future_and_history.html
/trunk/libs/statechart/doc/reference.html
=======================================
--- /dev/null
+++ /trunk/libs/random/build/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,18 @@
+# Jamfile.v2
+#
+# Copyright (c) 2010
+# Steven Watanabe
+#
+# 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)
+
+project /boost/random
+ : source-location ../src
+ : requirements <link>shared:<define>BOOST_RANDOM_DYN_LINK
+ : usage-requirements <link>shared:<define>BOOST_RANDOM_DYN_LINK
+;
+
+lib boost_random : [ glob *.cpp ] ;
+
+boost-install boost_random ;
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,122 @@
+# Jamfile.v2
+#
+# Copyright (c) 2009
+# Steven Watanabe
+#
+# 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)
+
+using quickbook ;
+using doxygen ;
+import boostbook ;
+import regex ;
+import os ;
+import path ;
+
+doxygen_files =
+ additive_combine
+ bernoulli_distribution
+ binomial_distribution
+ cauchy_distribution
+ discard_block
+ exponential_distribution
+ gamma_distribution
+ geometric_distribution
+ inversive_congruential
+ lagged_fibonacci
+ linear_congruential
+ linear_feedback_shift
+ lognormal_distribution
+ mersenne_twister
+ normal_distribution
+ poisson_distribution
+ random_number_generator
+ ranlux
+ shuffle_output
+ subtract_with_carry
+ triangle_distribution
+ uniform_01
+ uniform_int
+ uniform_on_sphere
+ uniform_real
+ uniform_smallint
+ variate_generator
+ xor_combine
+;
+
+path-constant here : . ;
+path-constant boost-root : ../../.. ;
+
+# Figure out where the root of the boost tree is relative
+# to the html directory.
+local BOOST_ROOT = [ path.relative-to
+ [ path.join [ path.pwd ] html ]
+ [ path.root
+ [ path.make $(boost-root) ]
+ [ path.pwd ] ] ] ;
+
+doxygen reference :
+ $(here)/../../../boost/random/$(doxygen_files).hpp
+ $(here)/../../../boost/nondet_random.hpp
+ $(here)/../../../boost/random.hpp
+ :
+ <doxygen:param>EXPAND_ONLY_PREDEF=YES
+ <doxygen:param>"ALIASES= \\
+ xmlnote=\"@xmlonly <note><para> @endxmlonly\" \\
+ endxmlnote=\"@xmlonly </para></note> @endxmlonly\" \\
+ blockquote=\"@xmlonly <blockquote><para> @endxmlonly\" \\
+ endblockquote=\"@xmlonly </para></blockquote> @endxmlonly\" \\
+ boost=\"$(BOOST_ROOT)\" \\
+ random_distribution=\"@xmlonly <link
linkend=\\\"boost_random.reference.concepts.random_distribution\\\">random
distribution</link> @endxmlonly\" \\
+ pseudo_random_number_generator=\"@xmlonly <link
linkend=\\\"boost_random.reference.concepts.pseudo_random_number_generator\\\">pseudo-random
number generator</link> @endxmlonly\" \\
+ uniform_random_number_generator=\"@xmlonly <link
linkend=\\\"boost_random.reference.concepts.uniform_random_number_generator\\\">uniform
random number generator</link> @endxmlonly\" \\
+ nondeterministic_random_number_generator=\"@xmlonly <link
linkend=\\\"boost_random.reference.concepts.non_deterministic_uniform_random_number_generator\\\">non-deterministic
random number generator</link> @endxmlonly\" \\
+ number_generator=\"@xmlonly <link
linkend=\\\"boost_random.reference.concepts.number_generator\\\">number
generator</link> @endxmlonly\" \\
+ generators=\"@xmlonly <link
linkend=\\\"boost_random.reference.generators\\\">generators</link>
@endxmlonly\" \\
+ distributions=\"@xmlonly <link
linkend=\\\"boost_random.reference.distributions\\\">distributions</link>
@endxmlonly\" \\
+ additive_combine=\"@xmlonly <classname
alt=\\\"boost::random::additive_combine\\\">additive_combine</classname>
@endxmlonly\" \\
+ discard_block=\"@xmlonly <classname
alt=\\\"boost::random::discard_block\\\">discard_block</classname>
@endxmlonly\" \\
+ lagged_fibonacci=\"@xmlonly<classname
alt=\\\"boost::random::lagged_fibonacci\\\">lagged_fibonacci</classname>@endxmlonly\"
\\
+ linear_congruential=\"@xmlonly<classname
alt=\\\"boost::random::linear_congruential\\\">linear_congruential</classname>@endxmlonly\"
\\
+ minstd_rand=\"@xmlonly <classname
alt=\\\"boost::minstd_rand\\\">minstd_rand</classname> @endxmlonly\" \\
+ minstd_rand0=\"@xmlonly <classname
alt=\\\"boost::minstd_rand0\\\">minstd_rand0</classname> @endxmlonly\" \\
+ rand48=\"@xmlonly <classname
alt=\\\"boost::rand48\\\">rand48</classname> @endxmlonly\" \\
+ mt11213b=\"@xmlonly <classname
alt=\\\"boost::mt11213b\\\">mt11213b</classname> @endxmlonly\" \\
+ mt19937=\"@xmlonly <classname
alt=\\\"boost::mt19937\\\">mt19937</classname> @endxmlonly\" \\
+ ecuyer1988=\"@xmlonly <classname
alt=\\\"boost::ecuyer1988\\\">ecuyer1988</classname> @endxmlonly\" \\
+ lagged_fibonacci607=\"@xmlonly <classname
alt=\\\"boost::lagged_fibonacci607\\\">lagged_fibonacci607</classname>
@endxmlonly\" \\
+ lagged_fibonacci44497=\"@xmlonly <classname
alt=\\\"boost::lagged_fibonacci44497\\\">lagged_fibonacci44497</classname>
@endxmlonly\" \\
+ bernoulli_distribution=\"@xmlonly <classname
alt=\\\"boost::bernoulli_distribution\\\">bernoulli_distribution</classname>
@endxmlonly\" \\
+ cauchy_distribution=\"@xmlonly <classname
alt=\\\"boost::cauchy_distribution\\\">cauchy_distribution</classname>
@endxmlonly\" \\
+ uniform_01=\"@xmlonly<classname
alt=\\\"boost::uniform_01\\\">uniform_01</classname>@endxmlonly\" \\
+ random_device=\"@xmlonly<classname
alt=\\\"boost::random_device\\\">random_device</classname>@endxmlonly\""
+ <doxygen:param>HIDE_UNDOC_MEMBERS=NO
+ <doxygen:param>QUIET=YES
+ <doxygen:param>WARN_IF_UNDOCUMENTED=NO
+ <doxygen:param>EXTRACT_PRIVATE=NO
+ <doxygen:param>ENABLE_PREPROCESSING=YES
+ <doxygen:param>MACRO_EXPANSION=YES
+ <doxygen:param>SEARCH_INCLUDES=NO
+ <doxygen:param>"PREDEFINED= \\
+ \"BOOST_RANDOM_DOXYGEN=1\" \\
+ \"BOOST_PREVENT_MACRO_SUBSTITUTION=\" \\
+ \"BOOST_STATIC_ASSERT(x)=\" \\
+ \"BOOST_STATIC_CONSTANT(type,value)=static const type value\" \\
+ \"BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self,T,t)=explicit
Self(T t)\" \\
+
\"BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self,T,t)=template<class T>
explicit Self(T& t)\" \\
+ \"BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self,T,t)=void seed(T t)\" \\
+ \"BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self,T,t)=template<class T>
void seed(T& t)\""
+ <reftitle>"Headers"
+ <doxygen:xml-imagedir>images/random
+;
+
+xml random : random.qbk : <dependency>reference ;
+
+boostbook standalone :
+ random
+ :
+ <implicit-dependency>reference
+ <xsl:param>boost.root=../../../..
+ <xsl:param>chunk.section.depth=2
+;
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/concepts.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,282 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[section Introduction]
+
+Random numbers are required in a number of different problem domains, such
as
+
+* numerics (simulation, Monte-Carlo integration)
+* games (non-deterministic enemy behavior)
+* security (key generation)
+* testing (random coverage in white-box tests)
+
+The Boost Random Number Generator Library provides a framework for random
+number generators with well-defined properties so that the generators can
be
+used in the demanding numerics and security domains. For a general
+introduction to random numbers in numerics, see
+
+[:"Numerical Recipes in C: The art of scientific computing", William H.
Press,
+Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd ed., 1992,
+pp. 274-328]
+
+Depending on the requirements of the problem domain, different variations
of
+random number generators are appropriate:
+
+* non-deterministic random number generator
+* pseudo-random number generator
+* quasi-random number generator
+
+All variations have some properties in common, these concepts (in the STL
+sense) are called __NumberGenerator and __UniformRandomNumberGenerator.
Each
+concept will be defined in a subsequent section.
+
+The goals for this library are the following:
+
+* allow easy integration of third-party random-number generators
+* define a validation interface for the generators
+* provide easy-to-use front-end classes which model popular distributions
+* provide maximum efficiency
+* allow control on quantization effects in front-end processing (not yet
done)
+
+[endsect]
+
+[section Number Generator]
+
+A number generator is a /function object/ (std:20.3
[lib.function.objects]) that
+takes zero arguments. Each call to `operator()` returns a number. In the
+following table, X denotes a number generator class returning objects of
type
+T, and u is a value of X.
+
+[table NumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X::result_type`] [`T`] [`std::numeric_limits<T>::is_specialized` is
+ `true`, `T` is __LessThanComparable]]
+ [[`u.operator()()`] [`T`] [-]]
+]
+
+[note The NumberGenerator requirements do not impose any restrictions on
the
+characteristics of the returned numbers.]
+
+[endsect]
+
+[section Uniform Random Number Generator]
+
+A uniform random number generator is a __NumberGenerator that provides a
+sequence of random numbers uniformly distributed on a given range. The
+range can be compile-time fixed or available (only) after run-time
construction
+of the object.
+
+The /tight lower bound/ of some (finite) set S is the (unique) member l in
S, so
+that for all v in S, l <= v holds. Likewise, the /tight upper bound/ of
some
+(finite) set S is the (unique) member u in S, so that for all v in S, v <=
u
+holds.
+
+In the following table, X denotes a number generator class returning
objects
+of type T, and v is a const value of X.
+
+[table UniformRandomNumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X::has_fixed_range`] [`bool`] [compile-time constant; if `true`, the
range
+ on which the random numbers are
uniformly
+ distributed is known at compile-time
and
+ members `min_value` and `max_value`
exist.
+ Note: This flag may also be `false`
due to
+ compiler limitations]]
+ [[`X::min_value`] [`T`] [compile-time constant; `min_value` is only
defined if
+ `has_fixed_range` is `true`. If it exists, it
is
+ equal to `v.min()`.]]
+ [[`X::max_value`] [`T`] [compile-time constant; `max_value` is only
defined if
+ `has_fixed_range` is `true`. If it exists, it
is
+ equal to `v.max()`]]
+ [[`v.min()`] [`T`] [tight lower bound on the set of all values returned
by
+ `operator()`. The return value of this function
shall not
+ change during the lifetime of the object.]]
+ [[`v.max()`] [`T`] [if `std::numeric_limits<T>::is_integer`, tight upper
+ bound on the set of all values returned by
`operator()`,
+ otherwise, the smallest representable number larger
than
+ the tight upper bound on the set of all values
returned
+ by `operator()`. In any case, the return value of
this
+ function shall not change during the lifetime of the
+ object.]]
+]
+
+The member functions `min`, `max`, and `operator()` shall have amortized
+constant time complexity.
+
+[note For integer generators (i.e. integer `T`), the generated values `x`
+fulfill `min() <= x <= max()`, for non-integer generators (i.e. non-integer
+`T`), the generated values `x` fulfill `min() <= x < max()`.
+
+Rationale: The range description with min and max serves two purposes.
First,
+it allows scaling of the values to some canonical range, such as [0..1).
+Second, it describes the significant bits of the values, which may be
+relevant for further processing.
+
+The range is a closed interval \[min,max\] for integers, because the
underlying
+type may not be able to represent the half-open interval \[min,max+1). It
is
+a half-open interval \[min, max) for non-integers, because this is much
more
+practical for borderline cases of continuous distributions.]
+
+[note The __UniformRandomNumberGenerator concept does not require
+`operator()(long)` and thus it does not fulfill the `RandomNumberGenerator`
+(std:25.2.11 \[lib.alg.random.shuffle\]) requirements. Use the
+__random_number_generator adapter for that.
+
+Rationale: `operator()(long)` is not provided, because mapping the output
of
+some generator with integer range to a different integer range is not
trivial.]
+
+[endsect]
+
+[section Non-deterministic Uniform Random Number Generator]
+
+A non-deterministic uniform random number generator is a
+__UniformRandomNumberGenerator that is based on some stochastic process.
+Thus, it provides a sequence of truly-random numbers. Examples for such
+processes are nuclear decay, noise of a Zehner diode, tunneling of quantum
+particles, rolling a die, drawing from an urn, and tossing a coin.
Depending
+on the environment, inter-arrival times of network packets or keyboard
events
+may be close approximations of stochastic processes.
+
+The class __random_device is a model for a non-deterministic random number
+generator.
+
+[note This type of random-number generator is useful for security
+applications, where it is important to prevent an outside attacker from
+guessing the numbers and thus obtaining your encryption or authentication
key.
+Thus, models of this concept should be cautious not to leak any
information,
+to the extent possible by the environment. For example, it might be
advisable
+to explicitly clear any temporary storage as soon as it is no longer
needed.]
+
+[endsect]
+
+[section Pseudo-Random Number Generator]
+
+A pseudo-random number generator is a __UniformRandomNumberGenerator which
+provides a deterministic sequence of pseudo-random numbers, based on some
+algorithm and internal state. [classref boost::random::linear_congruential
+Linear congruential] and [classref boost::random::inversive_congruential
+inversive congruential] generators are examples of such [prng pseudo-random
+number generators]. Often, these generators are very sensitive to their
+parameters. In order to prevent wrong implementations from being used, an
+external testsuite should check that the generated sequence and the
validation
+value provided do indeed match.
+
+Donald E. Knuth gives an extensive overview on pseudo-random number
generation
+in his book "The Art of Computer Programming, Vol. 2, 3rd edition,
+Addison-Wesley, 1997". The descriptions for the specific generators contain
+additional references.
+
+[note Because the state of a pseudo-random number generator is necessarily
+finite, the sequence of numbers returned by the generator will loop
+eventually.]
+
+In addition to the __UniformRandomNumberGenerator requirements,
+a pseudo-random number generator has some additional requirements. In the
+following table, `X` denotes a pseudo-random number generator class
returning
+objects of type `T`, `x` is a value of `T`, `u` is a value of `X`, and `v`
is
+a const value of `X`.
+
+[table PseudoRandomNumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X()`] [-] [creates a generator in some implementation-defined state.
+ Note: Several generators thusly created may possibly
produce
+ dependent or identical sequences of random numbers.]]
+ [[`explicit X(...)`] [-] [creates a generator with user-provided state;
the
+ implementation shall specify the constructor
+ argument(s)]]
+ [[`u.seed(...)`] [`void`] [sets the current state according to the
+ argument(s); at least functions with the same
+ signature as the non-default constructor(s)
+ shall be provided.]]
+ [[`X::validation(x)`] [`bool`] [compares the pre-computed and hardcoded
+ 10001th element in the generator's random
+ number sequence with x. The generator
must
+ have been constructed by its default
+ constructor and seed must not have been
+ called for the validation to be
+ meaningful.]]
+]
+
+[note The seed member function is similar to the assign member function in
+STL containers. However, the naming did not seem appropriate.]
+
+Classes which model a pseudo-random number generator shall also model
+__EqualityComparable, i.e. implement `operator==`. Two pseudo-random number
+generators are defined to be /equivalent/ if they both return an identical
+sequence of numbers starting from a given state.
+
+Classes which model a pseudo-random number generator should also model the
+__Streamable concept, i.e. implement `operator<<` and `operator>>`. If so,
+`operator<<` writes all current state of the pseudo-random number generator
+to the given `ostream` so that `operator>>` can restore the state at a
later
+time. The state shall be written in a platform-independent manner, but it
is
+assumed that the `locales` used for writing and reading be the same. The
+pseudo-random number generator with the restored state and the original at
+the just-written state shall be equivalent.
+
+Classes which model a pseudo-random number generator may also model the
+__CopyConstructible and __Assignable concepts. However, note that the
+sequences of the original and the copy are strongly correlated (in fact,
+they are identical), which may make them unsuitable for some problem
domains.
+Thus, copying pseudo-random number generators is discouraged; they should
+always be passed by (non-const) reference.
+
+The classes __rand48, __minstd_rand, and __mt19937 are models for a
+pseudo-random number generator.
+
+[note This type of random-number generator is useful for numerics, games
and
+testing. The non-zero arguments constructor(s) and the `seed()` member
+function(s) allow for a user-provided state to be installed in the
generator.
+This is useful for debugging Monte-Carlo algorithms and analyzing
particular
+test scenarios. The __Streamable concept allows to save/restore the state
of
+the generator, for example to re-run a test suite at a later time.]
+
+[endsect]
+
+[section Random Distribution]
+
+A random distribution produces random numbers distributed according to some
+distribution, given uniformly distributed random values as input. In the
+following table, `X` denotes a random distribution class returning objects
of
+type `T`, `u` is a value of `X`, `x` is a (possibly const) value of `X`,
and
+`e` is an lvalue of an arbitrary type that meets the requirements of a
+__UniformRandomNumberGenerator, returning values of type `U`.
+
+[table Random distribution requirements (in addition to NumberGenerator,
CopyConstructible, and Assignable)
+ [[expression] [return type] [pre/post-condition] [complexity]]
+ [[`X::input_type`] [`U`] [-] [compile-time]]
+ [[`u.reset()`] [`void`] [subsequent uses of `u` do not depend on values
+ produced by `e` prior to invoking `reset`.]
+ [constant]]
+ [[`u(e)`] [`T`] [the sequence of numbers returned by successive
invocations
+ with the same object `e` is randomly distributed with
some
+ probability density function `p(x)`]
+ [amortized constant number of invocations of `e`]]
+ [[`os << x`] [`std::ostream&`] [writes a textual representation for the
+ parameters and additional internal data
of
+ the distribution `x` to `os`.
+ post: The `os.fmtflags` and fill
character
+ are unchanged.]
+ [O(size of state)]]
+ [[`is >> u`] [`std::istream&`] [restores the parameters and additional
+ internal data of the distribution `u`.
+ pre: `is` provides a textual
representation
+ that was previously written by
`operator<<`
+ post: The `is.fmtflags` are unchanged.]
+ [O(size of state)]]
+]
+
+Additional requirements: The sequence of numbers produced by repeated
+invocations of `x(e)` does not change whether or not `os << x` is invoked
+between any of the invocations `x(e)`. If a textual representation is
written
+using `os << x` and that representation is restored into the same or a
+different object `y` of the same type using `is >> y`, repeated invocations
+of `y(e)` produce the same sequence of random numbers as would repeated
+invocations of `x(e)`.
+
+[endsect]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/distribution_performance_linux.qbk Mon May 31
00:54:22 2010
@@ -0,0 +1,23 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[table Distributions (Linux)
+ [[\[M rn/sec\]][minstd_rand][kreutzer1986][mt19937][lagged_fibonacci607]]
+ [[uniform_int][31.25][30.581][11.5607][16.0514]]
+ [[geometric][5.20833][6.66223][6.68449][6.73854]]
+ [[binomial][5.01505][21.7865][4.38982][10.9529]]
+ [[poisson][22.8311][22.1729][20.8768][24.3902]]
+ [[uniform_real][18.2815][84.0336][67.1141][72.4638]]
+ [[triangle][13.2802][33.4448][33.67][36.4964]]
+ [[exponential][6.19195][8.49618][8.2713][8.65052]]
+ [[normal polar][5.78369][6.56599][6.49773][6.48508]]
+ [[lognormal][4.13565][4.53515][4.51467][4.57875]]
+ [[cauchy][6.07533][7.92393][7.77605][8.35422]]
+ [[gamma][6.07533][7.92393][7.83085][8.34725]]
+ [[uniform_on_sphere][1.43472][1.62075][1.5625][1.5949]]
+]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/distribution_performance_windows.qbk Mon May 31
00:54:22 2010
@@ -0,0 +1,23 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[table Distributions (Windows)
+ [[\[M rn/sec\]][minstd_rand][kreutzer1986][mt19937][lagged_fibonacci607]]
+ [[uniform_int][14.7449][27.465][6.65292][28.5714]]
+ [[geometric][7.10328][5.53649][3.73622][9.38438]]
+ [[binomial][6.20155][5.78135][2.65118][4.65463]]
+ [[poisson][15.9617][8.77886][12.5486][17.9276]]
+ [[uniform_real][49.6032][27.1223][31.6857][60.35]]
+ [[triangle][21.3356][11.7][14.2857][22.3015]]
+ [[exponential][14.3493][6.05473][10.8472][12.982]]
+ [[normal polar][4.24394][2.75748][7.04871][6.09533]]
+ [[lognormal][3.30066][1.34822][5.36913][4.0024]]
+ [[cauchy][11.4286][2.92372][12.0525][7.55629]]
+ [[gamma][10.5263][3.72523][12.1433][5.87682]]
+ [[uniform_on_sphere][0.680874][0.38004][1.18737][0.486334]]
+]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/distributions.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,72 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+In addition to the [link boost_random.reference.generators random number
generators],
+this library provides distribution functions which map one distribution
+(often a uniform distribution provided by some generator) to another.
+
+Usually, there are several possible implementations of any given mapping.
+Often, there is a choice between using more space, more invocations of the
+underlying source of random numbers, or more time-consuming arithmetic such
+as trigonometric functions. This interface description does not mandate any
+specific implementation. However, implementations which cannot reach
certain
+values of the specified distribution or otherwise do not converge
+statistically to it are not acceptable.
+
+[table distributions
+ [[distribution] [explanation] [example]]
+ [[__uniform_smallint] [discrete uniform distribution on a small set of
integers
+ (much smaller than the range of the underlying
+ generator)]
+ [drawing from an urn]]
+ [[__uniform_int] [discrete uniform distribution on a set of integers; the
+ underlying generator may be called several times to
gather
+ enough randomness for the output]
+ [drawing from an urn]]
+ [[__uniform_01] [continuous uniform distribution on the range [0,1);
+ important basis for other distributions]
+ [-]]
+ [[__uniform_real] [continuous uniform distribution on some range [min,
max) of
+ real numbers]
+ [for the range [0, 2pi): randomly dropping a stick and
+ measuring its angle in radians (assuming the angle is
+ uniformly distributed)]]
+ [[__bernoulli_distribution] [Bernoulli experiment: discrete boolean
valued
+ distribution with configurable probability]
+ [tossing a coin (p=0.5)]]
+ [[__binomial_distribution] [counts outcomes of repeated Bernoulli
+ experiments]
+ [tossing a coin 20 times and counting how many
+ front sides are shown]]
+ [[__cauchy_distribution][cauchy distribution][-]]
+ [[__gamma_distribution][gamma distribution][-]]
+ [[__poisson_distribution][poisson distribution]
+ [counting the number of alpha particles emitted
+ by radioactive matter in a fixed period of
time]]
+ [[__geometric_distribution] [measures distance between outcomes of
repeated
+ Bernoulli experiments]
+ [throwing a die several times and counting the
+ number of tries until a "6" appears for the
+ first time]]
+ [[__triangle_distribution] [triangle distribution] [-]]
+ [[__exponential_distribution] [exponential distribution]
+ [measuring the inter-arrival time of alpha
+ particles emitted by radioactive matter]]
+ [[__normal_distribution] [counts outcomes of (infinitely) repeated
Bernoulli
+ experiments]
+ [tossing a coin 10000 times and counting how
many
+ front sides are shown]]
+ [[__lognormal_distribution] [lognormal distribution (sometimes used in
+ simulations)]
+ [measuring the job completion time of an
assembly
+ line worker]]
+ [[__uniform_on_sphere] [uniform distribution on a unit sphere of
arbitrary
+ dimension]
+ [choosing a random point on Earth (assumed to be a
+ sphere) where to spend the next vacations]]
+]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/generator_defs.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,37 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[template rand48_speed[] 68%]
+[template lrand48_run_time_speed[] 12%]
+[template minstd_rand0_speed[] 32%]
+[template minstd_rand_speed[] 26%]
+[template ecuyer_combined_speed[] 11%]
+[template kreutzer1986_speed[] 46%]
+[template hellekalek1995__inversive__speed[] 2%]
+[template mt11213b_speed[] 95%]
+[template mt19937_speed[] 100%]
+[template lagged_fibonacci607_speed[] 42%]
+[template lagged_fibonacci1279_speed[] 44%]
+[template lagged_fibonacci2281_speed[] 44%]
+[template lagged_fibonacci3217_speed[] 43%]
+[template lagged_fibonacci4423_speed[] 44%]
+[template lagged_fibonacci9689_speed[] 44%]
+[template lagged_fibonacci19937_speed[] 44%]
+[template lagged_fibonacci23209_speed[] 44%]
+[template lagged_fibonacci44497_speed[] 44%]
+[template subtract_with_carry_speed[] 72%]
+[template subtract_with_carry_01_speed[] 54%]
+[template ranlux3_speed[] 6%]
+[template ranlux4_speed[] 4%]
+[template ranlux3_01_speed[] 5%]
+[template ranlux4_01_speed[] 2%]
+[template ranlux64_3_speed[] 6%]
+[template ranlux64_4_speed[] 4%]
+[template ranlux64_3_01_speed[] 4%]
+[template ranlux64_4_01_speed[] 2%]
+[template mt19937ar_c_speed[] 97%]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/generator_performance_linux.qbk Mon May 31
00:54:22 2010
@@ -0,0 +1,42 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[table Basic Generators (Linux)
+ [[generator] [M rn/sec] [time per random number \[nsec\]] [relative
speed compared to fastest \[percent\]]]
+ [[rand48][312.5][3.2][100%]]
+ [[lrand48 run-time][303.03][3.3][96%]]
+ [[lrand48 (C library)][67.5676][14.8][21%]]
+ [[minstd_rand0][96.1538][10.4][30%]]
+ [[minstd_rand][93.4579][10.7][29%]]
+ [[ecuyer combined][60.6061][16.5][19%]]
+ [[kreutzer1986][97.0874][10.3][31%]]
+ [[taus88][243.902][4.1][78%]]
+ [[hellekalek1995 (inversive)][2.405][415.8][0%]]
+ [[mt11213b][138.889][7.2][44%]]
+ [[mt19937][138.889][7.2][44%]]
+ [[lagged_fibonacci607][81.9672][12.2][26%]]
+ [[lagged_fibonacci1279][81.9672][12.2][26%]]
+ [[lagged_fibonacci2281][81.9672][12.2][26%]]
+ [[lagged_fibonacci3217][81.3008][12.3][26%]]
+ [[lagged_fibonacci4423][80.6452][12.4][25%]]
+ [[lagged_fibonacci9689][80.6452][12.4][25%]]
+ [[lagged_fibonacci19937][80][12.5][25%]]
+ [[lagged_fibonacci23209][80.6452][12.4][25%]]
+ [[lagged_fibonacci44497][79.3651][12.6][25%]]
+ [[subtract_with_carry][76.9231][13][24%]]
+ [[subtract_with_carry_01][45.045][22.2][14%]]
+ [[ranlux3][8.78735][113.8][2%]]
+ [[ranlux4][5.11771][195.4][1%]]
+ [[ranlux3_01][5.29381][188.9][1%]]
+ [[ranlux4_01][3.04599][328.3][0%]]
+ [[ranlux64_3][8.74126][114.4][2%]]
+ [[ranlux64_4][5.09684][196.2][1%]]
+ [[ranlux64_3_01][5.30786][188.4][1%]]
+ [[ranlux64_4_01][3.02847][330.2][0%]]
+ [[mt19937ar.c][95.2381][10.5][30%]]
+]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/generator_performance_windows.qbk Mon May 31
00:54:22 2010
@@ -0,0 +1,41 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[table Basic Generators (Windows)
+ [[generator] [M rn/sec] [time per random number \[nsec\]] [relative
speed compared to fastest \[percent\]]]
+ [[rand48][98.5222][10.15][67%]]
+ [[lrand48 run-time][17.343][57.66][11%]]
+ [[minstd_rand0][46.3822][21.56][31%]]
+ [[minstd_rand][38.5505][25.94][26%]]
+ [[ecuyer combined][15.8028][63.28][10%]]
+ [[kreutzer1986][66.6667][15][45%]]
+ [[taus88][145.56][6.87][100%]]
+ [[hellekalek1995 (inversive)][4.26658][234.38][2%]]
+ [[mt11213b][139.082][7.19][95%]]
+ [[mt19937][142.248][7.03][97%]]
+ [[lagged_fibonacci607][61.5385][16.25][42%]]
+ [[lagged_fibonacci1279][58.7199][17.03][40%]]
+ [[lagged_fibonacci2281][64.0205][15.62][43%]]
+ [[lagged_fibonacci3217][62.1118][16.1][42%]]
+ [[lagged_fibonacci4423][63.3714][15.78][43%]]
+ [[lagged_fibonacci9689][64.6412][15.47][44%]]
+ [[lagged_fibonacci19937][63.3714][15.78][43%]]
+ [[lagged_fibonacci23209][64.6412][15.47][44%]]
+ [[lagged_fibonacci44497][64.0205][15.62][43%]]
+ [[subtract_with_carry][92.7644][10.78][63%]]
+ [[subtract_with_carry_01][78.0031][12.82][53%]]
+ [[ranlux3][9.86193][101.4][6%]]
+ [[ranlux4][5.80754][172.19][3%]]
+ [[ranlux3_01][7.15103][139.84][4%]]
+ [[ranlux4_01][3.8345][260.79][2%]]
+ [[ranlux64_3][9.10415][109.84][6%]]
+ [[ranlux64_4][5.05919][197.66][3%]]
+ [[ranlux64_3_01][6.12445][163.28][4%]]
+ [[ranlux64_4_01][3.39167][294.84][2%]]
+ [[mt19937ar.c][125.471][7.97][86%]]
+]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/generators.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,88 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+This library provides several [prng pseudo-random number generators]. The
+quality of a [prng pseudo random number generator] crucially depends on
both
+the algorithm and its parameters. This library implements the algorithms as
+class templates with template value parameters, hidden in
+`namespace boost::random`. Any particular choice of parameters is
represented
+as the appropriately specializing `typedef` in `namespace boost`.
+
+[prng Pseudo-random number generators] should not be constructed
(initialized)
+frequently during program execution, for two reasons. First, initialization
+requires full initialization of the internal state of the generator. Thus,
+generators with a lot of internal state (see below) are costly to
initialize.
+Second, initialization always requires some value used as a "seed" for the
+generated sequence. It is usually difficult to obtain several good seed
+values. For example, one method to obtain a seed is to determine the
current
+time at the highest resolution available, e.g. microseconds or nanoseconds.
+When the [prng pseudo-random number generator] is initialized again with
the
+then-current time as the seed, it is likely that this is at a near-constant
+(non-random) distance from the time given as the seed for first
+initialization. The distance could even be zero if the resolution of the
+clock is low, thus the generator re-iterates the same sequence of random
+numbers. For some applications, this is inappropriate.
+
+Note that all [prng pseudo-random number generators] described below are
+__CopyConstructible and __Assignable. Copying or assigning a generator will
+copy all its internal state, so the original and the copy will generate the
+identical sequence of random numbers. Often, such behavior is not wanted.
In
+particular, beware of the algorithms from the standard library such as
+`std::generate`. They take a functor argument by value, thereby invoking
the
+copy constructor when called.
+
+The following table gives an overview of some characteristics of the
+generators. The cycle length is a rough estimate of the quality of the
+generator; the approximate relative speed is a performance measure, higher
+numbers mean faster random number generation.
+
+[table generators
+ [[generator] [length of cycle] [approx. memory requirements] [approx.
speed compared to fastest] [comment]]
+ [[__minstd_rand0] [2[sup 31]-2] [`sizeof(int32_t)`]
[[minstd_rand0_speed]] [-]]
+ [[__minstd_rand] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand_speed]]
[-]]
+ [[__rand48][2[sup 48]-1] [`sizeof(uint64_t)`] [[rand48_speed]] [-]]
+ [[__ecuyer1988] [approx. 2[sup 61]] [`2*sizeof(int32_t)`]
[[ecuyer_combined_speed]] [-]]
+ [[__kreutzer1986] [?] [`1368*sizeof(uint32_t)`] [[kreutzer1986_speed]]
[-]]
+ [[__taus88] [~2[sup 88]] [`3*sizeof(uint32_t)`] [[taus88_speed]] [-]]
+ [[__hellekalek1995] [2[sup 31]-1] [`sizeof(int32_t)`]
[[hellekalek1995__inversive__speed]] [good uniform distribution in several
dimensions]]
+ [[__mt11213b] [2[sup 11213]-1] [`352*sizeof(uint32_t)`]
[[mt11213b_speed]] [good uniform distribution in up to 350 dimensions]]
+ [[__mt19937] [2[sup 19937]-1] [`625*sizeof(uint32_t)`] [[mt19937_speed]]
[good uniform distribution in up to 623 dimensions]]
+ [[__lagged_fibonacci607] [~2[sup 32000]] [`607*sizeof(double)`]
[[lagged_fibonacci607_speed]] [-]]
+ [[__lagged_fibonacci1279] [~2[sup 67000]] [`1279*sizeof(double)`]
[[lagged_fibonacci1279_speed]] [-]]
+ [[__lagged_fibonacci2281] [~2[sup 120000]] [`2281*sizeof(double)`]
[[lagged_fibonacci2281_speed]] [-]]
+ [[__lagged_fibonacci3217] [~2[sup 170000]] [`3217*sizeof(double)`]
[[lagged_fibonacci3217_speed]] [-]]
+ [[__lagged_fibonacci4423] [~2[sup 230000]] [`4423*sizeof(double)`]
[[lagged_fibonacci4423_speed]] [-]]
+ [[__lagged_fibonacci9689] [~2[sup 510000]] [`9689*sizeof(double)`]
[[lagged_fibonacci9689_speed]] [-]]
+ [[__lagged_fibonacci19937] [~2[sup 1050000]] [`19937*sizeof(double)`]
[[lagged_fibonacci19937_speed]] [-]]
+ [[__lagged_fibonacci23209] [~2[sup 1200000]] [`23209*sizeof(double)`]
[[lagged_fibonacci23209_speed]] [-]]
+ [[__lagged_fibonacci44497] [~2[sup 2300000]] [`44497*sizeof(double)`]
[[lagged_fibonacci44497_speed]] [-]]
+ [[__ranlux3] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux3_speed]] [-]]
+ [[__ranlux4] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux4_speed]] [-]]
+ [[__ranlux64_3] [~10[sup 171]] [`24*sizeof(int64_t)`]
[[ranlux64_3_speed]] [-]]
+ [[__ranlux64_4] [~10[sup 171]] [`24*sizeof(int64_t)`]
[[ranlux64_4_speed]] [-]]
+ [[__ranlux3_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux3_speed]]
[-]]
+ [[__ranlux4_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux4_speed]]
[-]]
+ [[__ranlux64_3_01] [~10[sup 171]] [`24*sizeof(double)`]
[[ranlux64_3_speed]] [-]]
+ [[__ranlux64_4_01] [~10[sup 171]] [`24*sizeof(double)`]
[[ranlux64_4_speed]] [-]]
+]
+
+As observable from the table, there is generally a
quality/performance/memory
+trade-off to be decided upon when choosing a random-number generator. The
+multitude of generators provided in this library allows the application
+programmer to optimize the trade-off with regard to his application domain.
+Additionally, employing several fundamentally different random number
+generators for a given application of Monte Carlo simulation will improve
+the confidence in the results.
+
+If the names of the generators don't ring any bell and you have no idea
+which generator to use, it is reasonable to employ __mt19937 for a start:
It
+is fast and has acceptable quality.
+
+[note These random number generators are not intended for use in
applications
+where non-deterministic random numbers are required. See __random_device
+for a choice of (hopefully) non-deterministic random number generators.]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/nondet_random.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,103 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[section Header <boost/nondet_random.hpp> Synopsis]
+
+ namespace boost {
+ class random_device;
+ } // namespace boost
+
+[endsect]
+
+[section Class random_device]
+
+[section Synopsis]
+
+ class random_device : noncopyable
+ {
+ public:
+ typedef unsigned int result_type;
+ static const bool has_fixed_range = true;
+ static const result_type min_value = /* implementation defined */;
+ static const result_type max_value = /* implementation defined */;
+ result_type min() const;
+ result_type max() const;
+ explicit random_device(const std::string& token = default_token);
+ ~random_device();
+ double entropy() const;
+ unsigned int operator()();
+ };
+
+[endsect]
+
+[section Description]
+
+Class `random_device` models a non-deterministic random number generator.
It
+uses one or more implementation-defined stochastic processes to generate a
+sequence of uniformly distributed non-deterministic random numbers. For
those
+environments where a non-deterministic random number generator is not
+available, class random_device must not be implemented. See
+
+[:"Randomness Recommendations for Security", D. Eastlake, S. Crocker,
+J. Schiller, Network Working Group, RFC 1750, December 1994]
+
+for further discussions.
+
+[note Some operating systems abstract the computer hardware enough to make
it
+difficult to non-intrusively monitor stochastic processes. However,
several do
+provide a special device for exactly this purpose. It seems to be
impossible
+to emulate the functionality using Standard C++ only, so users should be
aware
+that this class may not be available on all platforms.]
+
+[endsect]
+
+[section Members]
+
+ explicit random_device(const std::string& token = default_token)
+
+Effects: Constructs a random_device, optionally using the given token as an
+access specification (for example, a URL) to some implementation-defined
+service for monitoring a stochastic process.
+
+ double entropy() const
+
+Returns: An entropy estimate for the random numbers returned by
`operator()`,
+in the range `min()` to `log2(max()+1)`. A deterministic random number
+generator (e.g. a pseudo-random number engine) has entropy 0.
+
+Throws: Nothing.
+
+[endsect]
+
+Implementation Note for Linux
+On the Linux operating system, token is interpreted as a filesystem path.
It
+is assumed that this path denotes an operating system pseudo-device which
+generates a stream of non-deterministic random numbers. The pseudo-device
+should never signal an error or end-of-file. Otherwise,
std::ios_base::failure
+is thrown. By default, random_device uses the /dev/urandom pseudo-device to
+retrieve the random numbers. Another option would be to specify the
+/dev/random pseudo-device, which blocks on reads if the entropy pool has no
+more random bits available.
+
+[endsect]
+
+[section Performance]
+
+The test program nondet_random_speed.cpp measures the execution times of
the
+nondet_random.hpp implementation of the above algorithms in a tight loop.
+The performance has been evaluated on a Pentium Pro 200 MHz with gcc
2.95.2,
+Linux 2.2.13, glibc 2.1.2.
+
+[table preformance
+ [[class] [time per invocation \[usec\]]]
+ [[random_device] [92.0]]
+]
+
+The measurement error is estimated at +/- 1 usec.
+
+[endsect]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/performance.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,30 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+For some people, performance of random number generation is an important
+consideration when choosing a random number generator or a particular
+distribution function. This page provides numerous performance tests with
+the wide variety of generators and distributions available in the boost
+library.
+
+The performance has been evaluated on an Intel(R) Xeon(TM) MP
+CPU 3.66GHz, Gentoo Base System release 1.12.11.1, GCC 4.3.2,
+glibc 2.9 and on an Intel(R) Core(TM)2 CPU T7600
+@xxxx Ghz with Microsoft Windows XP Professional, Service Pack 2 Build
+2600, Microsoft Visual C++ 2008 9.0.21022.
+The speed is reported in million random numbers
+per second (M rn/sec), generated in a tight loop.
+
+[include generator_performance_linux.qbk]
+[include generator_performance_windows.qbk]
+
+Note that the lagged Fibonacci and ranlux_01 generators produce
+floating-point numbers, whereas all others produce integers.
+
+[include distribution_performance_linux.qbk]
+[include distribution_performance_windows.qbk]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/performance_data.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,39 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[template rand48_speed[] 100%]
+[template lrand48_run_time_speed[] 96%]
+[template lrand48__C_library__speed[] 21%]
+[template minstd_rand0_speed[] 30%]
+[template minstd_rand_speed[] 29%]
+[template ecuyer_combined_speed[] 19%]
+[template kreutzer1986_speed[] 31%]
+[template taus88_speed[] 78%]
+[template hellekalek1995__inversive__speed[] 0%]
+[template mt11213b_speed[] 44%]
+[template mt19937_speed[] 44%]
+[template lagged_fibonacci607_speed[] 26%]
+[template lagged_fibonacci1279_speed[] 26%]
+[template lagged_fibonacci2281_speed[] 26%]
+[template lagged_fibonacci3217_speed[] 26%]
+[template lagged_fibonacci4423_speed[] 25%]
+[template lagged_fibonacci9689_speed[] 25%]
+[template lagged_fibonacci19937_speed[] 25%]
+[template lagged_fibonacci23209_speed[] 25%]
+[template lagged_fibonacci44497_speed[] 25%]
+[template subtract_with_carry_speed[] 24%]
+[template subtract_with_carry_01_speed[] 14%]
+[template ranlux3_speed[] 2%]
+[template ranlux4_speed[] 1%]
+[template ranlux3_01_speed[] 1%]
+[template ranlux4_01_speed[] 0%]
+[template ranlux64_3_speed[] 2%]
+[template ranlux64_4_speed[] 1%]
+[template ranlux64_3_01_speed[] 1%]
+[template ranlux64_4_01_speed[] 0%]
+[template mt19937ar_c_speed[] 30%]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/random.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,167 @@
+[library Boost.Random
+ [quickbook 1.5]
+ [authors [Maurer, Jens]]
+ [copyright 2000-2005 Jens Maurer, 2009 Steven Watanabe]
+ [license
+ 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])
+ ]
+ [purpose A complete system for random number generation]
+]
+
+[template sup[text]'''<superscript>'''[text]'''</superscript>''']
+
+[template prng[text] [link
boost_random.reference.concepts.pseudo_random_number_generator [text]]]
+[template concepts[text] [link boost_random.reference.concepts [text]]]
+[template generators[text] [link boost_random.reference.generators [text]]]
+[template distributions[text] [link boost_random.reference.distributions
[text]]]
+
+[def __NumberGenerator [link
boost_random.reference.concepts.number_generator NumberGenerator]]
+[def __UniformRandomNumberGenerator [link
boost_random.reference.concepts.uniform_random_number_generator
UniformRandomNumberGenerator]]
+
+[def __CopyConstructible [@boost:/doc/html/CopyConstructible.html
CopyConstructible]]
+[def __Assignable [@boost:/doc/html/Assignable.html Assignable]]
+[def __LessThanComparable [@boost:/doc/html/LessThanComparable.html
LessThanComparable]]
+[def __EqualityComparable [@boost:/doc/html/EqualityComparable.html
EqualityComparable]]
+[def __Streamable Streamable]
+
+[def __random_device [classref boost::random_device random_device]]
+[def __random_number_generator [classref boost::random_number_generator
random_number_generator]]
+[def __variate_generator [classref boost::variate_generator
variate_generator]]
+
+[def __minstd_rand0 [classref boost::minstd_rand0 minstd_rand0]]
+[def __minstd_rand [classref boost::minstd_rand minstd_rand]]
+[def __rand48 [classref boost::rand48 rand48]]
+[def __ecuyer1988 [classref boost::ecuyer1988 ecuyer1988]]
+[def __kreutzer1986 [classref boost::kreutzer1986 kreutzer1986]]
+[def __taus88 [classref boost::taus88 taus88]]
+[def __hellekalek1995 [classref boost::hellekalek1995 hellekalek1995]]
+[def __mt11213b [classref boost::mt11213b mt11213b]]
+[def __mt19937 [classref boost::mt19937 mt19937]]
+[def __lagged_fibonacci607 [classref boost::lagged_fibonacci607
lagged_fibonacci607]]
+[def __lagged_fibonacci1279 [classref boost::lagged_fibonacci1279
lagged_fibonacci1279]]
+[def __lagged_fibonacci2281 [classref boost::lagged_fibonacci2281
lagged_fibonacci2281]]
+[def __lagged_fibonacci3217 [classref boost::lagged_fibonacci3217
lagged_fibonacci3217]]
+[def __lagged_fibonacci4423 [classref boost::lagged_fibonacci4423
lagged_fibonacci4423]]
+[def __lagged_fibonacci9689 [classref boost::lagged_fibonacci9689
lagged_fibonacci9689]]
+[def __lagged_fibonacci19937 [classref boost::lagged_fibonacci19937
lagged_fibonacci19937]]
+[def __lagged_fibonacci23209 [classref boost::lagged_fibonacci23209
lagged_fibonacci23209]]
+[def __lagged_fibonacci44497 [classref boost::lagged_fibonacci44497
lagged_fibonacci44497]]
+[def __ranlux3 [classref boost::ranlux3 ranlux3]]
+[def __ranlux4 [classref boost::ranlux4 ranlux4]]
+[def __ranlux64_3 [classref boost::ranlux64_3 ranlux64_3]]
+[def __ranlux64_4 [classref boost::ranlux64_4 ranlux64_4]]
+[def __ranlux3_01 [classref boost::ranlux3_01 ranlux3_01]]
+[def __ranlux4_01 [classref boost::ranlux4_01 ranlux4_01]]
+[def __ranlux64_3_01 [classref boost::ranlux64_3_01 ranlux64_3_01]]
+[def __ranlux64_4_01 [classref boost::ranlux64_4_01 ranlux64_4_01]]
+
+[def __uniform_smallint [classref boost::uniform_smallint
uniform_smallint]]
+[def __uniform_int [classref boost::uniform_int uniform_int]]
+[def __uniform_01 [classref boost::uniform_01 uniform_01]]
+[def __uniform_real [classref boost::uniform_real uniform_real]]
+[def __bernoulli_distribution [classref boost::bernoulli_distribution
bernoulli_distribution]]
+[def __binomial_distribution [classref boost::binomial_distribution
binomial_distribution]]
+[def __cauchy_distribution [classref boost::cauchy_distribution
cauchy_distribution]]
+[def __gamma_distribution [classref boost::gamma_distribution
gamma_distribution]]
+[def __poisson_distribution [classref boost::poisson_distribution
poisson_distribution]]
+[def __geometric_distribution [classref boost::geometric_distribution
geometric_distribution]]
+[def __triangle_distribution [classref boost::triangle_distribution
triangle_distribution]]
+[def __exponential_distribution [classref boost::exponential_distribution
exponential_distribution]]
+[def __normal_distribution [classref boost::normal_distribution
normal_distribution]]
+[def __lognormal_distribution [classref boost::lognormal_distribution
lognormal_distribution]]
+[def __uniform_on_sphere [classref boost::uniform_on_sphere
uniform_on_sphere]]
+
+[include performance_data.qbk]
+
+[section Introduction]
+
+Random numbers are useful in a variety of applications. The Boost Random
+Number Library (Boost.Random for short) provides a variety of
+[generators generators] and [distributions distributions] to produce
+random numbers having useful properties, such as uniform distribution.
+
+You should read the [concepts concepts documentation] for an introduction
and the
+definition of the basic concepts. For a quick start, it may be sufficient
+to have a look at [@boost:/libs/random/example/random_demo.cpp
random_demo.cpp].
+
+For a very quick start, here's an example:
+
+ ``[classref boost::mt19937]`` rng; // produces
randomness out of thin air
+ // see pseudo-random number
generators
+ ``[classref boost::uniform_int]<>`` six(1,6); // distribution that
maps to 1..6
+ // see random number distributions
+ ``[classref boost::variate_generator]``<``[classref boost::mt19937]``&,
``[classref boost::uniform_int]``<> >
+ die(rng, six); // glues randomness with mapping
+ int x = die(); // simulate rolling a die
+
+[endsect]
+
+[section Tutorial]
+[include tutorial.qbk]
+[endsect]
+
+[section Reference]
+
+[section Concepts]
+[include concepts.qbk]
+[endsect]
+
+[section Generators]
+[include generators.qbk]
+[endsect]
+
+[section Distributions]
+[include distributions.qbk]
+[endsect]
+
+[xinclude reference.xml]
+
+[endsect]
+
+[section Performance]
+[include performance.qbk]
+[endsect]
+
+[section Rationale]
+
+The methods for generating and evaluating deterministic and
non-deterministic
+random numbers differ radically. Furthermore, due to the inherent
+deterministic design of present-day computers, it is often difficult to
+implement non-deterministic random number generation facilities. Thus, the
+random number library is split into separate header files, mirroring the
two
+different application domains.
+
+[endsect]
+
+[section History and Acknowledgements]
+
+In November 1999, Jeet Sukumaran proposed a framework based on virtual
+functions, and later sketched a template-based approach. Ed Brey pointed
+out that Microsoft Visual C++ does not support in-class member
+initializations and suggested the enum workaround. Dave Abrahams
highlighted
+quantization issues.
+
+The first public release of this random number library materialized in
+March 2000 after extensive discussions on the boost mailing list. Many
+thanks to Beman Dawes for his original min_rand class, portability fixes,
+documentation suggestions, and general guidance. Harry Erwin sent a header
+file which provided additional insight into the requirements. Ed Brey and
+Beman Dawes wanted an iterator-like interface.
+
+Beman Dawes managed the formal review, during which Matthias Troyer,
+Csaba Szepesvari, and Thomas Holenstein gave detailed comments. The
+reviewed version became an official part of boost on 17 June 2000.
+
+Gary Powell contributed suggestions for code cleanliness. Dave Abrahams
+and Howard Hinnant suggested to move the basic generator templates from
+`namespace boost::detail` to `boost::random`.
+
+Ed Brey asked to remove superfluous warnings and helped with `uint64_t`
+handling. Andreas Scherer tested with MSVC. Matthias Troyer contributed
+a [headerref boost/random/lagged_fibonacci.hpp lagged Fibonacci generator].
+Michael Stevens found a bug in the copy semantics of __normal_distribution
+and suggested documentation improvements.
+
+[endsect]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/random_number_generator.qbk Mon May 31 00:54:22
2010
@@ -0,0 +1,61 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[section Synopsis of miscellaneous decorators in header <boost/random.hpp>]
+
+ namespace boost {
+ template<class UniformRandomNumberGenerator, class IntType = long>
+ class random_number_generator;
+ } // namespace boost
+
+[endsect]
+
+[section Class template random_number_generator]
+
+[section Synopsis]
+
+ template<class UniformRandomNumberGenerator, class IntType = long>
+ class random_number_generator
+ {
+ public:
+ typedef UniformRandomNumberGenerator base_type;
+ typedef IntType argument_type;
+ typedef IntType result_type;
+ random_number_generator(base_type & rng);
+ result_type operator()(argument_type n);
+ };
+
+[endsect]
+
+[section Description]
+
+Instantiations of class template random_number_generator model a
+RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]). On each
+invocation, it returns a uniformly distributed integer in the range [0..n).
+
+The template parameter IntType shall denote some integer-like value type.
+
+[note I consider it unfortunate that the C++ Standard uses the name
+RandomNumberGenerator for something rather specific.]
+
+[endsect]
+
+[section Members]
+
+ random_number_generator(base_type & rng)
+
+Effects: Constructs a random_number_generator functor with the given
uniform
+random number generator as the underlying source of random numbers.
+
+ result_type operator()(argument_type n)
+
+Returns: The value of uniform_int<base_type>(rng, 0, n-1)().
+
+[endsect]
+
+[endsect]
=======================================
--- /dev/null
+++ /trunk/libs/random/doc/tutorial.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,21 @@
+[/
+ / Copyright (c) 2009 Steven Watanabe
+ /
+ / 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)
+]
+
+[section Generating integers in a range]
+
+[import ../example/die.cpp]
+[die]
+
+[endsect]
+
+[section Generating integers with different probabilities]
+
+[import ../example/weighted_die.cpp]
+[weighted_die]
+
+[endsect]
=======================================
--- /dev/null
+++ /trunk/libs/random/example/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,11 @@
+# Jamfile.v2
+#
+# Copyright (c) 2009
+# Steven Watanabe
+#
+# 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)
+
+run die.cpp ;
+run weighted_die.cpp ;
=======================================
--- /dev/null
+++ /trunk/libs/random/example/die.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,68 @@
+// die.cpp
+//
+// Copyright (c) 2009
+// Steven Watanabe
+//
+// 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)
+
+//[die
+/*`
+ For the source of this example see
+ [@boost://libs/random/example/die.cpp die.cpp].
+ First we include the headers we need for __mt19937
+ and __uniform_int.
+*/
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/variate_generator.hpp>
+
+/*`
+ We use __mt19937 with the default seed as a source of
+ randomness. The numbers produced will be the same
+ every time the program is run. One common method to
+ change this is to seed with the current time (`std::time(0)`
+ defined in ctime).
+*/
+boost::mt19937 gen;
+/*`
+ [note We are using a /global/ generator object here. This
+ is important because we don't want to create a new [prng
+ pseudo-random number generator] at every call]
+*/
+/*`
+ Now we can define a function that simulates an ordinary
+ six-sided die.
+*/
+int roll_die() {
+ /*<< __mt19937 produces integers in the range [0, 2[sup 32]-1].
+ However, we want numbers in the range [1, 6]. The distribution
+ __uniform_int performs this transformation.
+ [warning Contrary to common C++ usage __uniform_int
+ does not take a /half-open range/. Instead it takes a /closed
range/.
+ Given the parameters 1 and 6, __uniform_int can
+ can produce any of the values 1, 2, 3, 4, 5, or 6.]
+ >>*/
+ boost::uniform_int<> dist(1, 6);
+ /*<< __variate_generator combines a generator with a distribution.
+ [important We pass [classref boost::mt19937 boost::mt19937&] to
+ __variate_generator instead of just [classref boost::mt19937]
+ (note the reference). Without the reference, __variate_generator
+ would make a copy of the generator and would leave the global
+ `gen` unchanged. Consequently, `roll_die` would produce *the same
value*
+ every time it was called.]
+ >>*/
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
die(gen, dist);
+ /*<< A __variate_generator is a function object. >>*/
+ return die();
+}
+//]
+
+#include <iostream>
+
+int main() {
+ for(int i = 0; i < 10; ++i) {
+ std::cout << roll_die() << std::endl;
+ }
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/example/random_demo.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,128 @@
+/* boost random_demo.cpp profane demo
+ *
+ * Copyright Jens Maurer 2000
+ * 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: random_demo.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * A short demo program how to use the random number library.
+ */
+
+#include <iostream>
+#include <fstream>
+#include <ctime> // std::time
+
+#include <boost/random/linear_congruential.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/uniform_real.hpp>
+#include <boost/random/variate_generator.hpp>
+
+// Sun CC doesn't handle boost::iterator_adaptor yet
+#if !defined(__SUNPRO_CC) || (__SUNPRO_CC > 0x530)
+#include <boost/generator_iterator.hpp>
+#endif
+
+#ifdef BOOST_NO_STDC_NAMESPACE
+namespace std {
+ using ::time;
+}
+#endif
+
+// This is a typedef for a random number generator.
+// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
+typedef boost::minstd_rand base_generator_type;
+
+// This is a reproducible simulation experiment. See main().
+void experiment(base_generator_type & generator)
+{
+ // Define a uniform random number distribution of integer values between
+ // 1 and 6 inclusive.
+ typedef boost::uniform_int<> distribution_type;
+ typedef boost::variate_generator<base_generator_type&,
distribution_type> gen_type;
+ gen_type die_gen(generator, distribution_type(1, 6));
+
+#if !defined(__SUNPRO_CC) || (__SUNPRO_CC > 0x530)
+ // If you want to use an STL iterator interface, use
iterator_adaptors.hpp.
+ // Unfortunately, this doesn't work on SunCC yet.
+ boost::generator_iterator<gen_type> die(&die_gen);
+ for(int i = 0; i < 10; i++)
+ std::cout << *die++ << " ";
+ std::cout << '\n';
+#endif
+}
+
+int main()
+{
+ // Define a random number generator and initialize it with a reproducible
+ // seed.
+ // (The seed is unsigned, otherwise the wrong overload may be selected
+ // when using mt19937 as the base_generator_type.)
+ base_generator_type generator(42u);
+
+ std::cout << "10 samples of a uniform distribution in [0..1):\n";
+
+ // Define a uniform random number distribution which produces "double"
+ // values between 0 and 1 (0 inclusive, 1 exclusive).
+ boost::uniform_real<> uni_dist(0,1);
+ boost::variate_generator<base_generator_type&, boost::uniform_real<> >
uni(generator, uni_dist);
+
+ std::cout.setf(std::ios::fixed);
+ // You can now retrieve random numbers from that distribution by means
+ // of a STL Generator interface, i.e. calling the generator as a zero-
+ // argument function.
+ for(int i = 0; i < 10; i++)
+ std::cout << uni() << '\n';
+
+ /*
+ * Change seed to something else.
+ *
+ * Caveat: std::time(0) is not a very good truly-random seed. When
+ * called in rapid succession, it could return the same values, and
+ * thus the same random number sequences could ensue. If not the same
+ * values are returned, the values differ only slightly in the
+ * lowest bits. A linear congruential generator with a small factor
+ * wrapped in a uniform_smallint (see experiment) will produce the same
+ * values for the first few iterations. This is because
uniform_smallint
+ * takes only the highest bits of the generator, and the generator itself
+ * needs a few iterations to spread the initial entropy from the lowest
bits
+ * to the whole state.
+ */
+ generator.seed(static_cast<unsigned int>(std::time(0)));
+
+ std::cout << "\nexperiment: roll a die 10 times:\n";
+
+ // You can save a generator's state by copy construction.
+ base_generator_type saved_generator = generator;
+
+ // When calling other functions which take a generator or distribution
+ // as a parameter, make sure to always call by reference (or pointer).
+ // Calling by value invokes the copy constructor, which means that the
+ // sequence of random numbers at the caller is disconnected from the
+ // sequence at the callee.
+ experiment(generator);
+
+ std::cout << "redo the experiment to verify it:\n";
+ experiment(saved_generator);
+
+ // After that, both generators are equivalent
+ assert(generator == saved_generator);
+
+ // as a degenerate case, you can set min = max for uniform_int
+ boost::uniform_int<> degen_dist(4,4);
+ boost::variate_generator<base_generator_type&, boost::uniform_int<> >
deg(generator, degen_dist);
+ std::cout << deg() << " " << deg() << " " << deg() << std::endl;
+
+#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
+ {
+ // You can save the generator state for future use. You can read the
+ // state back in at any later time using operator>>.
+ std::ofstream file("rng.saved", std::ofstream::trunc);
+ file << generator;
+ }
+#endif
+ // Some compilers don't pay attention to std:3.6.1/5 and issue a
+ // warning here if "return 0;" is omitted.
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/example/weighted_die.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,59 @@
+// weighted_die.cpp
+//
+// Copyright (c) 2009
+// Steven Watanabe
+//
+// 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)
+
+//[weighted_die
+/*`
+ For the source of this example see
+ [@boost://libs/random/example/weighted_die.cpp weighted_die.cpp].
+*/
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_real.hpp>
+#include <boost/random/variate_generator.hpp>
+#include <vector>
+#include <algorithm>
+#include <numeric>
+
+boost::mt19937 gen;
+
+/*`
+ This time, instead of a fair die, the probability of
+ rolling a 1 is 50% (!). The other five faces are all
+ equally likely.
+*/
+static const double probabilities[] = {
+ 0.5, 0.1, 0.1, 0.1, 0.1, 0.1
+};
+
+/*`
+ Now define a function that simulates rolling this die.
+ Note that the C++0x library contains a `discrete_distribution`
+ class which would be a better way to do this.
+*/
+int roll_weighted_die() {
+ std::vector<double> cumulative;
+ std::partial_sum(&probabilities[0], &probabilities[0] + 6,
+ std::back_inserter(cumulative));
+ boost::uniform_real<> dist(0, cumulative.back());
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<> >
die(gen, dist);
+ /*<< Find the position within the sequence and add 1
+ (to make sure that the result is in the range [1,6]
+ instead of [0,5])
+ >>*/
+ return (std::lower_bound(cumulative.begin(), cumulative.end(), die())
- cumulative.begin()) + 1;
+}
+
+//]
+
+#include <iostream>
+
+int main() {
+ for(int i = 0; i < 10; ++i) {
+ std::cout << roll_weighted_die() << std::endl;
+ }
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/extra/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,10 @@
+# Jamfile.v2
+#
+# Copyright (c) 2009
+# Steven Watanabe
+#
+# 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)
+
+run test_haertel.cpp ;
=======================================
--- /dev/null
+++ /trunk/libs/random/extra/haertel.hpp Mon May 31 00:54:22 2010
@@ -0,0 +1,156 @@
+/* haertel.hpp file
+ *
+ * Copyright Jens Maurer 2000, 2002
+ * 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: haertel.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * Revision history
+ */
+
+/*
+ * NOTE: This is not part of the official boost submission. It exists
+ * only as a collection of ideas.
+ */
+
+#ifndef BOOST_RANDOM_HAERTEL_HPP
+#define BOOST_RANDOM_HAERTEL_HPP
+
+#include <boost/cstdint.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/random/inversive_congruential.hpp>
+
+namespace boost {
+namespace random {
+
+// Wikramaratna 1989 ACORN
+template<class IntType, int k, IntType m, IntType val>
+class additive_congruential
+{
+public:
+ typedef IntType result_type;
+#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
+ static const bool has_fixed_range = true;
+ static const result_type min_value = 0;
+ static const result_type max_value = m-1;
+#else
+ enum {
+ has_fixed_range = true,
+ min_value = 0,
+ max_value = m-1
+ };
+#endif
+ template<class InputIterator>
+ explicit additive_congruential(InputIterator start) { seed(start); }
+ template<class InputIterator>
+ void seed(InputIterator start)
+ {
+ for(int i = 0; i <= k; ++i, ++start)
+ values[i] = *start;
+ }
+
+ result_type operator()()
+ {
+ for(int i = 1; i <= k; ++i) {
+ IntType tmp = values[i-1] + values[i];
+ if(tmp >= m)
+ tmp -= m;
+ values[i] = tmp;
+ }
+ return values[k];
+ }
+ result_type validation() const { return val; }
+private:
+ IntType values[k+1];
+};
+
+
+template<class IntType, int r, int s, IntType m, IntType val>
+class lagged_fibonacci_int
+{
+public:
+ typedef IntType result_type;
+#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
+ static const bool has_fixed_range = true;
+ static const result_type min_value = 0;
+ static const result_type max_value = m-1;
+#else
+ enum {
+ has_fixed_range = true,
+ min_value = 0,
+ max_value = m-1
+ };
+#endif
+ explicit lagged_fibonacci_int(IntType start) { seed(start); }
+ template<class Generator>
+ explicit lagged_fibonacci_int(Generator & gen) { seed(gen); }
+ void seed(IntType start)
+ {
+ linear_congruential<uint32_t, 299375077, 0, 0, 0> init;
+ seed(init);
+ }
+ template<class Generator>
+ void seed(Generator & gen)
+ {
+ assert(r > s);
+ for(int i = 0; i < 607; ++i)
+ values[i] = gen();
+ current = 0;
+ lag = r-s;
+ }
+
+ result_type operator()()
+ {
+ result_type tmp = values[current] + values[lag];
+ if(tmp >= m)
+ tmp -= m;
+ values[current] = tmp;
+ ++current;
+ if(current >= r)
+ current = 0;
+ ++lag;
+ if(lag >= r)
+ lag = 0;
+ return tmp;
+ }
+ result_type validation() const { return val; }
+private:
+ result_type values[r];
+ int current, lag;
+};
+
+} // namespace random
+} // namespace boost
+
+// distributions from Haertel's dissertation
+// (additional parameterizations of the basic templates)
+namespace Haertel {
+ typedef boost::random::linear_congruential<boost::uint64_t, 45965,
453816691,
+ (boost::uint64_t(1)<<31), 0> LCG_Af2;
+ typedef boost::random::linear_congruential<boost::uint64_t, 211936855, 0,
+ (boost::uint64_t(1)<<29)-3, 0> LCG_Die1;
+ typedef boost::random::linear_congruential<boost::uint32_t, 2824527309u,
0,
+ 0, 0> LCG_Fis;
+ typedef boost::random::linear_congruential<boost::uint64_t, 950706376u,
0,
+ (boost::uint64_t(1)<<31)-1, 0> LCG_FM;
+ typedef boost::random::linear_congruential<boost::int32_t, 51081, 0,
+ 2147483647, 0> LCG_Hae;
+ typedef boost::random::linear_congruential<boost::uint32_t, 69069, 1,
+ 0, 0> LCG_VAX;
+ typedef boost::random::inversive_congruential<boost::int64_t, 240318,
197,
+ 1000081, 0> NLG_Inv1;
+ typedef boost::random::inversive_congruential<boost::int64_t, 15707262,
+ 13262967, (1<<24)-17, 0> NLG_Inv2;
+ typedef boost::random::inversive_congruential<boost::int32_t, 1, 1,
+ 2147483647, 0> NLG_Inv4;
+ typedef boost::random::inversive_congruential<boost::int32_t, 1, 2,
+ 1<<30, 0> NLG_Inv5;
+ typedef boost::random::additive_congruential<boost::int32_t, 6,
+ (1<<30)-35, 0> MRG_Acorn7;
+ typedef boost::random::lagged_fibonacci_int<boost::uint32_t, 607, 273,
+ 0, 0> MRG_Fib2;
+} // namespace Haertel
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/random/extra/test_haertel.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,62 @@
+/* haertel.hpp file
+ *
+ * Copyright Jens Maurer 2000, 2002
+ * 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: test_haertel.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * Revision history
+ */
+
+#include <string>
+#include <iostream>
+
+#include <boost/format.hpp>
+
+#include "haertel.hpp"
+
+#define BOOST_TEST_MAIN
+#include <boost/test/included/unit_test.hpp>
+
+template<class Gen, class T>
+inline void check_validation(Gen & gen, T value, const std::string & name)
+{
+ for(int i = 0; i < 100000-1; ++i)
+ gen();
+
+ typename Gen::result_type actual = gen();
+ BOOST_CHECK_MESSAGE(value == actual,
+ boost::str(boost::format("%s: check value == gen() failed
[%d != %d]") %
+ name % value % actual));
+}
+
+// we have validation after 100000 steps with Haertel's generators
+template<class Gen, class T>
+void validate(T value, const std::string & name)
+{
+ Gen gen(1234567);
+ check_validation(gen, value, name);
+}
+
+BOOST_AUTO_TEST_CASE(test_haertel)
+{
+ using namespace Haertel;
+ validate<LCG_Af2>(183269031u, "LCG_Af2");
+ validate<LCG_Die1>(522319944u, "LCG_Die1");
+ validate<LCG_Fis>(-2065162233u, "LCG_Fis");
+ validate<LCG_FM>(581815473u, "LCG_FM");
+ validate<LCG_Hae>(28931709, "LCG_Hae");
+ validate<LCG_VAX>(1508154087u, "LCG_VAX");
+ validate<NLG_Inv2>(6666884, "NLG_Inv2");
+ validate<NLG_Inv4>(1521640076, "NLG_Inv4");
+ validate<NLG_Inv5>(641840839, "NLG_Inv5");
+ static const int acorn7_init[]
+ = { 1234567, 7654321, 246810, 108642, 13579, 97531, 555555 };
+ MRG_Acorn7 acorn7(acorn7_init);
+ check_validation(acorn7, 874294697, "MRG_Acorn7");
+ // This currently fails. I don't want to touch it until
+ // I trace the source of this generator. --SJW
+ validate<MRG_Fib2>(1234567u, "MRG_Fib2");
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/performance/generate_table.cpp Mon May 31 00:54:22
2010
@@ -0,0 +1,121 @@
+// generate_table.cpp
+//
+// Copyright (c) 2009
+// Steven Watanabe
+//
+// 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)
+
+#include <vector>
+#include <utility>
+#include <iostream>
+#include <cstring>
+#include <fstream>
+#include <boost/regex.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/foreach.hpp>
+#include <boost/format.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+boost::regex generator_regex("(?:fixed-range )?([^:]+): (\\d+(?:\\.\\d+)?)
nsec/loop = \\d+(?:\\.\\d+)? CPU cycles");
+boost::regex distribution_regex("([^\\s]+)( virtual function)? ([^:]+):
(\\d+(?:\\.\\d+)?) nsec/loop = \\d+(?:\\.\\d+)? CPU cycles");
+
+std::string template_name(std::string arg) {
+ return boost::regex_replace(arg, boost::regex("[^\\w]"), "_");
+}
+
+struct compare_second {
+ template<class Pair>
+ bool operator()(const Pair& p1, const Pair& p2) const {
+ return (p1.second < p2.second);
+ }
+};
+
+typedef boost::multi_index_container<
+ std::string,
+ boost::mpl::vector<
+ boost::multi_index::sequenced<>,
+
boost::multi_index::hashed_unique<boost::multi_index::identity<std::string>
+ >
+> unique_list;
+
+int main() {
+ std::vector<std::pair<std::string, double> > generator_info;
+ std::string line;
+ while(std::getline(std::cin, line)) {
+ boost::smatch match;
+ if(std::strncmp(line.c_str(), "counting ", 9) == 0) break;
+ if(boost::regex_match(line, match, generator_regex)) {
+ std::string generator(match[1]);
+ double time = boost::lexical_cast<double>(match[2]);
+ if(generator != "counting") {
+ generator_info.push_back(std::make_pair(generator, time));
+ }
+ } else {
+ std::cerr << "oops: " << line << std::endl;
+ }
+ }
+
+ double min = std::min_element(generator_info.begin(),
generator_info.end(), compare_second())->second;
+
+ std::ofstream generator_defs("performance_data.qbk");
+ std::ofstream generator_performance("generator_performance.qbk");
+ generator_performance << "[table Basic Generators\n";
+ generator_performance << " [[generator] [M rn/sec] [time per random
number \\[nsec\\]] "
+ "[relative speed compared to fastest
\\[percent\\]]]\n";
+
+ typedef std::pair<std::string, double> pair_type;
+ BOOST_FOREACH(const pair_type& pair, generator_info) {
+ generator_defs << boost::format("[template %s_speed[] %d%%]\n")
+ % template_name(pair.first) %
static_cast<int>(100*min/pair.second);
+ generator_performance << boost::format(" [[%s][%g][%g][%d%%]]\n")
+ % pair.first % (1000/pair.second) % pair.second %
static_cast<int>(100*min/pair.second);
+ }
+ generator_performance << "]\n";
+
+ std::map<std::pair<std::string, std::string>, double>
distribution_info;
+ unique_list generator_names;
+ unique_list distribution_names;
+ do {
+ boost::smatch match;
+ if(boost::regex_match(line, match, distribution_regex)) {
+ if(!match[2].matched && match[1] != "counting") {
+ std::string generator(match[1]);
+ std::string distribution(match[3]);
+ double time = boost::lexical_cast<double>(match[4]);
+ generator_names.push_back(generator);
+ distribution_names.push_back(distribution);
+
distribution_info.insert(std::make_pair(std::make_pair(distribution,
generator), time));
+ }
+ } else {
+ std::cerr << "oops: " << line << std::endl;
+ }
+ } while(std::getline(std::cin, line));
+
+ std::ofstream distribution_performance("distribution_performance.qbk");
+
+ distribution_performance << "[table Distributions\n";
+ distribution_performance << " [[\\[M rn/sec\\]]";
+ BOOST_FOREACH(const std::string& generator, generator_names) {
+ distribution_performance << boost::format("[%s]") % generator;
+ }
+ distribution_performance << "]\n";
+ BOOST_FOREACH(const std::string& distribution, distribution_names) {
+ distribution_performance << boost::format(" [[%s]") %
distribution;
+ BOOST_FOREACH(const std::string& generator, generator_names) {
+ std::map<std::pair<std::string, std::string>,
double>::iterator pos =
+ distribution_info.find(std::make_pair(distribution,
generator));
+ if(pos != distribution_info.end()) {
+ distribution_performance << boost::format("[%g]") %
(1000/pos->second);
+ } else {
+ distribution_performance << "[-]";
+ }
+ }
+ distribution_performance << "]\n";
+ }
+ distribution_performance << "]\n";
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/performance/nondet_random_speed.cpp Mon May 31
00:54:22 2010
@@ -0,0 +1,64 @@
+/* boost nondet_random_speed.cpp performance test
+ *
+ * Copyright Jens Maurer 2000
+ * 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: nondet_random_speed.cpp 60755 2010-03-22 00:45:06Z steven_watanabe
$
+ *
+ */
+
+#include <iostream>
+#include <string>
+#include <boost/timer.hpp>
+#include <boost/nondet_random.hpp>
+
+// set to your CPU frequency in MHz
+static const double cpu_frequency = 200 * 1e6;
+
+static void show_elapsed(double end, int iter, const std::string & name)
+{
+ double usec = end/iter*1e6;
+ double cycles = usec * cpu_frequency/1e6;
+ std::cout << name << ": "
+ << usec*1e3 << " nsec/loop = "
+ << cycles << " CPU cycles"
+ << std::endl;
+}
+
+template<class Result, class RNG>
+static void timing(RNG & rng, int iter, const std::string& name)
+{
+ volatile Result tmp; // make sure we're not optimizing too much
+ boost::timer t;
+ for(int i = 0; i < iter; i++)
+ tmp = rng();
+ show_elapsed(t.elapsed(), iter, name);
+}
+
+template<class RNG>
+void run(int iter, const std::string & name)
+{
+ RNG rng;
+ timing<long>(rng, iter, name);
+}
+
+int main(int argc, char*argv[])
+{
+ if(argc != 2) {
+ std::cerr << "usage: " << argv[0] << " iterations" << std::endl;
+ return 1;
+ }
+
+ int iter = std::atoi(argv[1]);
+
+#ifdef __linux__
+ boost::random_device dev;
+ timing<unsigned int>(dev, iter, "random_device");
+#else
+#error The non-deterministic random device is currently available on Linux
only.
+#endif
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/performance/random_speed.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,423 @@
+/* boost random_speed.cpp performance measurements
+ *
+ * Copyright Jens Maurer 2000
+ * 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: random_speed.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ */
+
+#include <iostream>
+#include <cstdlib>
+#include <string>
+#include <boost/config.hpp>
+#include <boost/random.hpp>
+#include <boost/progress.hpp>
+#include <boost/shared_ptr.hpp>
+
+/*
+ * Configuration Section
+ */
+
+// define if your C library supports the non-standard drand48 family
+#define HAVE_DRAND48
+
+// define if you have the original mt19937int.c (with commented out main())
+#undef HAVE_MT19937INT_C
+
+// define if you have the original mt19937ar.c (with commented out main())
+#define HAVE_MT19937AR_C
+
+// set to your CPU frequency in MHz
+static const double cpu_frequency = 3.66 * 1e9;
+
+/*
+ * End of Configuration Section
+ */
+
+/*
+ * General portability note:
+ * MSVC mis-compiles explicit function template instantiations.
+ * For example, f<A>() and f<B>() are both compiled to call f<A>().
+ * BCC is unable to implicitly convert a "const char *" to a std::string
+ * when using explicit function template instantiations.
+ *
+ * Therefore, avoid explicit function template instantiations.
+ */
+
+// provides a run-time configurable linear congruential generator, just
+// for comparison
+template<class IntType>
+class linear_congruential
+{
+public:
+ typedef IntType result_type;
+
+ BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+
+ linear_congruential(IntType x0, IntType a, IntType c, IntType m)
+ : _x(x0), _a(a), _c(c), _m(m) { }
+ // compiler-generated copy ctor and assignment operator are fine
+ void seed(IntType x0, IntType a, IntType c, IntType m)
+ { _x = x0; _a = a; _c = c; _m = m; }
+ void seed(IntType x0) { _x = x0; }
+ result_type operator()() { _x = (_a*_x+_c) % _m; return _x; }
+ result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _c ==
0 ? 1 : 0; }
+ result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _m
-1; }
+
+private:
+ IntType _x, _a, _c, _m;
+};
+
+
+// simplest "random" number generator possible, to check on overhead
+class counting
+{
+public:
+ typedef int result_type;
+
+ BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+
+ counting() : _x(0) { }
+ result_type operator()() { return ++_x; }
+ result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 1; }
+ result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return
(std::numeric_limits<result_type>::max)(); }
+
+private:
+ int _x;
+};
+
+
+// decoration of variate_generator to make it runtime-exchangeable
+// for speed comparison
+template<class Ret>
+class RandomGenBase
+{
+public:
+ virtual Ret operator()() = 0;
+ virtual ~RandomGenBase() { }
+};
+
+template<class URNG, class Dist, class Ret = typename Dist::result_type>
+class DynamicRandomGenerator
+ : public RandomGenBase<Ret>
+{
+public:
+ DynamicRandomGenerator(URNG& urng, const Dist& d) : _rng(urng, d) { }
+ Ret operator()() { return _rng(); }
+private:
+ boost::variate_generator<URNG&, Dist> _rng;
+};
+
+template<class Ret>
+class GenericRandomGenerator
+{
+public:
+ typedef Ret result_type;
+
+ GenericRandomGenerator() { };
+ void set(boost::shared_ptr<RandomGenBase<Ret> > p) { _p = p; }
+ // takes over ownership
+ void set(RandomGenBase<Ret> * p) { _p.reset(p); }
+ Ret operator()() { return (*_p)(); }
+private:
+ boost::shared_ptr<RandomGenBase<Ret> > _p;
+};
+
+
+// start implementation of measuring timing
+
+void show_elapsed(double end, int iter, const std::string & name)
+{
+ double usec = end/iter*1e6;
+ double cycles = usec * cpu_frequency/1e6;
+ std::cout << name << ": "
+ << usec*1e3 << " nsec/loop = "
+ << cycles << " CPU cycles"
+ << std::endl;
+}
+
+#if 0
+template<class RNG>
+void timing(RNG & rng, int iter, const std::string& name)
+{
+ // make sure we're not optimizing too much
+ volatile typename RNG::result_type tmp;
+ boost::timer t;
+ for(int i = 0; i < iter; i++)
+ tmp = rng();
+ show_elapsed(t.elapsed(), iter, name);
+}
+#endif
+
+// overload for using a copy, allows more concise invocation
+template<class RNG>
+void timing(RNG rng, int iter, const std::string& name)
+{
+ // make sure we're not optimizing too much
+ volatile typename RNG::result_type tmp;
+ boost::timer t;
+ for(int i = 0; i < iter; i++)
+ tmp = rng();
+ show_elapsed(t.elapsed(), iter, name);
+}
+
+template<class RNG>
+void timing_sphere(RNG rng, int iter, const std::string & name)
+{
+ boost::timer t;
+ for(int i = 0; i < iter; i++) {
+ // the special return value convention of uniform_on_sphere saves 20%
CPU
+ const std::vector<double> & tmp = rng();
+ (void) tmp[0];
+ }
+ show_elapsed(t.elapsed(), iter, name);
+}
+
+template<class RNG>
+void run(int iter, const std::string & name, RNG rng)
+{
+ std::cout << (RNG::has_fixed_range ? "fixed-range " : "");
+ // BCC has trouble with string autoconversion for explicit
specializations
+
+ // make sure we're not optimizing too much
+ volatile typename RNG::result_type tmp;
+ boost::timer t;
+ for(int i = 0; i < iter; i++)
+ tmp = rng();
+ show_elapsed(t.elapsed(), iter, name);
+}
+
+#ifdef HAVE_DRAND48
+// requires non-standard C library support for srand48/lrand48
+struct lrand48_ {
+ static const bool has_fixed_range = false;
+ typedef long result_type;
+ lrand48_() {
+ using namespace std;
+ srand48(1);
+ }
+ result_type operator()() {
+ using namespace std;
+ return lrand48();
+ }
+};
+#endif
+
+#ifdef HAVE_MT19937INT_C // requires the original mt19937int.c
+extern "C" void sgenrand(unsigned long);
+extern "C" unsigned long genrand();
+
+void run(int iter, const std::string & name, float)
+{
+ sgenrand(4357);
+ timing(genrand, iter, name, 0u);
+}
+#endif
+
+#ifdef HAVE_MT19937AR_C
+extern "C" {
+void init_genrand(unsigned long s);
+unsigned long genrand_int32(void);
+}
+struct mt19937_c {
+ static const bool has_fixed_range = false;
+ mt19937_c() {
+ init_genrand(5489);
+ }
+ typedef unsigned long result_type;
+ result_type operator()() {
+ return genrand_int32();
+ }
+};
+#endif
+
+template<class PRNG, class Dist>
+inline boost::variate_generator<PRNG&, Dist> make_gen(PRNG & rng, Dist d)
+{
+ return boost::variate_generator<PRNG&, Dist>(rng, d);
+}
+
+template<class Gen>
+void distrib(int iter, const std::string & name, const Gen &)
+{
+ Gen gen;
+
+ timing(make_gen(gen, boost::uniform_int<>(-2, 4)),
+ iter, name + " uniform_int");
+
+ timing(make_gen(gen, boost::geometric_distribution<>(0.5)),
+ iter, name + " geometric");
+
+ timing(make_gen(gen, boost::binomial_distribution<int>(4, 0.8)),
+ iter, name + " binomial");
+
+ timing(make_gen(gen, boost::poisson_distribution<>(1)),
+ iter, name + " poisson");
+
+
+ timing(make_gen(gen, boost::uniform_real<>(-5.3, 4.8)),
+ iter, name + " uniform_real");
+
+ timing(make_gen(gen, boost::triangle_distribution<>(1, 2, 7)),
+ iter, name + " triangle");
+
+ timing(make_gen(gen, boost::exponential_distribution<>(3)),
+ iter, name + " exponential");
+
+ timing(make_gen(gen, boost::normal_distribution<>()),
+ iter, name + " normal polar");
+
+ timing(make_gen(gen, boost::lognormal_distribution<>()),
+ iter, name + " lognormal");
+
+ timing(make_gen(gen, boost::cauchy_distribution<>()),
+ iter, name + " cauchy");
+
+ timing(make_gen(gen, boost::cauchy_distribution<>()),
+ iter, name + " gamma");
+
+ timing_sphere(make_gen(gen, boost::uniform_on_sphere<>(3)),
+ iter/10, name + " uniform_on_sphere");
+}
+
+
+template<class URNG, class Dist>
+inline boost::shared_ptr<DynamicRandomGenerator<URNG, Dist> >
+make_dynamic(URNG & rng, const Dist& d)
+{
+ typedef DynamicRandomGenerator<URNG, Dist> type;
+ return boost::shared_ptr<type>(new type(rng, d));
+}
+
+template<class Gen>
+void distrib_runtime(int iter, const std::string & n, const Gen &)
+{
+ std::string name = n + " virtual function ";
+ Gen gen;
+
+ GenericRandomGenerator<int> g_int;
+
+ g_int.set(make_dynamic(gen, boost::uniform_int<>(-2,4)));
+ timing(g_int, iter, name + "uniform_int");
+
+ g_int.set(make_dynamic(gen, boost::geometric_distribution<>(0.5)));
+ timing(g_int, iter, name + "geometric");
+
+ g_int.set(make_dynamic(gen, boost::binomial_distribution<>(4, 0.8)));
+ timing(g_int, iter, name + "binomial");
+
+ g_int.set(make_dynamic(gen, boost::poisson_distribution<>(1)));
+ timing(g_int, iter, name + "poisson");
+
+ GenericRandomGenerator<double> g;
+
+ g.set(make_dynamic(gen, boost::uniform_real<>(-5.3, 4.8)));
+ timing(g, iter, name + "uniform_real");
+
+ g.set(make_dynamic(gen, boost::triangle_distribution<>(1, 2, 7)));
+ timing(g, iter, name + "triangle");
+
+ g.set(make_dynamic(gen, boost::exponential_distribution<>(3)));
+ timing(g, iter, name + "exponential");
+
+ g.set(make_dynamic(gen, boost::normal_distribution<>()));
+ timing(g, iter, name + "normal polar");
+
+ g.set(make_dynamic(gen, boost::lognormal_distribution<>()));
+ timing(g, iter, name + "lognormal");
+
+ g.set(make_dynamic(gen, boost::cauchy_distribution<>()));
+ timing(g, iter, name + "cauchy");
+
+ g.set(make_dynamic(gen, boost::gamma_distribution<>(0.4)));
+ timing(g, iter, name + "gamma");
+}
+
+
+int main(int argc, char*argv[])
+{
+ if(argc != 2) {
+ std::cerr << "usage: " << argv[0] << " iterations" << std::endl;
+ return 1;
+ }
+
+ // okay, it's ugly, but it's only used here
+ int iter =
+#ifndef BOOST_NO_STDC_NAMESPACE
+ std::
+#endif
+ atoi(argv[1]);
+
+#if !defined(BOOST_NO_INT64_T) && \
+ !defined(BOOST_NO_INCLASS_MEMBER_INITIALIZATION)
+ run(iter, "rand48", boost::rand48());
+ linear_congruential<boost::uint64_t>
+ lcg48(boost::uint64_t(1)<<16 | 0x330e,
+ boost::uint64_t(0xDEECE66DUL) | (boost::uint64_t(0x5) << 32),
0xB,
+ boost::uint64_t(1)<<48);
+ timing(lcg48, iter, "lrand48 run-time");
+#endif
+
+#ifdef HAVE_DRAND48
+ // requires non-standard C library support for srand48/lrand48
+ run(iter, "lrand48", lrand48_()); // coded for lrand48()
+#endif
+
+ run(iter, "minstd_rand0", boost::minstd_rand0());
+ run(iter, "minstd_rand", boost::minstd_rand());
+ run(iter, "ecuyer combined", boost::ecuyer1988());
+ run(iter, "kreutzer1986", boost::kreutzer1986());
+ run(iter, "taus88", boost::taus88());
+
+ run(iter, "hellekalek1995 (inversive)", boost::hellekalek1995());
+
+ run(iter, "mt11213b", boost::mt11213b());
+ run(iter, "mt19937", boost::mt19937());
+
+ run(iter, "lagged_fibonacci607", boost::lagged_fibonacci607());
+ run(iter, "lagged_fibonacci1279", boost::lagged_fibonacci1279());
+ run(iter, "lagged_fibonacci2281", boost::lagged_fibonacci2281());
+ run(iter, "lagged_fibonacci3217", boost::lagged_fibonacci3217());
+ run(iter, "lagged_fibonacci4423", boost::lagged_fibonacci4423());
+ run(iter, "lagged_fibonacci9689", boost::lagged_fibonacci9689());
+ run(iter, "lagged_fibonacci19937", boost::lagged_fibonacci19937());
+ run(iter, "lagged_fibonacci23209", boost::lagged_fibonacci23209());
+ run(iter, "lagged_fibonacci44497", boost::lagged_fibonacci44497());
+
+ run(iter, "subtract_with_carry", boost::random::ranlux_base());
+ run(iter, "subtract_with_carry_01", boost::random::ranlux_base_01());
+ run(iter, "ranlux3", boost::ranlux3());
+ run(iter, "ranlux4", boost::ranlux4());
+ run(iter, "ranlux3_01", boost::ranlux3_01());
+ run(iter, "ranlux4_01", boost::ranlux4_01());
+ run(iter, "ranlux64_3", boost::ranlux3());
+ run(iter, "ranlux64_4", boost::ranlux4());
+ run(iter, "ranlux64_3_01", boost::ranlux3_01());
+ run(iter, "ranlux64_4_01", boost::ranlux4_01());
+
+ run(iter, "counting", counting());
+
+#ifdef HAVE_MT19937INT_C
+ // requires the original mt19937int.c
+ run<float>(iter, "mt19937 original"); // coded for sgenrand()/genrand()
+#endif
+
+#ifdef HAVE_MT19937AR_C
+ run(iter, "mt19937ar.c", mt19937_c());
+#endif
+
+ distrib(iter, "counting", counting());
+ distrib_runtime(iter, "counting", counting());
+
+ distrib(iter, "minstd_rand", boost::minstd_rand());
+
+ distrib(iter, "kreutzer1986", boost::kreutzer1986());
+
+ distrib(iter, "mt19937", boost::mt19937());
+
+ distrib(iter, "lagged_fibonacci607", boost::lagged_fibonacci607());
+
+ distrib_runtime(iter, "mt19937", boost::mt19937());
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/src/random_device.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,190 @@
+/* boost random_device.cpp implementation
+ *
+ * Copyright Jens Maurer 2000
+ * Copyright Steven Watanabe 2010
+ * 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: random_device.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ */
+
+#define BOOST_RANDOM_SOURCE
+
+#include <boost/nondet_random.hpp>
+#include <string>
+#include <cassert>
+
+
+#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
+// A definition is required even for integral static constants
+const bool boost::random_device::has_fixed_range;
+const boost::random_device::result_type boost::random_device::min_value;
+const boost::random_device::result_type boost::random_device::max_value;
+#endif
+
+
+#if defined(BOOST_WINDOWS)
+
+#include <windows.h>
+#include <wincrypt.h>
+#include <stdexcept> // std::invalid_argument
+
+#pragma comment(lib, "Advapi32.lib")
+
+BOOST_RANDOM_DECL const char * const boost::random_device::default_token =
MS_DEF_PROV_A;
+
+class boost::random_device::impl
+{
+public:
+ impl(const std::string & token) : provider(token) {
+ char buffer[80];
+ DWORD type;
+ DWORD len;
+
+ // Find the type of the provider
+ for(DWORD i = 0; ; ++i) {
+ len = sizeof(buffer);
+ if(!CryptEnumProvidersA(i, NULL, 0, &type, buffer, &len)) {
+ error("Could not find provider name");
+ }
+ if(buffer == provider) {
+ break;
+ }
+ }
+
+ if(!CryptAcquireContextA(&hProv, NULL, provider.c_str(), type,
+ CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
+ error("Could not acquire CSP context");
+ }
+ }
+
+ ~impl() {
+ if(!CryptReleaseContext(hProv, 0)) error("Could not release CSP
context");
+ }
+
+ unsigned int next() {
+ unsigned int result;
+
+ if(!CryptGenRandom(hProv, sizeof(result),
+ static_cast<BYTE*>(static_cast<void*>(&result)))) {
+ error("error while reading");
+ }
+
+ return result;
+ }
+
+private:
+ void error(const std::string & msg) {
+ DWORD error_code = GetLastError();
+ char buf[80];
+ DWORD num = FormatMessageA(
+ FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
+ NULL,
+ GetLastError(),
+ 0,
+ buf,
+ sizeof(buf),
+ NULL);
+
+ throw std::invalid_argument("boost::random_device: " + msg +
+ " Cryptopraphic Service Provider " +
provider +
+ ": " + std::string(&buf[0], &buf[0] +
num));
+ }
+ const std::string provider;
+ HCRYPTPROV hProv;
+};
+
+#else
+
+// the default is the unlimited capacity device, using some secure hash
+// try "/dev/random" for blocking when the entropy pool has drained
+const char * const boost::random_device::default_token = "/dev/urandom";
+
+/*
+ * This uses the POSIX interface for unbuffered reading.
+ * Using buffered std::istream would consume entropy which may
+ * not actually be used. Entropy is a precious good we avoid
+ * wasting.
+ */
+
+#if defined(__GNUC__) && defined(_CXXRT_STD_NAME)
+// I have severe difficulty to get the POSIX includes to work with
+// -fhonor-std and Dietmar Kuhl's standard C++ library. Hack around that
+// problem for now.
+extern "C" {
+static const int O_RDONLY = 0;
+extern int open(const char *__file, int __oflag, ...);
+extern int read(int __fd, __ptr_t __buf, size_t __nbytes);
+extern int close(int __fd);
+}
+#else
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h> // open
+#include <unistd.h> // read, close
+#endif
+
+#include <errno.h> // errno
+#include <string.h> // strerror
+#include <stdexcept> // std::invalid_argument
+
+
+class boost::random_device::impl
+{
+public:
+ impl(const std::string & token) : path(token) {
+ fd = open(token.c_str(), O_RDONLY);
+ if(fd < 0)
+ error("cannot open");
+ }
+
+ ~impl() { if(close(fd) < 0) error("could not close"); }
+
+ unsigned int next() {
+ unsigned int result;
+ long sz = read(fd, reinterpret_cast<char *>(&result), sizeof(result));
+ if(sz == -1)
+ error("error while reading");
+ else if(sz != sizeof(result)) {
+ errno = 0;
+ error("EOF while reading");
+ }
+ return result;
+ }
+
+private:
+ void error(const std::string & msg) {
+ throw std::invalid_argument("boost::random_device: " + msg +
+ " random-number pseudo-device " + path +
+ ": " + strerror(errno));
+ }
+ const std::string path;
+ int fd;
+};
+
+#endif // BOOST_WINDOWS
+
+BOOST_RANDOM_DECL boost::random_device::random_device(const std::string&
token)
+ : pimpl(new impl(token))
+{
+ assert((std::numeric_limits<result_type>::max)() == max_value);
+}
+
+BOOST_RANDOM_DECL boost::random_device::~random_device()
+{
+ // the complete class impl is now visible, so we're safe
+ // (see comment in random.hpp)
+ delete pimpl;
+}
+
+BOOST_RANDOM_DECL double boost::random_device::entropy() const
+{
+ return 10;
+}
+
+BOOST_RANDOM_DECL unsigned int boost::random_device::operator()()
+{
+ return pimpl->next();
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/test/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,51 @@
+# Copyright 2003 Jens Maurer
+# Copyright 2009-2010 Steven Watanabe
+# Distributed under the Boost Software License, Version 1.0. (See
accompany-
+# ing file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+# Boost Random Library test Jamfile
+
+# bring in rules for testing
+import testing ;
+
+project /boost/random/test ;
+
+run random_test.cpp ;
+run ../example/random_demo.cpp ;
+run validate.cpp ;
+
+local all-urngs =
+ rand48
+ minstd_rand0
+ minstd_rand
+ ecuyer1988
+ kreutzer1986
+ hellekalek1995
+ mt11213b
+ mt19937
+ lagged_fibonacci
+ lagged_fibonacci607
+ ranlux3
+ ranlux4
+ ranlux3_01
+ ranlux4_01
+ ranlux64_3_01
+ ranlux64_4_01
+ taus88
+;
+
+for urng in $(all-urngs)
+{
+ run instantiate.cpp : : : <define>BOOST_RANDOM_URNG_TEST=$(urng) :
test_$(urng) ;
+}
+
+# run nondet_random_speed.cpp ;
+# run random_device.cpp ;
+# run random_speed.cpp ;
+# run statistic_tests.cpp ;
+
+exe statistic_tests.exe : statistic_tests.cpp ;
+explicit statistics_tests ;
+
+install statistic_tests : statistic_tests.exe : <install-type>EXE
<location>. ;
+explicit statistic_tests ;
=======================================
--- /dev/null
+++ /trunk/libs/random/test/histogram.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,165 @@
+/* boost histogram.cpp graphical verification of distribution functions
+ *
+ * Copyright Jens Maurer 2000
+ * 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: histogram.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * This test program allows to visibly examine the results of the
+ * distribution functions.
+ */
+
+#include <iostream>
+#include <iomanip>
+#include <vector>
+#include <algorithm>
+#include <cmath>
+#include <string>
+#include <boost/random.hpp>
+
+
+void plot_histogram(const std::vector<int>& slots, int samples,
+ double from, double to)
+{
+ int m = *std::max_element(slots.begin(), slots.end());
+ const int nRows = 20;
+ std::cout.setf(std::ios::fixed|std::ios::left);
+ std::cout.precision(5);
+ for(int r = 0; r < nRows; r++) {
+ double y = ((nRows - r) * double(m))/(nRows * samples);
+ std::cout << std::setw(10) << y << " ";
+ for(unsigned int col = 0; col < slots.size(); col++) {
+ char out = ' ';
+ if(slots[col]/double(samples) >= y)
+ out = 'x';
+ std::cout << out;
+ }
+ std::cout << std::endl;
+ }
+ std::cout << std::setw(12) << " "
+ << std::setw(10) << from;
+ std::cout.setf(std::ios::right, std::ios::adjustfield);
+ std::cout << std::setw(slots.size()-10) << to << std::endl;
+}
+
+// I am not sure whether these two should be in the library as well
+
+// maintain sum of NumberGenerator results
+template<class NumberGenerator,
+ class Sum = typename NumberGenerator::result_type>
+class sum_result
+{
+public:
+ typedef NumberGenerator base_type;
+ typedef typename base_type::result_type result_type;
+ explicit sum_result(const base_type & g) : gen(g), _sum(0) { }
+ result_type operator()() { result_type r = gen(); _sum += r; return r; }
+ base_type & base() { return gen; }
+ Sum sum() const { return _sum; }
+ void reset() { _sum = 0; }
+private:
+ base_type gen;
+ Sum _sum;
+};
+
+
+// maintain square sum of NumberGenerator results
+template<class NumberGenerator,
+ class Sum = typename NumberGenerator::result_type>
+class squaresum_result
+{
+public:
+ typedef NumberGenerator base_type;
+ typedef typename base_type::result_type result_type;
+ explicit squaresum_result(const base_type & g) : gen(g), _sum(0) { }
+ result_type operator()() { result_type r = gen(); _sum += r*r; return r;
}
+ base_type & base() { return gen; }
+ Sum squaresum() const { return _sum; }
+ void reset() { _sum = 0; }
+private:
+ base_type gen;
+ Sum _sum;
+};
+
+
+template<class RNG>
+void histogram(RNG base, int samples, double from, double to,
+ const std::string & name)
+{
+ typedef squaresum_result<sum_result<RNG, double>, double > SRNG;
+ SRNG gen((sum_result<RNG, double>(base)));
+ const int nSlots = 60;
+ std::vector<int> slots(nSlots,0);
+ for(int i = 0; i < samples; i++) {
+ double val = gen();
+ if(val < from || val >= to) // early check avoids overflow
+ continue;
+ int slot = int((val-from)/(to-from) * nSlots);
+ if(slot < 0 || slot > (int)slots.size())
+ continue;
+ slots[slot]++;
+ }
+ std::cout << name << std::endl;
+ plot_histogram(slots, samples, from, to);
+ double mean = gen.base().sum() / samples;
+ std::cout << "mean: " << mean
+ << " sigma: " << std::sqrt(gen.squaresum()/samples-mean*mean)
+ << "\n" << std::endl;
+}
+
+template<class PRNG, class Dist>
+inline boost::variate_generator<PRNG&, Dist> make_gen(PRNG & rng, Dist d)
+{
+ return boost::variate_generator<PRNG&, Dist>(rng, d);
+}
+
+template<class PRNG>
+void histograms()
+{
+ PRNG rng;
+ using namespace boost;
+ histogram(make_gen(rng, uniform_smallint<>(0, 5)), 100000, -1, 6,
+ "uniform_smallint(0,5)");
+ histogram(make_gen(rng, uniform_int<>(0, 5)), 100000, -1, 6,
+ "uniform_int(0,5)");
+ histogram(make_gen(rng, uniform_real<>(0,1)), 100000, -0.5, 1.5,
+ "uniform_real(0,1)");
+ histogram(make_gen(rng, bernoulli_distribution<>(0.2)), 100000, -0.5,
1.5,
+ "bernoulli(0.2)");
+ histogram(make_gen(rng, binomial_distribution<>(4, 0.2)), 100000, -1, 5,
+ "binomial(4, 0.2)");
+ histogram(make_gen(rng, triangle_distribution<>(1, 2, 8)), 100000, 0, 10,
+ "triangle(1,2,8)");
+ histogram(make_gen(rng, geometric_distribution<>(5.0/6.0)), 100000, 0,
10,
+ "geometric(5/6)");
+ histogram(make_gen(rng, exponential_distribution<>(0.3)), 100000, 0, 10,
+ "exponential(0.3)");
+ histogram(make_gen(rng, cauchy_distribution<>()), 100000, -5, 5,
+ "cauchy");
+ histogram(make_gen(rng, lognormal_distribution<>(3, 2)), 100000, 0, 10,
+ "lognormal");
+ histogram(make_gen(rng, normal_distribution<>()), 100000, -3, 3,
+ "normal");
+ histogram(make_gen(rng, normal_distribution<>(0.5, 0.5)), 100000, -3, 3,
+ "normal(0.5, 0.5)");
+ histogram(make_gen(rng, poisson_distribution<>(1.5)), 100000, 0, 5,
+ "poisson(1.5)");
+ histogram(make_gen(rng, poisson_distribution<>(10)), 100000, 0, 20,
+ "poisson(10)");
+ histogram(make_gen(rng, gamma_distribution<>(0.5)), 100000, 0, 0.5,
+ "gamma(0.5)");
+ histogram(make_gen(rng, gamma_distribution<>(1)), 100000, 0, 3,
+ "gamma(1)");
+ histogram(make_gen(rng, gamma_distribution<>(2)), 100000, 0, 6,
+ "gamma(2)");
+}
+
+
+int main()
+{
+ histograms<boost::mt19937>();
+ // histograms<boost::lagged_fibonacci607>();
+}
+
=======================================
--- /dev/null
+++ /trunk/libs/random/test/instantiate.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,441 @@
+/* boost validate.cpp
+ *
+ * Copyright Jens Maurer 2000
+ * 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: instantiate.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ */
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+#pragma warning( disable : 4786 )
+#endif
+
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <cmath>
+#include <iterator>
+#include <vector>
+#include <boost/random.hpp>
+#include <boost/config.hpp>
+#include <boost/preprocessor/stringize.hpp>
+
+#include <boost/test/test_tools.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#ifdef BOOST_NO_STDC_NAMESPACE
+ namespace std { using ::abs; using ::fabs; using ::pow; }
+#endif
+
+
+/*
+ * General portability note:
+ * MSVC mis-compiles explicit function template instantiations.
+ * For example, f<A>() and f<B>() are both compiled to call f<A>().
+ * BCC is unable to implicitly convert a "const char *" to a std::string
+ * when using explicit function template instantiations.
+ *
+ * Therefore, avoid explicit function template instantiations.
+ */
+
+/*
+ * Check function signatures
+ */
+
+#if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT( 0x570) )
+#pragma warn -par
+#endif
+template<class URNG, class Dist>
+void instantiate_dist(URNG& urng, const char * name, const Dist& dist)
+{
+ std::cout << "Testing " << name << std::endl;
+ // this makes a copy of urng
+ boost::variate_generator<URNG, Dist> gen(urng, dist);
+
+ // this keeps a reference to urng
+ boost::variate_generator<URNG&, Dist> genref(urng, dist);
+
+ BOOST_CHECK(gen.engine() == genref.engine());
+
+#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ // and here is a pointer to (a copy of) the urng
+ URNG copy = urng;
+ boost::variate_generator<URNG*, Dist> genptr(©, dist);
+#endif
+
+ for(int i = 0; i < 1000; ++i) {
+ (void) gen();
+ (void) genref();
+#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ (void) genptr();
+#endif
+ }
+ // If the values are not exactly equal, we cannot
+ // rely on them being close...
+ typename Dist::result_type g = gen();
+ BOOST_CHECK_EQUAL(g, genref());
+#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ BOOST_CHECK_EQUAL(g, genptr());
+#endif
+
+ (void) gen.engine();
+ gen.distribution().reset();
+
+ Dist d = dist; // copy ctor
+ d = dist; // copy assignment
+
+#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ {
+ std::ostringstream file;
+ file << urng << std::endl;
+ file << d;
+ std::istringstream input(file.str());
+ // std::cout << file.str() << std::endl;
+ URNG restored_engine;
+ input >> restored_engine;
+ input >> std::ws;
+ Dist restored_dist;
+ input >> restored_dist;
+#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // MSVC brokenness
+ boost::variate_generator<URNG, Dist> old(urng, d);
+ boost::variate_generator<URNG, Dist> restored(restored_engine,
restored_dist);
+ // advance some more so that state is exercised
+ for(int i = 0; i < 1000; ++i) {
+ (void) old();
+ (void) restored();
+ }
+ BOOST_CHECK_MESSAGE((std::abs(old()-restored()) < 0.0001),
+ (std::string(name) + " old == restored_dist"));
+#endif // BOOST_MSVC
+ }
+#endif // BOOST_RANDOM_NO_STREAM_OPERATORS
+}
+
+template<class URNG, class RealType>
+void instantiate_real_dist(URNG& urng, RealType /* ignored */)
+{
+ std::cout << "Testing real distributions with " <<
typeid(RealType).name() << std::endl;
+ instantiate_dist(urng, "uniform_01",
+ boost::uniform_01<RealType>());
+ instantiate_dist(urng, "uniform_real",
+ boost::uniform_real<RealType>(0, 2.1));
+ instantiate_dist(urng, "triangle_distribution",
+ boost::triangle_distribution<RealType>(1, 1.5, 7));
+ instantiate_dist(urng, "exponential_distribution",
+ boost::exponential_distribution<RealType>(5));
+ instantiate_dist(urng, "normal_distribution",
+ boost::normal_distribution<RealType>());
+ instantiate_dist(urng, "lognormal_distribution",
+ boost::lognormal_distribution<RealType>(1, 1));
+ instantiate_dist(urng, "cauchy_distribution",
+ boost::cauchy_distribution<RealType>(1));
+ instantiate_dist(urng, "gamma_distribution",
+ boost::gamma_distribution<RealType>(1));
+}
+
+template<class URNG, class T, class Converted>
+void test_seed_conversion(URNG & urng, const T & t, const Converted &) {
+ Converted c = static_cast<Converted>(t);
+ if(static_cast<T>(c) == t) {
+ URNG urng2(c);
+ std::ostringstream msg;
+ msg << "Testing seed: type " << typeid(Converted).name() << ",
value " << c;
+ BOOST_CHECK_MESSAGE(urng == urng2, msg.str());
+ urng2.seed(c);
+ BOOST_CHECK_MESSAGE(urng == urng2, msg.str());
+ }
+}
+
+// rand48 uses non-standard seeding
+template<class T, class Converted>
+void test_seed_conversion(boost::rand48 & urng, const T & t, const
Converted &) {
+ boost::rand48 urng2(t);
+ urng2.seed(t);
+}
+
+template<class URNG, class ResultType>
+void test_seed(const URNG &, const ResultType & value) {
+ URNG urng(value);
+
+ // integral types
+ test_seed_conversion(urng, value, static_cast<char>(0));
+ test_seed_conversion(urng, value, static_cast<signed char>(0));
+ test_seed_conversion(urng, value, static_cast<unsigned char>(0));
+ test_seed_conversion(urng, value, static_cast<short>(0));
+ test_seed_conversion(urng, value, static_cast<unsigned short>(0));
+ test_seed_conversion(urng, value, static_cast<int>(0));
+ test_seed_conversion(urng, value, static_cast<unsigned int>(0));
+ test_seed_conversion(urng, value, static_cast<long>(0));
+ test_seed_conversion(urng, value, static_cast<unsigned long>(0));
+#if !defined(BOOST_NO_INT64_T)
+ test_seed_conversion(urng, value, static_cast<boost::int64_t>(0));
+ test_seed_conversion(urng, value, static_cast<boost::uint64_t>(0));
+#endif
+
+ // floating point types
+ test_seed_conversion(urng, value, static_cast<float>(0));
+ test_seed_conversion(urng, value, static_cast<double>(0));
+ test_seed_conversion(urng, value, static_cast<long double>(0));
+}
+
+template<class URNG, class ResultType>
+void instantiate_seed(const URNG & urng, const ResultType &) {
+ {
+ URNG urng;
+ URNG urng2;
+ urng2.seed();
+ BOOST_CHECK(urng == urng2);
+ }
+ test_seed(urng, static_cast<ResultType>(0));
+ test_seed(urng, static_cast<ResultType>(127));
+ test_seed(urng, static_cast<ResultType>(539157235));
+ test_seed(urng, static_cast<ResultType>(~0u));
+}
+
+// ranlux uses int32_t for seeding instead of result_type
+template<class ResultType>
+void instantiate_seed(const boost::ranlux3 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux3, boost::uint32_t>(urng, ResultType());
+}
+template<class ResultType>
+void instantiate_seed(const boost::ranlux4 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux4, boost::uint32_t>(urng, ResultType());
+}
+template<class ResultType>
+void instantiate_seed(const boost::ranlux3_01 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux3_01, boost::uint32_t>(urng,
ResultType());
+}
+template<class ResultType>
+void instantiate_seed(const boost::ranlux4_01 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux4_01, boost::uint32_t>(urng,
ResultType());
+}
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+template<class ResultType>
+void instantiate_seed(const boost::ranlux64_3 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux64_3, boost::uint32_t>(urng,
ResultType());
+}
+template<class ResultType>
+void instantiate_seed(const boost::ranlux64_4 & urng, const ResultType &) {
+ instantiate_seed<boost::ranlux64_3, boost::uint32_t>(urng,
ResultType());
+}
+#endif
+template<class ResultType>
+void instantiate_seed(const boost::ranlux64_3_01 & urng, const ResultType
&) {
+ instantiate_seed<boost::ranlux64_3_01, boost::uint32_t>(urng,
ResultType());
+}
+template<class ResultType>
+void instantiate_seed(const boost::ranlux64_4_01 & urng, const ResultType
&) {
+ instantiate_seed<boost::ranlux64_4_01, boost::uint32_t>(urng,
ResultType());
+}
+
+
+template<class URNG, class ResultType>
+void instantiate_urng(const std::string & s, const URNG & u, const
ResultType & r)
+{
+ std::cout << "Basic tests for " << s << std::endl;
+ URNG urng;
+ instantiate_seed(u, r); // seed() member function
+ int a[URNG::has_fixed_range ? 5 : 10]; // compile-time constant
+ (void) a; // avoid "unused" warning
+ typename URNG::result_type x1 = urng();
+ ResultType x2 = x1;
+ (void) &x2; // avoid "unused" warning
+
+ URNG urng2 = urng; // copy constructor
+#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // MSVC brokenness
+ BOOST_CHECK(urng == urng2); // operator==
+ BOOST_CHECK(!(urng != urng2)); // operator!=
+ urng();
+ urng2 = urng; // copy assignment
+ BOOST_CHECK(urng == urng2);
+ urng2 = URNG(urng2); // copy constructor, not templated
constructor
+ BOOST_CHECK(urng == urng2);
+#endif // BOOST_MSVC
+
+ const std::vector<int> v(9999u, 0x41);
+ std::vector<int>::const_iterator it = v.begin();
+ std::vector<int>::const_iterator it_end = v.end();
+ URNG urng3(it, it_end);
+ BOOST_CHECK(it != v.begin());
+ std::iterator_traits<std::vector<int>::const_iterator>::difference_type
n_words = (it - v.begin());
+ std::cout << "; seeding uses " << n_words << " words" << std::endl;
+
+ it = v.end();
+ BOOST_CHECK_THROW(urng3.seed(it, it_end), std::invalid_argument);
+
+ if(n_words > 1) {
+ it = v.end();
+ --it;
+ BOOST_CHECK_THROW(urng3.seed(it, it_end), std::invalid_argument);
+ }
+
+ // check for min/max members
+ ResultType min = (urng3.min)();
+ (void) &min;
+ ResultType max = (urng3.max)();
+ (void) &max;
+
+#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ // Streamable concept not supported for broken compilers
+
+ std::cout << "Testing stream operators" << std::endl;
+
+ // advance a little so that state is relatively arbitrary
+ for(int i = 0; i < 9307; ++i)
+ urng();
+ urng2 = urng;
+
+ {
+ // narrow stream first
+ std::ostringstream file;
+ file << urng;
+ // move forward
+ urng();
+ // restore old state
+ std::istringstream input(file.str());
+ input >> urng;
+ // std::cout << file.str() << std::endl;
+#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // MSVC brokenness
+ // advance some more so that state is exercised
+ for(int i = 0; i < 10000; ++i) {
+ urng();
+ urng2();
+ }
+ BOOST_CHECK(urng == urng2);
+#endif // BOOST_MSVC
+ }
+
+ urng2 = urng;
+#if !defined(BOOST_NO_STD_WSTREAMBUF) && !defined(BOOST_NO_STD_WSTRING)
+ {
+ // then wide stream
+ std::wostringstream file;
+ file << urng;
+ // move forward
+ urng();
+ std::wistringstream input(file.str());
+ input >> urng;
+#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // MSVC brokenness
+ // advance some more so that state is exercised
+ for(int i = 0; i < 10000; ++i) {
+ urng();
+ urng2();
+ }
+ BOOST_CHECK(urng == urng2);
+#endif // BOOST_MSVC
+ }
+#endif // BOOST_NO_STD_WSTREAMBUF, BOOST_NO_STD_WSTRING
+#endif // BOOST_RANDOM_NO_STREAM_OPERATORS
+
+ // instantiate various distributions with this URNG
+ instantiate_dist(urng, "uniform_smallint", boost::uniform_smallint<>(0,
11));
+ instantiate_dist(urng, "uniform_int", boost::uniform_int<>(-200, 20000));
+ instantiate_dist(urng, "bernoulli_distribution",
+ boost::bernoulli_distribution<>(0.2));
+ instantiate_dist(urng, "binomial_distribution",
+ boost::binomial_distribution<>(4, 0.2));
+ instantiate_dist(urng, "geometric_distribution",
+ boost::geometric_distribution<>(0.8));
+ instantiate_dist(urng, "poisson_distribution",
+ boost::poisson_distribution<>(1));
+
+ instantiate_real_dist(urng, 1.0f);
+ instantiate_real_dist(urng, 1.0);
+ instantiate_real_dist(urng, 1.0l);
+
+#if 0
+ // We cannot compare the outcomes before/after save with std::abs(x-y)
+ instantiate_dist("uniform_on_sphere",
+ boost::uniform_on_sphere<URNG>(urng, 2));
+#endif
+}
+
+template<class T>
+void extra_tests(T*)
+{
+}
+
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+void extra_tests(boost::rand48*)
+{
+ using namespace boost;
+ rand48 rnd(boost::int32_t(5));
+ rand48 rnd2(boost::uint64_t(0x80000000) * 42);
+ rnd.seed(boost::int32_t(17));
+ rnd2.seed(boost::uint64_t(0x80000000) * 49);
+}
+#endif
+
+void extra_tests(boost::minstd_rand*)
+{
+ using namespace boost;
+ minstd_rand mstd(42);
+ mstd.seed(17);
+}
+
+void extra_tests(boost::mt19937*)
+{
+ using namespace boost;
+ minstd_rand mstd(42);
+ mstd.seed(17);
+
+ mt19937 mt(boost::uint32_t(17)); // needs to be an exact type match for
MSVC
+ int i = 42;
+ mt.seed(boost::uint32_t(i));
+ mt19937 mt2(mstd);
+ mt2.seed(mstd);
+
+ random_number_generator<mt19937> std_rng(mt2);
+ (void) std_rng(10);
+}
+
+void instantiate_all()
+{
+ using namespace boost;
+
+ typedef boost::random::lagged_fibonacci<boost::uint32_t, 24, 607, 273>
lagged_fibonacci;
+
+ typedef BOOST_RANDOM_URNG_TEST::result_type result_type;
+ instantiate_urng(BOOST_PP_STRINGIZE(BOOST_RANDOM_URNG_TEST),
BOOST_RANDOM_URNG_TEST(), static_cast<result_type>(0));
+ BOOST_RANDOM_URNG_TEST* type_ptr = 0;
+ extra_tests(type_ptr);
+
+}
+
+
+#if defined(BOOST_MSVC) && _MSC_VER < 1300
+
+// These explicit instantiations are necessary, otherwise MSVC does
+// not find the <boost/operators.hpp> inline friends.
+// We ease the typing with a suitable preprocessor macro.
+#define INSTANT(x) \
+template class boost::uniform_smallint<x>; \
+template class boost::uniform_int<x>; \
+template class boost::uniform_real<x>; \
+template class boost::bernoulli_distribution<x>; \
+template class boost::geometric_distribution<x>; \
+template class boost::triangle_distribution<x>; \
+template class boost::exponential_distribution<x>; \
+template class boost::normal_distribution<x>; \
+template class boost::uniform_on_sphere<x>; \
+template class boost::lognormal_distribution<x>;
+
+INSTANT(boost::minstd_rand0)
+INSTANT(boost::minstd_rand)
+INSTANT(boost::ecuyer1988)
+INSTANT(boost::kreutzer1986)
+INSTANT(boost::hellekalek1995)
+INSTANT(boost::mt19937)
+INSTANT(boost::mt11213b)
+
+#undef INSTANT
+#endif
+
+
+int test_main(int, char*[])
+{
+ instantiate_all();
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/test/integrate.hpp Mon May 31 00:54:22 2010
@@ -0,0 +1,79 @@
+/* integrate.hpp header file
+ *
+ * Copyright Jens Maurer 2000
+ * 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: integrate.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * Revision history
+ * 01 April 2001: Modified to use new <boost/limits.hpp> header.
(JMaddock)
+ */
+
+#ifndef INTEGRATE_HPP
+#define INTEGRATE_HPP
+
+#include <boost/limits.hpp>
+
+template<class UnaryFunction>
+inline typename UnaryFunction::result_type
+trapezoid(UnaryFunction f, typename UnaryFunction::argument_type a,
+ typename UnaryFunction::argument_type b, int n)
+{
+ typename UnaryFunction::result_type tmp = 0;
+ for(int i = 1; i <= n-1; ++i)
+ tmp += f(a+(b-a)/n*i);
+ return (b-a)/2/n * (f(a) + f(b) + 2*tmp);
+}
+
+template<class UnaryFunction>
+inline typename UnaryFunction::result_type
+simpson(UnaryFunction f, typename UnaryFunction::argument_type a,
+ typename UnaryFunction::argument_type b, int n)
+{
+ typename UnaryFunction::result_type tmp1 = 0;
+ for(int i = 1; i <= n-1; ++i)
+ tmp1 += f(a+(b-a)/n*i);
+ typename UnaryFunction::result_type tmp2 = 0;
+ for(int i = 1; i <= n ; ++i)
+ tmp2 += f(a+(b-a)/2/n*(2*i-1));
+
+ return (b-a)/6/n * (f(a) + f(b) + 2*tmp1 + 4*tmp2);
+}
+
+// compute b so that f(b) = y; assume f is monotone increasing
+template<class UnaryFunction, class T>
+inline T
+invert_monotone_inc(UnaryFunction f, typename UnaryFunction::result_type y,
+ T lower = -1,
+ T upper = 1)
+{
+ while(upper-lower > 1e-6) {
+ double middle = (upper+lower)/2;
+ if(f(middle) > y)
+ upper = middle;
+ else
+ lower = middle;
+ }
+ return (upper+lower)/2;
+}
+
+// compute b so that I(f(x), a, b) == y
+template<class UnaryFunction>
+inline typename UnaryFunction::argument_type
+quantil(UnaryFunction f, typename UnaryFunction::argument_type a,
+ typename UnaryFunction::result_type y,
+ typename UnaryFunction::argument_type step)
+{
+ typedef typename UnaryFunction::result_type result_type;
+ if(y >= 1.0)
+ return std::numeric_limits<result_type>::infinity();
+ typename UnaryFunction::argument_type b = a;
+ for(result_type result = 0; result < y; b += step)
+ result += step*f(b);
+ return b;
+}
+
+
+#endif /* INTEGRATE_HPP */
=======================================
--- /dev/null
+++ /trunk/libs/random/test/random_test.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,291 @@
+/* boost random_test.cpp various tests
+ *
+ * Copyright Jens Maurer 2000
+ * 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: random_test.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ */
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+#pragma warning( disable : 4786 )
+#endif
+
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <cmath>
+#include <iterator>
+#include <vector>
+#include <boost/random.hpp>
+#include <boost/config.hpp>
+
+#include <boost/test/test_tools.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#ifdef BOOST_NO_STDC_NAMESPACE
+ namespace std { using ::abs; using ::fabs; using ::pow; }
+#endif
+
+
+/*
+ * General portability note:
+ * MSVC mis-compiles explicit function template instantiations.
+ * For example, f<A>() and f<B>() are both compiled to call f<A>().
+ * BCC is unable to implicitly convert a "const char *" to a std::string
+ * when using explicit function template instantiations.
+ *
+ * Therefore, avoid explicit function template instantiations.
+ */
+
+/*
+ * A few equidistribution tests
+ */
+
+// yet to come...
+
+template<class Generator>
+void check_uniform_int(Generator & gen, int iter)
+{
+ std::cout << "testing uniform_int(" << (gen.min)() << "," << (gen.max)()
+ << ")" << std::endl;
+ int range = (gen.max)()-(gen.min)()+1;
+ std::vector<int> bucket(range);
+ for(int j = 0; j < iter; j++) {
+ int result = gen();
+ if(result < (gen.min)() || result > (gen.max)())
+ std::cerr << " ... delivers " << result << std::endl;
+ else
+ bucket[result-(gen.min)()]++;
+ }
+ int sum = 0;
+ // use a different variable name "k", because MSVC has broken "for"
scoping
+ for(int k = 0; k < range; k++)
+ sum += bucket[k];
+ double avg = static_cast<double>(sum)/range;
+ double p = 1 / static_cast<double>(range);
+ double threshold = 2*std::sqrt(static_cast<double>(iter)*p*(1-p));
+ for(int i = 0; i < range; i++) {
+ if(std::fabs(bucket[i] - avg) > threshold) {
+ // 95% confidence interval
+ std::cout << " ... has bucket[" << i << "] = " << bucket[i]
+ << " (distance " << (bucket[i] - avg) << ")"
+ << std::endl;
+ }
+ }
+}
+
+template<class Generator>
+void test_uniform_int(Generator & gen)
+{
+ typedef boost::uniform_int<int> int_gen;
+
+ // large range => small range (modulo case)
+ typedef boost::variate_generator<Generator&, int_gen> level_one;
+
+ level_one uint12(gen, int_gen(1,2));
+ BOOST_CHECK((uint12.distribution().min)() == 1);
+ BOOST_CHECK((uint12.distribution().max)() == 2);
+ check_uniform_int(uint12, 100000);
+ level_one uint16(gen, int_gen(1,6));
+ check_uniform_int(uint16, 100000);
+
+ // test chaining to get all cases in operator()
+
+ // identity map
+ typedef boost::variate_generator<level_one&, int_gen> level_two;
+ level_two uint01(uint12, int_gen(0, 1));
+ check_uniform_int(uint01, 100000);
+
+ // small range => larger range
+ level_two uint05(uint12, int_gen(-3, 2));
+ check_uniform_int(uint05, 100000);
+
+ // small range => larger range
+ level_two uint099(uint12, int_gen(0, 99));
+ check_uniform_int(uint099, 100000);
+
+ // larger => small range, rejection case
+ typedef boost::variate_generator<level_two&, int_gen> level_three;
+ level_three uint1_4(uint05, int_gen(1, 4));
+ check_uniform_int(uint1_4, 100000);
+
+ typedef boost::uniform_int<boost::uint8_t> int8_gen;
+ typedef boost::variate_generator<Generator&, int8_gen> gen8_t;
+
+ gen8_t gen8_03(gen, int8_gen(0, 3));
+
+ // use the full range of the type, where the destination
+ // range is a power of the source range
+ typedef boost::variate_generator<gen8_t, int8_gen> uniform_uint8;
+ uniform_uint8 uint8_0255(gen8_03, int8_gen(0, 255));
+ check_uniform_int(uint8_0255, 100000);
+
+ // use the full range, but a generator whose range is not
+ // a root of the destination range.
+ gen8_t gen8_02(gen, int8_gen(0, 2));
+ uniform_uint8 uint8_0255_2(gen8_02, int8_gen(0, 255));
+ check_uniform_int(uint8_0255_2, 100000);
+
+ // expand the range to a larger type.
+ typedef boost::variate_generator<gen8_t, int_gen> uniform_uint_from8;
+ uniform_uint_from8 uint0300(gen8_03, int_gen(0, 300));
+ check_uniform_int(uint0300, 100000);
+}
+
+#if defined(BOOST_MSVC) && _MSC_VER < 1300
+
+// These explicit instantiations are necessary, otherwise MSVC does
+// not find the <boost/operators.hpp> inline friends.
+// We ease the typing with a suitable preprocessor macro.
+#define INSTANT(x) \
+template class boost::uniform_smallint<x>; \
+template class boost::uniform_int<x>; \
+template class boost::uniform_real<x>; \
+template class boost::bernoulli_distribution<x>; \
+template class boost::geometric_distribution<x>; \
+template class boost::triangle_distribution<x>; \
+template class boost::exponential_distribution<x>; \
+template class boost::normal_distribution<x>; \
+template class boost::uniform_on_sphere<x>; \
+template class boost::lognormal_distribution<x>;
+
+INSTANT(boost::minstd_rand0)
+INSTANT(boost::minstd_rand)
+INSTANT(boost::ecuyer1988)
+INSTANT(boost::kreutzer1986)
+INSTANT(boost::hellekalek1995)
+INSTANT(boost::mt19937)
+INSTANT(boost::mt11213b)
+
+#undef INSTANT
+#endif
+
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+// testcase by Mario Rutti
+class ruetti_gen
+{
+public:
+ ruetti_gen() : state((max)() - 1) {}
+ typedef boost::uint64_t result_type;
+ result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
+ result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return
std::numeric_limits<result_type>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); }
+ result_type operator()() { return state--; }
+private:
+ result_type state;
+};
+
+void test_overflow_range()
+{
+ ruetti_gen gen;
+ boost::variate_generator<ruetti_gen, boost::uniform_int<> >
+ rng(gen, boost::uniform_int<>(0, 10));
+ for (int i=0;i<10;i++)
+ (void) rng();
+}
+#else
+void test_overflow_range()
+{ }
+#endif
+
+template <typename EngineT>
+struct rand_for_random_shuffle
+{
+ explicit rand_for_random_shuffle(EngineT &engine)
+ : m_engine(engine)
+ { }
+
+ template <typename IntT>
+ IntT operator()(IntT upperBound)
+ {
+ assert(upperBound > 0);
+
+ if (upperBound == 1)
+ {
+ return 0;
+ }
+
+ typedef boost::uniform_int<IntT> distribution_type;
+ typedef boost::variate_generator<EngineT &, distribution_type>
generator_type;
+
+ return generator_type(m_engine, distribution_type(0, upperBound -
1))();
+ }
+
+ EngineT &m_engine;
+
+};
+
+// Test that uniform_int<> can be used with std::random_shuffle
+// Author: Jos Hickson
+void test_random_shuffle()
+{
+ typedef boost::uniform_int<> distribution_type;
+ typedef boost::variate_generator<boost::mt19937 &, distribution_type>
generator_type;
+
+ boost::mt19937 engine1(1234);
+ boost::mt19937 engine2(1234);
+
+ rand_for_random_shuffle<boost::mt19937> referenceRand(engine1);
+
+ distribution_type dist(0,10);
+ generator_type testRand(engine2, dist);
+
+ std::vector<int> referenceVec;
+
+ for (int i = 0; i < 200; ++i)
+ {
+ referenceVec.push_back(i);
+ }
+
+ std::vector<int> testVec(referenceVec);
+
+ std::random_shuffle(referenceVec.begin(), referenceVec.end(),
referenceRand);
+ std::random_shuffle(testVec.begin(), testVec.end(), testRand);
+
+ typedef std::vector<int>::iterator iter_type;
+ iter_type theEnd(referenceVec.end());
+
+ for (iter_type referenceIter(referenceVec.begin()),
testIter(testVec.begin());
+ referenceIter != theEnd;
+ ++referenceIter, ++testIter)
+ {
+ BOOST_CHECK_EQUAL(*referenceIter, *testIter);
+ }
+}
+
+
+int test_main(int, char*[])
+{
+
+#if !defined(__INTEL_COMPILER) || !defined(_MSC_VER) || __INTEL_COMPILER >
700
+ boost::mt19937 mt;
+ test_uniform_int(mt);
+
+ // bug report from Ken Mahler: This used to lead to an endless loop.
+ typedef boost::uniform_int<unsigned int> uint_dist;
+ boost::minstd_rand mr;
+ boost::variate_generator<boost::minstd_rand, uint_dist> r2(mr,
+ uint_dist(0,
0xffffffff));
+ r2();
+ r2();
+
+ // bug report from Fernando Cacciola: This used to lead to an endless
loop.
+ // also from Douglas Gregor
+ boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >
x(mr, boost::uniform_int<>(0, 8361));
+ (void) x();
+
+ // bug report from Alan Stokes and others: this throws an assertion
+ boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >
y(mr, boost::uniform_int<>(1,1));
+ std::cout << "uniform_int(1,1) " << y() << ", " << y() << ", " << y()
+ << std::endl;
+
+ test_overflow_range();
+ test_random_shuffle();
+
+ return 0;
+#else
+ std::cout << "Intel 7.00 on Win32 loops, so the test is disabled\n";
+ return 1;
+#endif
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/test/statistic_tests.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,503 @@
+/* statistic_tests.cpp file
+ *
+ * Copyright Jens Maurer 2000, 2002
+ * 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: statistic_tests.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * Revision history
+ */
+
+#include <iostream>
+#include <iomanip>
+#include <string>
+#include <functional>
+#include <vector>
+#include <set>
+#include <algorithm>
+
+#include <boost/cstdint.hpp>
+#include <boost/random.hpp>
+
+#include <boost/math/special_functions/gamma.hpp>
+
+#include <boost/math/distributions/uniform.hpp>
+#include <boost/math/distributions/chi_squared.hpp>
+#include <boost/math/distributions/normal.hpp>
+#include <boost/math/distributions/triangular.hpp>
+#include <boost/math/distributions/cauchy.hpp>
+#include <boost/math/distributions/gamma.hpp>
+#include <boost/math/distributions/exponential.hpp>
+#include <boost/math/distributions/lognormal.hpp>
+
+#include "statistic_tests.hpp"
+#include "integrate.hpp"
+
+class test_environment;
+
+class test_base
+{
+protected:
+ explicit test_base(test_environment & env) : environment(env) { }
+ void check_(double val) const;
+private:
+ test_environment & environment;
+};
+
+class equidistribution_test : test_base
+{
+public:
+ equidistribution_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+ test_distrib_chi_square(boost::math::chi_squared(classes-1),
high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "equidistribution: " << std::flush;
+ equidistribution_experiment equi(classes);
+ variate_generator<RNG&, uniform_smallint<> > uint_linear(rng,
uniform_smallint<>(0, classes-1));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(equi, uint_linear, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(equi, uint_linear, n1),
2*n2));
+
+ std::cout << " 2D: " << std::flush;
+ equidistribution_2d_experiment equi_2d(classes);
+ unsigned int root = static_cast<unsigned
int>(std::sqrt(double(classes)));
+ assert(root * root == classes);
+ variate_generator<RNG&, uniform_smallint<> > uint_square(rng,
uniform_smallint<>(0, root-1));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(equi_2d, uint_square, n1),
n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(equi_2d, uint_square, n1),
2*n2));
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class ks_distribution_test : test_base
+{
+public:
+ ks_distribution_test(test_environment & env, unsigned int classes)
+ : test_base(env),
+ test_distrib_chi_square(kolmogorov_smirnov_probability(5000),
+ classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ boost::math::uniform ud(static_cast<double>((rng.min)()),
static_cast<double>((rng.max)()));
+ run(rng, ud, n1, n2);
+ }
+ template<class RNG, class Dist>
+ void run(RNG & rng, const Dist& dist, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "KS: " << std::flush;
+ kolmogorov_experiment ks(n1);
+ check_(run_experiment(test_distrib_chi_square,
+ ks_experiment_generator(ks, rng, dist), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ ks_experiment_generator(ks, rng, dist), 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ distribution_experiment test_distrib_chi_square;
+};
+
+class runs_test : test_base
+{
+public:
+ runs_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+ test_distrib_chi_square(boost::math::chi_squared(classes-1),
high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "runs: up: " << std::flush;
+ runs_experiment<true> r_up(classes);
+
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(r_up, rng, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(r_up, rng, n1), 2*n2));
+
+ std::cout << " down: " << std::flush;
+ runs_experiment<false> r_down(classes);
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(r_down, rng, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(r_down, rng, n1), 2*n2));
+
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class gap_test : test_base
+{
+public:
+ gap_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+ test_distrib_chi_square(boost::math::chi_squared(classes-1),
high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ boost::math::uniform ud(
+ static_cast<double>((rng.min)()),
+ static_cast<double>((rng.max)()) +
+ (std::numeric_limits<typename RNG::result_type>::is_integer? 0.0 :
1.0));
+ run(rng, ud, n1, n2);
+ }
+
+ template<class RNG, class Dist>
+ void run(RNG & rng, const Dist& dist, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "gaps: " << std::flush;
+ gap_experiment gap(classes, dist, 0.2, 0.8);
+
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(gap, rng, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(gap, rng, n1), 2*n2));
+
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class poker_test : test_base
+{
+public:
+ poker_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+ test_distrib_chi_square(boost::math::chi_squared(classes-1),
high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "poker: " << std::flush;
+ poker_experiment poker(8, classes);
+ variate_generator<RNG&, uniform_smallint<> > usmall(rng,
uniform_smallint<>(0, 7));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(poker, usmall, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(poker, usmall, n1), 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class coupon_collector_test : test_base
+{
+public:
+ coupon_collector_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+ test_distrib_chi_square(boost::math::chi_squared(classes-1),
high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "coupon collector: " << std::flush;
+ coupon_collector_experiment coupon(5, classes);
+
+ variate_generator<RNG&, uniform_smallint<> > usmall(rng,
uniform_smallint<>(0, 4));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(coupon, usmall, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(coupon, usmall, n1), 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class permutation_test : test_base
+{
+public:
+ permutation_test(test_environment & env, unsigned int classes,
+ unsigned int high_classes)
+ : test_base(env), classes(classes),
+
test_distrib_chi_square(boost::math::chi_squared(fac<int>(classes)-1),
+ high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "permutation: " << std::flush;
+ permutation_experiment perm(classes);
+
+ // generator_reference_t<RNG> gen_ref(rng);
+ RNG& gen_ref(rng);
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(perm, gen_ref, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(perm, gen_ref, n1), 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ unsigned int classes;
+ distribution_experiment test_distrib_chi_square;
+};
+
+class maximum_test : test_base
+{
+public:
+ maximum_test(test_environment & env, unsigned int high_classes)
+ : test_base(env),
+ test_distrib_chi_square(kolmogorov_smirnov_probability(1000),
+ high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "maximum-of-t: " << std::flush;
+ maximum_experiment<RNG> mx(rng, n1, 5);
+ check_(run_experiment(test_distrib_chi_square, mx, n2));
+ check_(run_experiment(test_distrib_chi_square, mx, 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ distribution_experiment test_distrib_chi_square;
+};
+
+class birthday_test : test_base
+{
+public:
+ birthday_test(test_environment & env, unsigned int high_classes)
+ : test_base(env),
+ test_distrib_chi_square(boost::math::chi_squared(4-1), high_classes)
+ { }
+
+ template<class RNG>
+ void run(RNG & rng, int n1, int n2)
+ {
+ using namespace boost;
+ std::cout << "birthday spacing: " << std::flush;
+ boost::variate_generator<RNG&, boost::uniform_int<> > uni(rng,
boost::uniform_int<>(0, (1<<25)-1));
+ birthday_spacing_experiment bsp(4, 512, (1<<25));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(bsp, uni, n1), n2));
+ check_(run_experiment(test_distrib_chi_square,
+ experiment_generator(bsp, uni, n1), 2*n2));
+ std::cout << std::endl;
+ }
+private:
+ distribution_experiment test_distrib_chi_square;
+};
+
+#ifdef BOOST_MSVC
+#pragma warning(disable:4355)
+#endif
+
+class test_environment
+{
+public:
+ static const int classes = 20;
+ explicit test_environment(double confid)
+ : confidence(confid),
+
confidence_chi_square_quantil(quantile(boost::math::chi_squared(classes-1),
confidence)),
+ test_distrib_chi_square6(boost::math::chi_squared(7-1), classes),
+ ksdist_test(*this, classes),
+ equi_test(*this, 100, classes),
+ rns_test(*this, 7, classes),
+ gp_test(*this, 7, classes),
+ pk_test(*this, 5, classes),
+ cpn_test(*this, 15, classes),
+ perm_test(*this, 5, classes),
+ max_test(*this, classes),
+ bday_test(*this, classes)
+ {
+ std::cout << "Confidence level: " << confid
+ << "; 1-alpha = " << (1-confid)
+ << "; chi_square(" << (classes-1)
+ << ", " << confidence_chi_square_quantil
+ << ") = "
+ << cdf(boost::math::chi_squared(classes-1),
confidence_chi_square_quantil)
+ << std::endl;
+ }
+
+ bool check_confidence(double val, double chi_square_conf) const
+ {
+ std::cout << val;
+ bool result = (val <= chi_square_conf);
+ if(!result) {
+ std::cout << "* [";
+ double prob = (val > 10*chi_square_conf ? 1 :
+ cdf(boost::math::chi_squared(classes-1), val));
+ std::cout << (1-prob) << "]";
+ }
+ std::cout << " " << std::flush;
+ return result;
+ }
+
+ bool check_(double chi_square_value) const
+ {
+ return check_confidence(chi_square_value,
confidence_chi_square_quantil);
+ }
+
+ template<class RNG>
+ void run_test(const std::string & name)
+ {
+ using namespace boost;
+
+ std::cout << "Running tests on " << name << std::endl;
+
+ RNG rng(1234567);
+
+ ksdist_test.run(rng, 5000, 250);
+ equi_test.run(rng, 5000, 250);
+ rns_test.run(rng, 100000, 250);
+ gp_test.run(rng, 10000, 250);
+ pk_test.run(rng, 5000, 250);
+ cpn_test.run(rng, 500, 250);
+ perm_test.run(rng, 1200, 250);
+ max_test.run(rng, 1000, 250);
+ bday_test.run(rng, 1000, 150);
+
+ std::cout << std::endl;
+ }
+
+ template<class RNG, class Dist, class ExpectedDist>
+ void run_test(const std::string & name, const Dist & dist, const
ExpectedDist & expected_dist)
+ {
+ using namespace boost;
+
+ std::cout << "Running tests on " << name << std::endl;
+
+ RNG rng;
+ variate_generator<RNG&, Dist> vgen(rng, dist);
+
+ ksdist_test.run(vgen, expected_dist, 5000, 250);
+ rns_test.run(vgen, 100000, 250);
+ gp_test.run(vgen, expected_dist, 10000, 250);
+ perm_test.run(vgen, 1200, 250);
+
+ std::cout << std::endl;
+ }
+
+private:
+ double confidence;
+ double confidence_chi_square_quantil;
+ distribution_experiment test_distrib_chi_square6;
+ ks_distribution_test ksdist_test;
+ equidistribution_test equi_test;
+ runs_test rns_test;
+ gap_test gp_test;
+ poker_test pk_test;
+ coupon_collector_test cpn_test;
+ permutation_test perm_test;
+ maximum_test max_test;
+ birthday_test bday_test;
+};
+
+void test_base::check_(double val) const
+{
+ environment.check_(val);
+}
+
+class program_args
+{
+public:
+ program_args(int argc, char** argv)
+ {
+ if(argc > 0) {
+ names.insert(argv + 1, argv + argc);
+ }
+ }
+ bool check_(const std::string & test_name) const
+ {
+ return(names.empty() || names.find(test_name) != names.end());
+ }
+private:
+ std::set<std::string> names;
+};
+
+int main(int argc, char* argv[])
+{
+ program_args args(argc, argv);
+ test_environment env(0.99);
+
+#define TEST(name) \
+ if(args.check_(#name)) \
+ env.run_test<boost::name>(#name)
+
+ TEST(minstd_rand0);
+ TEST(minstd_rand);
+ TEST(rand48);
+ TEST(ecuyer1988);
+ TEST(kreutzer1986);
+ TEST(taus88);
+ TEST(hellekalek1995);
+ TEST(mt11213b);
+ TEST(mt19937);
+ TEST(lagged_fibonacci607);
+ TEST(lagged_fibonacci1279);
+ TEST(lagged_fibonacci2281);
+ TEST(lagged_fibonacci3217);
+ TEST(lagged_fibonacci4423);
+ TEST(lagged_fibonacci9689);
+ TEST(lagged_fibonacci19937);
+ TEST(lagged_fibonacci23209);
+ TEST(lagged_fibonacci44497);
+ TEST(ranlux3);
+ TEST(ranlux4);
+
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+ TEST(ranlux64_3);
+ TEST(ranlux64_4);
+#endif
+
+ TEST(ranlux3_01);
+ TEST(ranlux4_01);
+ TEST(ranlux64_3_01);
+ TEST(ranlux64_4_01);
+
+ if(args.check_("normal"))
+ env.run_test<boost::mt19937>("normal", boost::normal_distribution<>(),
boost::math::normal());
+ if(args.check_("triangle"))
+ env.run_test<boost::mt19937>("triangle",
boost::triangle_distribution<>(0, 1, 3), boost::math::triangular(0, 1, 3));
+ if(args.check_("cauchy"))
+ env.run_test<boost::mt19937>("cauchy", boost::cauchy_distribution<>(),
boost::math::cauchy());
+ if(args.check_("gamma"))
+ env.run_test<boost::mt19937>("gamma", boost::gamma_distribution<>(1),
boost::math::gamma_distribution<>(1));
+ if(args.check_("exponential"))
+ env.run_test<boost::mt19937>("exponential",
boost::exponential_distribution<>(), boost::math::exponential());
+ if(args.check_("lognormal"))
+ env.run_test<boost::mt19937>("lognormal",
boost::lognormal_distribution<>(1, 1),
+ boost::math::lognormal(std::log(1.0/std::sqrt(2.0)),
std::sqrt(std::log(2.0))));
+}
=======================================
--- /dev/null
+++ /trunk/libs/random/test/statistic_tests.hpp Mon May 31 00:54:22 2010
@@ -0,0 +1,706 @@
+/* statistic_tests.hpp header file
+ *
+ * Copyright Jens Maurer 2000
+ * 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: statistic_tests.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ */
+
+#ifndef STATISTIC_TESTS_HPP
+#define STATISTIC_TESTS_HPP
+
+#include <stdexcept>
+#include <iterator>
+#include <vector>
+#include <boost/limits.hpp>
+#include <algorithm>
+#include <cmath>
+
+#include <boost/random.hpp>
+#include <boost/config.hpp>
+#include <boost/bind.hpp>
+
+#include "integrate.hpp"
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+namespace std
+{
+ inline double pow(double a, double b) { return ::pow(a,b); }
+ inline double ceil(double x) { return ::ceil(x); }
+} // namespace std
+#endif
+
+
+template<class T>
+inline T fac(int k)
+{
+ T result = 1;
+ for(T i = 2; i <= k; ++i)
+ result *= i;
+ return result;
+}
+
+template<class T>
+T binomial(int n, int k)
+{
+ if(k < n/2)
+ k = n-k;
+ T result = 1;
+ for(int i = k+1; i<= n; ++i)
+ result *= i;
+ return result / fac<T>(n-k);
+}
+
+template<class T>
+T stirling2(int n, int m)
+{
+ T sum = 0;
+ for(int k = 0; k <= m; ++k)
+ sum += binomial<T>(m, k) * std::pow(double(k), n) *
+ ( (m-k)%2 == 0 ? 1 : -1);
+ return sum / fac<T>(m);
+}
+
+/*
+ * Experiments which create an empirical distribution in classes,
+ * suitable for the chi-square test.
+ */
+// std::floor(gen() * classes)
+
+class experiment_base
+{
+public:
+ experiment_base(int cls) : _classes(cls) { }
+ unsigned int classes() const { return _classes; }
+protected:
+ unsigned int _classes;
+};
+
+class equidistribution_experiment : public experiment_base
+{
+public:
+ explicit equidistribution_experiment(unsigned int classes)
+ : experiment_base(classes) { }
+
+ template<class NumberGenerator, class Counter>
+ void run(NumberGenerator & f, Counter & count, int n) const
+ {
+ assert((f.min)() == 0 &&
+ static_cast<unsigned int>((f.max)()) == classes()-1);
+ for(int i = 0; i < n; ++i)
+ count(f());
+ }
+ double probability(int i) const { return 1.0/classes(); }
+};
+
+// two-dimensional equidistribution experiment
+class equidistribution_2d_experiment : public equidistribution_experiment
+{
+public:
+ explicit equidistribution_2d_experiment(unsigned int classes)
+ : equidistribution_experiment(classes) { }
+
+ template<class NumberGenerator, class Counter>
+ void run(NumberGenerator & f, Counter & count, int n) const
+ {
+ unsigned int range = (f.max)()+1;
+ assert((f.min)() == 0 && range*range == classes());
+ for(int i = 0; i < n; ++i) {
+ int y1 = f();
+ int y2 = f();
+ count(y1 + range * y2);
+ }
+ }
+};
+
+// distribution experiment: assume a probability density and
+// count events so that an equidistribution results.
+class distribution_experiment : public equidistribution_experiment
+{
+public:
+ template<class Distribution>
+ distribution_experiment(Distribution dist , unsigned int classes)
+ : equidistribution_experiment(classes), limit(classes)
+ {
+ for(unsigned int i = 0; i < classes-1; ++i)
+ limit[i] = quantile(dist, (i+1)*0.05);
+ limit[classes-1] = std::numeric_limits<double>::infinity();
+ if(limit[classes-1] < (std::numeric_limits<double>::max)())
+ limit[classes-1] = (std::numeric_limits<double>::max)();
+#if 0
+ std::cout << __PRETTY_FUNCTION__ << ": ";
+ for(unsigned int i = 0; i < classes; ++i)
+ std::cout << limit[i] << " ";
+ std::cout << std::endl;
+#endif
+ }
+
+ template<class NumberGenerator, class Counter>
+ void run(NumberGenerator & f, Counter & count, int n) const
+ {
+ for(int i = 0; i < n; ++i) {
+ limits_type::const_iterator it =
+ std::lower_bound(limit.begin(), limit.end(), f());
+ count(it-limit.begin());
+ }
+ }
+private:
+ typedef std::vector<double> limits_type;
+ limits_type limit;
+};
+
+template<bool up, bool is_float>
+struct runs_direction_helper
+{
+ template<class T>
+ static T init(T)
+ {
+ return (std::numeric_limits<T>::max)();
+ }
+};
+
+template<>
+struct runs_direction_helper<true, true>
+{
+ template<class T>
+ static T init(T)
+ {
+ return -(std::numeric_limits<T>::max)();
+ }
+};
+
+template<>
+struct runs_direction_helper<true, false>
+{
+ template<class T>
+ static T init(T)
+ {
+ return (std::numeric_limits<T>::min)();
+ }
+};
+
+// runs-up/runs-down experiment
+template<bool up>
+class runs_experiment : public experiment_base
+{
+public:
+ explicit runs_experiment(unsigned int classes) :
experiment_base(classes) { }
+
+ template<class NumberGenerator, class Counter>
+ void run(NumberGenerator & f, Counter & count, int n) const
+ {
+ typedef typename NumberGenerator::result_type result_type;
+ result_type init =
+ runs_direction_helper<
+ up,
+ !std::numeric_limits<result_type>::is_integer
+ >::init(result_type());
+ result_type previous = init;
+ unsigned int length = 0;
+ for(int i = 0; i < n; ++i) {
+ result_type val = f();
+ if(up ? previous <= val : previous >= val) {
+ previous = val;
+ ++length;
+ } else {
+ count((std::min)(length, classes())-1);
+ length = 0;
+ previous = init;
+ // don't use this value, so that runs are independent
+ }
+ }
+ }
+ double probability(unsigned int r) const
+ {
+ if(r == classes()-1)
+ return 1.0/fac<double>(classes());
+ else
+ return static_cast<double>(r+1)/fac<double>(r+2);
+ }
+};
+
+// gap length experiment
+class gap_experiment : public experiment_base
+{
+public:
+ template<class Dist>
+ gap_experiment(unsigned int classes, const Dist & dist, double alpha,
double beta)
+ : experiment_base(classes), alpha(alpha), beta(beta),
low(quantile(dist, alpha)), high(quantile(dist, beta)) {}
+
+ template<class NumberGenerator, class Counter>
+ void run(NumberGenerator & f, Counter & count, int n) const
+ {
+ typedef typename NumberGenerator::result_type result_type;
+ unsigned int length = 0;
+ for(int i = 0; i < n; ) {
+ result_type value = f();
+ if(value < low || value > high)
+ ++length;
+ else {
+ count((std::min)(length, classes()-1));
+ length = 0;
+ ++i;
+ }
+ }
+ }
+ double probability(unsigned int r) const
+ {
+ double p = beta-alpha;
+ if(r == classes()-1)
+ return std::pow(1-p, static_cast<double>(r));
+ else
+ return p * std::pow(1-p, static_cast<double>(r));
+ }
+private:
+ double alpha, beta;
+ double low, high;
+};
+
+// poker experiment
+class poker_experiment : public experiment_base
+{
+public:
+ poker_experiment(unsigned int d, unsigned int k)
+ : experiment_base(k), range(d)
+ {
+ assert(range > 1);
+ }
+
+ template<class UniformRandomNumberGenerator, class Counter>
+ void run(UniformRandomNumberGenerator & f, Counter & count, int n) const
+ {
+ typedef typename UniformRandomNumberGenerator::result_type result_type;
+ assert(std::numeric_limits<result_type>::is_integer);
+ assert((f.min)() == 0);
+ assert((f.max)() == static_cast<result_type>(range-1));
+ std::vector<result_type> v(classes());
+ for(int i = 0; i < n; ++i) {
+ for(unsigned int j = 0; j < classes(); ++j)
+ v[j] = f();
+ std::sort(v.begin(), v.end());
+ result_type prev = v[0];
+ int r = 1; // count different values in v
+ for(unsigned int i = 1; i < classes(); ++i) {
+ if(prev != v[i]) {
+ prev = v[i];
+ ++r;
+ }
+ }
+ count(r-1);
+ }
+ }
+
+ double probability(unsigned int r) const
+ {
+ ++r; // transform to 1 <= r <= 5
+ double result = range;
+ for(unsigned int i = 1; i < r; ++i)
+ result *= range-i;
+ return result / std::pow(range, static_cast<double>(classes())) *
+ stirling2<double>(classes(), r);
+ }
+private:
+ unsigned int range;
+};
+
+// coupon collector experiment
+class coupon_collector_experiment : public experiment_base
+{
+public:
+ coupon_collector_experiment(unsigned int d, unsigned int cls)
+ : experiment_base(cls), d(d)
+ {
+ assert(d > 1);
+ }
+
+ template<class UniformRandomNumberGenerator, class Counter>
+ void run(UniformRandomNumberGenerator & f, Counter & count, int n) const
+ {
+ typedef typename UniformRandomNumberGenerator::result_type result_type;
+ assert(std::numeric_limits<result_type>::is_integer);
+ assert((f.min)() == 0);
+ assert((f.max)() == static_cast<result_type>(d-1));
+ std::vector<bool> occurs(d);
+ for(int i = 0; i < n; ++i) {
+ occurs.assign(d, false);
+ unsigned int r = 0; // length of current sequence
+ int q = 0; // number of non-duplicates in
current set
+ for(;;) {
+ result_type val = f();
+ ++r;
+ if(!occurs[val]) { // new set element
+ occurs[val] = true;
+ ++q;
+ if(q == d)
+ break; // one complete set
+ }
+ }
+ count((std::min)(r-d, classes()-1));
+ }
+ }
+ double probability(unsigned int r) const
+ {
+ if(r == classes()-1)
+ return 1-fac<double>(d)/std::pow(d,
static_cast<double>(d+classes()-2))*
+ stirling2<double>(d+classes()-2, d);
+ else
+ return fac<double>(d)/std::pow(d, static_cast<double>(d+r)) *
+ stirling2<double>(d+r-1, d-1);
+ }
+private:
+ int d;
+};
+
+// permutation test
+class permutation_experiment : public equidistribution_experiment
+{
+public:
+ permutation_experiment(unsigned int t)
+ : equidistribution_experiment(fac<int>(t)), t(t)
+ {
+ assert(t > 1);
+ }
+
+ template<class UniformRandomNumberGenerator, class Counter>
+ void run(UniformRandomNumberGenerator & f, Counter & count, int n) const
+ {
+ typedef typename UniformRandomNumberGenerator::result_type result_type;
+ std::vector<result_type> v(t);
+ for(int i = 0; i < n; ++i) {
+ for(int j = 0; j < t; ++j) {
+ v[j] = f();
+ }
+ int x = 0;
+ for(int r = t-1; r > 0; r--) {
+ typename std::vector<result_type>::iterator it =
+ std::max_element(v.begin(), v.begin()+r+1);
+ x = (r+1)*x + (it-v.begin());
+ std::iter_swap(it, v.begin()+r);
+ }
+ count(x);
+ }
+ }
+private:
+ int t;
+};
+
+// birthday spacing experiment test
+class birthday_spacing_experiment : public experiment_base
+{
+public:
+ birthday_spacing_experiment(unsigned int d, int n, int m)
+ : experiment_base(d), n(n), m(m)
+ {
+ }
+
+ template<class UniformRandomNumberGenerator, class Counter>
+ void run(UniformRandomNumberGenerator & f, Counter & count, int n_total)
const
+ {
+ typedef typename UniformRandomNumberGenerator::result_type result_type;
+ assert(std::numeric_limits<result_type>::is_integer);
+ assert((f.min)() == 0);
+ assert((f.max)() == static_cast<result_type>(m-1));
+
+ for(int j = 0; j < n_total; j++) {
+ std::vector<result_type> v(n);
+ std::generate_n(v.begin(), n, f);
+ std::sort(v.begin(), v.end());
+ std::vector<result_type> spacing(n);
+ for(int i = 0; i < n-1; i++)
+ spacing[i] = v[i+1]-v[i];
+ spacing[n-1] = v[0] + m - v[n-1];
+ std::sort(spacing.begin(), spacing.end());
+ unsigned int k = 0;
+ for(int i = 0; i < n-1; ++i) {
+ if(spacing[i] == spacing[i+1])
+ ++k;
+ }
+ count((std::min)(k, classes()-1));
+ }
+ }
+
+ double probability(unsigned int r) const
+ {
+ assert(classes() == 4);
+ assert(m == (1<<25));
+ assert(n == 512);
+ static const double prob[] = { 0.368801577, 0.369035243, 0.183471182,
+ 0.078691997 };
+ return prob[r];
+ }
+private:
+ int n, m;
+};
+/*
+ * Misc. helper functions.
+ */
+
+template<class Float>
+struct distribution_function
+{
+ typedef Float result_type;
+ typedef Float argument_type;
+ typedef Float first_argument_type;
+ typedef Float second_argument_type;
+};
+
+// computes P(K_n <= t) or P(t1 <= K_n <= t2). See Knuth, 3.3.1
+class kolmogorov_smirnov_probability : public distribution_function<double>
+{
+public:
+ kolmogorov_smirnov_probability(int n)
+ : approx(n > 50), n(n), sqrt_n(std::sqrt(double(n)))
+ {
+ if(!approx)
+ n_n = std::pow(static_cast<double>(n), n);
+ }
+
+ double cdf(double t) const
+ {
+ if(approx) {
+ return 1-std::exp(-2*t*t)*(1-2.0/3.0*t/sqrt_n);
+ } else {
+ t *= sqrt_n;
+ double sum = 0;
+ for(int k = static_cast<int>(std::ceil(t)); k <= n; k++)
+ sum += binomial<double>(n, k) * std::pow(k-t, k) *
+ std::pow(t+n-k, n-k-1);
+ return 1 - t/n_n * sum;
+ }
+ }
+ //double operator()(double t1, double t2) const
+ //{ return operator()(t2) - operator()(t1); }
+
+private:
+ bool approx;
+ int n;
+ double sqrt_n;
+ double n_n;
+};
+
+inline double cdf(const kolmogorov_smirnov_probability& dist, double val)
+{
+ return dist.cdf(val);
+}
+
+inline double quantile(const kolmogorov_smirnov_probability& dist, double
val)
+{
+ return invert_monotone_inc(boost::bind(&cdf, dist, _1), val, 0.0,
1000.0);
+}
+
+/*
+ * Experiments for generators with continuous distribution functions
+ */
+class kolmogorov_experiment
+{
+public:
+ kolmogorov_experiment(int n) : n(n), ksp(n) { }
+ template<class NumberGenerator, class Distribution>
+ double run(NumberGenerator & gen, Distribution distrib) const
+ {
+ const int m = n;
+ typedef std::vector<double> saved_temp;
+ saved_temp a(m,1.0), b(m,0);
+ std::vector<int> c(m,0);
+ for(int i = 0; i < n; ++i) {
+ double val = static_cast<double>(gen());
+ double y = cdf(distrib, val);
+ int k = static_cast<int>(std::floor(m*y));
+ if(k >= m)
+ --k; // should not happen
+ a[k] = (std::min)(a[k], y);
+ b[k] = (std::max)(b[k], y);
+ ++c[k];
+ }
+ double kplus = 0, kminus = 0;
+ int j = 0;
+ for(int k = 0; k < m; ++k) {
+ if(c[k] > 0) {
+ kminus = (std::max)(kminus, a[k]-j/static_cast<double>(n));
+ j += c[k];
+ kplus = (std::max)(kplus, j/static_cast<double>(n) - b[k]);
+ }
+ }
+ kplus *= std::sqrt(double(n));
+ kminus *= std::sqrt(double(n));
+ // std::cout << "k+ " << kplus << " k- " << kminus << std::endl;
+ return kplus;
+ }
+ double probability(double x) const
+ {
+ return cdf(ksp, x);
+ }
+private:
+ int n;
+ kolmogorov_smirnov_probability ksp;
+};
+
+struct power_distribution
+{
+ power_distribution(double t) : t(t) {}
+ double t;
+};
+
+double cdf(const power_distribution& dist, double val)
+{
+ return std::pow(val, dist.t);
+}
+
+// maximum-of-t test (KS-based)
+template<class UniformRandomNumberGenerator>
+class maximum_experiment
+{
+public:
+ typedef UniformRandomNumberGenerator base_type;
+ maximum_experiment(base_type & f, int n, int t) : f(f), ke(n), t(t)
+ { }
+
+ double operator()() const
+ {
+ generator gen(f, t);
+ return ke.run(gen, power_distribution(t));
+ }
+
+private:
+ struct generator {
+ generator(base_type & f, int t) : f(f, boost::uniform_01<>()), t(t) { }
+ double operator()()
+ {
+ double mx = f();
+ for(int i = 1; i < t; ++i)
+ mx = (std::max)(mx, f());
+ return mx;
+ }
+ private:
+ boost::variate_generator<base_type&, boost::uniform_01<> > f;
+ int t;
+ };
+ base_type & f;
+ kolmogorov_experiment ke;
+ int t;
+};
+
+// compute a chi-square value for the distribution approximation error
+template<class ForwardIterator, class UnaryFunction>
+typename UnaryFunction::result_type
+chi_square_value(ForwardIterator first, ForwardIterator last,
+ UnaryFunction probability)
+{
+ typedef std::iterator_traits<ForwardIterator> iter_traits;
+ typedef typename iter_traits::value_type counter_type;
+ typedef typename UnaryFunction::result_type result_type;
+ unsigned int classes = std::distance(first, last);
+ result_type sum = 0;
+ counter_type n = 0;
+ for(unsigned int i = 0; i < classes; ++first, ++i) {
+ counter_type count = *first;
+ n += count;
+ sum += (count/probability(i)) * count; // avoid overflow
+ }
+#if 0
+ for(unsigned int i = 0; i < classes; ++i) {
+ // std::cout << (n*probability(i)) << " ";
+ if(n * probability(i) < 5)
+ std::cerr << "Not enough test runs for slot " << i
+ << " p=" << probability(i) << ", n=" << n
+ << std::endl;
+ }
+#endif
+ // std::cout << std::endl;
+ // throw std::invalid_argument("not enough test runs");
+
+ return sum/n - n;
+}
+template<class RandomAccessContainer>
+class generic_counter
+{
+public:
+ explicit generic_counter(unsigned int classes) : container(classes, 0) {
}
+ void operator()(int i)
+ {
+ assert(i >= 0);
+ assert(static_cast<unsigned int>(i) < container.size());
+ ++container[i];
+ }
+ typename RandomAccessContainer::const_iterator begin() const
+ { return container.begin(); }
+ typename RandomAccessContainer::const_iterator end() const
+ { return container.end(); }
+
+private:
+ RandomAccessContainer container;
+};
+
+// chi_square test
+template<class Experiment, class Generator>
+double run_experiment(const Experiment & experiment, Generator & gen, int
n)
+{
+ generic_counter<std::vector<int> > v(experiment.classes());
+ experiment.run(gen, v, n);
+ return chi_square_value(v.begin(), v.end(),
+
std::bind1st(std::mem_fun_ref(&Experiment::probability),
+ experiment));
+}
+
+// chi_square test
+template<class Experiment, class Generator>
+double run_experiment(const Experiment & experiment, const Generator &
gen, int n)
+{
+ generic_counter<std::vector<int> > v(experiment.classes());
+ experiment.run(gen, v, n);
+ return chi_square_value(v.begin(), v.end(),
+
std::bind1st(std::mem_fun_ref(&Experiment::probability),
+ experiment));
+}
+
+// number generator with experiment results (for nesting)
+template<class Experiment, class Generator>
+class experiment_generator_t
+{
+public:
+ experiment_generator_t(const Experiment & exper, Generator & gen, int n)
+ : experiment(exper), generator(gen), n(n) { }
+ double operator()() const { return run_experiment(experiment, generator,
n); }
+private:
+ const Experiment & experiment;
+ Generator & generator;
+ int n;
+};
+
+template<class Experiment, class Generator>
+experiment_generator_t<Experiment, Generator>
+experiment_generator(const Experiment & e, Generator & gen, int n)
+{
+ return experiment_generator_t<Experiment, Generator>(e, gen, n);
+}
+
+
+template<class Experiment, class Generator, class Distribution>
+class ks_experiment_generator_t
+{
+public:
+ ks_experiment_generator_t(const Experiment & exper, Generator & gen,
+ const Distribution & distrib)
+ : experiment(exper), generator(gen), distribution(distrib) { }
+ double operator()() const { return experiment.run(generator,
distribution); }
+private:
+ const Experiment & experiment;
+ Generator & generator;
+ Distribution distribution;
+};
+
+template<class Experiment, class Generator, class Distribution>
+ks_experiment_generator_t<Experiment, Generator, Distribution>
+ks_experiment_generator(const Experiment & e, Generator & gen,
+ const Distribution & distrib)
+{
+ return ks_experiment_generator_t<Experiment, Generator, Distribution>
+ (e, gen, distrib);
+}
+
+
+#endif /* STATISTIC_TESTS_HPP */
+
=======================================
--- /dev/null
+++ /trunk/libs/random/test/validate.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,131 @@
+/* boost validate.cpp
+ *
+ * Copyright Jens Maurer 2000
+ * 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: validate.cpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ */
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+#pragma warning( disable : 4786 )
+#endif
+
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <cmath>
+#include <iterator>
+#include <vector>
+#include <boost/random.hpp>
+#include <boost/config.hpp>
+
+#include <boost/test/test_tools.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#ifdef BOOST_NO_STDC_NAMESPACE
+ namespace std { using ::abs; using ::fabs; using ::pow; }
+#endif
+
+
+/*
+ * General portability note:
+ * MSVC mis-compiles explicit function template instantiations.
+ * For example, f<A>() and f<B>() are both compiled to call f<A>().
+ * BCC is unable to implicitly convert a "const char *" to a std::string
+ * when using explicit function template instantiations.
+ *
+ * Therefore, avoid explicit function template instantiations.
+ */
+
+/*
+ * Validate correct implementation
+ */
+
+// own run
+bool check_(unsigned long x, const boost::mt11213b&) { return x ==
3809585648U; }
+
+// validation by experiment from mt19937.c
+bool check_(unsigned long x, const boost::mt19937&) { return x ==
4123659995U; }
+
+// validation values from the publications
+bool check_(int x, const boost::minstd_rand0&) { return x == 1043618065; }
+
+// validation values from the publications
+bool check_(int x, const boost::minstd_rand&) { return x == 399268537; }
+
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+// by experiment from lrand48()
+bool check_(unsigned long x, const boost::rand48&) { return x ==
1993516219; }
+#endif
+
+// ????
+bool check_(unsigned long x, const boost::taus88&) { return x ==
3535848941U; }
+
+// ????
+bool check_(int x, const boost::ecuyer1988&) { return x == 2060321752; }
+
+// validation by experiment from Harry Erwin's generator.h (private e-mail)
+bool check_(unsigned int x, const boost::kreutzer1986&) { return x ==
139726; }
+
+bool check_(double x, const boost::lagged_fibonacci607&) { return
std::abs(x-0.401269) < 1e-5; }
+
+// principal operation validated with CLHEP, values by experiment
+bool check_(unsigned long x, const boost::ranlux3&) { return x == 5957620;
}
+bool check_(unsigned long x, const boost::ranlux4&) { return x == 8587295;
}
+
+bool check_(float x, const boost::ranlux3_01&)
+{ return std::abs(x-5957620/std::pow(2.0f,24)) < 1e-6; }
+bool check_(float x, const boost::ranlux4_01&)
+{ return std::abs(x-8587295/std::pow(2.0f,24)) < 1e-6; }
+
+bool check_(double x, const boost::ranlux64_3_01&)
+{ return std::abs(x-0.838413) < 1e-6; }
+bool check_(double x, const boost::ranlux64_4_01&)
+{ return std::abs(x-0.59839) < 1e-6; }
+
+template<class PRNG>
+void validate(const std::string & name, const PRNG &)
+{
+ std::cout << "validating " << name << ": ";
+ PRNG rng; // default ctor
+ for(int i = 0; i < 9999; i++)
+ rng();
+ typename PRNG::result_type val = rng();
+ // make sure the validation function is a static member
+ bool result = check_(val, rng);
+
+ // allow for a simple eyeball check for MSVC instantiation brokenness
+ // (if the numbers for all generators are the same, it's obviously
broken)
+ std::cout << val << std::endl;
+ BOOST_CHECK(result);
+}
+
+void validate_all()
+{
+ using namespace boost;
+#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+ validate("rand48", rand48());
+#endif
+ validate("minstd_rand", minstd_rand());
+ validate("minstd_rand0", minstd_rand0());
+ validate("ecuyer combined", ecuyer1988());
+ validate("mt11213b", mt11213b());
+ validate("mt19937", mt19937());
+ validate("kreutzer1986", kreutzer1986());
+ validate("ranlux3", ranlux3());
+ validate("ranlux4", ranlux4());
+ validate("ranlux3_01", ranlux3_01());
+ validate("ranlux4_01", ranlux4_01());
+ validate("ranlux64_3_01", ranlux64_3_01());
+ validate("ranlux64_4_01", ranlux64_4_01());
+ validate("taus88", taus88());
+ validate("lagged_fibonacci607", lagged_fibonacci607());
+}
+
+int test_main(int, char*[])
+{
+ validate_all();
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/Jamfile.v2 Mon May 31 00:54:22 2010
@@ -0,0 +1,32 @@
+#// Boost.Range library
+#//
+#// Copyright Thorsten Ottosen 2003-2008. Use, modification and
+#// distribution is subject to 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)
+#//
+#// For more information, see http://www.boost.org/libs/range/
+#//
+
+project boost/libs/range/doc ;
+using boostbook ;
+using quickbook ;
+
+path-constant images_location : html ;
+
+boostbook quickbook
+ :
+ boost_range.qbk
+ :
+ <xsl:param>boost.root=../../../..
+ <xsl:param>boost.libraries=../../../libraries.htm
+ <xsl:param>html.stylesheet=../../../../doc/html/boostbook.css
+ <xsl:param>chunk.section.depth=4
+ <xsl:param>chunk.first.sections=1
+ <xsl:param>toc.section.depth=3
+ <xsl:param>toc.max.depth=3
+ <xsl:param>generate.section.toc.level=4
+
<format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/doc/html
+ <format>pdf:<xsl:param>img.src.path=$(images_location)/
+ ;
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/boost_range.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,195 @@
+[/==============================================================================
+ Copyright (C) 2003-2010 Thorsten Ottosen, Neil Groves
+
+ Use, modification and distribution is subject to 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
+==============================================================================/]
+[library Range
+ [quickbook 1.5]
+ [version 2.0]
+ [authors [Ottosen, Thorsten], [Groves, Neil]]
+ [copyright 2003-2010 Thorsten Ottosen, Neil Groves]
+ [purpose Half-open range library]
+ [license
+ 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])
+ ]
+]
+
+[/ Converted to Quickbook format by Darren Garvey, 2007]
+
+[def __note__ [$images/note.png]]
+[def __alert__ [$images/alert.png]]
+[def __tip__ [$images/tip.png]]
+[def __caution__ [$images/caution.png]]
+
+[def __boost_range_home__ [link range Boost.Range]]
+[def __ranges__ [link range.concepts Ranges]]
+[def __range_concepts__ [link range.concepts Range concepts]]
+[def __forward_range__ [link range.concepts.forward_range Forward
Range]]
+[def __single_pass_range__ [link range.concepts.single_pass_range
Single Pass Range]]
+[def __bidirectional_range__ [link range.concepts.bidirectional_range
Bidirectional Range]]
+[def __random_access_range__ [link range.concepts.random_access_range
Random Access Range]]
+
+[def __iterator_range__ [link
range.reference.utilities.iterator_range `iterator_range`]]
+[def __sub_range__ [link range.reference.utilities.sub_range
`sub_range`]]
+[def __minimal_interface__ [link range.reference.extending minimal
interface]]
+[def __range_result_iterator__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_result_iterator`]]
+[def __extending_for_udts__ [link range.reference.extending Extending the
library for UDTs]]
+[def __implementation_of_metafunctions__ [link
range.reference.concept_implementation.semantics.metafunctions
Implementation of metafunctions]]
+[def __implementation_of_functions__ [link
range.reference.concept_implementation.semantics.functions Implementation
of functions]]
+
+[def __range_value__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_value`]]
+[def __range_iterator__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_iterator`]]
+[def __range_difference__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_difference`]]
+[def __range_pointer__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_pointer`]]
+[def __range_category__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_category`]]
+[def __range_reverse_iterator__ [link
range.reference.concept_implementation.semantics.metafunctions
`range_reverse_iterator`]]
+[def __begin__ [link
range.reference.concept_implementation.semantics.functions `begin`]]
+[def __const_begin__ [link
range.reference.concept_implementation.semantics.functions `const_begin`]]
+[def __end__ [link
range.reference.concept_implementation.semantics.functions `end`]]
+[def __const_end__ [link
range.reference.concept_implementation.semantics.functions `const_end`]]
+[def __empty__ [link
range.reference.concept_implementation.semantics.functions `empty`]]
+[def __distance__ [link
range.reference.concept_implementation.semantics.functions `distance`]]
+[def __size__ [link
range.reference.concept_implementation.semantics.functions `size`]]
+[def __rbegin__ [link
range.reference.concept_implementation.semantics.functions `rbegin`]]
+[def __const_rbegin__ [link
range.reference.concept_implementation.semantics.functions `const_rbegin`]]
+[def __rend__ [link
range.reference.concept_implementation.semantics.functions `rend`]]
+[def __const_rend__ [link
range.reference.concept_implementation.semantics.functions `const_rend`]]
+[def __as_array__ [link
range.reference.concept_implementation.semantics.functions `as_array`]]
+[def __as_literal__ [link
range.reference.concept_implementation.semantics.functions `as_literal`]]
+[def __counting_range__ [link
range.reference.ranges.counting_range `counting_range`]]
+[def __irange__ [link range.reference.ranges.irange
`irange`]]
+[def __istream_range__ [link range.reference.ranges.istream_range
`istream_range`]]
+[def __join__ [link range.reference.utilities.join
`join`]]
+
+[def __range_adaptors__ [link range.reference.adaptors
Range adaptors]]
+[def __range_adaptors_adjacent_filtered__ [link
range.reference.adaptors.reference.adjacent_filtered adjacent_filtered]]
+[def __range_adaptors_copied__ [link
range.reference.adaptors.reference.copied copied]]
+[def __range_adaptors_filtered__ [link
range.reference.adaptors.reference.filtered filtered]]
+[def __range_adaptors_indexed__ [link
range.reference.adaptors.reference.indexed indexed]]
+[def __range_adaptors_indirected__ [link
range.reference.adaptors.reference.indirected indirected]]
+[def __range_adaptors_map_keys__ [link
range.reference.adaptors.reference.map_keys map_keys]]
+[def __range_adaptors_map_values__ [link
range.reference.adaptors.reference.map_values map_values]]
+[def __range_adaptors_replaced__ [link
range.reference.adaptors.reference.replaced replaced]]
+[def __range_adaptors_replaced_if__ [link
range.reference.adaptors.reference.replaced_if replaced_if]]
+[def __range_adaptors_reversed__ [link
range.reference.adaptors.reference.reversed reversed]]
+[def __range_adaptors_sliced__ [link
range.reference.adaptors.reference.sliced sliced]]
+[def __range_adaptors_strided__ [link
range.reference.adaptors.reference.strided strided]]
+[def __range_adaptors_tokenized__ [link
range.reference.adaptors.reference.tokenized tokenized]]
+[def __range_adaptors_transformed__ [link
range.reference.adaptors.reference.transformed transformed]]
+[def __range_adaptors_uniqued__ [link
range.reference.adaptors.reference.uniqued uniqued]]
+
+
+[def __range_algorithms__ [link
range.reference.algorithms Range algorithms]]
+[def __range_algorithms_adjacent_find__ [link
range.reference.algorithms.non_mutating.adjacent_find adjacent_find]]
+[def __range_algorithms_binary_search__ [link
range.reference.algorithms.non_mutating.binary_search binary_search]]
+[def __range_algorithms_count__ [link
range.reference.algorithms.non_mutating.count count]]
+[def __range_algorithms_count_if__ [link
range.reference.algorithms.non_mutating.count_if count_if]]
+[def __range_algorithms_equal__ [link
range.reference.algorithms.non_mutating.equal equal]]
+[def __range_algorithms_equal_range__ [link
range.reference.algorithms.non_mutating.equal_range equal_range]]
+[def __range_algorithms_for_each__ [link
range.reference.algorithms.non_mutating.for_each for_each]]
+[def __range_algorithms_find__ [link
range.reference.algorithms.non_mutating.find find]]
+[def __range_algorithms_find_end__ [link
range.reference.algorithms.non_mutating.find_end find_end]]
+[def __range_algorithms_find_first_of__ [link
range.reference.algorithms.non_mutating.find_first_of find_first_of]]
+[def __range_algorithms_find_if__ [link
range.reference.algorithms.non_mutating.find_if find_if]]
+[def __range_algorithms_lexicographical_compare__ [link
range.reference.algorithms.non_mutating.lexicographical_compare
lexicographical_compare]]
+[def __range_algorithms_lower_bound__ [link
range.reference.algorithms.non_mutating.lower_bound lower_bound]]
+[def __range_algorithms_max_element__ [link
range.reference.algorithms.non_mutating.max_element max_element]]
+[def __range_algorithms_min_element__ [link
range.reference.algorithms.non_mutating.min_element min_element]]
+[def __range_algorithms_mismatch__ [link
range.reference.algorithms.non_mutating.mismatch mismatch]]
+[def __range_algorithms_search__ [link
range.reference.algorithms.non_mutating.search search]]
+[def __range_algorithms_search_n__ [link
range.reference.algorithms.non_mutating.search_n search_n]]
+[def __range_algorithms_upper_bound__ [link
range.reference.algorithms.non_mutating.upper_bound upper_bound]]
+
+[def __range_algorithms_copy__ [link
range.reference.algorithms.mutating.copy copy]]
+[def __range_algorithms_copy_backward__ [link
range.reference.algorithms.mutating.copy_backward copy_backward]]
+[def __range_algorithms_fill__ [link
range.reference.algorithms.mutating.fill fill]]
+[def __range_algorithms_fill_n__ [link
range.reference.algorithms.mutating.fill_n fill_n]]
+[def __range_algorithms_generate__ [link
range.reference.algorithms.mutating.generate generate]]
+[def __range_algorithms_inplace_merge__ [link
range.reference.algorithms.mutating.inplace_merge inplace_merge]]
+[def __range_algorithms_merge__ [link
range.reference.algorithms.mutating.merge merge]]
+[def __range_algorithms_nth_element__ [link
range.reference.algorithms.mutating.nth_element nth_element]]
+[def __range_algorithms_partial_sort__ [link
range.reference.algorithms.mutating.partial_sort partial_sort]]
+[def __range_algorithms_partition__ [link
range.reference.algorithms.mutating.partition partition]]
+[def __range_algorithms_random_shuffle__ [link
range.reference.algorithms.mutating.random_shuffle random_shuffle]]
+[def __range_algorithms_remove__ [link
range.reference.algorithms.mutating.remove remove]]
+[def __range_algorithms_remove_copy__ [link
range.reference.algorithms.mutating.remove_copy remove_copy]]
+[def __range_algorithms_remove_copy_if__ [link
range.reference.algorithms.mutating.remove_copy_if remove_copy_if]]
+[def __range_algorithms_remove_if__ [link
range.reference.algorithms.mutating.remove_if remove_if]]
+[def __range_algorithms_replace__ [link
range.reference.algorithms.mutating.replace replace]]
+[def __range_algorithms_replace_copy__ [link
range.reference.algorithms.mutating.replace_copy replace_copy]]
+[def __range_algorithms_replace_copy_if__ [link
range.reference.algorithms.mutating.replace_copy_if replace_copy_if]]
+[def __range_algorithms_replace_if__ [link
range.reference.algorithms.mutating.replace_if replace_if]]
+[def __range_algorithms_reverse__ [link
range.reference.algorithms.mutating.reverse reverse]]
+[def __range_algorithms_reverse_copy__ [link
range.reference.algorithms.mutating.reverse_copy reverse_copy]]
+[def __range_algorithms_rotate__ [link
range.reference.algorithms.mutating.rotate rotate]]
+[def __range_algorithms_rotate_copy__ [link
range.reference.algorithms.mutating.rotate_copy rotate_copy]]
+[def __range_algorithms_sort__ [link
range.reference.algorithms.mutating.sort sort]]
+[def __range_algorithms_stable_partition__ [link
range.reference.algorithms.mutating.stable_partition stable_partition]]
+[def __range_algorithms_stable_sort__ [link
range.reference.algorithms.mutating.stable_sort stable_sort]]
+[def __range_algorithms_swap_ranges__ [link
range.reference.algorithms.mutating.swap_ranges swap_ranges]]
+[def __range_algorithms_transform__ [link
range.reference.algorithms.mutating.transform transform]]
+[def __range_algorithms_unique__ [link
range.reference.algorithms.mutating.unique unique]]
+[def __range_algorithms_unique_copy__ [link
range.reference.algorithms.mutating.unique_copy unique_copy]]
+
+[def __range_algorithms_includes__ [link
range.reference.algorithms.set.includes includes]]
+[def __range_algorithms_set_union__ [link
range.reference.algorithms.set.set_union set_union]]
+[def __range_algorithms_set_intersection__ [link
range.reference.algorithms.set.set_intersection set_intersection]]
+[def __range_algorithms_set_difference__ [link
range.reference.algorithms.set.set_difference set_difference]]
+[def __range_algorithms_set_symmetric_difference__ [link
range.reference.algorithms.set.set_symmetric_difference
set_symmetric_difference]]
+
+[def __range_algorithms_push_heap__ [link
range.reference.algorithms.heap.push_heap push_heap]]
+[def __range_algorithms_pop_heap__ [link
range.reference.algorithms.heap.pop_heap pop_heap]]
+[def __range_algorithms_make_heap__ [link
range.reference.algorithms.heap.make_heap make_heap]]
+[def __range_algorithms_sort_heap__ [link
range.reference.algorithms.heap.sort_heap sort_heap]]
+
+[def __range_algorithms_next_permutation__ [link
range.reference.algorithms.permutation.next_permutation next_permutation]]
+[def __range_algorithms_prev_permutation__ [link
range.reference.algorithms.permutation.prev_permutation prev_permutation]]
+
+[def __range_algorithm_ext_copy_n__ [link
range.reference.algorithms.new.copy_n copy_n]]
+[def __range_algorithm_ext_erase__ [link
range.reference.algorithms.new.erase erase]]
+[def __range_algorithm_ext_for_each__ [link
range.reference.algorithms.new.for_each for_each]]
+[def __range_algorithm_ext_insert__ [link
range.reference.algorithms.new.insert insert]]
+[def __range_algorithm_ext_iota__ [link
range.reference.algorithms.new.iota iota]]
+[def __range_algorithm_ext_is_sorted__ [link
range.reference.algorithms.new.is_sorted is_sorted]]
+[def __range_algorithm_ext_overwrite__ [link
range.reference.algorithms.new.overwrite overwrite]]
+[def __range_algorithm_ext_push_back__ [link
range.reference.algorithms.new.push_back push_back]]
+[def __range_algorithm_ext_push_front__ [link
range.reference.algorithms.new.push_front push_front]]
+
+[def __single_pass_iterator__
[@boost:/libs/iterator/doc/new-iter-concepts.html#singls-pass-iterators-lib-single-pass-iterators
Single Pass Iterator]]
+[def __forward_traversal_iterator__
[@boost:/libs/iterator/doc/new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators
Forward Traversal Iterator]]
+[def __bidirectional_traversal_iterator__
[@boost:/libs/iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators
Bidirectional Traversal Iterator]]
+[def __random_access_traversal_iterator__
[@boost:/libs/iterator/doc/new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators
Random Access Traversal Iterator]]
+[def __new_style_iterators__
[@boost:/libs/iterator/doc/new-iter-concepts.html new style iterators]]
+[def __iterator_concepts__
[@boost:/libs/iterator/doc/iterator_concepts.html Iterator concepts]]
+
+[def __container__
[@http://www.sgi.com/Technology/STL/Container.html Container]]
+[def __metafunctions__
[@boost:/libs/mpl/doc/refmanual/metafunction.html metafunctions]]
+[def __concept_check__ [@boost:/libs/concept_check/index.html
Boost Concept Check library]]
+[def __boost_array__ [@boost:/libs/array/index.html
boost::array]]
+[def __the_forwarding_problem__
[@http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1385.htm The
Forwarding Problem]]
+
+[def __sgi_inner_product__
[@http://www.sgi.com/tech/stl/inner_product.html inner_product]]
+[def __sgi_partial_sum__
[@http://www.sgi.com/tech/stl/partial_sum.html partial_sum]]
+
+Boost.Range is a collection of concepts and utilities, range-based
algorithms,
+as well as range adaptors that allow for efficient and expressive code.
+
+Using Boost.Range inplace of the standard library alternatives results in
more
+readable code and in many cases greater efficiency.
+
+[include introduction.qbk]
+[include concepts.qbk]
+[include reference.qbk]
+[include style.qbk]
+[include headers.qbk]
+[include examples.qbk]
+[include mfc_atl.qbk]
+[include upgrade.qbk]
+[include portability.qbk]
+[include faq.qbk]
+[include history_ack.qbk]
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/concepts.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,251 @@
+[section:concepts Range Concepts]
+
+[section Overview]
+
+A Range is a [*/concept/] similar to the STL
[@http://www.sgi.com/Technology/STL/Container.html Container] concept. A
Range provides iterators for accessing a half-open range
`[first,one_past_last)` of elements and provides information about the
number of elements in the Range. However, a Range has fewer requirements
than a Container.
+
+The motivation for the Range concept is that there are many useful
Container-like types that do not meet the full requirements of Container,
and many algorithms that can be written with this reduced set of
requirements. In particular, a Range does not necessarily
+
+* own the elements that can be accessed through it,
+* have copy semantics,
+
+Because of the second requirement, a Range object must be passed by (const
or non-const) reference in generic code.
+
+The operations that can be performed on a Range is dependent on the
[@../../iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal
traversal category] of the underlying iterator type. Therefore the range
concepts are named to reflect which traversal category its iterators
support. See also terminology and style guidelines. for more information
about naming of ranges.
+
+The concepts described below specifies associated types as
[@../../libs/mpl/doc/refmanual/metafunction.html metafunctions] and all
functions as free-standing functions to allow for a layer of indirection.
+
+[endsect]
+
+
+[section Single Pass Range]
+
+[heading Notation]
+
+[table
+ []
+ [[`X`] [A type that is a model of __single_pass_range__.]]
+ [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of
__single_pass_iterator__.
+
+[heading Associated types]
+
+[table
+ []
+ [[Iterator type ] [`boost::range_iterator<X>::type` ] [The
type of iterator used to iterate through a Range's elements. The iterator's
value type is expected to be the Range's value type. A conversion from the
iterator type to the `const` iterator type must exist.]]
+ [[Const iterator type] [`boost::range_iterator<const X>::type`] [A type
of iterator that may be used to examine, but not to modify, a Range's
elements.]]
+]
+
+[heading Valid expressions]
+
+The following expressions must be valid.
+
+[table
+ [[Name ] [Expression ] [Return type ]]
+ [[Beginning of range] [`boost::begin(a)`]
[`boost::range_iterator<X>::type` if `a` is mutable,
`boost::range_iterator<const X>::type` otherwise]]
+ [[End of range ] [`boost::end(a)` ]
[`boost::range_iterator<X>::type` if `a` is mutable,
`boost::range_iterator<const X>::type` otherwise]]
+]
+
+[heading Expression semantics]
+
+[table
+ [[Expression ]
[Semantics ]
[Postcondition]]
+ [[`boost::begin(a)`] [Returns an iterator pointing to the first element
in the Range. ] [`boost::begin(a)` is either dereferenceable or
past-the-end. It is past-the-end if and only if `boost::distance(a) == 0`.]]
+ [[`boost::end(a)` ] [Returns an iterator pointing one past the last
element in the Range. ] [`boost::end(a)` is past-the-end.]]
+]
+
+[heading Complexity guarantees]
+
+`boost::end(a)` is at most amortized linear time, `boost::begin(a)` is
amortized constant time. For most practical purposes, one can expect both
to be amortized constant time.
+
+[heading Invariants]
+
+[table
+ []
+ [[Valid range ] [For any Range `a`, `[boost::begin(a),boost::end(a))` is
a valid range, that is, `boost::end(a)` is reachable from `boost::begin(a)`
in a finite number of increments.]]
+
+ [[Completeness] [An algorithm that iterates through the range
`[boost::begin(a),boost::end(a))` will pass through every element of `a`.]]
+]
+
+[heading See also]
+
+__extending_for_udts__
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+__container__
+
+[endsect]
+
+
+[section Forward Range]
+
+[heading Notation]
+
+[table
+ []
+ [[`X`] [A type that is a model of __forward_range__.]]
+ [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of
__forward_traversal_iterator__.
+
+[heading Refinement of]
+
+__single_pass_range__
+
+[heading Associated types]
+
+[table
+ []
+ [[Distance type] [`boost::range_difference<X>::type`] [A signed integral
type used to represent the distance between two of the Range's iterators.
This type must be the same as the iterator's distance type.]]
+ [[Size type ] [`boost::range_size<X>::type` ] [An unsigned
integral type that can represent any nonnegative value of the Range's
distance type.]]
+]
+
+[heading See also]
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+[endsect]
+
+
+[section Bidirectional Range]
+
+[heading Notation]
+
+[table
+ []
+ [[`X`] [A type that is a model of __bidirectional_range__.]]
+ [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+This concept provides access to iterators that traverse in both directions
(forward and reverse). The `boost::range_iterator<X>::type` iterator must
meet all of the requirements of __bidirectional_traversal_iterator__.
+
+[heading Refinement of]
+
+__forward_range__
+
+[heading Associated types]
+
+[table
+ []
+ [[Reverse Iterator type ]
[`boost::range_reverse_iterator<X>::type` ] [The type of iterator used
to iterate through a Range's elements in reverse order. The iterator's
value type is expected to be the Range's value type. A conversion from the
reverse iterator type to the const reverse iterator type must exist.]]
+
+ [[Const reverse iterator type] [`boost::range_reverse_iterator<const
X>::type`] [A type of reverse iterator that may be used to examine, but not
to modify, a Range's elements.]]
+]
+
+[heading Valid expressions]
+
+[table
+ [[Name ] [Expression ] [Return type] [Semantics]]
+ [[Beginning of range] [`boost::rbegin(a)`]
[`boost::range_reverse_iterator<X>::type` if `a` is mutable
`boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to
`boost::range_reverse_iterator<X>::type(boost::end(a))`.]]
+
+ [[End of range ] [`boost::rend(a)` ]
[`boost::range_reverse_iterator<X>::type` if `a` is mutable,
`boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to
`boost::range_reverse_iterator<X>::type(boost::begin(a))`.]]
+]
+
+[heading Complexity guarantees]
+
+`boost::rbegin(a)` has the same complexity as `boost::end(a)` and
`boost::rend(a)` has the same complexity as `boost::begin(a)` from
__forward_range__.
+
+[heading Invariants]
+
+[table
+ []
+ [[Valid reverse range] [For any Bidirectional Range a,
`[boost::rbegin(a),boost::rend(a))` is a valid range, that is,
`boost::rend(a)` is reachable from `boost::rbegin(a)` in a finite number of
increments.]]
+
+ [[Completeness ] [An algorithm that iterates through the range
`[boost::rbegin(a),boost::rend(a))` will pass through every element of
`a`.]]
+]
+
+[heading See also]
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+[endsect]
+
+
+[section Random Access Range]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of
__random_access_traversal_iterator__.
+
+[heading Refinement of]
+
+__bidirectional_range__
+
+[heading Valid expressions]
+
+[table
+ [[Name ] [Expression ] [Return type ]]
+ [[Size of range] [`boost::size(a)`] [`boost::range_size<X>::type`]]
+]
+
+[heading Expression semantics]
+
+[table
+ [[Expression ] [Semantics] [Postcondition]]
+ [[`boost::size(a)`] [Returns the size of the Range, that is, its number
of elements. Note `boost::size(a) == 0u` is equivalent to
`boost::empty(a)`.] [`boost::size(a) >= 0`]]
+]
+
+[heading Complexity guarantees]
+
+`boost::size(a)` completes in amortized constant time.
+
+[heading Invariants]
+
+[table
+ []
+ [[Range size] [`boost::size(a)` is equal to the `boost::end(a)` -
`boost::begin(a)`.]]
+]
+
+[endsect]
+
+
+[section Concept Checking]
+
+Each of the range concepts has a corresponding concept checking class in
the file [@../../boost/range/concepts.hpp `<boost/range/concepts.hpp>`].
These classes may be used in conjunction with the __concept_check__ to
ensure that the type of a template parameter is compatible with a range
concept. If not, a meaningful compile time error is generated. Checks are
provided for the range concepts related to iterator traversal categories.
For example, the following line checks that the type `T` models the
__forward_range__ concept.
+
+``
+BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> ));
+``
+
+An additional concept check is required for the value access property of
the range based on the range's iterator type. For example to check for a
ForwardReadableRange, the following code is required.
+
+``
+BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> ));
+BOOST_CONCEPT_ASSERT(( ReadableIteratorConcept<typename
range_iterator<T>::type> ));
+``
+
+The following range concept checking classes are provided.
+
+* Class SinglePassRangeConcept checks for __single_pass_range__
+* Class ForwardRangeConcept checks for __forward_range__
+* Class BidirectionalRangeConcept checks for __bidirectional_range__
+* Class RandomAccessRangeConcept checks for __random_access_range__
+
+[heading See also]
+
+[link range.style_guide Range Terminology and style guidelines]
+
+__iterator_concepts__
+
+__concept_check__
+
+[endsect]
+
+[endsect]
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/example.cpp Mon May 31 00:54:22 2010
@@ -0,0 +1,151 @@
+// Boost.Range library
+//
+// Copyright Thorsten Ottosen 2003-2008. Use, modification and
+// distribution is subject to 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)
+//
+// For more information, see http://www.boost.org/libs/range/
+//
+
+#include <boost/range.hpp>
+#include <iterator> // for std::iterator_traits, std::distance()
+
+namespace Foo
+{
+ //
+ // Our sample UDT. A 'Pair'
+ // will work as a range when the stored
+ // elements are iterators.
+ //
+ template< class T >
+ struct Pair
+ {
+ T first, last;
+ };
+
+} // namespace 'Foo'
+
+namespace boost
+{
+ //
+ // Specialize metafunctions. We must include the range.hpp header.
+ // We must open the 'boost' namespace.
+ //
+ /*
+ template< class T >
+ struct range_value< Foo::Pair<T> >
+ {
+ typedef typename std::iterator_traits<T>::value_type type;
+ };
+ */
+
+ template< class T >
+ struct range_iterator< Foo::Pair<T> >
+ {
+ typedef T type;
+ };
+
+ template< class T >
+ struct range_const_iterator< Foo::Pair<T> >
+ {
+ //
+ // Remark: this is defined similar to 'range_iterator'
+ // because the 'Pair' type does not distinguish
+ // between an iterator and a const_iterator.
+ //
+ typedef T type;
+ };
+
+ /*
+ template< class T >
+ struct range_difference< Foo::Pair<T> >
+ {
+ typedef typename std::iterator_traits<T>::difference_type
type;
+ };
+ */
+
+ template< class T >
+ struct range_size< Foo::Pair<T> >
+ {
+ int static_assertion[ sizeof( std::size_t ) >=
+ sizeof( typename range_difference< Foo::Pair<T>
::type ) ];
+ typedef std::size_t type;
+ };
+
+} // namespace 'boost'
+
+namespace Foo
+{
+ //
+ // The required functions. These should be defined in
+ // the same namespace as 'Pair', in this case
+ // in namespace 'Foo'.
+ //
+
+ template< class T >
+ inline T boost_range_begin( Pair<T>& x )
+ {
+ return x.first;
+ }
+
+ template< class T >
+ inline T boost_range_begin( const Pair<T>& x )
+ {
+ return x.first;
+ }
+
+ template< class T >
+ inline T boost_range_end( Pair<T>& x )
+ {
+ return x.last;
+ }
+
+ template< class T >
+ inline T boost_range_end( const Pair<T>& x )
+ {
+ return x.last;
+ }
+
+ template< class T >
+ inline typename boost::range_size< Pair<T> >::type
+ boost_range_size( const Pair<T>& x )
+ {
+ return std::distance(x.first,x.last);
+ }
+
+} // namespace 'Foo'
+
+#include <vector>
+
+int main()
+{
+ typedef std::vector<int>::iterator iter;
+ std::vector<int> vec;
+ vec.push_back( 42 );
+ Foo::Pair<iter> pair = { vec.begin(),
vec.end() };
+ const Foo::Pair<iter>& cpair = pair;
+ //
+ // Notice that we call 'begin' etc with qualification.
+ //
+ iter i = boost::begin( pair );
+ iter e = boost::end( pair );
+ i = boost::begin( cpair );
+ e = boost::end( cpair );
+ boost::range_size< Foo::Pair<iter> >::type s = boost::size( pair );
+ s = boost::size( cpair );
+ boost::range_const_reverse_iterator< Foo::Pair<iter> >::type
+ ri = boost::rbegin( cpair ),
+ re = boost::rend( cpair );
+
+ //
+ // Test metafunctions
+ //
+
+ boost::range_value< Foo::Pair<iter> >::type
+ v = *boost::begin(pair);
+
+ boost::range_difference< Foo::Pair<iter> >::type
+ d = boost::end(pair) - boost::begin(pair);
+}
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/examples.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,23 @@
+[section Examples]
+
+Some examples are given in the accompanying test files:
+
+* [@http://www.boost.org/libs/range/test/string.cpp string.cpp] shows how
to implement a container version of `std::find()` that works with
`char[]`,`wchar_t[]`,`char*`,`wchar_t*`.
+
+* [@http://www.boost.org/libs/range/test/algorithm_example.cpp
algorithm_example.cpp] shows the replace example from the introduction.
+
+* [@http://www.boost.org/libs/range/test/iterator_range.cpp
iterator_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/sub_range.cpp sub_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/iterator_pair.cpp
iterator_pair.cpp]
+
+* [@http://www.boost.org/libs/range/test/reversible_range.cpp
reversible_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/std_container.cpp
std_container.cpp]
+
+* [@http://www.boost.org/libs/range/test/array.cpp array.cpp]
+
+[endsect]
+
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/faq.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,25 @@
+[section FAQ]
+
+1. ['[*Why is there no difference between `range_iterator<C>::type` and
`range_const_iterator<C>::type` for `std::pair<iterator, iterator>`?]]
+
+[:In general it is not possible nor desirable to find a corresponding
`const_iterator`. When it is possible to come up with one, the client might
choose to construct a `std::pair<const_iterator,const_iterator>` object.]
+
+[:Note that an __iterator_range__ is somewhat more convenient than a
`pair` and that a __sub_range__ does propagate const-ness.]
+
+2. ['[*Why is there not supplied more types or more functions?]]
+
+[:The library has been kept small because its current interface will serve
most purposes. If and when a genuine need arises for more functionality, it
can be implemented.]
+
+3. ['[*How should I implement generic algorithms for ranges?]]
+
+[:One should always start with a generic algorithm that takes two
iterators (or more) as input. Then use Boost.Range to build handier
versions on top of the iterator based algorithm. Please notice that once
the range version of the algorithm is done, it makes sense not to expose
the iterator version in the public interface.]
+
+4. ['[*Why is there no Incrementable Range concept?]]
+
+[:Even though we speak of incrementable iterators, it would not make much
sense for ranges; for example, we cannot determine the size and emptiness
of a range since we cannot even compare its iterators.]
+
+[:Note also that incrementable iterators are derived from output iterators
and so there exist no output range.]
+
+[endsect]
+
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/headers.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,138 @@
+[section Library Headers]
+
+[section General]
+[table
+ [[Header ] [Includes ]
[Related Concept ]]
+ [[`<boost/range.hpp>` ] [everything from Boost.Range
version 1 (Boost versions 1.42 and below). Includes the core range
functions and metafunctinos, but excludes Range Adaptors and Range
Algorithms. ] [- ]]
+ [[`<boost/range/metafunctions.hpp>` ] [every metafunction ]
[- ]]
+ [[`<boost/range/functions.hpp>` ] [every function ]
[- ]]
+ [[`<boost/range/value_type.hpp>` ] [__range_value__ ]
[__single_pass_range__ ]]
+ [[`<boost/range/iterator.hpp>` ] [__range_iterator__ ]
[__single_pass_range__ ]]
+ [[`<boost/range/difference_type.hpp>` ] [__range_difference__ ]
[__forward_range__ ]]
+ [[`<boost/range/pointer.hpp>` ] [__range_pointer__ ]
[-]]
+ [[`<boost/range/category.hpp>` ] [__range_category__ ]
[-]]
+ [[`<boost/range/reverse_iterator.hpp>`] [__range_reverse_iterator__ ]
[__bidirectional_range__ ]]
+ [[`<boost/range/begin.hpp>` ] [__begin__ and __const_begin__
] [__single_pass_range__ ]]
+ [[`<boost/range/end.hpp>` ] [__end__ and __const_end__ ]
[__single_pass_range__ ]]
+ [[`<boost/range/empty.hpp>` ] [__empty__ ]
[__single_pass_range__ ]]
+ [[`<boost/range/distance.hpp>` ] [__distance__ ]
[__forward_range__ ]]
+ [[`<boost/range/size.hpp>` ] [__size__ ]
[__random_access_range__ ]]
+ [[`<boost/range/rbegin.hpp>` ] [__rbegin__ and
__const_rbegin__] [__bidirectional_range__ ]]
+ [[`<boost/range/rend.hpp>` ] [__rend__ and __const_rend__ ]
[__bidirectional_range__ ]]
+ [[`<boost/range/as_array.hpp>` ] [__as_array__ ]
[- ]]
+ [[`<boost/range/as_literal.hpp>` ] [__as_literal__ ]
[- ]]
+ [[`<boost/range/iterator_range.hpp>` ] [__iterator_range__ ]
[- ]]
+ [[`<boost/range/sub_range.hpp>` ] [__sub_range__ ]
[- ]]
+ [[`<boost/range/concepts.hpp>` ] [__range_concepts__ ]
[- ]]
+ [[`<boost/range/adaptors.hpp>` ] [every range adaptor ]
[- ]]
+ [[`<boost/range/algorithm.hpp>` ] [every range equivalent of an
STL algorithm ] [- ]]
+ [[`<boost/range/algorithm_ext.hpp>` ] [every range algorithm that is
an extension of the STL algorithms ] [- ]]
+ [[`<boost/range/counting_range.hpp>` ] [ __counting_range__ ] [-]]
+ [[`<boost/range/istream_range.hpp>` ] [ __istream_range__ ] [-]]
+ [[`<boost/range/irange.hpp>` ] [ __irange__ ] [-]]
+ [[`<boost/range/join.hpp>` ] [ __join__ ] [-]]
+]
+[endsect]
+
+[section Adaptors]
+[table
+ [[Header
][Includes ]]
+ [[`<boost/range/adaptor/adjacent_filtered.hpp>`]
[__range_adaptors_adjacent_filtered__ ]]
+ [[`<boost/range/adaptor/copied.hpp>`]
[__range_adaptors_copied__]]
+ [[`<boost/range/adaptor/filtered.hpp>`]
[__range_adaptors_filtered__]]
+ [[`<boost/range/adaptor/indexed.hpp>`]
[__range_adaptors_indexed__]]
+ [[`<boost/range/adaptor/indirected.hpp.`]
[__range_adaptors_indirected__]]
+ [[`<boost/range/adaptor/map.hpp>`]
[__range_adaptors_map_keys__ __range_adaptors_map_values__]]
+ [[`<boost/range/adaptor/replaced.hpp>`]
[__range_adaptors_replaced__]]
+ [[`<boost/range/adaptor/replaced_if.hpp>`]
[__range_adaptors_replaced_if__]]
+ [[`<boost/range/adaptor/reversed.hpp>`]
[__range_adaptors_reversed__]]
+ [[`<boost/range/adaptor/sliced.hpp>`]
[__range_adaptors_sliced__]]
+ [[`<boost/range/adaptor/strided.hpp>`]
[__range_adaptors_strided__]]
+ [[`<boost/range/adaptor/tokenized.hpp>`]
[__range_adaptors_tokenized__]]
+ [[`<boost/range/adaptor/transformed.hpp>`]
[__range_adaptors_transformed__]]
+ [[`<boost/range/adaptor/uniqued.hpp>`]
[__range_adaptors_uniqued__]]
+]
+[endsect]
+
+[section Algorithm]
+[table
+ [[Header
][Includes ]]
+ [[`<boost/range/algorithm/adjacent_find.hpp>`]
[__range_algorithms_adjacent_find__]]
+ [[`<boost/range/algorithm/binary_search.hpp>`]
[__range_algorithms_binary_search__]]
+ [[`<boost/range/algorithm/copy.hpp>`]
[__range_algorithms_copy__]]
+ [[`<boost/range/algorithm/copy_backward.hpp>`]
[__range_algorithms_copy_backward__]]
+ [[`<boost/range/algorithm/count.hpp>`]
[__range_algorithms_count__]]
+ [[`<boost/range/algorithm/count_if.hpp>`]
[__range_algorithms_count_if__]]
+ [[`<boost/range/algorithm/equal.hpp>`]
[__range_algorithms_equal__]]
+ [[`<boost/range/algorithm/equal_range.hpp>`]
[__range_algorithms_equal_range__]]
+ [[`<boost/range/algorithm/fill.hpp>`]
[__range_algorithms_fill__]]
+ [[`<boost/range/algorithm/fill_n.hpp>`]
[__range_algorithms_fill_n__]]
+ [[`<boost/range/algorithm/find.hpp>`]
[__range_algorithms_find__]]
+ [[`<boost/range/algorithm/find_end.hpp>`]
[__range_algorithms_find_end__]]
+ [[`<boost/range/algorithm/find_first_of.hpp>`]
[__range_algorithms_find_first_of__]]
+ [[`<boost/range/algorithm/find_if.hpp>`]
[__range_algorithms_find_if__]]
+ [[`<boost/range/algorithm/for_each.hpp>`]
[__range_algorithms_for_each__]]
+ [[`<boost/range/algorithm/generate.hpp>`]
[__range_algorithms_generate__]]
+ [[`<boost/range/algorithm/heap_algorithm.hpp>`]
[__range_algorithms_push_heap__
+
__range_algorithms_pop_heap__
+
__range_algorithms_make_heap__
+
__range_algorithms_sort_heap__]]
+ [[`<boost/range/algorithm/inplace_merge.hpp>`]
[__range_algorithms_inplace_merge__]]
+ [[`<boost/range/algorithm/lexicographical_compare.hpp>`]
[__range_algorithms_lexicographical_compare__]]
+ [[`<boost/range/algorithm/lower_bound.hpp>`]
[__range_algorithms_lower_bound__]]
+ [[`<boost/range/algorithm/max_element.hpp>`]
[__range_algorithms_max_element__]]
+ [[`<boost/range/algorithm/merge.hpp>`]
[__range_algorithms_merge__]]
+ [[`<boost/range/algorithm/min_element.hpp>`]
[__range_algorithms_min_element__]]
+ [[`<boost/range/algorithm/mismatch.hpp>`]
[__range_algorithms_mismatch__]]
+ [[`<boost/range/algorithm/nth_element.hpp>`]
[__range_algorithms_nth_element__]]
+ [[`<boost/range/algorithm/partial_sort.hpp>`]
[__range_algorithms_partial_sort__]]
+ [[`<boost/range/algorithm/partition.hpp>`]
[__range_algorithms_partition__]]
+ [[`<boost/range/algorithm/permutation.hpp>`]
[__range_algorithms_next_permutation__
+
__range_algorithms_prev_permutation__]]
+ [[`<boost/range/algorithm/random_shuffle.hpp>`]
[__range_algorithms_random_shuffle__]]
+ [[`<boost/range/algorithm/remove.hpp>`]
[__range_algorithms_remove__]]
+ [[`<boost/range/algorithm/remove_copy.hpp>`]
[__range_algorithms_remove_copy__]]
+ [[`<boost/range/algorithm/remove_copy_if.hpp>`]
[__range_algorithms_remove_copy_if__]]
+ [[`<boost/range/algorithm/remove_if.hpp>`]
[__range_algorithms_remove_if__]]
+ [[`<boost/range/algorithm/replace.hpp>`]
[__range_algorithms_replace__]]
+ [[`<boost/range/algorithm/replace_copy.hpp>`]
[__range_algorithms_replace_copy__]]
+ [[`<boost/range/algorithm/replace_copy_if.hpp>`]
[__range_algorithms_replace_copy_if__]]
+ [[`<boost/range/algorithm/replace_if.hpp>`]
[__range_algorithms_replace_if__]]
+ [[`<boost/range/algorithm/reverse.hpp>`]
[__range_algorithms_reverse__]]
+ [[`<boost/range/algorithm/reverse_copy.hpp>`]
[__range_algorithms_reverse_copy__]]
+ [[`<boost/range/algorithm/rotate.hpp>`]
[__range_algorithms_rotate__]]
+ [[`<boost/range/algorithm/rotate_copy.hpp>`]
[__range_algorithms_rotate_copy__]]
+ [[`<boost/range/algorithm/search.hpp>`]
[__range_algorithms_search__]]
+ [[`<boost/range/algorithm/search_n.hpp>`]
[__range_algorithms_search_n__]]
+ [[`<boost/range/algorithm/set_algorithm.hpp>`]
[__range_algorithms_includes__
+
__range_algorithms_set_union__
+
__range_algorithms_set_intersection__
+
__range_algorithms_set_difference__
+
__range_algorithms_set_symmetric_difference__]]
+ [[`<boost/range/algorithm/sort.hpp>`]
[__range_algorithms_sort__]]
+ [[`<boost/range/algorithm/stable_partition.hpp>`]
[__range_algorithms_stable_partition__]]
+ [[`<boost/range/algorithm/swap_ranges.hpp>`]
[__range_algorithms_swap_ranges__]]
+ [[`<boost/range/algorithm/transform.hpp>`]
[__range_algorithms_transform__]]
+ [[`<boost/range/algorithm/unique.hpp>`]
[__range_algorithms_unique__]]
+ [[`<boost/range/algorithm/unique_copy.hpp>`]
[__range_algorithms_unique_copy__]]
+ [[`<boost/range/algorithm/upper_bound.hpp>`]
[__range_algorithms_upper_bound__]]
+]
+[endsect]
+
+[section Algorithm Extensions]
+[table
+ [[Header
][Includes ]]
+ [[`<boost/range/algorithm_ext/copy_n.hpp>`]
[__range_algorithm_ext_copy_n__]]
+ [[`<boost/range/algorithm_ext/erase.hpp>`]
[__range_algorithm_ext_erase__]]
+ [[`<boost/range/algorithm_ext/for_each.hpp>`]
[__range_algorithm_ext_for_each__]]
+ [[`<boost/range/algorithm_ext/insert.hpp>`]
[__range_algorithm_ext_insert__]]
+ [[`<boost/range/algorithm_ext/iota.hpp>`]
[__range_algorithm_ext_iota__]]
+ [[`<boost/range/algorithm_ext/is_sorted.hpp>`]
[__range_algorithm_ext_is_sorted__]]
+ [[`<boost/range/algorithm_ext/overwrite.hpp>`]
[__range_algorithm_ext_overwrite__]]
+ [[`<boost/range/algorithm_ext/push_back.hpp>`]
[__range_algorithm_ext_push_back__]]
+ [[`<boost/range/algorithm_ext/push_front.hpp>`]
[__range_algorithm_ext_push_front__]]
+]
+[endsect]
+
+[endsect]
+
=======================================
--- /dev/null
+++ /trunk/libs/range/doc/history_ack.qbk Mon May 31 00:54:22 2010
@@ -0,0 +1,47 @@
+[section:history_ack History and Acknowledgement]
+
+[heading Version 1 - before Boost 1.43]
+The library have been under way for a long time. Dietmar Kühl originally
intended to submit an `array_traits` class template which had most of the
functionality present now, but only for arrays and standard containers.
+
+Meanwhile work on algorithms for containers in various contexts showed the
need for handling pairs of iterators, and string libraries needed special
treatment of character arrays. In the end it made sense to formalize the
minimal requirements of these similar concepts. And the results are the
Range concepts found in this library.
+
+The term Range was adopted because of paragraph 24.1/7 from the C++
standard:
+
+Most of the library's algorithmic templates that operate on data
structures have interfaces that use ranges. A range is a pair of iterators
that designate the beginning and end of the computation. A range [i, i) is
an empty range; in general, a range [i, j) refers to the elements in the
data structure starting with the one pointed to by i and up to but not
including the one pointed to by j. Range [i, j) is valid if and only if j
is reachable from i. The result of the application of functions in the
library to invalid ranges is undefined.
+
+Special thanks goes to
+
+* Pavol Droba for help with documentation and implementation
+* Pavel Vozenilek for help with porting the library
+* Jonathan Turkanis and John Torjo for help with documentation
+* Hartmut Kaiser for being review manager
+* Jonathan Turkanis for porting the lib (as far sa possible) to vc6 and
vc7.
+
+The concept checks and their documentation was provided by Daniel Walker.
+
+[heading Version 2 - Boost 1.43 and beyond]
+This version introduced Range Adaptors and Range Algorithms. This version
2 is
+the result of a merge of all of the RangeEx features into Boost.Range.
+
+There were an enormous number of very significant contributors through all
+stages of this library.
+
+The people in the following list all made contributions in the form of
reviews,
+user feedback, design suggestions, or defect detection:
+
+* Thorsten Ottosen: review management, design advice, documentation
feedback
+* Eric Niebler: feedback
+* Joel de Guzman: review
+* Mathias Gaunard: review
+* David Abrahams: implementation advice
+* Robert Jones: defect reports, usage feedback
+* Sean Parent: contributed experience from the Adobe range library
+* Arno Schoedl: implementations, and review
+* Rogier van Dalen: review
+* Vincente Botet: review, documentation feedback
+
+Regardless of how I write this section it will never truly fairly capture
the
+gratitude that I feel to all who have contributed. Thank you everyone.
+
+[endsect]
+
=======================================
***Additional files exist in this changeset.***
Other related posts:
- » [boost-doc-zh] r406 committed - 升级至1.43.0，第5批，libs/目录r-s子目录 - boost-doc-zh
