9
3

map.hpp 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702
  1. /*-----------------------------------------------------------------------------+
  2. Copyright (c) 2007-2011: Joachim Faulhaber
  3. +------------------------------------------------------------------------------+
  4. Distributed under the Boost Software License, Version 1.0.
  5. (See accompanying file LICENCE.txt or copy at
  6. http://www.boost.org/LICENSE_1_0.txt)
  7. +-----------------------------------------------------------------------------*/
  8. #ifndef BOOST_ICL_MAP_HPP_JOFA_070519
  9. #define BOOST_ICL_MAP_HPP_JOFA_070519
  10. #include <boost/icl/impl_config.hpp>
  11. #if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION)
  12. # include <boost/container/map.hpp>
  13. # include <boost/container/set.hpp>
  14. #elif defined(ICL_USE_STD_IMPLEMENTATION)
  15. # include <map>
  16. # include <set>
  17. #else // Default for implementing containers
  18. # include <map>
  19. # include <set>
  20. #endif
  21. #include <string>
  22. #include <boost/call_traits.hpp>
  23. #include <boost/icl/detail/notate.hpp>
  24. #include <boost/icl/detail/design_config.hpp>
  25. #include <boost/icl/detail/concept_check.hpp>
  26. #include <boost/icl/detail/on_absorbtion.hpp>
  27. #include <boost/icl/type_traits/is_map.hpp>
  28. #include <boost/icl/type_traits/absorbs_identities.hpp>
  29. #include <boost/icl/type_traits/is_total.hpp>
  30. #include <boost/icl/type_traits/is_element_container.hpp>
  31. #include <boost/icl/type_traits/has_inverse.hpp>
  32. #include <boost/icl/associative_element_container.hpp>
  33. #include <boost/icl/functors.hpp>
  34. #include <boost/icl/type_traits/to_string.hpp>
  35. namespace boost{namespace icl
  36. {
  37. struct partial_absorber
  38. {
  39. enum { absorbs_identities = true };
  40. enum { is_total = false };
  41. };
  42. template<>
  43. inline std::string type_to_string<partial_absorber>::apply() { return "@0"; }
  44. struct partial_enricher
  45. {
  46. enum { absorbs_identities = false };
  47. enum { is_total = false };
  48. };
  49. template<>
  50. inline std::string type_to_string<partial_enricher>::apply() { return "e0"; }
  51. struct total_absorber
  52. {
  53. enum { absorbs_identities = true };
  54. enum { is_total = true };
  55. };
  56. template<>
  57. inline std::string type_to_string<total_absorber>::apply() { return "^0"; }
  58. struct total_enricher
  59. {
  60. enum { absorbs_identities = false };
  61. enum { is_total = true };
  62. };
  63. template<>
  64. inline std::string type_to_string<total_enricher>::apply() { return "e^0"; }
  65. /** \brief Addable, subractable and intersectable maps */
  66. template
  67. <
  68. typename DomainT,
  69. typename CodomainT,
  70. class Traits = icl::partial_absorber,
  71. ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
  72. ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
  73. ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
  74. ICL_ALLOC Alloc = std::allocator
  75. >
  76. class map: private ICL_IMPL_SPACE::map<DomainT, CodomainT, ICL_COMPARE_DOMAIN(Compare,DomainT),
  77. Alloc<std::pair<const DomainT, CodomainT> > >
  78. {
  79. public:
  80. typedef Alloc<typename std::pair<const DomainT, CodomainT> > allocator_type;
  81. typedef typename icl::map<DomainT,CodomainT,Traits, Compare,Combine,Section,Alloc> type;
  82. typedef typename ICL_IMPL_SPACE::map<DomainT, CodomainT, ICL_COMPARE_DOMAIN(Compare,DomainT),
  83. allocator_type> base_type;
  84. typedef Traits traits;
  85. public:
  86. typedef DomainT domain_type;
  87. typedef typename boost::call_traits<DomainT>::param_type domain_param;
  88. typedef DomainT key_type;
  89. typedef CodomainT codomain_type;
  90. typedef CodomainT mapped_type;
  91. typedef CodomainT data_type;
  92. typedef std::pair<const DomainT, CodomainT> element_type;
  93. typedef std::pair<const DomainT, CodomainT> value_type;
  94. typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
  95. typedef ICL_COMBINE_CODOMAIN(Combine,CodomainT) codomain_combine;
  96. typedef domain_compare key_compare;
  97. typedef ICL_COMPARE_DOMAIN(Compare,element_type) element_compare;
  98. typedef typename inverse<codomain_combine >::type inverse_codomain_combine;
  99. typedef typename mpl::if_
  100. <has_set_semantics<codomain_type>
  101. , ICL_SECTION_CODOMAIN(Section,CodomainT)
  102. , codomain_combine
  103. >::type codomain_intersect;
  104. typedef typename inverse<codomain_intersect>::type inverse_codomain_intersect;
  105. typedef typename base_type::value_compare value_compare;
  106. typedef typename ICL_IMPL_SPACE::set<DomainT, domain_compare, Alloc<DomainT> > set_type;
  107. typedef set_type key_object_type;
  108. BOOST_STATIC_CONSTANT(bool, _total = (Traits::is_total));
  109. BOOST_STATIC_CONSTANT(bool, _absorbs = (Traits::absorbs_identities));
  110. BOOST_STATIC_CONSTANT(bool,
  111. total_invertible = (mpl::and_<is_total<type>, has_inverse<codomain_type> >::value));
  112. typedef on_absorbtion<type,codomain_combine,Traits::absorbs_identities>
  113. on_identity_absorbtion;
  114. public:
  115. typedef typename base_type::pointer pointer;
  116. typedef typename base_type::const_pointer const_pointer;
  117. typedef typename base_type::reference reference;
  118. typedef typename base_type::const_reference const_reference;
  119. typedef typename base_type::iterator iterator;
  120. typedef typename base_type::const_iterator const_iterator;
  121. typedef typename base_type::size_type size_type;
  122. typedef typename base_type::difference_type difference_type;
  123. typedef typename base_type::reverse_iterator reverse_iterator;
  124. typedef typename base_type::const_reverse_iterator const_reverse_iterator;
  125. public:
  126. BOOST_STATIC_CONSTANT(bool,
  127. is_total_invertible = ( Traits::is_total
  128. && has_inverse<codomain_type>::value));
  129. BOOST_STATIC_CONSTANT(int, fineness = 4);
  130. public:
  131. //==========================================================================
  132. //= Construct, copy, destruct
  133. //==========================================================================
  134. map()
  135. {
  136. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
  137. BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
  138. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
  139. BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
  140. }
  141. map(const key_compare& comp): base_type(comp){}
  142. template <class InputIterator>
  143. map(InputIterator first, InputIterator past)
  144. : base_type(first,past){}
  145. template <class InputIterator>
  146. map(InputIterator first, InputIterator past, const key_compare& comp)
  147. : base_type(first,past,comp)
  148. {}
  149. map(const map& src)
  150. : base_type(src)
  151. {
  152. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
  153. BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
  154. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
  155. BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
  156. }
  157. explicit map(const element_type& key_value_pair): base_type::map()
  158. {
  159. insert(key_value_pair);
  160. }
  161. # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
  162. //==========================================================================
  163. //= Move semantics
  164. //==========================================================================
  165. map(map&& src)
  166. : base_type(boost::move(src))
  167. {
  168. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
  169. BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
  170. BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
  171. BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
  172. }
  173. map& operator = (map src)
  174. {
  175. base_type::operator=(boost::move(src));
  176. return *this;
  177. }
  178. //==========================================================================
  179. # else
  180. map& operator = (const map& src)
  181. {
  182. base_type::operator=(src);
  183. return *this;
  184. }
  185. # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
  186. void swap(map& src) { base_type::swap(src); }
  187. //==========================================================================
  188. using base_type::empty;
  189. using base_type::clear;
  190. using base_type::begin;
  191. using base_type::end;
  192. using base_type::rbegin;
  193. using base_type::rend;
  194. using base_type::size;
  195. using base_type::max_size;
  196. using base_type::key_comp;
  197. using base_type::value_comp;
  198. using base_type::erase;
  199. using base_type::find;
  200. using base_type::count;
  201. using base_type::lower_bound;
  202. using base_type::upper_bound;
  203. using base_type::equal_range;
  204. using base_type::operator[];
  205. public:
  206. //==========================================================================
  207. //= Containedness
  208. //==========================================================================
  209. template<class SubObject>
  210. bool contains(const SubObject& sub)const
  211. { return icl::contains(*this, sub); }
  212. bool within(const map& super)const
  213. { return icl::contains(super, *this); }
  214. //==========================================================================
  215. //= Size
  216. //==========================================================================
  217. /** \c iterative_size() yields the number of elements that is visited
  218. throu complete iteration. For interval sets \c iterative_size() is
  219. different from \c size(). */
  220. std::size_t iterative_size()const { return base_type::size(); }
  221. //==========================================================================
  222. //= Selection
  223. //==========================================================================
  224. /** Total select function. */
  225. codomain_type operator()(const domain_type& key)const
  226. {
  227. const_iterator it = find(key);
  228. return it==end() ? identity_element<codomain_type>::value()
  229. : it->second;
  230. }
  231. //==========================================================================
  232. //= Addition
  233. //==========================================================================
  234. /** \c add inserts \c value_pair into the map if it's key does
  235. not exist in the map.
  236. If \c value_pairs's key value exists in the map, it's data
  237. value is added to the data value already found in the map. */
  238. map& add(const value_type& value_pair)
  239. {
  240. return _add<codomain_combine>(value_pair);
  241. }
  242. /** \c add add \c value_pair into the map using \c prior as a hint to
  243. insert \c value_pair after the position \c prior is pointing to. */
  244. iterator add(iterator prior, const value_type& value_pair)
  245. {
  246. return _add<codomain_combine>(prior, value_pair);
  247. }
  248. //==========================================================================
  249. //= Subtraction
  250. //==========================================================================
  251. /** If the \c value_pair's key value is in the map, it's data value is
  252. subtraced from the data value stored in the map. */
  253. map& subtract(const element_type& value_pair)
  254. {
  255. on_invertible<type, is_total_invertible>
  256. ::subtract(*this, value_pair);
  257. return *this;
  258. }
  259. map& subtract(const domain_type& key)
  260. {
  261. icl::erase(*this, key);
  262. return *this;
  263. }
  264. //==========================================================================
  265. //= Insertion, erasure
  266. //==========================================================================
  267. std::pair<iterator,bool> insert(const value_type& value_pair)
  268. {
  269. if(on_identity_absorbtion::is_absorbable(value_pair.second))
  270. return std::pair<iterator,bool>(end(),true);
  271. else
  272. return base_type::insert(value_pair);
  273. }
  274. iterator insert(iterator prior, const value_type& value_pair)
  275. {
  276. if(on_identity_absorbtion::is_absorbable(value_pair.second))
  277. return end();
  278. else
  279. return base_type::insert(prior, value_pair);
  280. }
  281. template<class Iterator>
  282. iterator insert(Iterator first, Iterator last)
  283. {
  284. iterator prior = end(), it = first;
  285. while(it != last)
  286. prior = this->insert(prior, *it++);
  287. }
  288. /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
  289. map& set(const element_type& key_value_pair)
  290. {
  291. return icl::set_at(*this, key_value_pair);
  292. }
  293. /** erase \c key_value_pair from the map.
  294. Erase only if, the exact value content \c val is stored for the given key. */
  295. size_type erase(const element_type& key_value_pair)
  296. {
  297. return icl::erase(*this, key_value_pair);
  298. }
  299. //==========================================================================
  300. //= Intersection
  301. //==========================================================================
  302. /** The intersection of \c key_value_pair and \c *this map is added to \c section. */
  303. void add_intersection(map& section, const element_type& key_value_pair)const
  304. {
  305. on_definedness<type, Traits::is_total>
  306. ::add_intersection(section, *this, key_value_pair);
  307. }
  308. //==========================================================================
  309. //= Symmetric difference
  310. //==========================================================================
  311. map& flip(const element_type& operand)
  312. {
  313. on_total_absorbable<type,_total,_absorbs>::flip(*this, operand);
  314. return *this;
  315. }
  316. private:
  317. template<class Combiner>
  318. map& _add(const element_type& value_pair);
  319. template<class Combiner>
  320. iterator _add(iterator prior, const element_type& value_pair);
  321. template<class Combiner>
  322. map& _subtract(const element_type& value_pair);
  323. template<class FragmentT>
  324. void total_add_intersection(type& section, const FragmentT& fragment)const
  325. {
  326. section += *this;
  327. section.add(fragment);
  328. }
  329. void partial_add_intersection(type& section, const element_type& operand)const
  330. {
  331. const_iterator it_ = find(operand.first);
  332. if(it_ != end())
  333. {
  334. section.template _add<codomain_combine >(*it_);
  335. section.template _add<codomain_intersect>(operand);
  336. }
  337. }
  338. private:
  339. //--------------------------------------------------------------------------
  340. template<class Type, bool is_total_invertible>
  341. struct on_invertible;
  342. template<class Type>
  343. struct on_invertible<Type, true>
  344. {
  345. typedef typename Type::element_type element_type;
  346. typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
  347. static void subtract(Type& object, const element_type& operand)
  348. { object.template _add<inverse_codomain_combine>(operand); }
  349. };
  350. template<class Type>
  351. struct on_invertible<Type, false>
  352. {
  353. typedef typename Type::element_type element_type;
  354. typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
  355. static void subtract(Type& object, const element_type& operand)
  356. { object.template _subtract<inverse_codomain_combine>(operand); }
  357. };
  358. friend struct on_invertible<type, true>;
  359. friend struct on_invertible<type, false>;
  360. //--------------------------------------------------------------------------
  361. //--------------------------------------------------------------------------
  362. template<class Type, bool is_total>
  363. struct on_definedness;
  364. template<class Type>
  365. struct on_definedness<Type, true>
  366. {
  367. static void add_intersection(Type& section, const Type& object,
  368. const element_type& operand)
  369. { object.total_add_intersection(section, operand); }
  370. };
  371. template<class Type>
  372. struct on_definedness<Type, false>
  373. {
  374. static void add_intersection(Type& section, const Type& object,
  375. const element_type& operand)
  376. { object.partial_add_intersection(section, operand); }
  377. };
  378. friend struct on_definedness<type, true>;
  379. friend struct on_definedness<type, false>;
  380. //--------------------------------------------------------------------------
  381. //--------------------------------------------------------------------------
  382. template<class Type, bool has_set_semantics, bool absorbs_identities>
  383. struct on_codomain_model;
  384. template<class Type>
  385. struct on_codomain_model<Type, false, false>
  386. { // !codomain_is_set, !absorbs_identities
  387. static void subtract(Type&, typename Type::iterator it_,
  388. const typename Type::codomain_type& )
  389. { (*it_).second = identity_element<typename Type::codomain_type>::value(); }
  390. };
  391. template<class Type>
  392. struct on_codomain_model<Type, false, true>
  393. { // !codomain_is_set, absorbs_identities
  394. static void subtract(Type& object, typename Type::iterator it_,
  395. const typename Type::codomain_type& )
  396. { object.erase(it_); }
  397. };
  398. template<class Type>
  399. struct on_codomain_model<Type, true, false>
  400. { // !codomain_is_set, !absorbs_identities
  401. typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
  402. static void subtract(Type&, typename Type::iterator it_,
  403. const typename Type::codomain_type& co_value)
  404. {
  405. inverse_codomain_intersect()((*it_).second, co_value);
  406. }
  407. };
  408. template<class Type>
  409. struct on_codomain_model<Type, true, true>
  410. { // !codomain_is_set, absorbs_identities
  411. typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
  412. static void subtract(Type& object, typename Type::iterator it_,
  413. const typename Type::codomain_type& co_value)
  414. {
  415. inverse_codomain_intersect()((*it_).second, co_value);
  416. if((*it_).second == identity_element<codomain_type>::value())
  417. object.erase(it_);
  418. }
  419. };
  420. //--------------------------------------------------------------------------
  421. //--------------------------------------------------------------------------
  422. template<class Type, bool is_total, bool absorbs_identities>
  423. struct on_total_absorbable;
  424. template<class Type>
  425. struct on_total_absorbable<Type, true, true>
  426. {
  427. typedef typename Type::element_type element_type;
  428. static void flip(Type& object, const typename Type::element_type&)
  429. { icl::clear(object); }
  430. };
  431. template<class Type>
  432. struct on_total_absorbable<Type, true, false>
  433. {
  434. typedef typename Type::element_type element_type;
  435. typedef typename Type::codomain_type codomain_type;
  436. static void flip(Type& object, const element_type& operand)
  437. {
  438. object.add(operand);
  439. ICL_FORALL(typename Type, it_, object)
  440. (*it_).second = identity_element<codomain_type>::value();
  441. }
  442. };
  443. template<class Type>
  444. struct on_total_absorbable<Type, false, true>
  445. { // !is_total, absorbs_identities
  446. typedef typename Type::element_type element_type;
  447. typedef typename Type::codomain_type codomain_type;
  448. typedef typename Type::iterator iterator;
  449. typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
  450. static void flip(Type& object, const element_type& operand)
  451. {
  452. std::pair<iterator,bool> insertion = object.insert(operand);
  453. if(!insertion.second)
  454. on_codomain_model<Type, has_set_semantics<codomain_type>::value, true>
  455. ::subtract(object, insertion.first, operand.second);
  456. }
  457. };
  458. template<class Type>
  459. struct on_total_absorbable<Type, false, false>
  460. { // !is_total !absorbs_identities
  461. typedef typename Type::element_type element_type;
  462. typedef typename Type::codomain_type codomain_type;
  463. typedef typename Type::iterator iterator;
  464. typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
  465. static void flip(Type& object, const element_type& operand)
  466. {
  467. std::pair<iterator,bool> insertion = object.insert(operand);
  468. if(!insertion.second)
  469. on_codomain_model<Type, has_set_semantics<codomain_type>::value, false>
  470. ::subtract(object, insertion.first, operand.second);
  471. }
  472. };
  473. friend struct on_total_absorbable<type, true, true >;
  474. friend struct on_total_absorbable<type, false, true >;
  475. friend struct on_total_absorbable<type, true, false>;
  476. friend struct on_total_absorbable<type, false, false>;
  477. //--------------------------------------------------------------------------
  478. };
  479. //==============================================================================
  480. //= Addition<ElementMap>
  481. //==============================================================================
  482. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  483. template <class Combiner>
  484. map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
  485. map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
  486. ::_add(const element_type& addend)
  487. {
  488. typedef typename on_absorbtion
  489. <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
  490. const codomain_type& co_val = addend.second;
  491. if(on_absorbtion_::is_absorbable(co_val))
  492. return *this;
  493. std::pair<iterator,bool> insertion
  494. = base_type::insert(value_type(addend.first, version<Combiner>()(co_val)));
  495. if(!insertion.second)
  496. {
  497. iterator it = insertion.first;
  498. Combiner()((*it).second, co_val);
  499. if(on_absorbtion_::is_absorbable((*it).second))
  500. erase(it);
  501. }
  502. return *this;
  503. }
  504. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  505. template <class Combiner>
  506. typename map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::iterator
  507. map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>
  508. ::_add(iterator prior_, const value_type& addend)
  509. {
  510. typedef typename on_absorbtion
  511. <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
  512. const codomain_type& co_val = addend.second;
  513. if(on_absorbtion_::is_absorbable(co_val))
  514. return end();
  515. iterator inserted_
  516. = base_type::insert(prior_,
  517. value_type(addend.first, Combiner::identity_element()));
  518. Combiner()((*inserted_).second, addend.second);
  519. if(on_absorbtion_::is_absorbable((*inserted_).second))
  520. {
  521. erase(inserted_);
  522. return end();
  523. }
  524. else
  525. return inserted_;
  526. }
  527. //==============================================================================
  528. //= Subtraction<ElementMap>
  529. //==============================================================================
  530. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  531. template <class Combiner>
  532. map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>&
  533. map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>::_subtract(const value_type& minuend)
  534. {
  535. typedef typename on_absorbtion
  536. <type,Combiner,absorbs_identities<type>::value>::type on_absorbtion_;
  537. iterator it_ = find(minuend.first);
  538. if(it_ != end())
  539. {
  540. Combiner()((*it_).second, minuend.second);
  541. if(on_absorbtion_::is_absorbable((*it_).second))
  542. erase(it_);
  543. }
  544. return *this;
  545. }
  546. //-----------------------------------------------------------------------------
  547. // type traits
  548. //-----------------------------------------------------------------------------
  549. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  550. struct is_map<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
  551. {
  552. typedef is_map<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> > type;
  553. BOOST_STATIC_CONSTANT(bool, value = true);
  554. };
  555. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  556. struct has_inverse<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
  557. {
  558. typedef has_inverse<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> > type;
  559. BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
  560. };
  561. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  562. struct absorbs_identities<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
  563. {
  564. typedef absorbs_identities type;
  565. BOOST_STATIC_CONSTANT(int, value = Traits::absorbs_identities);
  566. };
  567. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  568. struct is_total<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
  569. {
  570. typedef is_total type;
  571. BOOST_STATIC_CONSTANT(int, value = Traits::is_total);
  572. };
  573. template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_ALLOC Alloc>
  574. struct type_to_string<icl::map<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc> >
  575. {
  576. static std::string apply()
  577. {
  578. return "map<"+ type_to_string<DomainT>::apply() + ","
  579. + type_to_string<CodomainT>::apply() + ","
  580. + type_to_string<Traits>::apply() +">";
  581. }
  582. };
  583. }} // namespace icl boost
  584. #endif // BOOST_ICL_MAP_HPP_JOFA_070519