1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING3.  If not see
18// <http://www.gnu.org/licenses/>.
19
20
21// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
22
23// Permission to use, copy, modify, sell, and distribute this software
24// is hereby granted without fee, provided that the above copyright
25// notice appears in all copies, and that both that copyright notice
26// and this permission notice appear in supporting documentation. None
27// of the above authors, nor IBM Haifa Research Laboratories, make any
28// representation about the suitability of this software for any
29// purpose. It is provided "as is" without express or implied
30// warranty.
31
32/**
33 * @file assoc_container_traits_example.cpp
34 * A basic example showing how to use container_traits for querying container types
35 *    for their behavior.
36 */
37
38/**
39 * The following example shows how to use container_traits in order to print
40 * out information on an associative container's behavior, e.g., its underlying
41 * data structure, or whether its objects guarantee storing entries sorted
42 * by key order.
43 */
44
45#include <iostream>
46#include <ext/pb_ds/assoc_container.hpp>
47#include <ext/pb_ds/tag_and_trait.hpp>
48
49using namespace std;
50using namespace __gnu_pbds;
51
52template<class DS_Category>
53void
54print_container_category(DS_Category);
55
56template<>
57void
58print_container_category(cc_hash_tag)
59{
60  cout << "Collision-chaining hash based associative-container:" << endl;
61}
62
63template<>
64void
65print_container_category(gp_hash_tag)
66{
67  cout << "Probing hash based associative-container:" << endl;
68}
69
70template<>
71void
72print_container_category(rb_tree_tag)
73{
74  cout << "Red-black tree associative-container:" << endl;
75}
76
77template<>
78void
79print_container_category(splay_tree_tag)
80{
81  cout << "Splay tree associative-container:" << endl;
82}
83
84template<>
85void
86print_container_category(ov_tree_tag)
87{
88  cout << "Ordered-vector tree associative-container:" << endl;
89}
90
91template<>
92void
93print_container_category(list_update_tag)
94{
95  cout << "List-based associative-container:" << endl;
96}
97
98void
99print_erase_can_throw(bool can)
100{
101  if (can)
102    {
103      cout << "Erase can throw" << endl;
104      return;
105    }
106  cout << "Erase cannot throw" << endl;
107}
108
109void
110print_order_preserving(bool does)
111{
112  if (does)
113    {
114      cout << "Preserves order" << endl;
115      return;
116    }
117  cout << "Does not preserve order" << endl;
118}
119
120template<class Invalidation_Guarantee>
121void
122print_invalidation_guarantee(Invalidation_Guarantee);
123
124template<>
125void
126print_invalidation_guarantee(basic_invalidation_guarantee)
127{
128  cout << "Guarantees only that found references, pointers, and "
129    "iterators are valid as long as the container object is not "
130    "modified" << endl;
131}
132
133template<>
134void
135print_invalidation_guarantee(point_invalidation_guarantee)
136{
137  cout << "Guarantees that found references, pointers, and "
138    "point_iterators are valid even if the container object "
139    "is modified" << endl;
140}
141
142template<>
143void
144print_invalidation_guarantee(range_invalidation_guarantee)
145{
146  cout << "Guarantees that iterators remain valid even if the "
147    "container object is modified" << endl;
148}
149
150void
151print_reverse_iteration(bool does)
152{
153  if (does)
154    {
155      cout << "Supports reverse iteration" << endl;
156      return;
157    }
158  cout << "Does not support reverse iteration" << endl;
159}
160
161template<class DS_Traits>
162void
163print_container_attributes()
164{
165  // First print out the data structure category.
166  print_container_category(typename DS_Traits::container_category());
167
168  // Now print the attributes of the container.
169  print_erase_can_throw(DS_Traits::erase_can_throw);
170  print_order_preserving(DS_Traits::order_preserving);
171  print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee());
172  print_reverse_iteration(DS_Traits::reverse_iteration);
173
174  cout << endl << endl;
175}
176
177int
178main()
179{
180  {
181    // Print the attributes of a collision-chaining hash table.
182    typedef cc_hash_table< int, char> t;
183    print_container_attributes<container_traits<t> >();
184  }
185
186  {
187    // Print the attributes of a (general) probing hash table.
188    typedef gp_hash_table< int, char> t;
189    print_container_attributes<container_traits<t> >();
190  }
191
192  {
193    // Print the attributes of a red-black tree.
194    typedef tree< int, char> t;
195    print_container_attributes<container_traits<t> >();
196  }
197
198  {
199    // Print the attributes of a splay tree.
200    typedef
201      tree<
202      int,
203      char,
204      less<int>,
205      splay_tree_tag>
206      t;
207
208    print_container_attributes<container_traits<t> >();
209  }
210
211  {
212    // Print the attributes of an ordered-vector tree.
213    typedef
214      tree<
215      int,
216      char,
217      less<int>,
218      ov_tree_tag>
219      t;
220    print_container_attributes<container_traits<t> >();
221  }
222
223  {
224    // Print the attributes of an list-based container.
225    typedef list_update< int, char> t;
226    print_container_attributes<container_traits<t> >();
227  }
228
229  return 0;
230}
231