OSDN Git Service

2011-05-23 Benjamin Kosnik <bkoz@redhat.com>
authorbkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 24 May 2011 02:38:19 +0000 (02:38 +0000)
committerbkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 24 May 2011 02:38:19 +0000 (02:38 +0000)
PR libstdc++/37144
PR libstdc++/28457
Interface changes for ext/pb_ds.
PB_DS_BASE_C_DEC to unique PB_DS_*_BASE macros.
* include/ext/pb_ds/assoc_container.hpp (container_base): Remove.
(basic_hash_table, basic_branch, list_update): Derive from
container_base_dispatch.
* include/ext/pb_ds/list_update_policy.hpp (null_lu_metadata): Remove.
(move_to_front_lu_policy): To lu_move_to_front_policy.
(counter_lu_policy): To lu_counter_policy.
* include/ext/pb_ds/tree_policy.hpp (null_tree_node_update): Remove.
* include/ext/pb_ds/tag_and_trait.hpp (container_base_dispatch): Adjust
template parameters, declare here.
(null_mapped_type) Remove.
(null_type): Just use this for template tricks everywhere.
* include/ext/pb_ds/hash_policy.hpp (null_hash_fn, null_probe_fn):
Remove.
* include/ext/pb_ds/trie_policy.hpp (null_trie_node_update): Remove.
(string_trie_e_access_traits): To trie_string_access_traits.
* include/ext/pb_ds/priority_queue.hpp: Use container_base_dispatch.

File changes.
* include/Makefile.am (pb_headers): Removed and changed file names.
* include/Makefile.in: Regenerated.
* include/ext/pb_ds/detail/basic_types.hpp: Remove.
* include/ext/pb_ds/detail/bin_search_tree_/
  cond_dtor_entry_dealtor.hpp: Remove.
* include/ext/pb_ds/detail/bin_search_tree_/
  cond_key_dtor_entry_dealtor.hpp: Remove.
* include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp: Move..
* include/ext/pb_ds/detail/binary_heap_/
  point_const_iterator.hpp: ..here.
* include/ext/pb_ds/detail/basic_tree_policy: Move to...
* include/ext/pb_ds/detail/branch_policy: This.
* include/ext/pb_ds/detail/branch_policy/
  basic_tree_policy_base.hpp: Move...
* include/ext/pb_ds/detail/branch_policy/branch_policy.hpp: ...here.
* include/ext/pb_ds/detail/branch_policy/null_node_metadata.hpp: Add.
* include/ext/pb_ds/detail/branch_policy/traits.hpp: Add.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
null_metadata.hpp: Remove.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
const_point_iterator.hpp: Move...
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
point_const_iterator.hpp: ...here.
* include/ext/pb_ds/detail/list_update_policy/
counter_lu_metadata.hpp: Move..
* include/ext/pb_ds/detail/list_update_policy/
lu_counter_metadata.hpp: ...here.
* include/ext/pb_ds/detail/list_update_policy/
counter_lu_policy_imp.hpp: Remove.
* include/ext/pb_ds/detail/list_update_policy/
mtf_lu_policy_imp.hpp: Remove.
* include/ext/pb_ds/detail/trie_policy/
string_trie_e_access_traits_imp.hpp: Move...
* include/ext/pb_ds/detail/trie_policy/
sample_trie_access_traits.hpp: ...here.
* include/ext/pb_ds/detail/trie_policy/
sample_trie_e_access_traits.hpp: Move...
* include/ext/pb_ds/detail/trie_policy/
trie_string_access_traits_imp.hpp: ...here.
* include/ext/pb_ds/detail/trie_policy/null_node_update_imp.hpp: Remove.
* include/ext/pb_ds/detail/tree_policy/null_node_update_imp.hpp: Remove.
* include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp: Remove.
* include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: New, fold all
types found in the following files into pat_trie_base.
* include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/
  cond_dtor_entry_dealtor.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/head.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/internal_node.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Folded.
* include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp: Move...
* include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp: ...here.
* include/ext/pb_ds/detail/unordered_iterator/
const_point_iterator.hpp: Move...
* include/ext/pb_ds/detail/unordered_iterator/
point_const_iterator.hpp: ...here.

Adjust for above changes.
* include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp: Same.
* include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp: Same.
* include/ext/pb_ds/detail/resize_policy/
  sample_resize_trigger.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
  binomial_heap_base_.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_base_/
  split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/container_base_dispatch.hpp: Same. Adjust
  for template parameter ordering change.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  erase_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  resize_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  entry_list_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  find_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  cond_key_dtor_entry_dealtor.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  debug_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  resize_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
  standard_policies.hpp: Same.
* include/ext/pb_ds/detail/tree_trace_base.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/iterator.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp: Same.
* include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/traits.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/
  policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/traits.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/
  split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_policy/
  sample_update_policy.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  erase_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  resize_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  iterator_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  find_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  find_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  debug_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  resize_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
  standard_policies.hpp: Same.
* include/ext/pb_ds/detail/standard_policies.hpp: Same.
* include/ext/pb_ds/detail/types_traits.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp: Same.
* include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp: Same.
* include/ext/pb_ds/detail/tree_policy/
  sample_tree_node_update.hpp: Same.
* include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp: Same.
* include/ext/pb_ds/detail/trie_policy/
  sample_trie_node_update.hpp: Same.
* include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp: Same.
* include/ext/pb_ds/detail/trie_policy/
  prefix_search_node_update_imp.hpp: Same.
* include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp: Same.
* include/ext/pb_ds/detail/cond_dealtor.hpp: Same.
* include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp: Same.
  Adjust for template parameter change, fold into
  container_base_dispatch.
* include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
* include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
* include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/type_utils.hpp: Same.
* include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp: Same.
* include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  left_child_next_sibling_heap_.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  const_iterator.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  node.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
  iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/traits.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/debug_map_base.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Same.
* include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/node.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/traits.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
  entry_metadata_base.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
  constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
  rc_binomial_heap_.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
* include/ext/pb_ds/detail/rc_binomial_heap_/
  split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/
  constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/traits.hpp: Same.

Documentation changes.
* include/ext/pb_ds/*: Add doxygen markup.
* doc/doxygen/user.cfg.in: Add details for extracting comments
from pb_ds.
* scripts/run_doxygen: Fixup __gnu_pb_ds::detail.
* scripts/make_graph.py: Move to svg output. Re-format generated tables.

* doc/Makefile.am (stamp-html-copy): New rule.
(stamp-html): Use it to copy non-generated files into html docs.
* doc/Makefile.in: Regenerated.

* doc/html/ext/pb_ds/sample_trie_e_access_traits.html: Move...
* doc/html/ext/pb_ds/trie_string_access_traits.html: ...here.
* doc/html/ext/pb_ds/string_trie_e_access_traits.html: Move..
* doc/html/ext/pb_ds/sample_trie_access_traits.html: ...here.

* doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png,
hash_random_int_erase_mem_usage_test_local.png,
multimap_text_insert_mem_usage_test_small_s2p_hash_local.png,
tree_text_insert_timing_test_pat_trie_local.png ,
multimap_text_insert_mem_usage_test_small_s2p_tree_local.png ,
priority_queue_text_modify_down_timing_test_local.png,
gp_hash_random_int_subscript_timing_test_find_local.png,
text_find_timing_test_hash_local.png,
multimap_text_insert_timing_test_small_s2p_hash_local.png,
multimap_text_insert_timing_test_small_s2p_tree_local.png,
multimap_text_insert_mem_usage_test_large_s2p_hash_local.png,
multimap_text_insert_mem_usage_test_large_s2p_tree_local.png,
multimap_text_insert_timing_test_large_s2p_hash_local.png,
hash_zlob_random_int_find_timing_test_local.png,
multimap_text_insert_timing_test_large_s2p_tree_local.png,
binary_priority_queue_random_int_push_timing_test_local.png,
priority_queue_text_pop_mem_usage_test_local.png,
priority_queue_text_modify_down_timing_test_pairing_thin_local.png,
tree_split_join_timing_test_local.png,
multimap_text_find_timing_test_small_s2p_hash_local.png,
ccgp_hash_random_int_subscript_timing_test_insert_local.png,
priority_queue_random_int_push_pop_timing_test_local.png,
multimap_text_find_timing_test_small_s2p_tree_local.png,
gp_hash_random_int_subscript_timing_test_insert_local.png,
priority_queue_text_push_timing_test_local.png,
cc_hash_random_int_subscript_timing_test_find_local.png,
tree_text_insert_timing_test_vector_tree_local.png,
multimap_text_find_timing_test_large_s2p_hash_local.png,
pairing_priority_queue_text_push_timing_test_local.png,
tree_order_statistics_timing_test_local.png,
priority_queue_text_push_pop_timing_test_local.png,
text_find_timing_test_tree_like_local.png,
multimap_text_find_timing_test_large_s2p_tree_local.png,
priority_queue_text_modify_up_timing_test_pairing_thin_local.png,
cc_hash_random_int_subscript_timing_test_insert_local.png,
priority_queue_text_modify_up_timing_test_local.png,
random_int_find_find_timing_test_tree_local.png,
priority_queue_random_int_push_timing_test_local.png,
tree_text_insert_timing_test_node_tree_local.png,
pairing_priority_queue_text_push_pop_timing_test_local.png,
gp_hash_random_int_find_timing_test_local.png,
cc_hash_random_int_find_timing_test_local.png,
priority_queue_text_join_timing_test_local.png: Update local pngs.

Testsuite changes.
* testsuite/ext/pb_ds/regression/tree_no_data_map_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/tree_data_map_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/priority_queue_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/trie_no_data_map_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/trie_data_map_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/list_update_no_data_map_rand_debug.cc:
New.
* testsuite/ext/pb_ds/regression/list_update_data_map_rand_debug.cc:
New.
* testsuite/ext/pb_ds/regression/hash_no_data_map_rand_debug.cc: New.
* testsuite/ext/pb_ds/regression/hash_data_map_rand_debug.cc: New.

* testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc: Fix typo.

* testsuite/ext/pb_ds/example/basic_set.cc: Update.
* testsuite/ext/pb_ds/example/ranged_hash.cc: Same.
* testsuite/ext/pb_ds/example/tree_order_statistics.cc: Same.
* testsuite/ext/pb_ds/example/trie_prefix_search.cc: Same.
* testsuite/ext/pb_ds/example/trie_dna.cc: Same.
* testsuite/ext/pb_ds/example/tree_intervals.cc: Same.
* testsuite/ext/pb_ds/example/basic_multimap.cc: Same.
* testsuite/performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc:
  Same.
* testsuite/performance/ext/pb_ds/tree_split_join_timing.cc: Same.
* testsuite/performance/ext/pb_ds/tree_order_statistics_timing.cc: Same.
* testsuite/data/make_graph_test_infos.xml: Same.
* testsuite/util/regression/common_type.hpp: Same.
* testsuite/util/regression/trait/assoc/native_type_trait.hpp: Same.
* testsuite/util/regression/trait/assoc/trait.hpp: Same.
* testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
* testsuite/util/regression/rand/priority_queue/
  rand_regression_test.hpp: Same.
* testsuite/util/regression/rand/priority_queue/
  container_rand_regression_test.tcc: Same.
* testsuite/util/regression/rand/assoc/rand_regression_test.hpp: Same.
* testsuite/util/regression/rand/assoc/container_rand_regression_test.h
* testsuite/util/regression/rand/assoc/
  container_rand_regression_test.tcc: Same.
* testsuite/util/native_type/native_priority_queue.hpp: Same.
* testsuite/util/native_type/native_multimap.hpp: Same.
* testsuite/util/native_type/native_hash_multimap.hpp: Same.
* testsuite/util/native_type/native_set.hpp: Same.
* testsuite/util/native_type/native_map.hpp: Same.
* testsuite/util/native_type/native_hash_set.hpp: Same.
* testsuite/util/native_type/native_hash_map.hpp: Same.
* testsuite/util/testsuite_containers.h
* testsuite/util/common_type/priority_queue/common_type.hpp: Same.
* testsuite/util/common_type/assoc/common_type.hpp: Same.
* testsuite/util/common_type/assoc/string_form.hpp: Same.
* testsuite/util/common_type/assoc/template_policy.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  trigger_policy_string_form.hpp: Same.
* testsuite/util/common_type/assoc/detail/ds_string_form.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  size_policy_string_form.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  probe_fn_string_form.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  tree_supports_order_statistics.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  trie_supports_prefix_search.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  list_update_policy_string_form.hpp: Same.
* testsuite/util/common_type/assoc/detail/
  trie_supports_order_statistics.hpp: Same.
* testsuite/util/common_type/assoc/native_set.hpp: Same.
* testsuite/util/performance/assoc/timing/common_type.hpp: Same.
* testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.
* testsuite/util/performance/assoc/multimap_common_type.hpp: Same.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@174100 138bc75d-0d04-0410-961f-82ee72b054a4

360 files changed:
libstdc++-v3/ChangeLog
libstdc++-v3/doc/Makefile.am
libstdc++-v3/doc/Makefile.in
libstdc++-v3/doc/doxygen/user.cfg.in
libstdc++-v3/doc/html/ext/pb_ds/binary_priority_queue_random_int_push_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_find_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_find_local.png
libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_insert_local.png
libstdc++-v3/doc/html/ext/pb_ds/ccgp_hash_random_int_subscript_timing_test_insert_local.png
libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_find_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_find_local.png
libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_insert_local.png
libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/hash_zlob_random_int_find_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_pop_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_pairing_thin_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_pairing_thin_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_pop_mem_usage_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/random_int_find_find_timing_test_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/sample_trie_access_traits.html [moved from libstdc++-v3/doc/html/ext/pb_ds/sample_trie_e_access_traits.html with 100% similarity]
libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_hash_local.png
libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_tree_like_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_split_join_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_node_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_pat_trie_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_vector_tree_local.png
libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png
libstdc++-v3/doc/html/ext/pb_ds/trie_string_access_traits.html [moved from libstdc++-v3/doc/html/ext/pb_ds/string_trie_e_access_traits.html with 100% similarity]
libstdc++-v3/include/Makefile.am
libstdc++-v3/include/Makefile.in
libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
libstdc++-v3/include/ext/pb_ds/detail/basic_types.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp with 80% similarity]
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp [new file with mode: 0644]
libstdc++-v3/include/ext/pb_ds/detail/branch_policy/null_node_metadata.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp with 69% similarity]
libstdc++-v3/include/ext/pb_ds/detail/branch_policy/traits.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp with 51% similarity]
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/standard_policies.hpp
libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp
libstdc++-v3/include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/container_base_dispatch.hpp
libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp
libstdc++-v3/include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp
libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/standard_policies.hpp
libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp with 82% similarity]
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/counter_lu_policy_imp.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/lu_counter_metadata.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/counter_lu_metadata.hpp with 64% similarity]
libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/mtf_lu_policy_imp.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp [new file with mode: 0644]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp with 50% similarity]
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp
libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp
libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp
libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp
libstdc++-v3/include/ext/pb_ds/detail/tree_policy/null_node_update_imp.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp
libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp
libstdc++-v3/include/ext/pb_ds/detail/tree_trace_base.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/null_node_update_imp.hpp [deleted file]
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_e_access_traits.hpp with 67% similarity]
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp
libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp with 88% similarity]
libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp
libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp
libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp
libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp
libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp [moved from libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp with 89% similarity]
libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp
libstdc++-v3/include/ext/pb_ds/hash_policy.hpp
libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp
libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
libstdc++-v3/scripts/make_graph.py
libstdc++-v3/scripts/run_doxygen
libstdc++-v3/testsuite/data/make_graph_test_infos.xml
libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc
libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc
libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc
libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc
libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc
libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc
libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc
libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc
libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand_debug.cc [new file with mode: 0644]
libstdc++-v3/testsuite/performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc
libstdc++-v3/testsuite/performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc
libstdc++-v3/testsuite/performance/ext/pb_ds/tree_order_statistics_timing.cc
libstdc++-v3/testsuite/performance/ext/pb_ds/tree_split_join_timing.cc
libstdc++-v3/testsuite/util/common_type/assoc/common_type.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/ds_string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/list_update_policy_string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/probe_fn_string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/size_policy_string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/tree_supports_order_statistics.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_order_statistics.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_prefix_search.hpp
libstdc++-v3/testsuite/util/common_type/assoc/detail/trigger_policy_string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/native_set.hpp
libstdc++-v3/testsuite/util/common_type/assoc/string_form.hpp
libstdc++-v3/testsuite/util/common_type/assoc/template_policy.hpp
libstdc++-v3/testsuite/util/common_type/priority_queue/common_type.hpp
libstdc++-v3/testsuite/util/native_type/native_hash_map.hpp
libstdc++-v3/testsuite/util/native_type/native_hash_multimap.hpp
libstdc++-v3/testsuite/util/native_type/native_hash_set.hpp
libstdc++-v3/testsuite/util/native_type/native_map.hpp
libstdc++-v3/testsuite/util/native_type/native_multimap.hpp
libstdc++-v3/testsuite/util/native_type/native_priority_queue.hpp
libstdc++-v3/testsuite/util/native_type/native_set.hpp
libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp
libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp
libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp
libstdc++-v3/testsuite/util/regression/common_type.hpp
libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h
libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc
libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp
libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp
libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp
libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
libstdc++-v3/testsuite/util/testsuite_containers.h

index 76afc47..9c1cc03 100644 (file)
@@ -1,3 +1,512 @@
+2011-05-23  Benjamin Kosnik  <bkoz@redhat.com>
+
+       PR libstdc++/37144
+       PR libstdc++/28457
+       Interface changes for ext/pb_ds.
+       PB_DS_BASE_C_DEC to unique PB_DS_*_BASE macros.
+       * include/ext/pb_ds/assoc_container.hpp (container_base): Remove.
+       (basic_hash_table, basic_branch, list_update): Derive from
+       container_base_dispatch.
+       * include/ext/pb_ds/list_update_policy.hpp (null_lu_metadata): Remove.
+       (move_to_front_lu_policy): To lu_move_to_front_policy.
+       (counter_lu_policy): To lu_counter_policy.
+       * include/ext/pb_ds/tree_policy.hpp (null_tree_node_update): Remove.
+       * include/ext/pb_ds/tag_and_trait.hpp (container_base_dispatch): Adjust
+       template parameters, declare here.
+       (null_mapped_type) Remove.
+       (null_type): Just use this for template tricks everywhere.
+       * include/ext/pb_ds/hash_policy.hpp (null_hash_fn, null_probe_fn):
+       Remove.
+       * include/ext/pb_ds/trie_policy.hpp (null_trie_node_update): Remove.
+       (string_trie_e_access_traits): To trie_string_access_traits.
+       * include/ext/pb_ds/priority_queue.hpp: Use container_base_dispatch.
+
+       File changes.
+       * include/Makefile.am (pb_headers): Removed and changed file names.
+       * include/Makefile.in: Regenerated.
+       * include/ext/pb_ds/detail/basic_types.hpp: Remove.
+       * include/ext/pb_ds/detail/bin_search_tree_/
+         cond_dtor_entry_dealtor.hpp: Remove.
+       * include/ext/pb_ds/detail/bin_search_tree_/
+         cond_key_dtor_entry_dealtor.hpp: Remove.
+       * include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp: Move..
+       * include/ext/pb_ds/detail/binary_heap_/
+         point_const_iterator.hpp: ..here.
+       * include/ext/pb_ds/detail/basic_tree_policy: Move to...
+       * include/ext/pb_ds/detail/branch_policy: This.
+       * include/ext/pb_ds/detail/branch_policy/
+         basic_tree_policy_base.hpp: Move...
+       * include/ext/pb_ds/detail/branch_policy/branch_policy.hpp: ...here.
+       * include/ext/pb_ds/detail/branch_policy/null_node_metadata.hpp: Add.
+       * include/ext/pb_ds/detail/branch_policy/traits.hpp: Add.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+       null_metadata.hpp: Remove.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+       const_point_iterator.hpp: Move...
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+       point_const_iterator.hpp: ...here.
+       * include/ext/pb_ds/detail/list_update_policy/
+       counter_lu_metadata.hpp: Move..
+       * include/ext/pb_ds/detail/list_update_policy/
+       lu_counter_metadata.hpp: ...here.
+       * include/ext/pb_ds/detail/list_update_policy/
+       counter_lu_policy_imp.hpp: Remove.
+       * include/ext/pb_ds/detail/list_update_policy/
+       mtf_lu_policy_imp.hpp: Remove.
+       * include/ext/pb_ds/detail/trie_policy/
+       string_trie_e_access_traits_imp.hpp: Move...
+       * include/ext/pb_ds/detail/trie_policy/
+       sample_trie_access_traits.hpp: ...here.
+       * include/ext/pb_ds/detail/trie_policy/
+       sample_trie_e_access_traits.hpp: Move...
+       * include/ext/pb_ds/detail/trie_policy/
+       trie_string_access_traits_imp.hpp: ...here.
+       * include/ext/pb_ds/detail/trie_policy/null_node_update_imp.hpp: Remove.
+       * include/ext/pb_ds/detail/tree_policy/null_node_update_imp.hpp: Remove.
+       * include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp: Remove.
+       * include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: New, fold all
+       types found in the following files into pat_trie_base.
+       * include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/
+         cond_dtor_entry_dealtor.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/head.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/internal_node.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Folded.
+       * include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp: Move...
+       * include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp: ...here.
+       * include/ext/pb_ds/detail/unordered_iterator/
+       const_point_iterator.hpp: Move...
+       * include/ext/pb_ds/detail/unordered_iterator/
+       point_const_iterator.hpp: ...here.
+
+
+       Adjust for above changes.
+       * include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp: Same.
+       * include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp: Same.
+       * include/ext/pb_ds/detail/resize_policy/
+         sample_resize_trigger.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/
+         binomial_heap_base_.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_base_/
+         split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/container_base_dispatch.hpp: Same. Adjust
+         for template parameter ordering change.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         erase_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         constructor_destructor_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         insert_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         resize_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         constructor_destructor_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         insert_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         entry_list_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         find_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         debug_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         constructor_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         cond_key_dtor_entry_dealtor.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         debug_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         erase_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         resize_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/cc_hash_table_map_/
+         standard_policies.hpp: Same.
+       * include/ext/pb_ds/detail/tree_trace_base.hpp: Same.
+       * include/ext/pb_ds/detail/unordered_iterator/iterator.hpp: Same.
+       * include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp: Same.
+       * include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/traits.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/
+         policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/traits.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/
+         split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_policy/
+         sample_update_policy.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         erase_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         constructor_destructor_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         insert_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         resize_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         constructor_destructor_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         insert_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         iterator_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         find_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         find_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         debug_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         constructor_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         debug_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         erase_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         resize_no_store_hash_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/gp_hash_table_map_/
+         standard_policies.hpp: Same.
+       * include/ext/pb_ds/detail/standard_policies.hpp: Same.
+       * include/ext/pb_ds/detail/types_traits.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp: Same.
+       * include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp: Same.
+       * include/ext/pb_ds/detail/tree_policy/
+         sample_tree_node_update.hpp: Same.
+       * include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp: Same.
+       * include/ext/pb_ds/detail/trie_policy/
+         sample_trie_node_update.hpp: Same.
+       * include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp: Same.
+       * include/ext/pb_ds/detail/trie_policy/
+         prefix_search_node_update_imp.hpp: Same.
+       * include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp: Same.
+       * include/ext/pb_ds/detail/cond_dealtor.hpp: Same.
+       * include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp: Same.
+         Adjust for template parameter change, fold into
+         container_base_dispatch.
+       * include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/type_utils.hpp: Same.
+       * include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp: Same.
+       * include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         left_child_next_sibling_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         const_iterator.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         node.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+         iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/traits.hpp: Same.
+       * include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/debug_map_base.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Same.
+       * include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/node.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
+       * include/ext/pb_ds/detail/splay_tree_/traits.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/
+         entry_metadata_base.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/
+         constructor_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/
+         rc_binomial_heap_.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
+       * include/ext/pb_ds/detail/rc_binomial_heap_/
+         split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/
+         constructors_destructor_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp: Same.
+       * include/ext/pb_ds/detail/rb_tree_map_/traits.hpp: Same.
+
+
+       Documentation changes.
+       * include/ext/pb_ds/*: Add doxygen markup.
+       * doc/doxygen/user.cfg.in: Add details for extracting comments
+       from pb_ds.
+       * scripts/run_doxygen: Fixup __gnu_pb_ds::detail.
+       * scripts/make_graph.py: Move to svg output. Re-format generated tables.
+
+       * doc/Makefile.am (stamp-html-copy): New rule.
+       (stamp-html): Use it to copy non-generated files into html docs.
+       * doc/Makefile.in: Regenerated.
+
+       * doc/html/ext/pb_ds/sample_trie_e_access_traits.html: Move...
+       * doc/html/ext/pb_ds/trie_string_access_traits.html: ...here.
+       * doc/html/ext/pb_ds/string_trie_e_access_traits.html: Move..
+       * doc/html/ext/pb_ds/sample_trie_access_traits.html: ...here.
+
+       * doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png,
+       hash_random_int_erase_mem_usage_test_local.png,
+       multimap_text_insert_mem_usage_test_small_s2p_hash_local.png,
+       tree_text_insert_timing_test_pat_trie_local.png ,
+       multimap_text_insert_mem_usage_test_small_s2p_tree_local.png ,
+       priority_queue_text_modify_down_timing_test_local.png,
+       gp_hash_random_int_subscript_timing_test_find_local.png,
+       text_find_timing_test_hash_local.png,
+       multimap_text_insert_timing_test_small_s2p_hash_local.png,
+       multimap_text_insert_timing_test_small_s2p_tree_local.png,
+       multimap_text_insert_mem_usage_test_large_s2p_hash_local.png,
+       multimap_text_insert_mem_usage_test_large_s2p_tree_local.png,
+       multimap_text_insert_timing_test_large_s2p_hash_local.png,
+       hash_zlob_random_int_find_timing_test_local.png,
+       multimap_text_insert_timing_test_large_s2p_tree_local.png,
+       binary_priority_queue_random_int_push_timing_test_local.png,
+       priority_queue_text_pop_mem_usage_test_local.png,
+       priority_queue_text_modify_down_timing_test_pairing_thin_local.png,
+       tree_split_join_timing_test_local.png,
+       multimap_text_find_timing_test_small_s2p_hash_local.png,
+       ccgp_hash_random_int_subscript_timing_test_insert_local.png,
+       priority_queue_random_int_push_pop_timing_test_local.png,
+       multimap_text_find_timing_test_small_s2p_tree_local.png,
+       gp_hash_random_int_subscript_timing_test_insert_local.png,
+       priority_queue_text_push_timing_test_local.png,
+       cc_hash_random_int_subscript_timing_test_find_local.png,
+       tree_text_insert_timing_test_vector_tree_local.png,
+       multimap_text_find_timing_test_large_s2p_hash_local.png,
+       pairing_priority_queue_text_push_timing_test_local.png,
+       tree_order_statistics_timing_test_local.png,
+       priority_queue_text_push_pop_timing_test_local.png,
+       text_find_timing_test_tree_like_local.png,
+       multimap_text_find_timing_test_large_s2p_tree_local.png,
+       priority_queue_text_modify_up_timing_test_pairing_thin_local.png,
+       cc_hash_random_int_subscript_timing_test_insert_local.png,
+       priority_queue_text_modify_up_timing_test_local.png,
+       random_int_find_find_timing_test_tree_local.png,
+       priority_queue_random_int_push_timing_test_local.png,
+       tree_text_insert_timing_test_node_tree_local.png,
+       pairing_priority_queue_text_push_pop_timing_test_local.png,
+       gp_hash_random_int_find_timing_test_local.png,
+       cc_hash_random_int_find_timing_test_local.png,
+       priority_queue_text_join_timing_test_local.png: Update local pngs.
+
+
+       Testsuite changes.
+       * testsuite/ext/pb_ds/regression/tree_no_data_map_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/tree_data_map_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/priority_queue_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/trie_no_data_map_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/trie_data_map_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/list_update_no_data_map_rand_debug.cc:
+       New.
+       * testsuite/ext/pb_ds/regression/list_update_data_map_rand_debug.cc:
+       New.
+       * testsuite/ext/pb_ds/regression/hash_no_data_map_rand_debug.cc: New.
+       * testsuite/ext/pb_ds/regression/hash_data_map_rand_debug.cc: New.
+
+       * testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc: Fix typo.
+
+       * testsuite/ext/pb_ds/example/basic_set.cc: Update.
+       * testsuite/ext/pb_ds/example/ranged_hash.cc: Same.
+       * testsuite/ext/pb_ds/example/tree_order_statistics.cc: Same.
+       * testsuite/ext/pb_ds/example/trie_prefix_search.cc: Same.
+       * testsuite/ext/pb_ds/example/trie_dna.cc: Same.
+       * testsuite/ext/pb_ds/example/tree_intervals.cc: Same.
+       * testsuite/ext/pb_ds/example/basic_multimap.cc: Same.
+       * testsuite/performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc:
+         Same.
+       * testsuite/performance/ext/pb_ds/tree_split_join_timing.cc: Same.
+       * testsuite/performance/ext/pb_ds/tree_order_statistics_timing.cc: Same.
+       * testsuite/data/make_graph_test_infos.xml: Same.
+       * testsuite/util/regression/common_type.hpp: Same.
+       * testsuite/util/regression/trait/assoc/native_type_trait.hpp: Same.
+       * testsuite/util/regression/trait/assoc/trait.hpp: Same.
+       * testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
+       * testsuite/util/regression/rand/priority_queue/
+         rand_regression_test.hpp: Same.
+       * testsuite/util/regression/rand/priority_queue/
+         container_rand_regression_test.tcc: Same.
+       * testsuite/util/regression/rand/assoc/rand_regression_test.hpp: Same.
+       * testsuite/util/regression/rand/assoc/container_rand_regression_test.h
+       * testsuite/util/regression/rand/assoc/
+         container_rand_regression_test.tcc: Same.
+       * testsuite/util/native_type/native_priority_queue.hpp: Same.
+       * testsuite/util/native_type/native_multimap.hpp: Same.
+       * testsuite/util/native_type/native_hash_multimap.hpp: Same.
+       * testsuite/util/native_type/native_set.hpp: Same.
+       * testsuite/util/native_type/native_map.hpp: Same.
+       * testsuite/util/native_type/native_hash_set.hpp: Same.
+       * testsuite/util/native_type/native_hash_map.hpp: Same.
+       * testsuite/util/testsuite_containers.h
+       * testsuite/util/common_type/priority_queue/common_type.hpp: Same.
+       * testsuite/util/common_type/assoc/common_type.hpp: Same.
+       * testsuite/util/common_type/assoc/string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/template_policy.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         trigger_policy_string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/ds_string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         size_policy_string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         probe_fn_string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         tree_supports_order_statistics.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         trie_supports_prefix_search.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         list_update_policy_string_form.hpp: Same.
+       * testsuite/util/common_type/assoc/detail/
+         trie_supports_order_statistics.hpp: Same.
+       * testsuite/util/common_type/assoc/native_set.hpp: Same.
+       * testsuite/util/performance/assoc/timing/common_type.hpp: Same.
+       * testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.
+       * testsuite/util/performance/assoc/multimap_common_type.hpp: Same.
+
 2011-05-23  Paolo Carlini  <paolo.carlini@oracle.com>
 
        * include/bits/streambuf_iterator.h: Use noexcept per the FDIS.
index b564f1c..7e75cc7 100644 (file)
@@ -136,9 +136,17 @@ doc-install-xml: doc-xml
 
 # HTML
 htmldir="$(DESTDIR)@docdir@"
-stamp-html: stamp-html-docbook stamp-html-doxygen
+stamp-html: stamp-html-copy stamp-html-doxygen
        $(STAMP) stamp-html
 
+copydir=${docbook_outdir}/html/manual/ext/
+stamp-html-copy: stamp-html-docbook
+       cp -r ${top_srcdir}/doc/html/ext ${docbook_outdir}/html/manual/ext
+       cd ${docbook_outdir}/html/manual/ext
+       rm -rf ${docbook_outdir}/html/manual/ext/.svn 
+       rm -rf ${docbook_outdir}/html/manual/ext/pb_ds/.svn
+       $(STAMP) stamp-html-copy
+
 doc-html: stamp-html
 
 doc-install-html: doc-html
index e177733..8247b60 100644 (file)
@@ -324,6 +324,7 @@ AM_CPPFLAGS = $(GLIBCXX_INCLUDES)
 
 # XML
 xmldir = "$(DESTDIR)@docdir@"
+copydir = ${docbook_outdir}/html/manual/ext/
 
 # EPUB
 # Assumes ruby installed
@@ -649,8 +650,14 @@ doc-install-xml: doc-xml
        test -z ${xmldir} || $(mkinstalldirs) ${xmldir}
        $(INSTALL_DATA) ${manual_xml} ${xmldir}
        $(INSTALL_DATA) ${api_xml} ${xmldir}
-stamp-html: stamp-html-docbook stamp-html-doxygen
+stamp-html: stamp-html-copy stamp-html-doxygen
        $(STAMP) stamp-html
+stamp-html-copy: stamp-html-docbook
+       cp -r ${top_srcdir}/doc/html/ext ${docbook_outdir}/html/manual/ext
+       cd ${docbook_outdir}/html/manual/ext
+       rm -rf ${docbook_outdir}/html/manual/ext/.svn 
+       rm -rf ${docbook_outdir}/html/manual/ext/pb_ds/.svn
+       $(STAMP) stamp-html-copy
 
 doc-html: stamp-html
 
index 920a4cd..6332dc1 100644 (file)
@@ -1,4 +1,4 @@
-# Doxyfile 1.7.2
+# Doxyfile 1.7.4
 
 # This file describes the settings to be used by the documentation system
 # doxygen (www.doxygen.org) for a project.
@@ -33,6 +33,19 @@ PROJECT_NAME           = libstdc++
 
 PROJECT_NUMBER         =
 
+# Using the PROJECT_BRIEF tag one can provide an optional one line description
+# for a project that appears at the top of each page and should give viewer
+# a quick idea about the purpose of the project. Keep the description short.
+
+PROJECT_BRIEF          =
+
+# With the PROJECT_LOGO tag one can specify an logo or icon that is
+# included in the documentation. The maximum height of the logo should not
+# exceed 55 pixels and the maximum width should not exceed 200 pixels.
+# Doxygen will copy the logo to the output directory.
+
+PROJECT_LOGO           =
+
 # The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute)
 # base path where the generated documentation will be put.
 # If a relative path is entered, it will be relative to the location
@@ -57,7 +70,7 @@ CREATE_SUBDIRS         = NO
 # Croatian, Czech, Danish, Dutch, Esperanto, Farsi, Finnish, French, German,
 # Greek, Hungarian, Italian, Japanese, Japanese-en (Japanese with English
 # messages), Korean, Korean-en, Lithuanian, Norwegian, Macedonian, Persian,
-# Polish, Portuguese, Romanian, Russian, Serbian, Serbian-Cyrilic, Slovak,
+# Polish, Portuguese, Romanian, Russian, Serbian, Serbian-Cyrillic, Slovak,
 # Slovene, Spanish, Swedish, Ukrainian, and Vietnamese.
 
 OUTPUT_LANGUAGE        = English
@@ -179,10 +192,9 @@ TAB_SIZE               = 4
 # will result in a user-defined paragraph with heading "Side Effects:".
 # You can put \n's in the value part of an alias to insert newlines.
 
-ALIASES = doctodo="@todo\nNeeds documentation! See http://gcc.gnu.org/onlinedocs/libstdc++/manual/documentation_style.html"
-
-ALIASES += headername{1}="Instead, include <\1>."
-ALIASES += headername{2}="Instead, include <\1> or <\2>."
+ALIASES                = "doctodo=@todo\nNeeds documentation! See http://gcc.gnu.org/onlinedocs/libstdc++/manual/documentation_style.html" \
+                        "headername{1}=Instead, include <\1>." \
+                        "headername{2}=Instead, include <\1> or <\2>."
 
 # Set the OPTIMIZE_OUTPUT_FOR_C tag to YES if your project consists of C
 # sources only. Doxygen will then generate output that is more tailored for C.
@@ -266,6 +278,13 @@ DISTRIBUTE_GROUP_DOC   = YES
 
 SUBGROUPING            = YES
 
+# When the INLINE_GROUPED_CLASSES tag is set to YES, classes, structs and
+# unions are shown inside the group in which they are included (e.g. using
+# @ingroup) instead of on a separate page (for HTML and Man pages) or
+# section (for LaTeX and RTF).
+
+INLINE_GROUPED_CLASSES = NO
+
 # When TYPEDEF_HIDES_STRUCT is enabled, a typedef of a struct, union, or enum
 # is documented as struct, union, or enum with the name of the typedef. So
 # typedef struct TypeS {} TypeT, will appear in the documentation as a struct
@@ -282,7 +301,7 @@ TYPEDEF_HIDES_STRUCT   = NO
 # For small to medium size projects (<1000 input files) the default value is
 # probably good enough. For larger projects a too small cache size can cause
 # doxygen to be busy swapping symbols to and from disk most of the time
-# causing a significant performance penality.
+# causing a significant performance penalty.
 # If the system has enough physical memory increasing the cache will improve the
 # performance by keeping more symbols in memory. Note that the value works on
 # a logarithmic scale so increasing the size by one will roughly double the
@@ -441,6 +460,15 @@ SORT_GROUP_NAMES       = YES
 
 SORT_BY_SCOPE_NAME     = YES
 
+# If the STRICT_PROTO_MATCHING option is enabled and doxygen fails to
+# do proper type resolution of all parameters of a function it will reject a
+# match between the prototype and the implementation of a member function even
+# if there is only one candidate or it is obvious which candidate to choose
+# by doing a simple string match. By disabling STRICT_PROTO_MATCHING doxygen
+# will still accept a match between prototype and implementation in such cases.
+
+STRICT_PROTO_MATCHING  = NO
+
 # The GENERATE_TODOLIST tag can be used to enable (YES) or
 # disable (NO) the todo list. This list is created by putting \todo
 # commands in the documentation.
@@ -585,142 +613,165 @@ WARN_LOGFILE           =
 # with spaces.
 
 INPUT                  = @srcdir@/doc/doxygen/doxygroups.cc \
-                         @srcdir@/libsupc++/cxxabi.h \
-                         @srcdir@/libsupc++/exception \
-                         @srcdir@/libsupc++/initializer_list \
-                         @srcdir@/libsupc++/new \
-                         @srcdir@/libsupc++/typeinfo \
-                         include/algorithm \
-                         include/array \
-                         include/atomic \
-                         include/bitset \
-                         include/chrono \
-                         include/complex \
-                         include/condition_variable \
-                         include/deque \
-                         include/forward_list \
-                         include/fstream \
-                         include/functional \
-                         include/future \
-                         include/iomanip \
-                         include/ios \
-                         include/iosfwd \
-                         include/iostream \
-                         include/istream \
-                         include/iterator \
-                         include/limits \
-                         include/list \
-                         include/locale \
-                         include/map \
-                         include/memory \
-                         include/mutex \
-                         include/numeric \
-                         include/ostream \
-                         include/queue \
-                         include/random \
-                         include/ratio \
-                         include/regex \
-                         include/set \
-                         include/sstream \
-                         include/stack \
-                         include/stdexcept \
-                         include/streambuf \
-                         include/string \
-                         include/system_error \
-                         include/thread \
-                         include/tuple \
-                         include/typeindex \
-                         include/type_traits \
-                         include/unordered_map \
-                         include/unordered_set \
-                         include/utility \
-                         include/valarray \
-                         include/vector \
-                         include/cassert \
-                         include/ccomplex \
-                         include/cctype \
-                         include/cerrno \
-                         include/cfenv \
-                         include/cfloat \
-                         include/cinttypes \
-                         include/ciso646 \
-                         include/climits \
-                         include/clocale \
-                         include/cmath \
-                         include/csetjmp \
-                         include/csignal \
-                         include/cstdarg \
-                         include/cstdbool \
-                         include/cstddef \
-                         include/cstdint \
-                         include/cstdio \
-                         include/cstdlib \
-                         include/cstring \
-                         include/ctgmath \
-                         include/ctime \
-                         include/cwchar \
-                         include/cwctype \
-                         include/backward/hash_map \
-                         include/backward/hash_set \
-                         include/backward/strstream \
-                         include/debug/bitset \
-                         include/debug/deque \
-                         include/debug/forward_list \
-                         include/debug/list \
-                         include/debug/map \
-                         include/debug/set \
-                         include/debug/string \
-                         include/debug/unordered_map \
-                         include/debug/unordered_set \
-                         include/debug/vector \
-                         include/profile/bitset \
-                         include/profile/deque \
-                         include/profile/forward_list \
-                         include/profile/list \
-                         include/profile/map \
-                         include/profile/set \
-                         include/profile/unordered_map \
-                         include/profile/unordered_set \
-                         include/profile/vector \
-                         include/ext/algorithm \
-                         include/ext/functional \
-                         include/ext/iterator \
-                         include/ext/memory \
-                         include/ext/numeric \
-                         include/ext/rb_tree \
-                         include/ext/rope \
-                         include/ext/slist \
-                         include/parallel/algorithm \
-                         include/parallel/numeric \
-                         include/tr1/ccomplex \
-                         include/tr1/cctype \
-                         include/tr1/cfenv \
-                         include/tr1/cfloat \
-                         include/tr1/cinttypes \
-                         include/tr1/climits \
-                         include/tr1/cmath \
-                         include/tr1/complex \
-                         include/tr1/cstdarg \
-                         include/tr1/cstdbool \
-                         include/tr1/cstdint \
-                         include/tr1/cstdio \
-                         include/tr1/cstdlib \
-                         include/tr1/ctgmath \
-                         include/tr1/ctime \
-                         include/tr1/cwchar \
-                         include/tr1/cwctype \
-                         include/decimal/decimal \
-                         include/ \
-                         include/@host_alias@/bits \
-                         include/backward \
-                         include/bits \
-                         include/debug \
-                         include/parallel \
-                         include/profile \
-                         include/profile/impl \
-                         include/ext \
-                         include/ext/pb_ds \
-                         include/ext/pb_ds/detail
+                        @srcdir@/libsupc++/cxxabi.h \
+                        @srcdir@/libsupc++/exception \
+                        @srcdir@/libsupc++/initializer_list \
+                        @srcdir@/libsupc++/new \
+                        @srcdir@/libsupc++/typeinfo \
+                        include/algorithm \
+                        include/array \
+                        include/atomic \
+                        include/bitset \
+                        include/chrono \
+                        include/complex \
+                        include/condition_variable \
+                        include/deque \
+                        include/forward_list \
+                        include/fstream \
+                        include/functional \
+                        include/future \
+                        include/iomanip \
+                        include/ios \
+                        include/iosfwd \
+                        include/iostream \
+                        include/istream \
+                        include/iterator \
+                        include/limits \
+                        include/list \
+                        include/locale \
+                        include/map \
+                        include/memory \
+                        include/mutex \
+                        include/numeric \
+                        include/ostream \
+                        include/queue \
+                        include/random \
+                        include/ratio \
+                        include/regex \
+                        include/set \
+                        include/sstream \
+                        include/stack \
+                        include/stdexcept \
+                        include/streambuf \
+                        include/string \
+                        include/system_error \
+                        include/thread \
+                        include/tuple \
+                        include/typeindex \
+                        include/type_traits \
+                        include/unordered_map \
+                        include/unordered_set \
+                        include/utility \
+                        include/valarray \
+                        include/vector \
+                        include/cassert \
+                        include/ccomplex \
+                        include/cctype \
+                        include/cerrno \
+                        include/cfenv \
+                        include/cfloat \
+                        include/cinttypes \
+                        include/ciso646 \
+                        include/climits \
+                        include/clocale \
+                        include/cmath \
+                        include/csetjmp \
+                        include/csignal \
+                        include/cstdarg \
+                        include/cstdbool \
+                        include/cstddef \
+                        include/cstdint \
+                        include/cstdio \
+                        include/cstdlib \
+                        include/cstring \
+                        include/ctgmath \
+                        include/ctime \
+                        include/cwchar \
+                        include/cwctype \
+                        include/ \
+                        include/bits \
+                        include/@host_alias@/bits \
+                        include/backward \
+                        include/backward/hash_map \
+                        include/backward/hash_set \
+                        include/backward/strstream \
+                        include/debug \
+                        include/debug/bitset \
+                        include/debug/deque \
+                        include/debug/forward_list \
+                        include/debug/list \
+                        include/debug/map \
+                        include/debug/set \
+                        include/debug/string \
+                        include/debug/unordered_map \
+                        include/debug/unordered_set \
+                        include/debug/vector \
+                        include/profile \
+                        include/profile/impl \
+                        include/profile/bitset \
+                        include/profile/deque \
+                        include/profile/forward_list \
+                        include/profile/list \
+                        include/profile/map \
+                        include/profile/set \
+                        include/profile/unordered_map \
+                        include/profile/unordered_set \
+                        include/profile/vector \
+                        include/ext/algorithm \
+                        include/ext/functional \
+                        include/ext/iterator \
+                        include/ext/memory \
+                        include/ext/numeric \
+                        include/ext/rb_tree \
+                        include/ext/rope \
+                        include/ext/slist \
+                        include/parallel \
+                        include/parallel/algorithm \
+                        include/parallel/numeric \
+                        include/tr1/ccomplex \
+                        include/tr1/cctype \
+                        include/tr1/cfenv \
+                        include/tr1/cfloat \
+                        include/tr1/cinttypes \
+                        include/tr1/climits \
+                        include/tr1/cmath \
+                        include/tr1/complex \
+                        include/tr1/cstdarg \
+                        include/tr1/cstdbool \
+                        include/tr1/cstdint \
+                        include/tr1/cstdio \
+                        include/tr1/cstdlib \
+                        include/tr1/ctgmath \
+                        include/tr1/ctime \
+                        include/tr1/cwchar \
+                        include/tr1/cwctype \
+                        include/decimal/decimal \
+                        include/ext \
+                        include/ext/pb_ds \
+                        include/ext/pb_ds/detail \
+                        include/ext/pb_ds/detail/binary_heap_ \
+                        include/ext/pb_ds/detail/binomial_heap_ \
+                        include/ext/pb_ds/detail/binomial_heap_base_ \
+                        include/ext/pb_ds/detail/bin_search_tree_ \
+                        include/ext/pb_ds/detail/branch_policy \
+                        include/ext/pb_ds/detail/cc_hash_table_map_ \
+                        include/ext/pb_ds/detail/eq_fn \
+                        include/ext/pb_ds/detail/gp_hash_table_map_ \
+                        include/ext/pb_ds/detail/hash_fn \
+                        include/ext/pb_ds/detail/left_child_next_sibling_heap_ \
+                        include/ext/pb_ds/detail/list_update_map_ \
+                        include/ext/pb_ds/detail/list_update_policy \
+                        include/ext/pb_ds/detail/ov_tree_map_ \
+                        include/ext/pb_ds/detail/pairing_heap_ \
+                        include/ext/pb_ds/detail/pat_trie_ \
+                        include/ext/pb_ds/detail/rb_tree_map_ \
+                        include/ext/pb_ds/detail/rc_binomial_heap_ \
+                        include/ext/pb_ds/detail/resize_policy \
+                        include/ext/pb_ds/detail/splay_tree_ \
+                        include/ext/pb_ds/detail/thin_heap_ \
+                        include/ext/pb_ds/detail/tree_policy \
+                        include/ext/pb_ds/detail/trie_policy \
+                        include/ext/pb_ds/detail/unordered_iterator
 
 # This tag can be used to specify the character encoding of the source files
 # that doxygen parses. Internally doxygen uses the UTF-8 encoding, which is
@@ -736,11 +787,11 @@ INPUT_ENCODING         = UTF-8
 # blank the following patterns are tested:
 # *.c *.cc *.cxx *.cpp *.c++ *.d *.java *.ii *.ixx *.ipp *.i++ *.inl *.h *.hh
 # *.hxx *.hpp *.h++ *.idl *.odl *.cs *.php *.php3 *.inc *.m *.mm *.dox *.py
-# *.f90 *.f *.vhd *.vhdl
+# *.f90 *.f *.for *.vhd *.vhdl
 
 FILE_PATTERNS          = *.h \
-                         *.hpp \
-                         *.tcc
+                        *.hpp \
+                        *.tcc
 
 # The RECURSIVE tag can be used to turn specify whether or not subdirectories
 # should be searched for input files as well. Possible values are YES and NO.
@@ -755,7 +806,7 @@ RECURSIVE              = NO
 EXCLUDE                = Makefile
 
 # The EXCLUDE_SYMLINKS tag can be used select whether or not files or
-# directories that are symbolic links (a Unix filesystem feature) are excluded
+# directories that are symbolic links (a Unix file system feature) are excluded
 # from the input.
 
 EXCLUDE_SYMLINKS       = NO
@@ -766,9 +817,10 @@ EXCLUDE_SYMLINKS       = NO
 # against the file with absolute path, so to exclude all test directories
 # for example use the pattern */test/*
 
-EXCLUDE_PATTERNS       = stamp-* doxygroups.cc \
-                         *.gch \
-                         */.svn/*
+EXCLUDE_PATTERNS       = stamp-* \
+                        doxygroups.cc \
+                        *.gch \
+                        */.svn/*
 
 # The EXCLUDE_SYMBOLS tag can be used to specify one or more symbol names
 # (namespaces, classes, functions, etc.) that should be excluded from the
@@ -821,8 +873,8 @@ INPUT_FILTER           =
 # filter if there is a match.
 # The filters are a list of the form:
 # pattern=filter (like *.cpp=my_cpp_filter). See INPUT_FILTER for further
-# info on how filters are used. If FILTER_PATTERNS is empty, INPUT_FILTER
-# is applied to all files.
+# info on how filters are used. If FILTER_PATTERNS is empty or if
+# non of the patterns match the file name, INPUT_FILTER is applied.
 
 FILTER_PATTERNS        =
 
@@ -832,6 +884,14 @@ FILTER_PATTERNS        =
 
 FILTER_SOURCE_FILES    = NO
 
+# The FILTER_SOURCE_PATTERNS tag can be used to specify source filters per file
+# pattern. A pattern will override the setting for FILTER_PATTERN (if any)
+# and it is also possible to disable source filtering for a specific pattern
+# using *.ext= (so without naming a filter). This option only has effect when
+# FILTER_SOURCE_FILES is enabled.
+
+FILTER_SOURCE_PATTERNS =
+
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
@@ -934,7 +994,13 @@ HTML_FILE_EXTENSION    = .html
 
 # The HTML_HEADER tag can be used to specify a personal HTML header for
 # each generated HTML page. If it is left blank doxygen will generate a
-# standard header.
+# standard header. Note that when using a custom header you are responsible
+# for the proper inclusion of any scripts and style sheets that doxygen
+# needs, which is dependent on the configuration options used.
+# It is adviced to generate a default header using "doxygen -w html
+# header.html footer.html stylesheet.css YourConfigFile" and then modify
+# that header. Note that the header is subject to change so you typically
+# have to redo this when upgrading to a newer version of doxygen or when changing the value of configuration settings such as GENERATE_TREEVIEW!
 
 HTML_HEADER            =
 
@@ -953,6 +1019,15 @@ HTML_FOOTER            =
 
 HTML_STYLESHEET        =
 
+# The HTML_EXTRA_FILES tag can be used to specify one or more extra images or
+# other source files which should be copied to the HTML output directory. Note
+# that these files will be copied to the base HTML output directory. Use the
+# $relpath$ marker in the HTML_HEADER and/or HTML_FOOTER files to load these
+# files. In the HTML_STYLESHEET file, use the file name only. Also note that
+# the files will be copied as-is; there are no commands or markers available.
+
+HTML_EXTRA_FILES       =
+
 # The HTML_COLORSTYLE_HUE tag controls the color of the HTML output.
 # Doxygen will adjust the colors in the stylesheet and background images
 # according to this color. Hue is specified as an angle on a colorwheel,
@@ -1155,9 +1230,10 @@ ECLIPSE_DOC_ID         = org.doxygen.Project
 
 DISABLE_INDEX          = YES
 
-# This tag can be used to set the number of enum values (range [0,1..20])
-# that doxygen will group on one line in the generated HTML documentation.
-# Note that a value of 0 will completely suppress the enum values from appearing in the overview section.
+# The ENUM_VALUES_PER_LINE tag can be used to set the number of enum values
+# (range [0,1..20]) that doxygen will group on one line in the generated HTML
+# documentation. Note that a value of 0 will completely suppress the enum
+# values from appearing in the overview section.
 
 ENUM_VALUES_PER_LINE   = 4
 
@@ -1216,7 +1292,8 @@ USE_MATHJAX            = NO
 # HTML output directory using the MATHJAX_RELPATH option. The destination
 # directory should contain the MathJax.js script. For instance, if the mathjax
 # directory is located at the same level as the HTML output directory, then
-# MATHJAX_RELPATH should be ../mathjax. The default value points to the mathjax.org site, so you can quickly see the result without installing
+# MATHJAX_RELPATH should be ../mathjax. The default value points to the
+# mathjax.org site, so you can quickly see the result without installing
 # MathJax, but it is strongly recommended to install a local copy of MathJax
 # before deployment.
 
@@ -1295,6 +1372,13 @@ EXTRA_PACKAGES         = amsmath
 
 LATEX_HEADER           =
 
+# The LATEX_FOOTER tag can be used to specify a personal LaTeX footer for
+# the generated latex document. The footer should contain everything after
+# the last chapter. If it is left blank doxygen will generate a
+# standard footer. Notice: only use this tag if you know what you are doing!
+
+LATEX_FOOTER           =
+
 # If the PDF_HYPERLINKS tag is set to YES, the LaTeX that is generated
 # is prepared for conversion to pdf (using ps2pdf). The pdf file will
 # contain links (just like the HTML output) instead of page references
@@ -1504,7 +1588,7 @@ MACRO_EXPANSION        = YES
 EXPAND_ONLY_PREDEF     = NO
 
 # If the SEARCH_INCLUDES tag is set to YES (the default) the includes files
-# in the INCLUDE_PATH (see below) will be search if a #include is found.
+# pointed to by INCLUDE_PATH will be searched when a #include is found.
 
 SEARCH_INCLUDES        = YES
 
@@ -1512,7 +1596,7 @@ SEARCH_INCLUDES        = YES
 # contain include files that are not input files but should be processed by
 # the preprocessor.
 
-INCLUDE_PATH           =
+INCLUDE_PATH           = include
 
 # You can use the INCLUDE_FILE_PATTERNS tag to specify one or more wildcard
 # patterns (like *.h and *.hpp) to filter out the header-files in the
@@ -1530,57 +1614,59 @@ INCLUDE_FILE_PATTERNS  =
 # instead of the = operator.
 
 PREDEFINED             = __cplusplus \
-                         __GTHREADS \
-                         _GLIBCXX_HAS_GTHREADS \
-                         __GXX_EXPERIMENTAL_CXX0X__ \
-                         _GLIBCXX_INCLUDE_AS_CXX0X \
-                         "_GLIBCXX_PURE= " \
-                         "_GLIBCXX_CONST= " \
-                         "_GLIBCXX_NORETURN= " \
-                         "_GLIBCXX_NOTHROW= " \
-                         "_GLIBCXX_STD_C= " \
-                         "_GLIBCXX_STD_A= " \
+                        __GTHREADS \
+                        _GLIBCXX_HAS_GTHREADS \
+                        __GXX_EXPERIMENTAL_CXX0X__ \
+                        _GLIBCXX_INCLUDE_AS_CXX0X \
+                        "_GLIBCXX_PURE= " \
+                        "_GLIBCXX_CONST= " \
+                        "_GLIBCXX_NORETURN= " \
+                        "_GLIBCXX_NOTHROW= " \
+                        "_GLIBCXX_STD_C= " \
+                        "_GLIBCXX_STD_A= " \
                         "_GLIBCXX_VISIBILITY(V)= " \
-                         "_GLIBCXX_BEGIN_NAMESPACE_VERSION= " \
-                         "_GLIBCXX_BEGIN_NAMESPACE_ALGO= " \
-                         "_GLIBCXX_BEGIN_NAMESPACE_CONTAINER= " \
-                         "_GLIBCXX_BEGIN_NAMESPACE_LDBL= " \
-                         "_GLIBCXX_END_NAMESPACE_VERSION= " \
-                         "_GLIBCXX_END_NAMESPACE_ALGO= " \
-                         "_GLIBCXX_END_NAMESPACE_CONTAINER= " \
-                         "_GLIBCXX_END_NAMESPACE_LDBL= " \
-                         "_GLIBCXX_TEMPLATE_ARGS=...  " \
-                         _GLIBCXX_DEPRECATED \
-                         _GLIBCXX_CONSTEXPR=constexpr \
-                         _GLIBCXX_USE_CONSTEXPR=constexpr \
-                         _GLIBCXX_USE_WCHAR_T \
-                         _GLIBCXX_USE_LONG_LONG \
-                         _GLIBCXX_USE_C99_STDINT_TR1 \
-                         _GLIBCXX_ATOMIC_BUILTINS_1 \
-                         _GLIBCXX_ATOMIC_BUILTINS_2 \
-                         _GLIBCXX_ATOMIC_BUILTINS_4 \
-                         _GLIBCXX_ATOMIC_BUILTINS_8 \
-                         _GLIBCXX_USE_SCHED_YIELD \
-                         _GLIBCXX_USE_NANOSLEEP \
-                         __GXX_RTTI \
-                         __glibcxx_function_requires=// \
-                         __glibcxx_class_requires=// \
-                         __glibcxx_class_requires2=// \
-                         __glibcxx_class_requires3=// \
-                         __glibcxx_class_requires4=//
+                        "_GLIBCXX_BEGIN_NAMESPACE_VERSION= " \
+                        "_GLIBCXX_BEGIN_NAMESPACE_ALGO= " \
+                        "_GLIBCXX_BEGIN_NAMESPACE_CONTAINER= " \
+                        "_GLIBCXX_BEGIN_NAMESPACE_LDBL= " \
+                        "_GLIBCXX_END_NAMESPACE_VERSION= " \
+                        "_GLIBCXX_END_NAMESPACE_ALGO= " \
+                        "_GLIBCXX_END_NAMESPACE_CONTAINER= " \
+                        "_GLIBCXX_END_NAMESPACE_LDBL= " \
+                        "_GLIBCXX_TEMPLATE_ARGS=...  " \
+                        _GLIBCXX_DEPRECATED \
+                        _GLIBCXX_CONSTEXPR=constexpr \
+                        _GLIBCXX_USE_CONSTEXPR=constexpr \
+                        _GLIBCXX_USE_WCHAR_T \
+                        _GLIBCXX_USE_LONG_LONG \
+                        _GLIBCXX_USE_C99_STDINT_TR1 \
+                        _GLIBCXX_ATOMIC_BUILTINS_1 \
+                        _GLIBCXX_ATOMIC_BUILTINS_2 \
+                        _GLIBCXX_ATOMIC_BUILTINS_4 \
+                        _GLIBCXX_ATOMIC_BUILTINS_8 \
+                        _GLIBCXX_USE_SCHED_YIELD \
+                        _GLIBCXX_USE_NANOSLEEP \
+                        PB_DS_DATA_TRUE_INDICATOR \
+                        __EXCEPTIONS \
+                        __GXX_RTTI \
+                        __glibcxx_function_requires=// \
+                        __glibcxx_class_requires=// \
+                        __glibcxx_class_requires2=// \
+                        __glibcxx_class_requires3=// \
+                        __glibcxx_class_requires4=//
 
 # If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then
 # this tag can be used to specify a list of macro names that should be expanded.
 # The macro definition that is found in the sources will be used.
-# Use the PREDEFINED tag if you want to use a different macro definition.
+# Use the PREDEFINED tag if you want to use a different macro definition that
+# overrules the definition found in the source code.
 
 EXPAND_AS_DEFINED      =
 
 # If the SKIP_FUNCTION_MACROS tag is set to YES (the default) then
-# doxygen's preprocessor will remove all function-like macros that are alone
-# on a line, have an all uppercase name, and do not end with a semicolon. Such
-# function macros are typically used for boiler-plate code, and will confuse
-# the parser if not removed.
+# doxygen's preprocessor will remove all references to function-like macros
+# that are alone on a line, have an all uppercase name, and do not end with a
+# semicolon, because these will confuse the parser if not removed.
 
 SKIP_FUNCTION_MACROS   = YES
 
@@ -1671,11 +1757,10 @@ HAVE_DOT               = YES
 
 DOT_NUM_THREADS        = 0
 
-# By default doxygen will write a font called FreeSans.ttf to the output
-# directory and reference it in all dot files that doxygen generates. This
-# font does not include all possible unicode characters however, so when you need
-# these (or just want a differently looking font) you can specify the font name
-# using DOT_FONTNAME. You need need to make sure dot is able to find the font,
+# By default doxygen will write a font called Helvetica to the output
+# directory and reference it in all dot files that doxygen generates.
+# When you want a differently looking font you can specify the font name
+# using DOT_FONTNAME. You need to make sure dot is able to find the font,
 # which can be done by putting it in a standard location or by setting the
 # DOTFONTPATH environment variable or by setting DOT_FONTPATH to the directory
 # containing the font.
@@ -1767,7 +1852,7 @@ GRAPHICAL_HIERARCHY    = YES
 DIRECTORY_GRAPH        = YES
 
 # The DOT_IMAGE_FORMAT tag can be used to set the image format of the images
-# generated by dot. Possible values are png, jpg, or gif.
+# generated by dot. Possible values are svg, png, jpg, or gif.
 # If left blank png will be used.
 
 DOT_IMAGE_FORMAT       = png
index 76e02f1..c69cf1e 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/binary_priority_queue_random_int_push_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/binary_priority_queue_random_int_push_timing_test_local.png differ
index 4f578c6..40404c8 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_find_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_find_timing_test_local.png differ
index ca4db96..bb5f30b 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_find_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_find_local.png differ
index 48fcf76..8dc7735 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_insert_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/cc_hash_random_int_subscript_timing_test_insert_local.png differ
index 2449e1d..2b8c0e7 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/ccgp_hash_random_int_subscript_timing_test_insert_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/ccgp_hash_random_int_subscript_timing_test_insert_local.png differ
index 1b31b7f..299737d 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_find_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_find_timing_test_local.png differ
index c693ed3..7e4d7fa 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_find_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_find_local.png differ
index 9fa08a0..587ff1d 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_insert_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/gp_hash_random_int_subscript_timing_test_insert_local.png differ
index dbd3ee9..66bb0eb 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test_local.png differ
index 0be2f00..81848ba 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/hash_zlob_random_int_find_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/hash_zlob_random_int_find_timing_test_local.png differ
index 32a61ca..121af9e 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_hash_local.png differ
index 10b3980..3ac90d5 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_large_s2p_tree_local.png differ
index a8fa261..4fc3d59 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_hash_local.png differ
index b3d1061..123c3a6 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_find_timing_test_small_s2p_tree_local.png differ
index 8af7100..73a35ce 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_hash_local.png differ
index 63c0c8d..fce364c 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_large_s2p_tree_local.png differ
index 589dccd..df0becc 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_hash_local.png differ
index d7322f2..9bacb35 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small_s2p_tree_local.png differ
index 5f89460..de6ee23 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_hash_local.png differ
index 2b496b4..307ca2d 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_large_s2p_tree_local.png differ
index 4af78fa..4174fab 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_hash_local.png differ
index 40b5b2c..c5f4e57 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_timing_test_small_s2p_tree_local.png differ
index 97ca4e9..81f7a59 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_pop_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_pop_timing_test_local.png differ
index cedcb4c..472d869 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/pairing_priority_queue_text_push_timing_test_local.png differ
index 51f8211..b8cc153 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_pop_timing_test_local.png differ
index dead185..51fa718 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_random_int_push_timing_test_local.png differ
index 1701b4d..67318f0 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_join_timing_test_local.png differ
index 2fa9c79..d8d3b7a 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_local.png differ
index 977d167..23ac5e7 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_pairing_thin_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_down_timing_test_pairing_thin_local.png differ
index 31575b4..dc48e39 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_local.png differ
index b878dde..9a73934 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_pairing_thin_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_modify_up_timing_test_pairing_thin_local.png differ
index c1413fc..d1966e3 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_pop_mem_usage_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_pop_mem_usage_test_local.png differ
index a7c5f89..fd52d5a 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_pop_timing_test_local.png differ
index da7297b..18cca76 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/priority_queue_text_push_timing_test_local.png differ
index 8310520..dd7c184 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/random_int_find_find_timing_test_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/random_int_find_find_timing_test_tree_local.png differ
index d85980f..5364778 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_hash_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_hash_local.png differ
index b7fdc47..8ec5cfb 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_tree_like_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/text_find_timing_test_tree_like_local.png differ
index 2b92174..9f46319 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_order_statistics_timing_test_local.png differ
index 131d24a..fe5ba81 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_split_join_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_split_join_timing_test_local.png differ
index bb10008..c98488c 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_node_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_node_tree_local.png differ
index 228de14..eff7eef 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_pat_trie_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_pat_trie_local.png differ
index cecb8a1..f67156d 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_vector_tree_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_insert_timing_test_vector_tree_local.png differ
index 26f7151..960803b 100644 (file)
Binary files a/libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png and b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png differ
index 27aff0d..73b8589 100644 (file)
@@ -201,7 +201,7 @@ pb_subdirs = \
        ${pb_builddir}/detail/pairing_heap_ \
        ${pb_builddir}/detail/splay_tree_ \
        ${pb_builddir}/detail/list_update_map_ \
-       ${pb_builddir}/detail/basic_tree_policy \
+       ${pb_builddir}/detail/branch_policy \
        ${pb_builddir}/detail/trie_policy \
        ${pb_builddir}/detail/gp_hash_table_map_ \
        ${pb_builddir}/detail/tree_policy \
@@ -236,13 +236,12 @@ pb_headers1 = \
        ${pb_srcdir}/tag_and_trait.hpp \
        ${pb_srcdir}/tree_policy.hpp \
        ${pb_srcdir}/trie_policy.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/basic_tree_policy_base.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/null_node_metadata.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/traits.hpp \
-       ${pb_srcdir}/detail/basic_types.hpp \
+       ${pb_srcdir}/detail/branch_policy/branch_policy.hpp \
+       ${pb_srcdir}/detail/branch_policy/null_node_metadata.hpp \
+       ${pb_srcdir}/detail/branch_policy/traits.hpp \
        ${pb_srcdir}/detail/binary_heap_/binary_heap_.hpp \
        ${pb_srcdir}/detail/binary_heap_/const_iterator.hpp \
-       ${pb_srcdir}/detail/binary_heap_/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/binary_heap_/point_const_iterator.hpp \
        ${pb_srcdir}/detail/binary_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/binary_heap_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/binary_heap_/entry_cmp.hpp \
@@ -266,9 +265,7 @@ pb_headers1 = \
        ${pb_srcdir}/detail/binomial_heap_/binomial_heap_.hpp \
        ${pb_srcdir}/detail/binomial_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/binomial_heap_/debug_fn_imps.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/bin_search_tree_.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp
+       ${pb_srcdir}/detail/bin_search_tree_/bin_search_tree_.hpp 
 
 pb_headers2 = \
        ${pb_srcdir}/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp \
@@ -359,7 +356,7 @@ pb_headers4 = \
        ${pb_srcdir}/detail/hash_fn/sample_ranged_probe_fn.hpp \
        ${pb_srcdir}/detail/hash_fn/sample_range_hashing.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/const_iterator.hpp \
-       ${pb_srcdir}/detail/left_child_next_sibling_heap_/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/left_child_next_sibling_heap_/point_const_iterator.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp \
@@ -368,7 +365,6 @@ pb_headers4 = \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/node.hpp \
-       ${pb_srcdir}/detail/left_child_next_sibling_heap_/null_metadata.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/list_update_map_/constructor_destructor_fn_imps.hpp \
@@ -381,12 +377,9 @@ pb_headers4 = \
        ${pb_srcdir}/detail/list_update_map_/iterators_fn_imps.hpp \
        ${pb_srcdir}/detail/list_update_map_/lu_map_.hpp \
        ${pb_srcdir}/detail/list_update_map_/trace_fn_imps.hpp \
-       ${pb_srcdir}/detail/list_update_policy/counter_lu_metadata.hpp \
-       ${pb_srcdir}/detail/list_update_policy/counter_lu_policy_imp.hpp \
-       ${pb_srcdir}/detail/list_update_policy/mtf_lu_policy_imp.hpp \
+       ${pb_srcdir}/detail/list_update_policy/lu_counter_metadata.hpp \
        ${pb_srcdir}/detail/list_update_policy/sample_update_policy.hpp \
        ${pb_srcdir}/detail/debug_map_base.hpp \
-       ${pb_srcdir}/detail/ov_tree_map_/cond_dtor.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/erase_fn_imps.hpp \
@@ -407,30 +400,20 @@ pb_headers5 = \
        ${pb_srcdir}/detail/pairing_heap_/insert_fn_imps.hpp \
        ${pb_srcdir}/detail/pairing_heap_/pairing_heap_.hpp \
        ${pb_srcdir}/detail/pairing_heap_/split_join_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/child_iterator.hpp \
-       ${pb_srcdir}/detail/pat_trie_/cond_dtor_entry_dealtor.hpp \
-       ${pb_srcdir}/detail/pat_trie_/const_child_iterator.hpp \
        ${pb_srcdir}/detail/pat_trie_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/erase_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/find_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/head.hpp \
        ${pb_srcdir}/detail/pat_trie_/info_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/insert_join_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/internal_node.hpp \
        ${pb_srcdir}/detail/pat_trie_/iterators_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/leaf.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_base.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_iterators.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_metadata_base.hpp \
        ${pb_srcdir}/detail/pat_trie_/pat_trie_.hpp \
-       ${pb_srcdir}/detail/pat_trie_/point_iterators.hpp \
+       ${pb_srcdir}/detail/pat_trie_/pat_trie_base.hpp \
        ${pb_srcdir}/detail/pat_trie_/policy_access_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/r_erase_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/rotate_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/split_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/split_join_branch_bag.hpp \
-       ${pb_srcdir}/detail/pat_trie_/synth_e_access_traits.hpp \
+       ${pb_srcdir}/detail/pat_trie_/synth_access_traits.hpp \
        ${pb_srcdir}/detail/pat_trie_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/traits.hpp \
        ${pb_srcdir}/detail/pat_trie_/update_fn_imps.hpp \
@@ -487,22 +470,20 @@ pb_headers7 = \
        ${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
        ${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-       ${pb_srcdir}/detail/tree_policy/null_node_update_imp.hpp \
        ${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
        ${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
        ${pb_srcdir}/detail/tree_trace_base.hpp \
        ${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
-       ${pb_srcdir}/detail/trie_policy/null_node_update_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/order_statistics_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/prefix_search_node_update_imp.hpp \
-       ${pb_srcdir}/detail/trie_policy/sample_trie_e_access_traits.hpp \
+       ${pb_srcdir}/detail/trie_policy/sample_trie_access_traits.hpp \
        ${pb_srcdir}/detail/trie_policy/sample_trie_node_update.hpp \
-       ${pb_srcdir}/detail/trie_policy/string_trie_e_access_traits_imp.hpp \
+       ${pb_srcdir}/detail/trie_policy/trie_string_access_traits_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/trie_policy_base.hpp \
        ${pb_srcdir}/detail/types_traits.hpp \
        ${pb_srcdir}/detail/type_utils.hpp \
        ${pb_srcdir}/detail/unordered_iterator/const_iterator.hpp \
-       ${pb_srcdir}/detail/unordered_iterator/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/unordered_iterator/point_const_iterator.hpp \
        ${pb_srcdir}/detail/unordered_iterator/iterator.hpp \
        ${pb_srcdir}/detail/unordered_iterator/point_iterator.hpp
 
index e7f7951..aa90813 100644 (file)
@@ -451,7 +451,7 @@ pb_subdirs = \
        ${pb_builddir}/detail/pairing_heap_ \
        ${pb_builddir}/detail/splay_tree_ \
        ${pb_builddir}/detail/list_update_map_ \
-       ${pb_builddir}/detail/basic_tree_policy \
+       ${pb_builddir}/detail/branch_policy \
        ${pb_builddir}/detail/trie_policy \
        ${pb_builddir}/detail/gp_hash_table_map_ \
        ${pb_builddir}/detail/tree_policy \
@@ -486,13 +486,12 @@ pb_headers1 = \
        ${pb_srcdir}/tag_and_trait.hpp \
        ${pb_srcdir}/tree_policy.hpp \
        ${pb_srcdir}/trie_policy.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/basic_tree_policy_base.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/null_node_metadata.hpp \
-       ${pb_srcdir}/detail/basic_tree_policy/traits.hpp \
-       ${pb_srcdir}/detail/basic_types.hpp \
+       ${pb_srcdir}/detail/branch_policy/branch_policy.hpp \
+       ${pb_srcdir}/detail/branch_policy/null_node_metadata.hpp \
+       ${pb_srcdir}/detail/branch_policy/traits.hpp \
        ${pb_srcdir}/detail/binary_heap_/binary_heap_.hpp \
        ${pb_srcdir}/detail/binary_heap_/const_iterator.hpp \
-       ${pb_srcdir}/detail/binary_heap_/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/binary_heap_/point_const_iterator.hpp \
        ${pb_srcdir}/detail/binary_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/binary_heap_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/binary_heap_/entry_cmp.hpp \
@@ -516,9 +515,7 @@ pb_headers1 = \
        ${pb_srcdir}/detail/binomial_heap_/binomial_heap_.hpp \
        ${pb_srcdir}/detail/binomial_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/binomial_heap_/debug_fn_imps.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/bin_search_tree_.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp \
-       ${pb_srcdir}/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp
+       ${pb_srcdir}/detail/bin_search_tree_/bin_search_tree_.hpp 
 
 pb_headers2 = \
        ${pb_srcdir}/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp \
@@ -609,7 +606,7 @@ pb_headers4 = \
        ${pb_srcdir}/detail/hash_fn/sample_ranged_probe_fn.hpp \
        ${pb_srcdir}/detail/hash_fn/sample_range_hashing.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/const_iterator.hpp \
-       ${pb_srcdir}/detail/left_child_next_sibling_heap_/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/left_child_next_sibling_heap_/point_const_iterator.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp \
@@ -618,7 +615,6 @@ pb_headers4 = \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/node.hpp \
-       ${pb_srcdir}/detail/left_child_next_sibling_heap_/null_metadata.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp \
        ${pb_srcdir}/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/list_update_map_/constructor_destructor_fn_imps.hpp \
@@ -631,12 +627,9 @@ pb_headers4 = \
        ${pb_srcdir}/detail/list_update_map_/iterators_fn_imps.hpp \
        ${pb_srcdir}/detail/list_update_map_/lu_map_.hpp \
        ${pb_srcdir}/detail/list_update_map_/trace_fn_imps.hpp \
-       ${pb_srcdir}/detail/list_update_policy/counter_lu_metadata.hpp \
-       ${pb_srcdir}/detail/list_update_policy/counter_lu_policy_imp.hpp \
-       ${pb_srcdir}/detail/list_update_policy/mtf_lu_policy_imp.hpp \
+       ${pb_srcdir}/detail/list_update_policy/lu_counter_metadata.hpp \
        ${pb_srcdir}/detail/list_update_policy/sample_update_policy.hpp \
        ${pb_srcdir}/detail/debug_map_base.hpp \
-       ${pb_srcdir}/detail/ov_tree_map_/cond_dtor.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/ov_tree_map_/erase_fn_imps.hpp \
@@ -657,30 +650,20 @@ pb_headers5 = \
        ${pb_srcdir}/detail/pairing_heap_/insert_fn_imps.hpp \
        ${pb_srcdir}/detail/pairing_heap_/pairing_heap_.hpp \
        ${pb_srcdir}/detail/pairing_heap_/split_join_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/child_iterator.hpp \
-       ${pb_srcdir}/detail/pat_trie_/cond_dtor_entry_dealtor.hpp \
-       ${pb_srcdir}/detail/pat_trie_/const_child_iterator.hpp \
        ${pb_srcdir}/detail/pat_trie_/constructors_destructor_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/debug_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/erase_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/find_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/head.hpp \
        ${pb_srcdir}/detail/pat_trie_/info_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/insert_join_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/internal_node.hpp \
        ${pb_srcdir}/detail/pat_trie_/iterators_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/leaf.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_base.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_iterators.hpp \
-       ${pb_srcdir}/detail/pat_trie_/node_metadata_base.hpp \
        ${pb_srcdir}/detail/pat_trie_/pat_trie_.hpp \
-       ${pb_srcdir}/detail/pat_trie_/point_iterators.hpp \
+       ${pb_srcdir}/detail/pat_trie_/pat_trie_base.hpp \
        ${pb_srcdir}/detail/pat_trie_/policy_access_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/r_erase_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/rotate_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/split_fn_imps.hpp \
-       ${pb_srcdir}/detail/pat_trie_/split_join_branch_bag.hpp \
-       ${pb_srcdir}/detail/pat_trie_/synth_e_access_traits.hpp \
+       ${pb_srcdir}/detail/pat_trie_/synth_access_traits.hpp \
        ${pb_srcdir}/detail/pat_trie_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/pat_trie_/traits.hpp \
        ${pb_srcdir}/detail/pat_trie_/update_fn_imps.hpp \
@@ -737,22 +720,20 @@ pb_headers7 = \
        ${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
        ${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
        ${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-       ${pb_srcdir}/detail/tree_policy/null_node_update_imp.hpp \
        ${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
        ${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
        ${pb_srcdir}/detail/tree_trace_base.hpp \
        ${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
-       ${pb_srcdir}/detail/trie_policy/null_node_update_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/order_statistics_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/prefix_search_node_update_imp.hpp \
-       ${pb_srcdir}/detail/trie_policy/sample_trie_e_access_traits.hpp \
+       ${pb_srcdir}/detail/trie_policy/sample_trie_access_traits.hpp \
        ${pb_srcdir}/detail/trie_policy/sample_trie_node_update.hpp \
-       ${pb_srcdir}/detail/trie_policy/string_trie_e_access_traits_imp.hpp \
+       ${pb_srcdir}/detail/trie_policy/trie_string_access_traits_imp.hpp \
        ${pb_srcdir}/detail/trie_policy/trie_policy_base.hpp \
        ${pb_srcdir}/detail/types_traits.hpp \
        ${pb_srcdir}/detail/type_utils.hpp \
        ${pb_srcdir}/detail/unordered_iterator/const_iterator.hpp \
-       ${pb_srcdir}/detail/unordered_iterator/const_point_iterator.hpp \
+       ${pb_srcdir}/detail/unordered_iterator/point_const_iterator.hpp \
        ${pb_srcdir}/detail/unordered_iterator/iterator.hpp \
        ${pb_srcdir}/detail/unordered_iterator/point_iterator.hpp
 
index 12a3fc5..d366f43 100644 (file)
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the terms
 #include <ext/pb_ds/tag_and_trait.hpp>
 #include <ext/pb_ds/detail/standard_policies.hpp>
 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
-#include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
+#include <ext/pb_ds/detail/branch_policy/traits.hpp>
 
 namespace __gnu_pbds
 {
-  /** @defgroup pbds Policy-Based Data Structures
-   *  @ingroup extensions
-   *
-   *  This is a library of policy-based elementary data structures:
-   *  associative containers and priority queues. It is designed for
-   *  high-performance, flexibility, semantic safety, and conformance
-   *  to the corresponding containers in std (except for some points
-   *  where it differs by design).
-   *
-   *  For details, see: 
-   *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
-   *
+  /**
+   *  @addtogroup pbds
    *  @{
    */
-#define PB_DS_BASE_C_DEC \
-  detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
-
-  /// An abstract basic associative container.
-  template<typename Key, 
-          typename Mapped, 
-          typename Tag, 
-          typename Policy_Tl, 
-          typename Allocator>
-  class container_base : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef typename PB_DS_BASE_C_DEC                  base_type;
-
-  public:
-    typedef Tag                                        container_category;
-    typedef Allocator                                  allocator_type;
-    typedef typename allocator_type::size_type                 size_type;
-    typedef typename allocator_type::difference_type   difference_type;
-
-    // key_type
-    typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
-    typedef typename allocator_type::template rebind<key_type>::other key_rebind;
-    typedef typename key_rebind::reference             key_reference;
-    typedef typename key_rebind::const_reference       const_key_reference;
-    typedef typename key_rebind::pointer               key_pointer;
-    typedef typename key_rebind::const_pointer                 const_key_pointer;
-
-    // mapped_type
-    typedef Mapped                                     mapped_type;
-    typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
-    typedef typename mapped_rebind::reference          mapped_reference;
-    typedef typename mapped_rebind::const_reference    const_mapped_reference;
-    typedef typename mapped_rebind::pointer            mapped_pointer;
-    typedef typename mapped_rebind::const_pointer      const_mapped_pointer;
-
-    // value_type
-    typedef typename base_type::value_type             value_type;
-    typedef typename allocator_type::template rebind<value_type>::other value_rebind;
-    typedef typename value_rebind::reference           reference;
-    typedef typename value_rebind::const_reference     const_reference;
-    typedef typename value_rebind::pointer             pointer;
-    typedef typename value_rebind::const_pointer       const_pointer;
-
-    // iterators
-    typedef typename base_type::iterator               iterator;
-    typedef typename base_type::const_iterator                 const_iterator;
-    typedef typename base_type::point_iterator                 point_iterator;
-    typedef typename base_type::const_point_iterator   const_point_iterator;
-
-    virtual
-    ~container_base() { }
-
-  protected:
-#define PB_DS_CLASS_NAME               container_base
-#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
-#undef PB_DS_CLASS_NAME
-  };
-
-#undef PB_DS_BASE_C_DEC
 
-
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
-  typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
+#define PB_DS_HASH_BASE \
+  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
+    typename __gnu_cxx::typelist::append< \
+    typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
+    detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
 
   /// An abstract basic hash-based associative container.
   template<typename Key,
@@ -139,12 +69,12 @@ namespace __gnu_pbds
           typename Resize_Policy,
           bool Store_Hash,
           typename Tag,
-          typename Policy_TL,
-          typename Allocator>
-  class basic_hash_table : public PB_DS_BASE_C_DEC
+          typename Policy_Tl,
+          typename _Alloc>
+  class basic_hash_table : public PB_DS_HASH_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC base_type;
+    typedef typename PB_DS_HASH_BASE           base_type;
 
   public:
     virtual
@@ -156,17 +86,17 @@ namespace __gnu_pbds
 #undef PB_DS_CLASS_NAME
 
   private:
-    basic_hash_table& 
+    basic_hash_table&
     operator=(const base_type&);
   };
 
-#undef PB_DS_BASE_C_DEC
+#undef PB_DS_HASH_BASE
 
 
-#define PB_DS_BASE_C_DEC \
+#define PB_DS_CC_HASH_BASE \
   basic_hash_table<Key, Mapped,        Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
                   cc_hash_tag, \
-         typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
+         typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
 
   /// A concrete collision-chaining hash-based associative container.
   template<typename Key,
@@ -176,24 +106,25 @@ namespace __gnu_pbds
           typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
           typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
           bool Store_Hash = detail::default_store_hash,
-          typename Allocator = std::allocator<char> >
-  class cc_hash_table :  public PB_DS_BASE_C_DEC
+          typename _Alloc = std::allocator<char> >
+  class cc_hash_table :  public PB_DS_CC_HASH_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC   base_type;
+    typedef PB_DS_CC_HASH_BASE                         base_type;
 
   public:
-    typedef Hash_Fn            hash_fn;
-    typedef Eq_Fn              eq_fn;
-    typedef Resize_Policy      resize_policy;
-    typedef Comb_Hash_Fn       comb_hash_fn;
+    typedef cc_hash_tag                                container_category;
+    typedef Hash_Fn                            hash_fn;
+    typedef Eq_Fn                              eq_fn;
+    typedef Resize_Policy                      resize_policy;
+    typedef Comb_Hash_Fn                       comb_hash_fn;
 
     // Default constructor.
     cc_hash_table() { }
 
     // Constructor taking some policy objects. r_hash_fn will be
     // copied by the Hash_Fn object of the container object.
-    cc_hash_table(const hash_fn& h) 
+    cc_hash_table(const hash_fn& h)
     : base_type(h) { }
 
     // Constructor taking some policy objects. r_hash_fn will be
@@ -217,8 +148,8 @@ namespace __gnu_pbds
     // r_comb_hash_fn will be copied by the comb_hash_fn object of the
     // container object, and r_resize_policy will be copied by the
     // resize_policy object of the container object.
-    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 
-                 const resize_policy& rp)    
+    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
+                 const resize_policy& rp)
     : base_type(h, e, ch, rp) { }
 
     // Constructor taking __iterators to a range of value_types. The
@@ -269,7 +200,7 @@ namespace __gnu_pbds
     // object of the container object, and r_resize_policy will be
     // copied by the resize_policy object of the container object.
     template<typename It>
-    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
+    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
                  const comb_hash_fn& ch, const resize_policy& rp)
     : base_type(h, e, ch, rp)
     { this->copy_from_range(first, last); }
@@ -281,7 +212,7 @@ namespace __gnu_pbds
     virtual
     ~cc_hash_table() { }
 
-    cc_hash_table& 
+    cc_hash_table&
     operator=(const cc_hash_table& other)
     {
       if (this != &other)
@@ -297,13 +228,13 @@ namespace __gnu_pbds
     { base_type::swap(other); }
   };
 
-#undef PB_DS_BASE_C_DEC
+#undef PB_DS_CC_HASH_BASE
 
 
-#define PB_DS_BASE_C_DEC \
+#define PB_DS_GP_HASH_BASE \
   basic_hash_table<Key, Mapped,        Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
                   gp_hash_tag, \
-                  typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
+  typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
 
   /// A concrete general-probing hash-based associative container.
   template<typename Key,
@@ -314,18 +245,19 @@ namespace __gnu_pbds
           typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
           typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
           bool Store_Hash = detail::default_store_hash,
-          typename Allocator = std::allocator<char> >
-  class gp_hash_table : public PB_DS_BASE_C_DEC
+          typename _Alloc = std::allocator<char> >
+  class gp_hash_table : public PB_DS_GP_HASH_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC   base_type;
+    typedef PB_DS_GP_HASH_BASE                         base_type;
 
   public:
-    typedef Hash_Fn            hash_fn;
-    typedef Eq_Fn              eq_fn;
-    typedef Comb_Probe_Fn      comb_probe_fn;
-    typedef Probe_Fn           probe_fn;
-    typedef Resize_Policy      resize_policy;
+    typedef gp_hash_tag                                container_category;
+    typedef Hash_Fn                            hash_fn;
+    typedef Eq_Fn                              eq_fn;
+    typedef Comb_Probe_Fn                      comb_probe_fn;
+    typedef Probe_Fn                           probe_fn;
+    typedef Resize_Policy                      resize_policy;
 
     // Default constructor.
     gp_hash_table() { }
@@ -356,7 +288,7 @@ namespace __gnu_pbds
     // r_comb_probe_fn will be copied by the comb_probe_fn object of
     // the container object, and r_probe_fn will be copied by the
     // probe_fn object of the container object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
+    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
                  const probe_fn& p)
     : base_type(h, e, cp, p) { }
 
@@ -367,7 +299,7 @@ namespace __gnu_pbds
     // the container object, r_probe_fn will be copied by the probe_fn
     // object of the container object, and r_resize_policy will be
     // copied by the Resize_Policy object of the container object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
+    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
                  const probe_fn& p, const resize_policy& rp)
     : base_type(h, e, cp, p, rp) { }
 
@@ -406,7 +338,7 @@ namespace __gnu_pbds
     // object, and r_comb_probe_fn will be copied by the comb_probe_fn
     // object of the container object.
     template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
+    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
                  const comb_probe_fn& cp)
     : base_type(h, e, cp)
     { base_type::copy_from_range(first, last); }
@@ -420,7 +352,7 @@ namespace __gnu_pbds
     // object of the container object, and r_probe_fn will be copied
     // by the probe_fn object of the container object.
     template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
+    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
                  const comb_probe_fn& cp, const probe_fn& p)
     : base_type(h, e, cp, p)
     { base_type::copy_from_range(first, last); }
@@ -436,8 +368,8 @@ namespace __gnu_pbds
     // r_resize_policy will be copied by the resize_policy object of
     // the container object.
     template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
-                 const comb_probe_fn& cp, const probe_fn& p, 
+    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
+                 const comb_probe_fn& cp, const probe_fn& p,
                  const resize_policy& rp)
     : base_type(h, e, cp, p, rp)
     { base_type::copy_from_range(first, last); }
@@ -449,7 +381,7 @@ namespace __gnu_pbds
     virtual
     ~gp_hash_table() { }
 
-    gp_hash_table& 
+    gp_hash_table&
     operator=(const gp_hash_table& other)
     {
       if (this != &other)
@@ -465,56 +397,58 @@ namespace __gnu_pbds
     { base_type::swap(other); }
   };
 
-#undef PB_DS_BASE_C_DEC
-
+#undef PB_DS_GP_HASH_BASE
 
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
+#define PB_DS_BRANCH_BASE \
+  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
 
   /// An abstract basic tree-like (tree, trie) associative container.
-  template<typename Key, typename Mapped, typename Tag, 
-          typename Node_Update, typename Policy_Tl, typename Allocator>
-  class basic_tree : public PB_DS_BASE_C_DEC
+  template<typename Key, typename Mapped, typename Tag,
+          typename Node_Update, typename Policy_Tl, typename _Alloc>
+  class basic_branch : public PB_DS_BRANCH_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC   base_type;
+    typedef typename PB_DS_BRANCH_BASE                 base_type;
 
   public:
-    typedef Node_Update        node_update;
+    typedef Node_Update                        node_update;
 
     virtual
-    ~basic_tree() { }
+    ~basic_branch() { }
 
   protected:
-#define PB_DS_CLASS_NAME               basic_tree
+#define PB_DS_CLASS_NAME               basic_branch
 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
 #undef PB_DS_CLASS_NAME
   };
 
-#undef PB_DS_BASE_C_DEC
+#undef PB_DS_BRANCH_BASE
 
 
-#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
-  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
+#define PB_DS_TREE_NODE_AND_IT_TRAITS \
+  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
 
-#define PB_DS_BASE_C_DEC \
-  basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
-            typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
+#define PB_DS_TREE_BASE \
+  basic_branch<Key,Mapped, Tag, \
+              typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
+              typename __gnu_cxx::typelist::create2<Cmp_Fn, \
+              PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
 
-  /// A concrete basic tree-based associative container.
+  /// A basic tree-based associative container.
   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
           typename Tag = rb_tree_tag,
-          template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
-  class Node_Update = __gnu_pbds::null_tree_node_update,
-          typename Allocator = std::allocator<char> >
-  class tree : public PB_DS_BASE_C_DEC
+          template<typename Node_CItr, typename Node_Itr,
+                   typename Cmp_Fn_, typename _Alloc_>
+          class Node_Update = null_node_update,
+          typename _Alloc = std::allocator<char> >
+  class tree : public PB_DS_TREE_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC   base_type;
+    typedef PB_DS_TREE_BASE                    base_type;
 
   public:
     // Comparison functor type.
-    typedef Cmp_Fn             cmp_fn;
+    typedef Cmp_Fn                             cmp_fn;
 
     tree() { }
 
@@ -545,7 +479,7 @@ namespace __gnu_pbds
     virtual
     ~tree() { }
 
-    tree& 
+    tree&
     operator=(const tree& other)
     {
       if (this != &other)
@@ -561,43 +495,46 @@ namespace __gnu_pbds
     { base_type::swap(other); }
   };
 
-#undef PB_DS_BASE_C_DEC
-#undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
+#undef PB_DS_TREE_BASE
+#undef PB_DS_TREE_NODE_AND_IT_TRAITS
 
 
-#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
-  detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
+#define PB_DS_TRIE_NODE_AND_IT_TRAITS \
+  detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
 
-#define PB_DS_BASE_C_DEC \
-  basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
-            typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
+#define PB_DS_TRIE_BASE \
+  basic_branch<Key,Mapped,Tag, \
+              typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
+              typename __gnu_cxx::typelist::create2<_ATraits, \
+              PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
 
-  /// A concrete basic trie-based associative container.
+  /// A basic trie-based associative container.
   template<typename Key,
           typename Mapped,
-          typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
+          typename _ATraits = \
+                   typename detail::default_trie_access_traits<Key>::type,
           typename Tag = pat_trie_tag,
-          template<typename Const_Node_Iterator,
-                   typename Node_Iterator,
-                   typename E_Access_Traits_,
-                   typename Allocator_>
-  class Node_Update = null_trie_node_update,
-          typename Allocator = std::allocator<char> >
-  class trie : public PB_DS_BASE_C_DEC
+          template<typename Node_CItr,
+                   typename Node_Itr,
+                   typename _ATraits_,
+                   typename _Alloc_>
+          class Node_Update = null_node_update,
+          typename _Alloc = std::allocator<char> >
+  class trie : public PB_DS_TRIE_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC base_type;
+    typedef PB_DS_TRIE_BASE                    base_type;
 
   public:
     // Element access traits type.
-    typedef E_Access_Traits e_access_traits;
+    typedef _ATraits                           access_traits;
 
     trie() { }
 
-    // Constructor taking some policy objects. r_e_access_traits will
-    // be copied by the E_Access_Traits object of the container
+    // Constructor taking some policy objects. r_access_traits will
+    // be copied by the _ATraits object of the container
     // object.
-    trie(const e_access_traits& t)
+    trie(const access_traits& t)
     : base_type(t) { }
 
     // Constructor taking __iterators to a range of value_types. The
@@ -611,7 +548,7 @@ namespace __gnu_pbds
     // some policy objects. The value_types between first_it and
     // last_it will be inserted into the container object.
     template<typename It>
-    trie(It first, It last, const e_access_traits& t)
+    trie(It first, It last, const access_traits& t)
     : base_type(t)
     { base_type::copy_from_range(first, last); }
 
@@ -621,7 +558,7 @@ namespace __gnu_pbds
     virtual
     ~trie() { }
 
-    trie& 
+    trie&
     operator=(const trie& other)
     {
       if (this != &other)
@@ -637,29 +574,29 @@ namespace __gnu_pbds
     { base_type::swap(other); }
   };
 
-#undef PB_DS_BASE_C_DEC
-#undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
+#undef PB_DS_TRIE_BASE
+#undef PB_DS_TRIE_NODE_AND_IT_TRAITS
 
 
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, list_update_tag, \
-                typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
+#define PB_DS_LU_BASE \
+  detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag,        \
+    typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
 
   /// A list-update based associative container.
   template<typename Key,
           typename Mapped,
           class Eq_Fn = typename detail::default_eq_fn<Key>::type,
           class Update_Policy = detail::default_update_policy::type,
-          class Allocator = std::allocator<char> >
-  class list_update : public PB_DS_BASE_C_DEC
+          class _Alloc = std::allocator<char> >
+  class list_update : public PB_DS_LU_BASE
   {
   private:
-    typedef PB_DS_BASE_C_DEC   base_type;
+    typedef typename PB_DS_LU_BASE             base_type;
 
   public:
-    typedef Eq_Fn              eq_fn;
-    typedef Update_Policy      update_policy;
-    typedef Allocator          allocator;
+    typedef list_update_tag                    container_category;
+    typedef Eq_Fn                              eq_fn;
+    typedef Update_Policy                      update_policy;
 
     list_update() { }
 
@@ -676,7 +613,7 @@ namespace __gnu_pbds
     virtual
     ~list_update() { }
 
-    list_update& 
+    list_update&
     operator=(const list_update& other)
     {
       if (this !=& other)
@@ -692,9 +629,9 @@ namespace __gnu_pbds
     { base_type::swap(other); }
   };
 
-#undef PB_DS_BASE_C_DEC
+#undef PB_DS_LU_BASE
 
   // @} group pbds
 } // namespace __gnu_pbds
 
-#endif 
+#endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/basic_types.hpp b/libstdc++-v3/include/ext/pb_ds/detail/basic_types.hpp
deleted file mode 100644 (file)
index aac1397..0000000
+++ /dev/null
@@ -1,211 +0,0 @@
-// -*- C++ -*-
-
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library.  This library is free
-// software; you can redistribute it and/or modify it under the terms
-// of the GNU General Public License as published by the Free Software
-// Foundation; either version 3, or (at your option) any later
-// version.
-
-// This library is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-// General Public License for more details.
-
-// Under Section 7 of GPL version 3, you are granted additional
-// permissions described in the GCC Runtime Library Exception, version
-// 3.1, as published by the Free Software Foundation.
-
-// You should have received a copy of the GNU General Public License and
-// a copy of the GCC Runtime Library Exception along with this program;
-// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-// <http://www.gnu.org/licenses/>.
-
-// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
-
-// Permission to use, copy, modify, sell, and distribute this software
-// is hereby granted without fee, provided that the above copyright
-// notice appears in all copies, and that both that copyright notice
-// and this permission notice appear in supporting documentation. None
-// of the above authors, nor IBM Haifa Research Laboratories, make any
-// representation about the suitability of this software for any
-// purpose. It is provided "as is" without express or implied
-// warranty.
-
-/**
- * @file basic_types.hpp
- * Contains basic types used by containers.
- */
-
-#ifndef PB_DS_BASIC_TYPES_HPP
-#define PB_DS_BASIC_TYPES_HPP
-
-#include <algorithm>
-#include <utility>
-#include <ext/pb_ds/tag_and_trait.hpp>
-#include <ext/pb_ds/detail/type_utils.hpp>
-
-namespace __gnu_pbds
-{
-  namespace detail
-  {
-    template<typename Key, typename Mapped, typename Allocator, bool Store_Hash>
-    struct value_type_base;
-
-    /**
-     * Specialization of value_type_base for the case where the hash value
-     * is not stored alongside each value.
-     **/
-    template<typename Key, typename Mapped, typename Allocator>
-    struct value_type_base<Key, Mapped, Allocator, false>
-    {
-      typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
-      typedef typename mapped_type_allocator::value_type mapped_type;
-      typedef typename mapped_type_allocator::pointer mapped_pointer;
-      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
-      typedef typename mapped_type_allocator::reference mapped_reference;
-      typedef typename mapped_type_allocator::const_reference const_mapped_reference;
-
-      typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
-      typedef typename value_type_allocator::value_type value_type;
-      typedef typename value_type_allocator::pointer pointer;
-      typedef typename value_type_allocator::const_pointer const_pointer;
-      typedef typename value_type_allocator::reference reference;
-      typedef typename value_type_allocator::const_reference const_reference;
-
-      struct stored_value_type
-      {
-       value_type m_value;
-      };
-    };
-
-    /**
-     * Specialization of value_type_base for the case where the hash value
-     * is stored alongside each value.
-     **/
-    template<typename Key, typename Mapped, typename Allocator>
-    struct value_type_base<Key, Mapped, Allocator, true>
-    {
-      typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
-      typedef typename mapped_type_allocator::value_type mapped_type;
-      typedef typename mapped_type_allocator::pointer mapped_pointer;
-      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
-      typedef typename mapped_type_allocator::reference mapped_reference;
-      typedef typename mapped_type_allocator::const_reference const_mapped_reference;
-
-      typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
-      typedef typename value_type_allocator::value_type value_type;
-      typedef typename value_type_allocator::pointer pointer;
-      typedef typename value_type_allocator::const_pointer const_pointer;
-      typedef typename value_type_allocator::reference reference;
-      typedef typename value_type_allocator::const_reference const_reference;
-
-      struct stored_value_type
-      {
-       value_type m_value;
-       typename Allocator::size_type m_hash;
-      };
-    };
-
-#define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Allocator>
-
-#define PB_DS_CLASS_C_DEC \
-    value_type_base<Key, null_mapped_type, Allocator, false>
-
-    /**
-     * Specialization of value_type_base for the case where the hash value
-     * is not stored alongside each value.
-     **/
-    template<typename Key, typename Allocator>
-    struct value_type_base<Key, null_mapped_type, Allocator, false>
-    {
-      typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
-      typedef typename mapped_type_allocator::value_type mapped_type;
-      typedef typename mapped_type_allocator::pointer mapped_pointer;
-      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
-      typedef typename mapped_type_allocator::reference mapped_reference;
-      typedef typename mapped_type_allocator::const_reference const_mapped_reference;
-
-      typedef Key value_type;
-
-      typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
-      typedef typename value_type_allocator::pointer pointer;
-      typedef typename value_type_allocator::const_pointer const_pointer;
-      typedef typename value_type_allocator::reference reference;
-      typedef typename value_type_allocator::const_reference const_reference;
-
-      struct stored_value_type
-      {
-       value_type m_value;
-      };
-
-      static null_mapped_type s_null_mapped;
-    };
-
-    PB_DS_CLASS_T_DEC
-    null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
-
-#undef PB_DS_CLASS_T_DEC
-#undef PB_DS_CLASS_C_DEC
-
-#define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Allocator>
-
-#define PB_DS_CLASS_C_DEC \
-    value_type_base<Key, null_mapped_type, Allocator, true>
-
-    /**
-     * Specialization of value_type_base for the case where the hash value
-     * is stored alongside each value.
-     **/
-    template<typename Key, typename Allocator>
-    struct value_type_base<Key, null_mapped_type, Allocator, true>
-    {
-      typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
-      typedef typename mapped_type_allocator::value_type mapped_type;
-      typedef typename mapped_type_allocator::pointer mapped_pointer;
-      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
-      typedef typename mapped_type_allocator::reference mapped_reference;
-      typedef typename mapped_type_allocator::const_reference const_mapped_reference;
-
-      typedef Key value_type;
-
-      typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
-      typedef typename value_type_allocator::pointer pointer;
-      typedef typename value_type_allocator::const_pointer const_pointer;
-      typedef typename value_type_allocator::reference reference;
-      typedef typename value_type_allocator::const_reference const_reference;
-
-      struct stored_value_type
-      {
-       value_type m_value;
-       typename Allocator::size_type m_hash;
-      };
-
-      static null_mapped_type s_null_mapped;
-    };
-
-    PB_DS_CLASS_T_DEC
-    null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
-
-#undef PB_DS_CLASS_T_DEC
-#undef PB_DS_CLASS_C_DEC
-
-    template<typename Key, typename Mapped>
-    struct no_throw_copies
-    {
-      typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator;
-    };
-
-    template<typename Key>
-    struct no_throw_copies<Key, null_mapped_type>
-    {
-      typedef integral_constant<int, is_simple<Key>::value> indicator;
-    };
-  } // namespace detail
-} // namespace __gnu_pbds
-
-#endif 
-
index a73414a..a875e30 100644 (file)
 // warranty.
 
 /**
- * @file bin_search_tree_.hpp
- * Contains an implementation class for bin_search_tree_.
- */
-/*
- * This implementation uses an idea from the SGI STL (using a @a header node
- *    which is needed for efficient iteration).
+ *  @file bin_search_tree_/bin_search_tree_.hpp
+ *  Contains an implementation class for binary search tree.
  */
 
 #include <ext/pb_ds/exception.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
 #include <ext/pb_ds/detail/types_traits.hpp>
-#include <ext/pb_ds/detail/debug_map_base.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
 #include <ext/pb_ds/detail/cond_dealtor.hpp>
 #include <ext/pb_ds/detail/type_utils.hpp>
 #include <ext/pb_ds/detail/tree_trace_base.hpp>
+#ifdef _GLIBCXX_DEBUG
+#include <ext/pb_ds/detail/debug_map_base.hpp>
+#endif
 #include <utility>
 #include <functional>
 #include <debug/debug.h>
@@ -58,201 +56,129 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-
-#define PB_DS_CLASS_T_DEC                                              \
-    template<typename Key, typename Mapped, class Cmp_Fn,              \
-            class Node_And_It_Traits, class Allocator>
-
 #ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_CLASS_NAME                       \
-    bin_search_tree_data_
-#endif 
+#define PB_DS_BIN_TREE_NAME bin_search_tree_map
+#endif
 
 #ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_CLASS_NAME                       \
-    bin_search_tree_no_data_
-#endif 
-
-#define PB_DS_CLASS_C_DEC                                              \
-    PB_DS_CLASS_NAME<                                                  \
-                                               Key,                    \
-                                               Mapped,                 \
-                                               Cmp_Fn,                 \
-                                               Node_And_It_Traits,     \
-                                               Allocator>
-
-#define PB_DS_TYPES_TRAITS_C_DEC                               \
-    types_traits<                              \
-                                               Key,            \
-                                               Mapped,         \
-                                               Allocator,      \
-                                               false>
+#define PB_DS_BIN_TREE_NAME bin_search_tree_set
+#endif
 
-#ifdef _GLIBCXX_DEBUG
-#define PB_DS_DEBUG_MAP_BASE_C_DEC                                     \
-    debug_map_base<Key,        eq_by_less<Key, Cmp_Fn>, \
-             typename Allocator::template rebind<Key>::other::const_reference>
-#endif 
+#define PB_DS_CLASS_T_DEC \
+    template<typename Key, typename Mapped, typename Cmp_Fn, \
+            typename Node_And_It_Traits, typename _Alloc>
 
-#ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_V2F(X) (X).first
-#define PB_DS_V2S(X) (X).second
-#define PB_DS_EP2VP(X)& ((X)->m_value)
-#endif 
+#define PB_DS_CLASS_C_DEC \
+    PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
 
-#ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_V2F(X) (X)
-#define PB_DS_V2S(X) Mapped_Data()
-#define PB_DS_EP2VP(X)& ((X)->m_value.first)
-#endif 
+#define PB_DS_BIN_TREE_TRAITS_BASE \
+    types_traits<Key, Mapped, _Alloc, false>
+
+#ifdef _GLIBCXX_DEBUG
+#define PB_DS_DEBUG_MAP_BASE_C_DEC  \
+    debug_map_base<Key,        eq_by_less<Key, Cmp_Fn>, \
+             typename _Alloc::template rebind<Key>::other::const_reference>
+#endif
 
 #ifdef PB_DS_TREE_TRACE
-#define PB_DS_TREE_TRACE_BASE_C_DEC                                    \
-    tree_trace_base<                                                   \
-                                                                       typename Node_And_It_Traits::const_node_iterator, \
-                                                                       typename Node_And_It_Traits::node_iterator, \
-                                                                       Cmp_Fn, \
-                                                                       true, \
-                                                                       Allocator>
-#endif 
-
-    /**
-     * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
-     **/
-    template<typename Key,
-            typename Mapped,
-            class Cmp_Fn,
-            class Node_And_It_Traits,
-            class Allocator>
-    class PB_DS_CLASS_NAME :
+#define PB_DS_TREE_TRACE_BASE_C_DEC \
+    tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
+                   typename Node_And_It_Traits::node_iterator,       \
+                   Cmp_Fn, true, _Alloc>
+#endif
+
+
+    /*
+     *  @brief Binary search tree (BST).
+     *
+     *  This implementation uses an idea from the SGI STL (using a @a
+     *  header node which is needed for efficient iteration).
+     */
+    template<typename Key, typename Mapped, typename Cmp_Fn,
+            typename Node_And_It_Traits, typename _Alloc>
+    class PB_DS_BIN_TREE_NAME :
 #ifdef _GLIBCXX_DEBUG
       public PB_DS_DEBUG_MAP_BASE_C_DEC,
-#endif 
+#endif
 #ifdef PB_DS_TREE_TRACE
       public PB_DS_TREE_TRACE_BASE_C_DEC,
-#endif 
+#endif
       public Cmp_Fn,
-      public PB_DS_TYPES_TRAITS_C_DEC,
+      public PB_DS_BIN_TREE_TRAITS_BASE,
       public Node_And_It_Traits::node_update
     {
+      typedef Node_And_It_Traits                       traits_type;
 
     protected:
+      typedef PB_DS_BIN_TREE_TRAITS_BASE               traits_base;
+
       typedef
-      typename Allocator::template rebind<
-      typename Node_And_It_Traits::node>::other
+      typename _Alloc::template rebind<typename traits_type::node>::other
       node_allocator;
 
-      typedef typename node_allocator::value_type node;
-
-      typedef typename node_allocator::pointer node_pointer;
+      typedef typename node_allocator::value_type      node;
+      typedef typename node_allocator::pointer                 node_pointer;
 
-      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
-
-      typedef
-      typename Node_And_It_Traits::null_node_update_pointer
+      typedef typename traits_type::null_node_update_pointer
       null_node_update_pointer;
 
     private:
-      typedef cond_dealtor< node, Allocator> cond_dealtor_t;
+      typedef cond_dealtor<node, _Alloc>               cond_dealtor_t;
 
 #ifdef _GLIBCXX_DEBUG
-      typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
-#endif 
+      typedef PB_DS_DEBUG_MAP_BASE_C_DEC               debug_base;
+#endif
 
     public:
-
-      typedef typename Allocator::size_type size_type;
-
-      typedef typename Allocator::difference_type difference_type;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
-      const_key_pointer;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
-      const_key_reference;
+      typedef typename _Alloc::size_type               size_type;
+      typedef typename _Alloc::difference_type         difference_type;
+      typedef typename traits_base::key_type           key_type;
+      typedef typename traits_base::key_pointer        key_pointer;
+      typedef typename traits_base::key_const_pointer  key_const_pointer;
+      typedef typename traits_base::key_reference      key_reference;
+      typedef typename traits_base::key_const_reference key_const_reference;
 
 #ifdef PB_DS_DATA_TRUE_INDICATOR
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
-      mapped_pointer;
+      typedef typename traits_base::mapped_type        mapped_type;
+      typedef typename traits_base::mapped_pointer     mapped_pointer;
+      typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
+      typedef typename traits_base::mapped_reference   mapped_reference;
+      typedef typename traits_base::mapped_const_reference mapped_const_reference;
+#endif
 
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
-      const_mapped_pointer;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
-      mapped_reference;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
-      const_mapped_reference;
-#endif 
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
-
-      typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
-
-      typedef
-      typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
-      const_reference;
-
-      typedef
-      typename Node_And_It_Traits::const_point_iterator
-      const_point_iterator;
-
-      typedef const_point_iterator const_iterator;
-
-      typedef typename Node_And_It_Traits::point_iterator point_iterator;
+      typedef typename traits_base::value_type                 value_type;
+      typedef typename traits_base::pointer            pointer;
+      typedef typename traits_base::const_pointer      const_pointer;
+      typedef typename traits_base::reference          reference;
+      typedef typename traits_base::const_reference    const_reference;
+      typedef typename traits_type::point_const_iterator point_const_iterator;
 
-      typedef point_iterator iterator;
+      typedef point_const_iterator                     const_iterator;
+      typedef typename traits_type::point_iterator     point_iterator;
+      typedef point_iterator                           iterator;
 
-      typedef
-      typename Node_And_It_Traits::const_reverse_iterator
-      const_reverse_iterator;
-
-      typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
-
-      typedef
-      typename Node_And_It_Traits::const_node_iterator
-      const_node_iterator;
+      typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
 
-      typedef typename Node_And_It_Traits::node_iterator node_iterator;
+      typedef typename traits_type::reverse_iterator   reverse_iterator;
+      typedef typename traits_type::node_const_iterator node_const_iterator;
+      typedef typename traits_type::node_iterator      node_iterator;
+      typedef typename traits_type::node_update        node_update;
 
-      typedef Cmp_Fn cmp_fn;
-
-      typedef Allocator allocator_type;
-
-      typedef typename Node_And_It_Traits::node_update node_update;
-
-    public:
+      typedef Cmp_Fn                                   cmp_fn;
+      typedef _Alloc                                   allocator_type;
 
-      PB_DS_CLASS_NAME();
+      PB_DS_BIN_TREE_NAME();
 
-      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
+      PB_DS_BIN_TREE_NAME(const Cmp_Fn&);
 
-      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
+      PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&);
 
-      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
+      PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&);
 
       void
-      swap(PB_DS_CLASS_C_DEC& other);
+      swap(PB_DS_CLASS_C_DEC&);
 
-      ~PB_DS_CLASS_NAME();
+      ~PB_DS_BIN_TREE_NAME();
 
       inline bool
       empty() const;
@@ -263,29 +189,29 @@ namespace __gnu_pbds
       inline size_type
       max_size() const;
 
-      Cmp_Fn& 
+      Cmp_Fn&
       get_cmp_fn();
 
-      const Cmp_Fn& 
+      const Cmp_Fn&
       get_cmp_fn() const;
 
       inline point_iterator
-      lower_bound(const_key_reference r_key);
+      lower_bound(key_const_reference);
 
-      inline const_point_iterator
-      lower_bound(const_key_reference r_key) const;
+      inline point_const_iterator
+      lower_bound(key_const_reference) const;
 
       inline point_iterator
-      upper_bound(const_key_reference r_key);
+      upper_bound(key_const_reference);
 
-      inline const_point_iterator
-      upper_bound(const_key_reference r_key) const;
+      inline point_const_iterator
+      upper_bound(key_const_reference) const;
 
       inline point_iterator
-      find(const_key_reference r_key);
+      find(key_const_reference);
 
-      inline const_point_iterator
-      find(const_key_reference r_key) const;
+      inline point_const_iterator
+      find(key_const_reference) const;
 
       inline iterator
       begin();
@@ -311,13 +237,13 @@ namespace __gnu_pbds
       inline const_reverse_iterator
       rend() const;
 
-      inline const_node_iterator
+      inline node_const_iterator
       node_begin() const;
 
       inline node_iterator
       node_begin();
 
-      inline const_node_iterator
+      inline node_const_iterator
       node_end() const;
 
       inline node_iterator
@@ -327,148 +253,139 @@ namespace __gnu_pbds
       clear();
 
     protected:
-
       void
-      value_swap(PB_DS_CLASS_C_DEC& other);
+      value_swap(PB_DS_CLASS_C_DEC&);
 
       void
       initialize_min_max();
 
       inline iterator
-      insert_imp_empty(const_reference r_value);
+      insert_imp_empty(const_reference);
 
       inline iterator
-      insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
+      insert_leaf_new(const_reference, node_pointer, bool);
 
       inline node_pointer
-      get_new_node_for_leaf_insert(const_reference r_val, false_type);
+      get_new_node_for_leaf_insert(const_reference, false_type);
 
       inline node_pointer
-      get_new_node_for_leaf_insert(const_reference r_val, true_type);
+      get_new_node_for_leaf_insert(const_reference, true_type);
 
       inline void
-      actual_erase_node(node_pointer p_nd);
+      actual_erase_node(node_pointer);
 
       inline std::pair<node_pointer, bool>
-      erase(node_pointer p_nd);
+      erase(node_pointer);
 
       inline void
-      update_min_max_for_erased_node(node_pointer p_nd);
+      update_min_max_for_erased_node(node_pointer);
 
       static void
-      clear_imp(node_pointer p_nd);
+      clear_imp(node_pointer);
 
-      inline std::pair<
-       point_iterator,
-       bool>
-      insert_leaf(const_reference r_value);
+      inline std::pair<point_iterator, bool>
+      insert_leaf(const_reference);
 
       inline void
-      rotate_left(node_pointer p_x);
+      rotate_left(node_pointer);
 
       inline void
-      rotate_right(node_pointer p_y);
+      rotate_right(node_pointer);
 
       inline void
-      rotate_parent(node_pointer p_nd);
+      rotate_parent(node_pointer);
 
       inline void
-      apply_update(node_pointer p_nd, null_node_update_pointer);
+      apply_update(node_pointer, null_node_update_pointer);
 
       template<typename Node_Update_>
-      inline void
-      apply_update(node_pointer p_nd, Node_Update_* p_update);
+       inline void
+       apply_update(node_pointer, Node_Update_*);
 
       inline void
-      update_to_top(node_pointer p_nd, null_node_update_pointer);
+      update_to_top(node_pointer, null_node_update_pointer);
 
       template<typename Node_Update_>
-      inline void
-      update_to_top(node_pointer p_nd, Node_Update_* p_update);
+       inline void
+       update_to_top(node_pointer, Node_Update_*);
 
       bool
-      join_prep(PB_DS_CLASS_C_DEC& other);
+      join_prep(PB_DS_CLASS_C_DEC&);
 
       void
-      join_finish(PB_DS_CLASS_C_DEC& other);
+      join_finish(PB_DS_CLASS_C_DEC&);
 
       bool
-      split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
+      split_prep(key_const_reference, PB_DS_CLASS_C_DEC&);
 
       void
-      split_finish(PB_DS_CLASS_C_DEC& other);
+      split_finish(PB_DS_CLASS_C_DEC&);
 
       size_type
-      recursive_count(node_pointer p_nd) const;
+      recursive_count(node_pointer) const;
 
 #ifdef _GLIBCXX_DEBUG
       void
-      assert_valid(const char* file, int line) const;
+      assert_valid(const char*, int) const;
 
       void
-      structure_only_assert_valid(const char* file, int line) const;
+      structure_only_assert_valid(const char*, int) const;
 
       void
-      assert_node_consistent(const node_pointer p_nd,
-                            const char* file, int line) const;
-#endif 
+      assert_node_consistent(const node_pointer, const char*, int) const;
+#endif
 
     private:
 #ifdef _GLIBCXX_DEBUG
       void
-      assert_iterators(const char* file, int line) const;
+      assert_iterators(const char*, int) const;
 
       void
-      assert_consistent_with_debug_base(const char* file, int line) const;
+      assert_consistent_with_debug_base(const char*, int) const;
 
       void
-      assert_node_consistent_with_left(const node_pointer p_nd,
-                                      const char* file, int line) const;
+      assert_node_consistent_with_left(const node_pointer,
+                                      const char*, int) const;
 
       void
-      assert_node_consistent_with_right(const node_pointer p_nd,
-                                       const char* file, int line) const;
+      assert_node_consistent_with_right(const node_pointer,
+                                       const char*, int) const;
 
       void
-      assert_consistent_with_debug_base(const node_pointer p_nd,
-                                       const char* file, int line) const;
+      assert_consistent_with_debug_base(const node_pointer,
+                                       const char*, int) const;
 
       void
-      assert_min(const char* file, int line) const;
+      assert_min(const char*, int) const;
 
       void
-      assert_min_imp(const node_pointer p_nd,
-                    const char* file, int line) const;
+      assert_min_imp(const node_pointer, const char*, int) const;
 
       void
-      assert_max(const char* file, int line) const;
+      assert_max(const char*, int) const;
 
       void
-      assert_max_imp(const node_pointer p_nd,
-                    const char* file, int line) const;
+      assert_max_imp(const node_pointer, const char*, int) const;
 
       void
-      assert_size(const char* file, int line) const;
+      assert_size(const char*, int) const;
 
-      typedef std::pair< const_pointer, const_pointer> node_consistent_t;
+      typedef std::pair<const_pointer, const_pointer> node_consistent_t;
 
       node_consistent_t
-      assert_node_consistent_(const node_pointer p_nd,
-                             const char* file, int line) const;
-#endif 
+      assert_node_consistent_(const node_pointer, const char*, int) const;
+#endif
 
       void
       initialize();
 
       node_pointer
-      recursive_copy_node(const node_pointer p_nd);
+      recursive_copy_node(const node_pointer);
 
     protected:
-      node_pointer m_p_head;
-
-      size_type m_size;
-
-      static node_allocator s_node_allocator;
+      node_pointer             m_p_head;
+      size_type                m_size;
+      static node_allocator    s_node_allocator;
     };
 
 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X)                              \
@@ -492,17 +409,12 @@ namespace __gnu_pbds
 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID
 #undef PB_DS_CLASS_C_DEC
 #undef PB_DS_CLASS_T_DEC
-#undef PB_DS_CLASS_NAME
-#undef PB_DS_TYPES_TRAITS_C_DEC
+#undef PB_DS_BIN_TREE_NAME
+#undef PB_DS_BIN_TREE_TRAITS_BASE
 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 
 #ifdef PB_DS_TREE_TRACE
 #undef PB_DS_TREE_TRACE_BASE_C_DEC
-#endif 
-
-#undef PB_DS_V2F
-#undef PB_DS_EP2VP
-#undef PB_DS_V2S
-
+#endif
   } // namespace detail
 } // namespace __gnu_pbds
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp
deleted file mode 100644 (file)
index 370574c..0000000
+++ /dev/null
@@ -1,70 +0,0 @@
-// -*- C++ -*-
-
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library.  This library is free
-// software; you can redistribute it and/or modify it under the terms
-// of the GNU General Public License as published by the Free Software
-// Foundation; either version 3, or (at your option) any later
-// version.
-
-// This library is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-// General Public License for more details.
-
-// Under Section 7 of GPL version 3, you are granted additional
-// permissions described in the GCC Runtime Library Exception, version
-// 3.1, as published by the Free Software Foundation.
-
-// You should have received a copy of the GNU General Public License and
-// a copy of the GCC Runtime Library Exception along with this program;
-// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-// <http://www.gnu.org/licenses/>.
-
-// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
-
-// Permission to use, copy, modify, sell, and distribute this software
-// is hereby granted without fee, provided that the above copyright
-// notice appears in all copies, and that both that copyright notice
-// and this permission notice appear in supporting documentation. None
-// of the above authors, nor IBM Haifa Research Laboratories, make any
-// representation about the suitability of this software for any
-// purpose. It is provided "as is" without express or implied
-// warranty.
-
-/**
- * @file cond_dtor_entry_dealtor.hpp
- * Contains a binary tree container conditional deallocator
- */
-
-class bin_search_tree_cond_dtor_entry_dealtor_
-{
-public:
-  inline
-  bin_search_tree_cond_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd),
-                                                               m_no_action_dtor(false)
-  { }
-
-  inline void
-  set_no_action_dtor()
-  {
-    m_no_action_dtor = true;
-  }
-
-  inline
-  ~bin_search_tree_cond_dtor_entry_dealtor_()
-  {
-    if (m_no_action_dtor)
-      return;
-
-    typename Allocator::template rebind<Node>::other().
-      deallocate(m_p_nd, 1);
-  }
-
-protected:
-  node_pointer m_p_nd;
-
-  bool m_no_action_dtor;
-};
-
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp
deleted file mode 100644 (file)
index 612eceb..0000000
+++ /dev/null
@@ -1,81 +0,0 @@
-// -*- C++ -*-
-
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library.  This library is free
-// software; you can redistribute it and/or modify it under the terms
-// of the GNU General Public License as published by the Free Software
-// Foundation; either version 3, or (at your option) any later
-// version.
-
-// This library is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-// General Public License for more details.
-
-// Under Section 7 of GPL version 3, you are granted additional
-// permissions described in the GCC Runtime Library Exception, version
-// 3.1, as published by the Free Software Foundation.
-
-// You should have received a copy of the GNU General Public License and
-// a copy of the GCC Runtime Library Exception along with this program;
-// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-// <http://www.gnu.org/licenses/>.
-
-// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
-
-// Permission to use, copy, modify, sell, and distribute this software
-// is hereby granted without fee, provided that the above copyright
-// notice appears in all copies, and that both that copyright notice
-// and this permission notice appear in supporting documentation. None
-// of the above authors, nor IBM Haifa Research Laboratories, make any
-// representation about the suitability of this software for any
-// purpose. It is provided "as is" without express or implied
-// warranty.
-
-/**
- * @file cond_key_dtor_entry_dealtor.hpp
- * Contains a binary tree container conditional deallocator
- */
-
-class bin_seach_tree_cond_key_dtor_entry_dealtor_
-{
-public:
-  inline
-  bin_seach_tree_cond_key_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd),
-                                                                  m_no_action_dtor(false),
-                                                                  m_key_destruct(false)
-  { }
-
-  inline void
-  set_no_action_dtor()
-  {
-    m_no_action_dtor = true;
-  }
-
-  inline void
-  set_key_destruct()
-  {
-    m_key_destruct = true;
-  }
-
-  inline
-  ~bin_seach_tree_cond_key_dtor_entry_dealtor_()
-  {
-    if (m_no_action_dtor)
-      return;
-
-    if (m_key_destruct)
-      m_p_nd->m_value.first.~Key();
-
-    bin_tree_base::s_alloc.deallocate(m_p_nd, 1);
-  }
-
-protected:
-  node_pointer m_p_nd;
-
-  bool m_no_action_dtor;
-
-  bool m_key_destruct;
-};
-
index d7b5985..2815b42 100644 (file)
@@ -35,7 +35,7 @@
 // warranty.
 
 /**
- * @file constructors_destructor_fn_imps.hpp
+ * @file bin_search_tree_/constructors_destructor_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -45,7 +45,7 @@ PB_DS_CLASS_C_DEC::s_node_allocator;
 
 PB_DS_CLASS_T_DEC
 PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0)
+PB_DS_BIN_TREE_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0)
 {
   initialize();
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
@@ -53,7 +53,7 @@ PB_DS_CLASS_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0)
 
 PB_DS_CLASS_T_DEC
 PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
+PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn) :
   Cmp_Fn(r_cmp_fn), m_p_head(s_node_allocator.allocate(1)), m_size(0)
 {
   initialize();
@@ -62,7 +62,7 @@ PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
 
 PB_DS_CLASS_T_DEC
 PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
+PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
   Cmp_Fn(r_cmp_fn),
   node_update(r_node_update),
   m_p_head(s_node_allocator.allocate(1)),
@@ -74,7 +74,7 @@ PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
 
 PB_DS_CLASS_T_DEC
 PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
+PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC& other) :
 #ifdef _GLIBCXX_DEBUG
   debug_base(other),
 #endif 
@@ -132,7 +132,7 @@ value_swap(PB_DS_CLASS_C_DEC& other)
 
 PB_DS_CLASS_T_DEC
 PB_DS_CLASS_C_DEC::
-~PB_DS_CLASS_NAME()
+~PB_DS_BIN_TREE_NAME()
 {
   clear();
   s_node_allocator.deallocate(m_p_head, 1);
index 86d5c2e..1f77e31 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file debug_fn_imps.hpp
+ * @file bin_search_tree_/debug_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -272,8 +272,6 @@ PB_DS_CLASS_T_DEC
 void
 PB_DS_CLASS_C_DEC::
 assert_size(const char* __file, int __line) const
-{
-  PB_DS_DEBUG_VERIFY(recursive_count(m_p_head->m_p_parent) == m_size);
-}
+{ PB_DS_DEBUG_VERIFY(recursive_count(m_p_head->m_p_parent) == m_size); }
 
 #endif
index 60a5490..1d1b170 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file erase_fn_imps.hpp
+ * @file bin_search_tree_/erase_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -45,11 +45,8 @@ actual_erase_node(node_pointer p_z)
 {
   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   --m_size;
-
-  _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value));)
-
+  _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(p_z->m_value));)
   p_z->~node();
-
   s_node_allocator.deallocate(p_z, 1);
 }
 
@@ -61,24 +58,19 @@ update_min_max_for_erased_node(node_pointer p_z)
   if (m_size == 1)
     {
       m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
-
       return;
     }
 
   if (m_p_head->m_p_left == p_z)
     {
       iterator it(p_z);
-
       ++it;
-
       m_p_head->m_p_left = it.m_p_nd;
     }
   else if (m_p_head->m_p_right == p_z)
     {
       iterator it(p_z);
-
       --it;
-
       m_p_head->m_p_right = it.m_p_nd;
     }
 }
@@ -89,15 +81,10 @@ PB_DS_CLASS_C_DEC::
 clear()
 {
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
-
   clear_imp(m_p_head->m_p_parent);
-
   m_size = 0;
-
   initialize();
-
   _GLIBCXX_DEBUG_ONLY(debug_base::clear();)
-
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
 }
 
@@ -110,11 +97,7 @@ clear_imp(node_pointer p_nd)
     return;
 
   clear_imp(p_nd->m_p_left);
-
   clear_imp(p_nd->m_p_right);
-
   p_nd->~node();
-
   s_node_allocator.deallocate(p_nd, 1);
 }
-
index 6b50dc8..03b7fe8 100644 (file)
 // warranty.
 
 /**
- * @file find_fn_imps.hpp
+ * @file bin_search_tree_/find_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
 PB_DS_CLASS_T_DEC
-inline typename PB_DS_CLASS_C_DEC::const_point_iterator
+inline typename PB_DS_CLASS_C_DEC::point_const_iterator
 PB_DS_CLASS_C_DEC::
-lower_bound(const_key_reference r_key) const
+lower_bound(key_const_reference r_key) const
 {
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
   while (p_nd != 0)
-    if (Cmp_Fn::operator()(
-                          PB_DS_V2F(p_nd->m_value),
-                          r_key))
+    if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
       p_nd = p_nd->m_p_right;
     else
       {
        p_pot = p_nd;
-
        p_nd = p_nd->m_p_left;
       }
-
-  return (iterator(p_pot));
+  return iterator(p_pot);
 }
 
 PB_DS_CLASS_T_DEC
 inline typename PB_DS_CLASS_C_DEC::point_iterator
 PB_DS_CLASS_C_DEC::
-lower_bound(const_key_reference r_key)
+lower_bound(key_const_reference r_key)
 {
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
   while (p_nd != 0)
-    if (Cmp_Fn::operator()(
-                          PB_DS_V2F(p_nd->m_value),
-                          r_key))
+    if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
       p_nd = p_nd->m_p_right;
     else
       {
        p_pot = p_nd;
-
        p_nd = p_nd->m_p_left;
       }
-
-  return (iterator(p_pot));
+  return iterator(p_pot);
 }
 
 PB_DS_CLASS_T_DEC
-inline typename PB_DS_CLASS_C_DEC::const_point_iterator
+inline typename PB_DS_CLASS_C_DEC::point_const_iterator
 PB_DS_CLASS_C_DEC::
-upper_bound(const_key_reference r_key) const
+upper_bound(key_const_reference r_key) const
 {
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
   while (p_nd != 0)
-    if (Cmp_Fn::operator()(r_key,
-                          PB_DS_V2F(p_nd->m_value)))
+    if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
       {
-       p_pot = p_nd,
-
-         p_nd = p_nd->m_p_left;
+       p_pot = p_nd;
+       p_nd = p_nd->m_p_left;
       }
     else
       p_nd = p_nd->m_p_right;
-
-  return (const_iterator(p_pot));
+  return const_iterator(p_pot);
 }
 
 PB_DS_CLASS_T_DEC
 inline typename PB_DS_CLASS_C_DEC::point_iterator
 PB_DS_CLASS_C_DEC::
-upper_bound(const_key_reference r_key)
+upper_bound(key_const_reference r_key)
 {
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
   while (p_nd != 0)
-    if (Cmp_Fn::operator()(r_key,
-                          PB_DS_V2F(p_nd->m_value)))
+    if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
       {
-       p_pot = p_nd,
-
-         p_nd = p_nd->m_p_left;
+       p_pot = p_nd;
+       p_nd = p_nd->m_p_left;
       }
     else
       p_nd = p_nd->m_p_right;
-
-  return (point_iterator(p_pot));
+  return point_iterator(p_pot);
 }
 
 PB_DS_CLASS_T_DEC
 inline typename PB_DS_CLASS_C_DEC::point_iterator
 PB_DS_CLASS_C_DEC::
-find(const_key_reference r_key)
+find(key_const_reference r_key)
 {
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
-
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
@@ -142,25 +127,27 @@ find(const_key_reference r_key)
     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
       {
        p_pot = p_nd;
-
        p_nd = p_nd->m_p_left;
       }
     else
       p_nd = p_nd->m_p_right;
 
-  return point_iterator((p_pot != m_p_head
-                        && Cmp_Fn::operator()(r_key,
-                                              PB_DS_V2F(p_pot->m_value)))
-                               ? m_p_head : p_pot);
+  node_pointer ret = p_pot;
+  if (p_pot != m_p_head)
+    {
+      const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
+      if (__cmp)
+       ret = m_p_head;
+    }
+  return point_iterator(ret);
 }
 
 PB_DS_CLASS_T_DEC
-inline typename PB_DS_CLASS_C_DEC::const_point_iterator
+inline typename PB_DS_CLASS_C_DEC::point_const_iterator
 PB_DS_CLASS_C_DEC::
-find(const_key_reference r_key) const
+find(key_const_reference r_key) const
 {
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
-
   node_pointer p_pot = m_p_head;
   node_pointer p_nd = m_p_head->m_p_parent;
 
@@ -168,15 +155,17 @@ find(const_key_reference r_key) const
     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
       {
        p_pot = p_nd;
-
        p_nd = p_nd->m_p_left;
       }
     else
       p_nd = p_nd->m_p_right;
 
-  return const_point_iterator((p_pot != m_p_head
-                              && Cmp_Fn::operator()(r_key,
-                                                    PB_DS_V2F(p_pot->m_value)))
-                                       ? m_p_head : p_pot);
+  node_pointer ret = p_pot;
+  if (p_pot != m_p_head)
+    {
+      const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
+      if (__cmp)
+       ret = m_p_head;
+    }
+  return point_const_iterator(ret);
 }
-
index b3e4611..54cd52e 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file info_fn_imps.hpp
+ * @file bin_search_tree_/info_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
index eb0f76d..5a9a03e 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file insert_fn_imps.hpp
+ * @file bin_search_tree_/insert_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -101,38 +101,30 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
   if (left_nd)
     {
       _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == 0);
-      _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
-                                         PB_DS_V2F(r_value),
-                                         PB_DS_V2F(p_nd->m_value)));
+      _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(r_value),
+                                              PB_DS_V2F(p_nd->m_value)));
 
       p_nd->m_p_left = p_new_nd;
-
       if (m_p_head->m_p_left == p_nd)
        m_p_head->m_p_left = p_new_nd;
     }
   else
     {
       _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right == 0);
-      _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
-                                         PB_DS_V2F(p_nd->m_value),
-                                         PB_DS_V2F(r_value)));
+      _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
+                                              PB_DS_V2F(r_value)));
 
       p_nd->m_p_right = p_new_nd;
-
       if (m_p_head->m_p_right == p_nd)
        m_p_head->m_p_right = p_new_nd;
     }
 
   p_new_nd->m_p_parent = p_nd;
-
   p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
-
   PB_DS_ASSERT_NODE_CONSISTENT(p_nd)
 
   update_to_top(p_new_nd, (node_update* )this);
-
   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
-
   return iterator(p_new_nd);
 }
 
@@ -148,13 +140,10 @@ insert_imp_empty(const_reference r_value)
     m_p_head->m_p_parent = p_new_node;
 
   p_new_node->m_p_parent = m_p_head;
-
   p_new_node->m_p_left = p_new_node->m_p_right = 0;
-
   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
 
   update_to_top(m_p_head->m_p_parent, (node_update*)this);
-
   return iterator(p_new_node);
 }
 
@@ -164,18 +153,14 @@ PB_DS_CLASS_C_DEC::
 get_new_node_for_leaf_insert(const_reference r_val, false_type)
 {
   node_pointer p_new_nd = s_node_allocator.allocate(1);
-
   cond_dealtor_t cond(p_new_nd);
 
   new (const_cast<void* >(static_cast<const void* >(&p_new_nd->m_value)))
     typename node::value_type(r_val);
 
   cond.set_no_action();
-
   p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
-
   ++m_size;
-
   return p_new_nd;
 }
 
@@ -190,9 +175,6 @@ get_new_node_for_leaf_insert(const_reference r_val, true_type)
     typename node::value_type(r_val);
 
   p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
-
   ++m_size;
-
   return p_new_nd;
 }
-
index e5f6a4d..8076084 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file iterators_fn_imps.hpp
+ * @file bin_search_tree_/iterators_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -103,11 +103,11 @@ rend() const
 }
 
 PB_DS_CLASS_T_DEC
-inline typename PB_DS_CLASS_C_DEC::const_node_iterator
+inline typename PB_DS_CLASS_C_DEC::node_const_iterator
 PB_DS_CLASS_C_DEC::
 node_begin() const
 {
-  return (const_node_iterator(m_p_head->m_p_parent));
+  return (node_const_iterator(m_p_head->m_p_parent));
 }
 
 PB_DS_CLASS_T_DEC
@@ -119,11 +119,11 @@ node_begin()
 }
 
 PB_DS_CLASS_T_DEC
-inline typename PB_DS_CLASS_C_DEC::const_node_iterator
+inline typename PB_DS_CLASS_C_DEC::node_const_iterator
 PB_DS_CLASS_C_DEC::
 node_end() const
 {
-  return (const_node_iterator(0));
+  return (node_const_iterator(0));
 }
 
 PB_DS_CLASS_T_DEC
index b4ea453..d64bdf7 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file node_iterators.hpp
+ * @file bin_search_tree_/node_iterators.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -47,31 +47,27 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-
 #define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC                     \
     bin_search_tree_const_node_it_<                                    \
                                                        Node,           \
                                                        Const_Iterator, \
                                                        Iterator,       \
-                                                       Allocator>
+                                                       _Alloc>
 
-    // Const node iterator.
+    /// Const node iterator.
     template<typename Node,
             class Const_Iterator,
             class Iterator,
-            class Allocator>
+            typename _Alloc>
     class bin_search_tree_const_node_it_
     {
     private:
-
-    private:
       typedef
-      typename Allocator::template rebind<
+      typename _Alloc::template rebind<
       Node>::other::pointer
       node_pointer;
 
     public:
-
       // Category.
       typedef trivial_iterator_tag iterator_category;
 
@@ -92,11 +88,9 @@ namespace __gnu_pbds
 
       // Const metadata reference type.
       typedef
-      typename Allocator::template rebind<
+      typename _Alloc::template rebind<
        metadata_type>::other::const_reference
-      const_metadata_reference;
-
-    public:
+      metadata_const_reference;
 
       // Default constructor.
       /*
@@ -105,7 +99,8 @@ namespace __gnu_pbds
       */
 
       inline
-      bin_search_tree_const_node_it_(const node_pointer p_nd = 0) : m_p_nd(const_cast<node_pointer>(p_nd))
+      bin_search_tree_const_node_it_(const node_pointer p_nd = 0) 
+      : m_p_nd(const_cast<node_pointer>(p_nd))
       { }
 
       // Access.
@@ -116,7 +111,7 @@ namespace __gnu_pbds
       }
 
       // Metadata access.
-      inline const_metadata_reference
+      inline metadata_const_reference
       get_metadata() const
       {
        return (m_p_nd->get_metadata());
@@ -150,7 +145,6 @@ namespace __gnu_pbds
        return (m_p_nd != other.m_p_nd);
       }
 
-    public:
       node_pointer m_p_nd;
     };
 
@@ -159,26 +153,23 @@ namespace __gnu_pbds
                                                Node,           \
                                                Const_Iterator, \
                                                Iterator,       \
-                                               Allocator>
+                                               _Alloc>
 
-    // Node iterator.
+    /// Node iterator.
     template<typename Node,
             class Const_Iterator,
             class Iterator,
-            class Allocator>
-    class bin_search_tree_node_it_ : 
-      public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
-
+            typename _Alloc>
+    class bin_search_tree_node_it_ 
+    : public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
     {
-
     private:
       typedef
-      typename Allocator::template rebind<
+      typename _Alloc::template rebind<
       Node>::other::pointer
       node_pointer;
 
     public:
-
       // __Iterator's value type.
       typedef Iterator value_type;
 
@@ -188,8 +179,6 @@ namespace __gnu_pbds
       // __Iterator's __const reference type.
       typedef Iterator const_reference;
 
-    public:
-
       // Default constructor.
       /*
        inline
@@ -197,8 +186,8 @@ namespace __gnu_pbds
       */
 
       inline
-      bin_search_tree_node_it_(const node_pointer p_nd = 0) : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(
-                                                                                                           const_cast<node_pointer>(p_nd))
+      bin_search_tree_node_it_(const node_pointer p_nd = 0) 
+      : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(const_cast<node_pointer>(p_nd))
       { }
 
       // Access.
@@ -227,7 +216,6 @@ namespace __gnu_pbds
     };
 
 #undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
-
 #undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
 
   } // namespace detail
index 959df68..d999248 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file point_iterators.hpp
+ * @file bin_search_tree_/point_iterators.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -58,7 +58,7 @@ namespace __gnu_pbds
                                                Reference,              \
                                                Const_Reference,        \
                                                Is_Forward_Iterator,    \
-                                               Allocator>
+                                               _Alloc>
 
 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC                                 \
     bin_search_tree_const_it_<                                         \
@@ -69,7 +69,7 @@ namespace __gnu_pbds
                                                Reference,              \
                                                Const_Reference,        \
                                                !Is_Forward_Iterator,   \
-                                               Allocator>
+                                               _Alloc>
 
 #define PB_DS_TREE_IT_C_DEC                                            \
     bin_search_tree_it_<                                               \
@@ -80,7 +80,7 @@ namespace __gnu_pbds
                                                Reference,              \
                                                Const_Reference,        \
                                                Is_Forward_Iterator,    \
-                                               Allocator>
+                                               _Alloc>
 
 #define PB_DS_TREE_ODIR_IT_C_DEC                                       \
     bin_search_tree_it_<                                               \
@@ -91,9 +91,9 @@ namespace __gnu_pbds
                                                        Reference,      \
                                                        Const_Reference, \
                                                        !Is_Forward_Iterator, \
-                                                       Allocator>
+                                                       _Alloc>
 
-    // Const iterator.
+    /// Const iterator.
     template<typename Node_Pointer,
             typename Value_Type,
             typename Pointer,
@@ -101,27 +101,17 @@ namespace __gnu_pbds
             typename Reference,
             typename Const_Reference,
             bool Is_Forward_Iterator,
-            class Allocator>
+            typename _Alloc>
     class bin_search_tree_const_it_
     {
-
-    public:
-
-      typedef std::bidirectional_iterator_tag iterator_category;
-
-      typedef typename Allocator::difference_type difference_type;
-
-      typedef Value_Type value_type;
-
-      typedef Pointer pointer;
-
-      typedef Const_Pointer const_pointer;
-
-      typedef Reference reference;
-
-      typedef Const_Reference const_reference;
-
     public:
+      typedef std::bidirectional_iterator_tag          iterator_category;
+      typedef typename _Alloc::difference_type         difference_type;
+      typedef Value_Type                               value_type;
+      typedef Pointer                                  pointer;
+      typedef Const_Pointer                            const_pointer;
+      typedef Reference                                reference;
+      typedef Const_Reference                          const_reference;
 
       inline
       bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 
@@ -280,7 +270,7 @@ namespace __gnu_pbds
       Node_Pointer m_p_nd;
     };
 
-    // Iterator.
+    /// Iterator.
     template<typename Node_Pointer,
             typename Value_Type,
             typename Pointer,
@@ -288,14 +278,10 @@ namespace __gnu_pbds
             typename Reference,
             typename Const_Reference,
             bool Is_Forward_Iterator,
-            class Allocator>
-    class bin_search_tree_it_ : 
-      public PB_DS_TREE_CONST_IT_C_DEC
-
+            typename _Alloc>
+    class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
     {
-
     public:
-
       inline
       bin_search_tree_it_(const Node_Pointer p_nd = 0) 
       : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
index 63f307d..5b71c40 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file policy_access_fn_imps.hpp
+ * @file bin_search_tree_/policy_access_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -42,15 +42,11 @@ PB_DS_CLASS_T_DEC
 Cmp_Fn& 
 PB_DS_CLASS_C_DEC::
 get_cmp_fn()
-{
-  return (*this);
-}
+{ return (*this); }
 
 PB_DS_CLASS_T_DEC
 const Cmp_Fn& 
 PB_DS_CLASS_C_DEC::
 get_cmp_fn() const
-{
-  return (*this);
-}
+{ return (*this); }
 
index bcf3ce6..cfcccad 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file r_erase_fn_imps.hpp
+ * @file bin_search_tree_/r_erase_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -45,11 +45,8 @@ actual_erase_node(node_pointer p_z)
 {
   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   --m_size;
-
   _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value));)
-
   p_z->~node();
-
   s_node_allocator.deallocate(p_z, 1);
 }
 
@@ -61,24 +58,19 @@ update_min_max_for_erased_node(node_pointer p_z)
   if (m_size == 1)
     {
       m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
-
       return;
     }
 
   if (m_p_head->m_p_left == p_z)
     {
       iterator it(p_z);
-
       ++it;
-
       m_p_head->m_p_left = it.m_p_nd;
     }
   else if (m_p_head->m_p_right == p_z)
     {
       iterator it(p_z);
-
       --it;
-
       m_p_head->m_p_right = it.m_p_nd;
     }
 }
@@ -89,15 +81,10 @@ PB_DS_CLASS_C_DEC::
 clear()
 {
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
-
-    clear_imp(m_p_head->m_p_parent);
-
+  clear_imp(m_p_head->m_p_parent);
   m_size = 0;
-
   initialize();
-
   _GLIBCXX_DEBUG_ONLY(debug_base::clear();)
-
   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
 }
 
@@ -110,11 +97,7 @@ clear_imp(node_pointer p_nd)
     return;
 
   clear_imp(p_nd->m_p_left);
-
   clear_imp(p_nd->m_p_right);
-
   p_nd->~Node();
-
   s_node_allocator.deallocate(p_nd, 1);
 }
-
index c2090a1..63c757c 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file rotate_fn_imps.hpp
+ * @file bin_search_tree_/rotate_fn_imps.hpp
  * Contains imps for rotating nodes.
  */
 
@@ -130,7 +130,7 @@ PB_DS_CLASS_C_DEC::
 apply_update(node_pointer p_nd, Node_Update_*  /*p_update*/)
 {
   node_update::operator()(node_iterator(p_nd),
-                         const_node_iterator(static_cast<node_pointer>(0)));
+                         node_const_iterator(static_cast<node_pointer>(0)));
 }
 
 PB_DS_CLASS_T_DEC
index 00fbdf4..be2fd34 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file split_join_fn_imps.hpp
+ * @file bin_search_tree_/split_join_fn_imps.hpp
  * Contains an implementation class for bin_search_tree_.
  */
 
@@ -85,7 +85,7 @@ join_finish(PB_DS_CLASS_C_DEC& other)
 PB_DS_CLASS_T_DEC
 bool
 PB_DS_CLASS_C_DEC::
-split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
+split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)
 {
   PB_DS_ASSERT_VALID((*this))
   PB_DS_ASSERT_VALID(other)
index 58c30c3..3066c38 100644 (file)
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file traits.hpp
+ * @file bin_search_tree_/traits.hpp
  * Contains an implementation for bin_search_tree_.
  */
 
@@ -48,34 +48,28 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-
+    /// Binary search tree traits, primary template.
     template<typename Key,
             typename Mapped,
             class Cmp_Fn,
-            template<typename Const_Node_Iterator,
-                     class Node_Iterator,
+            template<typename Node_CItr,
+                     class Node_Itr,
                      class Cmp_Fn,
-                     class Allocator>
+                     typename _Alloc>
     class Node_Update,
             class Node,
-            class Allocator>
+            typename _Alloc>
     struct bin_search_tree_traits
     {
     private:
-      typedef
-      types_traits<
-      Key,
-      Mapped,
-      Allocator,
-      false>
-      type_traits;
+      typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
 
     public:
       typedef Node node;
 
       typedef
       bin_search_tree_const_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -83,12 +77,12 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        true,
-       Allocator>
-      const_point_iterator;
+       _Alloc>
+      point_const_iterator;
 
       typedef
       bin_search_tree_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -96,12 +90,12 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        true,
-       Allocator>
+       _Alloc>
       point_iterator;
 
       typedef
       bin_search_tree_const_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -109,12 +103,12 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        false,
-       Allocator>
+       _Alloc>
       const_reverse_iterator;
 
       typedef
       bin_search_tree_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -122,74 +116,69 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        false,
-       Allocator>
+       _Alloc>
       reverse_iterator;
 
       typedef
       bin_search_tree_const_node_it_<
        Node,
-       const_point_iterator,
+       point_const_iterator,
        point_iterator,
-       Allocator>
-      const_node_iterator;
+       _Alloc>
+      node_const_iterator;
 
       typedef
       bin_search_tree_node_it_<
        Node,
-       const_point_iterator,
+       point_const_iterator,
        point_iterator,
-       Allocator>
+       _Alloc>
       node_iterator;
 
       typedef
       Node_Update<
-       const_node_iterator,
+       node_const_iterator,
        node_iterator,
        Cmp_Fn,
-       Allocator>
+       _Alloc>
       node_update;
 
       typedef
-      __gnu_pbds::null_tree_node_update<
-       const_node_iterator,
+      __gnu_pbds::null_node_update<
+       node_const_iterator,
        node_iterator,
        Cmp_Fn,
-       Allocator>* 
+       _Alloc>* 
       null_node_update_pointer;
     };
 
+    /// Specialization.
     template<typename Key,
             class Cmp_Fn,
-            template<typename Const_Node_Iterator,
-                     class Node_Iterator,
+            template<typename Node_CItr,
+                     class Node_Itr,
                      class Cmp_Fn,
-                     class Allocator>
+                     typename _Alloc>
     class Node_Update,
             class Node,
-            class Allocator>
+            typename _Alloc>
     struct bin_search_tree_traits<
       Key,
-      null_mapped_type,
+      null_type,
       Cmp_Fn,
       Node_Update,
       Node,
-      Allocator>
+      _Alloc>
     {
     private:
-      typedef
-      types_traits<
-      Key,
-      null_mapped_type,
-      Allocator,
-      false>
-      type_traits;
+      typedef types_traits<Key, null_type, _Alloc, false> type_traits;
 
     public:
       typedef Node node;
 
       typedef
       bin_search_tree_const_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -197,14 +186,14 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        true,
-       Allocator>
-      const_point_iterator;
+       _Alloc>
+      point_const_iterator;
 
-      typedef const_point_iterator point_iterator;
+      typedef point_const_iterator point_iterator;
 
       typedef
       bin_search_tree_const_it_<
-       typename Allocator::template rebind<
+       typename _Alloc::template rebind<
        node>::other::pointer,
        typename type_traits::value_type,
        typename type_traits::pointer,
@@ -212,7 +201,7 @@ namespace __gnu_pbds
        typename type_traits::reference,
        typename type_traits::const_reference,
        false,
-       Allocator>
+       _Alloc>
       const_reverse_iterator;
 
       typedef const_reverse_iterator reverse_iterator;
@@ -220,27 +209,23 @@ namespace __gnu_pbds
       typedef
       bin_search_tree_const_node_it_<
        Node,
-       const_point_iterator,
+       point_const_iterator,
        point_iterator,
-       Allocator>
-      const_node_iterator;
+       _Alloc>
+      node_const_iterator;
 
-      typedef const_node_iterator node_iterator;
+      typedef node_const_iterator node_iterator;
 
       typedef
-      Node_Update<
-       const_node_iterator,
-       node_iterator,
-       Cmp_Fn,
-       Allocator>
+      Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
       node_update;
 
       typedef
-      __gnu_pbds::null_tree_node_update<
-       const_node_iterator,
+      __gnu_pbds::null_node_update<
+       node_const_iterator,
        node_iterator,
        Cmp_Fn,
-       Allocator>* 
+       _Alloc>* 
       null_node_update_pointer;
     };
 
index 4d65d2b..ee408e8 100644 (file)
 // warranty.
 
 /**
- * @file binary_heap_.hpp
+ * @file binary_heap_/binary_heap_.hpp
  * Contains an implementation class for a binary heap.
  */
 
 #ifndef PB_DS_BINARY_HEAP_HPP
 #define PB_DS_BINARY_HEAP_HPP
 
-/*
- * Based on CLRS.
- */
-
 #include <queue>
 #include <algorithm>
 #include <ext/pb_ds/detail/cond_dealtor.hpp>
@@ -53,7 +49,7 @@
 #include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>
 #include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>
 #include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>
-#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp>
+#include <ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp>
 #include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>
 #ifdef PB_DS_BINARY_HEAP_TRACE_
 #include <iostream>
@@ -66,126 +62,85 @@ namespace __gnu_pbds
   namespace detail
   {
 #define PB_DS_CLASS_T_DEC \
-    template<typename Value_Type, class Cmp_Fn, class Allocator>
+    template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
 
 #define PB_DS_CLASS_C_DEC \
-    binary_heap_<Value_Type, Cmp_Fn, Allocator>
+    binary_heap<Value_Type, Cmp_Fn, _Alloc>
 
 #define PB_DS_ENTRY_CMP_DEC \
-    entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type
+    entry_cmp<Value_Type, Cmp_Fn, _Alloc, is_simple<Value_Type>::value>::type
 
 #define PB_DS_RESIZE_POLICY_DEC        \
-    __gnu_pbds::detail::resize_policy<typename Allocator::size_type>
+    __gnu_pbds::detail::resize_policy<typename _Alloc::size_type>
 
     /**
-     * class description = "Base class for some types of h3ap$">
-     **/
-    template<typename Value_Type, class Cmp_Fn, class Allocator>
-    class binary_heap_ : public PB_DS_ENTRY_CMP_DEC,
-                        public PB_DS_RESIZE_POLICY_DEC
+     *  @brief Binary heaps composed of resize and compare policies.
+     *
+     *  Based on CLRS.
+     */
+    template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
+    class binary_heap
+    : public PB_DS_ENTRY_CMP_DEC, public PB_DS_RESIZE_POLICY_DEC
     {
+    public:
+      typedef Value_Type                               value_type;
+      typedef Cmp_Fn                                   cmp_fn;
+      typedef _Alloc                                   allocator_type;
+      typedef typename _Alloc::size_type               size_type;
+      typedef typename _Alloc::difference_type                 difference_type;
+      typedef typename PB_DS_ENTRY_CMP_DEC             entry_cmp;
+      typedef PB_DS_RESIZE_POLICY_DEC                  resize_policy;
+      typedef cond_dealtor<value_type, _Alloc>                 cond_dealtor_t;
 
     private:
       enum
        {
-         simple_value = is_simple<Value_Type>::value
+         simple_value = is_simple<value_type>::value
        };
 
-      typedef integral_constant<int, simple_value> no_throw_copies_t;
-
-      typedef
-      typename Allocator::template rebind<
-       Value_Type>::other
-      value_allocator;
-
-      typedef
-      typename __conditional_type<
-       simple_value,
-       Value_Type,
-       typename value_allocator::pointer>::__type
-      entry;
+      typedef integral_constant<int, simple_value>     no_throw_copies_t;
 
-      typedef
-      typename Allocator::template rebind<
-       entry>::other
-      entry_allocator;
-
-      typedef typename entry_allocator::pointer entry_pointer;
-
-      typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;
-
-      typedef PB_DS_RESIZE_POLICY_DEC resize_policy;
-
-      typedef
-      cond_dealtor<
-       Value_Type,
-       Allocator>
-      cond_dealtor_t;
+      typedef typename _Alloc::template rebind<value_type>     __rebind_v;
+      typedef typename __rebind_v::other               value_allocator;
 
     public:
+      typedef typename value_allocator::pointer                pointer;
+      typedef typename value_allocator::const_pointer  const_pointer;
+      typedef typename value_allocator::reference      reference;
+      typedef typename value_allocator::const_reference        const_reference;
 
-      typedef typename Allocator::size_type size_type;
-
-      typedef typename Allocator::difference_type difference_type;
+      typedef typename __conditional_type<simple_value,
+            &nbs