1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2007, 2009 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 multimap_find_test.hpp
34 * Contains a generic multimap_find_test test.
35 */
36
37#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
38#define PB_DS_MULTIMAP_INSERT_TEST_HPP
39
40#include <performance/time/timing_test_base.hpp>
41#include <performance/io/xml_formatter.hpp>
42#include <common_type/assoc/string_form.hpp>
43#include <iterator>
44
45namespace __gnu_pbds
46{
47  namespace test
48  {
49    namespace detail
50    {
51      template<typename It, class Cntnr, bool Native>
52      class multimap_find_functor
53      {
54      public:
55        multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
56	: m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
57	{ }
58
59	void
60        operator()(std::size_t resolution)
61	{
62	  size_t not_found_count = 0;
63	  typedef typename Cntnr::const_point_iterator iterator_type;
64	  for (std::size_t i = 0; i < resolution; ++i)
65	    {
66	      iterator_type end = m_r_container.end();
67	      for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
68		{
69		  iterator_type it = m_r_container.find(fnd_it->first);
70		  if (it == end ||
71		      it->second.find(fnd_it->second) == it->second.end())
72                    ++not_found_count;
73		}
74	    }
75
76	  if (not_found_count != 0)
77            std::abort();
78	}
79
80      private:
81	const Cntnr& m_r_container;
82	const It m_fnd_it_b;
83	const It m_fnd_it_e;
84      };
85
86      template<typename It, class Cntnr>
87      class multimap_find_functor<It, Cntnr, true>
88      {
89      public:
90        multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
91	: m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
92	{ }
93
94	void
95        operator()(std::size_t resolution)
96	{
97	  typedef typename Cntnr::const_reference const_reference;
98	  size_t not_found_count = 0;
99	  for (std::size_t i = 0; i < resolution; ++i)
100	    {
101	      Cntnr cntnr;
102	      for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
103                if (m_r_container.find(const_reference(*fnd_it))
104		    == m_r_container.end())
105		  ++not_found_count;
106	    }
107
108	  if (not_found_count != 0)
109            std::abort();
110	}
111
112      private:
113	const Cntnr& m_r_container;
114	const It m_fnd_it_b;
115	const It m_fnd_it_e;
116      };
117    } // namespace detail
118
119
120    template<typename It, bool Native>
121    class multimap_find_test
122    : private __gnu_pbds::test::detail::timing_test_base
123    {
124    public:
125      multimap_find_test(It ins_b, size_t ins_vn, size_t vs, size_t ins_vm)
126      : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(vs), m_ins_vm(ins_vm)
127      { }
128
129      template<typename Cntnr>
130      void
131      operator()(Cntnr);
132
133    private:
134      multimap_find_test(const multimap_find_test&);
135
136      template<typename Cntnr>
137      Cntnr
138      init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::true_type)
139      { return Cntnr(ins_b, ins_e); }
140
141      template<typename Cntnr>
142      Cntnr
143      init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::false_type)
144      {
145	Cntnr ret;
146	for (It it = ins_b; it != ins_e; ++it)
147	  ret[it->first].insert(it->second);
148	return ret;
149      }
150
151      const It m_ins_b;
152      const size_t m_ins_vn;
153      const size_t m_ins_vs;
154      const size_t m_ins_vm;
155    };
156
157
158    template<typename It, bool Native>
159    template<typename Cntnr>
160    void
161    multimap_find_test<It, Native>::
162    operator()(Cntnr)
163    {
164      typedef xml_result_set_performance_formatter formatter_type;
165      formatter_type res_set_fmt(string_form<Cntnr>::name(),
166				 string_form<Cntnr>::desc());
167
168      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
169	{
170	  const size_t v = m_ins_vn + i * m_ins_vs;
171	  It ins_it_b = m_ins_b;
172	  It ins_it_e = m_ins_b;
173	  std::advance(ins_it_e, v);
174
175	  Cntnr c = init(ins_it_b, ins_it_e, Cntnr(),
176			 __gnu_pbds::detail::integral_constant<int,Native>());
177
178	  __gnu_pbds::test::detail::multimap_find_functor<It, Cntnr, Native>
179            fn(c, ins_it_b, ins_it_e);
180
181	  const double res =
182            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
183
184	  res_set_fmt.add_res(v, res / v);
185	}
186    }
187  } // namespace test
188} // namespace __gnu_pbds
189
190#endif
191
192