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 native_multimap.hpp
34 * Contains an adapter to std::multimap
35 */
36
37#ifndef PB_DS_NATIVE_MULTIMAP_HPP
38#define PB_DS_NATIVE_MULTIMAP_HPP
39
40#include <map>
41#include <string>
42#include <ext/pb_ds/detail/type_utils.hpp>
43#include <native_type/native_tree_tag.hpp>
44
45namespace __gnu_pbds
46{
47  namespace test
48  {
49#define PB_DS_BASE_C_DEC \
50    std::multimap<Key, Data, Less_Fn, \
51      typename _Alloc::template rebind<std::pair<const Key, Data> >::other>
52
53    template<typename Key, typename Data, class Less_Fn = std::less<Key>,
54	     typename _Alloc = std::allocator<char> >
55    class native_multimap : public PB_DS_BASE_C_DEC
56    {
57    private:
58      typedef PB_DS_BASE_C_DEC base_type;
59
60    public:
61      typedef native_tree_tag container_category;
62
63      typedef _Alloc allocator;
64
65      typedef
66      typename _Alloc::template rebind<
67	std::pair<Key, Data> >::other::const_reference
68      const_reference;
69
70      typedef typename base_type::iterator iterator;
71      typedef typename base_type::const_iterator const_iterator;
72
73      native_multimap()  { }
74
75      template<typename It>
76      native_multimap(It f, It l) : base_type(f, l)
77      { }
78
79      inline void
80      insert(const_reference r_val)
81      {
82        typedef std::pair<iterator, iterator> eq_range_t;
83        eq_range_t f = base_type::equal_range(r_val.first);
84
85        iterator it = f.first;
86        while (it != f.second)
87	  {
88            if (it->second == r_val.second)
89	      return;
90            ++it;
91	  }
92        base_type::insert(r_val);
93      }
94
95      inline iterator
96      find(const_reference r_val)
97      {
98        typedef std::pair<iterator, iterator> eq_range_t;
99        eq_range_t f = base_type::equal_range(r_val.first);
100
101        iterator it = f.first;
102        while (it != f.second)
103	  {
104            if (it->second == r_val.second)
105	      return it;
106            ++it;
107	  }
108
109        return base_type::end();
110      }
111
112      inline const_iterator
113      find(const_reference r_val) const
114      {
115        typedef std::pair<const_iterator, const_iterator> eq_range_t;
116        eq_range_t f = base_type::equal_range(r_val.first);
117
118        const_iterator it = f.first;
119        while (it != f.second)
120	  {
121            if (it->second == r_val.second)
122	      return it;
123            ++it;
124	  }
125        return base_type::end();
126      }
127
128      static std::string
129      name()
130      { return std::string("n_mmap"); }
131
132      static std::string
133      desc()
134      { return make_xml_tag("type", "value", "std_multimap"); }
135    };
136
137#undef PB_DS_BASE_C_DEC
138} // namespace test
139
140} // namespace __gnu_pbds
141
142#endif // #ifndef PB_DS_NATIVE_MULTIMAP_HPP
143