1// -*- C++ -*-
2
3// Copyright (C) 2005-2013 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file list_update_map_/lu_map_.hpp
38 * Contains a list update map.
39 */
40
41#include <utility>
42#include <iterator>
43#include <ext/pb_ds/detail/cond_dealtor.hpp>
44#include <ext/pb_ds/tag_and_trait.hpp>
45#include <ext/pb_ds/detail/types_traits.hpp>
46#include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
47#include <ext/pb_ds/exception.hpp>
48#ifdef _GLIBCXX_DEBUG
49#include <ext/pb_ds/detail/debug_map_base.hpp>
50#endif
51#ifdef PB_DS_LU_MAP_TRACE_
52#include <iostream>
53#endif
54#include <debug/debug.h>
55
56namespace __gnu_pbds
57{
58  namespace detail
59  {
60#ifdef PB_DS_DATA_TRUE_INDICATOR
61#define PB_DS_LU_NAME lu_map
62#endif
63
64#ifdef PB_DS_DATA_FALSE_INDICATOR
65#define PB_DS_LU_NAME lu_set
66#endif
67
68#define PB_DS_CLASS_T_DEC \
69    template<typename Key, typename Mapped, typename Eq_Fn, \
70	     typename _Alloc, typename Update_Policy>
71
72#define PB_DS_CLASS_C_DEC \
73    PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy>
74
75#define PB_DS_LU_TRAITS_BASE \
76    types_traits<Key, Mapped, _Alloc, false>
77
78#ifdef _GLIBCXX_DEBUG
79#define PB_DS_DEBUG_MAP_BASE_C_DEC \
80    debug_map_base<Key, Eq_Fn, \
81	      typename _Alloc::template rebind<Key>::other::const_reference>
82#endif
83
84    /// list-based (with updates) associative container.
85    /// Skip to the lu, my darling.
86    template<typename Key,
87	     typename Mapped,
88	     typename Eq_Fn,
89	     typename _Alloc,
90	     typename Update_Policy>
91    class PB_DS_LU_NAME :
92#ifdef _GLIBCXX_DEBUG
93      protected PB_DS_DEBUG_MAP_BASE_C_DEC,
94#endif
95      public PB_DS_LU_TRAITS_BASE
96    {
97    private:
98      typedef PB_DS_LU_TRAITS_BASE 	       	traits_base;
99
100      struct entry
101     : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
102      {
103	typename traits_base::value_type m_value;
104	typename _Alloc::template rebind<entry>::other::pointer m_p_next;
105      };
106
107      typedef typename _Alloc::template rebind<entry>::other entry_allocator;
108      typedef typename entry_allocator::pointer entry_pointer;
109      typedef typename entry_allocator::const_pointer const_entry_pointer;
110      typedef typename entry_allocator::reference entry_reference;
111      typedef typename entry_allocator::const_reference const_entry_reference;
112
113      typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
114      typedef typename entry_pointer_allocator::pointer entry_pointer_array;
115
116      typedef typename traits_base::value_type value_type_;
117      typedef typename traits_base::pointer pointer_;
118      typedef typename traits_base::const_pointer const_pointer_;
119      typedef typename traits_base::reference reference_;
120      typedef typename traits_base::const_reference const_reference_;
121
122#define PB_DS_GEN_POS entry_pointer
123
124#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
125#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
126#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
127#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
128
129#undef PB_DS_GEN_POS
130
131
132#ifdef _GLIBCXX_DEBUG
133      typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
134#endif
135
136      typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
137
138    public:
139      typedef _Alloc allocator_type;
140      typedef typename _Alloc::size_type size_type;
141      typedef typename _Alloc::difference_type difference_type;
142      typedef Eq_Fn eq_fn;
143      typedef Update_Policy update_policy;
144      typedef typename Update_Policy::metadata_type update_metadata;
145      typedef typename traits_base::key_type key_type;
146      typedef typename traits_base::key_pointer key_pointer;
147      typedef typename traits_base::key_const_pointer key_const_pointer;
148      typedef typename traits_base::key_reference key_reference;
149      typedef typename traits_base::key_const_reference key_const_reference;
150      typedef typename traits_base::mapped_type mapped_type;
151      typedef typename traits_base::mapped_pointer mapped_pointer;
152      typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
153      typedef typename traits_base::mapped_reference mapped_reference;
154      typedef typename traits_base::mapped_const_reference mapped_const_reference;
155      typedef typename traits_base::value_type value_type;
156      typedef typename traits_base::pointer pointer;
157      typedef typename traits_base::const_pointer const_pointer;
158      typedef typename traits_base::reference reference;
159      typedef typename traits_base::const_reference const_reference;
160
161#ifdef PB_DS_DATA_TRUE_INDICATOR
162      typedef point_iterator_ 			point_iterator;
163#endif
164
165#ifdef PB_DS_DATA_FALSE_INDICATOR
166      typedef point_const_iterator_ 		point_iterator;
167#endif
168
169      typedef point_const_iterator_ 		point_const_iterator;
170
171#ifdef PB_DS_DATA_TRUE_INDICATOR
172      typedef iterator_ 			iterator;
173#endif
174
175#ifdef PB_DS_DATA_FALSE_INDICATOR
176      typedef const_iterator_ 			iterator;
177#endif
178
179      typedef const_iterator_ 			const_iterator;
180
181    public:
182      PB_DS_LU_NAME();
183
184      PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&);
185
186      virtual
187      ~PB_DS_LU_NAME();
188
189      template<typename It>
190      PB_DS_LU_NAME(It, It);
191
192      void
193      swap(PB_DS_CLASS_C_DEC&);
194
195      inline size_type
196      size() const;
197
198      inline size_type
199      max_size() const;
200
201      inline bool
202      empty() const;
203
204      inline mapped_reference
205      operator[](key_const_reference r_key)
206      {
207#ifdef PB_DS_DATA_TRUE_INDICATOR
208	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
209	return insert(std::make_pair(r_key, mapped_type())).first->second;
210#else
211	insert(r_key);
212	return traits_base::s_null_type;
213#endif
214      }
215
216      inline std::pair<point_iterator, bool>
217      insert(const_reference);
218
219      inline point_iterator
220      find(key_const_reference r_key)
221      {
222	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
223	entry_pointer p_e = find_imp(r_key);
224	return point_iterator(p_e == 0 ? 0: &p_e->m_value);
225      }
226
227      inline point_const_iterator
228      find(key_const_reference r_key) const
229      {
230	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
231	entry_pointer p_e = find_imp(r_key);
232	return point_const_iterator(p_e == 0 ? 0: &p_e->m_value);
233      }
234
235      inline bool
236      erase(key_const_reference);
237
238      template<typename Pred>
239      inline size_type
240      erase_if(Pred);
241
242      void
243      clear();
244
245      inline iterator
246      begin();
247
248      inline const_iterator
249      begin() const;
250
251      inline iterator
252      end();
253
254      inline const_iterator
255      end() const;
256
257#ifdef _GLIBCXX_DEBUG
258      void
259      assert_valid(const char* file, int line) const;
260#endif
261
262#ifdef PB_DS_LU_MAP_TRACE_
263      void
264      trace() const;
265#endif
266
267    protected:
268
269      template<typename It>
270      void
271      copy_from_range(It, It);
272
273    private:
274#ifdef PB_DS_DATA_TRUE_INDICATOR
275      friend class iterator_;
276#endif
277
278      friend class const_iterator_;
279
280      inline entry_pointer
281      allocate_new_entry(const_reference, false_type);
282
283      inline entry_pointer
284      allocate_new_entry(const_reference, true_type);
285
286      template<typename Metadata>
287      inline static void
288      init_entry_metadata(entry_pointer, type_to_type<Metadata>);
289
290      inline static void
291      init_entry_metadata(entry_pointer, type_to_type<null_type>);
292
293      void
294      deallocate_all();
295
296      void
297      erase_next(entry_pointer);
298
299      void
300      actual_erase_entry(entry_pointer);
301
302      void
303      inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
304      {
305	r_pos = r_pos->m_p_next;
306	r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
307      }
308
309      template<typename Metadata>
310      inline static bool
311      apply_update(entry_pointer, type_to_type<Metadata>);
312
313      inline static bool
314      apply_update(entry_pointer, type_to_type<null_type>);
315
316      inline entry_pointer
317      find_imp(key_const_reference) const;
318
319      static entry_allocator 			s_entry_allocator;
320      static Eq_Fn 				s_eq_fn;
321      static Update_Policy 			s_update_policy;
322      static type_to_type<update_metadata> 	s_metadata_type_indicator;
323      static null_type 				s_null_type;
324
325      mutable entry_pointer 			m_p_l;
326    };
327
328#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
329#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
330#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
331#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
332#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
333#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
334#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
335#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
336
337#undef PB_DS_CLASS_T_DEC
338#undef PB_DS_CLASS_C_DEC
339#undef PB_DS_LU_TRAITS_BASE
340#undef PB_DS_DEBUG_MAP_BASE_C_DEC
341#undef PB_DS_LU_NAME
342  } // namespace detail
343} // namespace __gnu_pbds
344