xtree (6654B)
1 // -*- c++ -*- 2 3 #pragma once 4 5 #include <xmemory> 6 #include <stdexcept> 7 8 // patch (multi_)?(map|set) to support is_transparent in find method 9 // other methods not patched... 10 11 // similiarities with some code in the original xtree is not a coincidence... 12 // it has these lovingly written copyright notices: 13 14 /* 15 * This file is derived from software bearing the following 16 * restrictions: 17 * 18 * Copyright (c) 1994 19 * Hewlett-Packard Company 20 * 21 * Permission to use, copy, modify, distribute and sell this 22 * software and its documentation for any purpose is hereby 23 * granted without fee, provided that the above copyright notice 24 * appear in all copies and that both that copyright notice and 25 * this permission notice appear in supporting documentation. 26 * Hewlett-Packard Company makes no representations about the 27 * suitability of this software for any purpose. It is provided 28 * "as is" without express or implied warranty. 29 */ 30 31 /* 32 * Copyright (c) 1992-2012 by P.J. Plauger. ALL RIGHTS RESERVED. 33 * Consult your license regarding permissions and restrictions. 34 V6.00:0009 */ 35 36 37 // not noexcept because standard doesn't say it and std::less isn't noexcept 38 #define crend() __ignore_this_function_msvc_header_hack_move_along(); \ 39 template <typename K, typename Comp = key_compare, \ 40 typename = typename Comp::is_transparent> \ 41 iterator find(const K& key) \ 42 { \ 43 iterator it(transparent_lbound(key), this); \ 44 if (it == end() || \ 45 _DEBUG_LT_PRED(this->_Getcomp(), key, this->_Key(it._Mynode()))) \ 46 return end(); \ 47 return it; \ 48 } \ 49 template <typename K, typename Comp = key_compare, \ 50 typename = typename Comp::is_transparent> \ 51 const_iterator find(const K& key) const \ 52 { \ 53 const_iterator it(transparent_lbound(key), this); \ 54 if (it == end() || \ 55 _DEBUG_LT_PRED(this->_Getcomp(), key, this->_Key(it._Mynode()))) \ 56 return end(); \ 57 return it; \ 58 } \ 59 private: \ 60 template <typename K> \ 61 _Nodeptr transparent_lbound(const K& k) const \ 62 { \ 63 auto node = _Root(); \ 64 auto head = _Myhead; /* aka end() */ \ 65 while (!_Isnil(node)) \ 66 if (_DEBUG_LT_PRED(_Getcomp(), _Key(node), k)) \ 67 node = _Right(node); \ 68 else \ 69 { \ 70 head = node; \ 71 node = _Left(node); \ 72 } \ 73 return head; \ 74 } \ 75 public: \ 76 template <typename M> \ 77 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) \ 78 { \ 79 auto it = lower_bound(k); \ 80 if (it == end() || \ 81 _DEBUG_LT_PRED(this->_Getcomp(), k, this->_Key(it._Mynode()))) \ 82 { \ 83 /* not found, insert */ \ 84 auto cit = emplace_hint(it, k, std::forward<M>(obj)); \ 85 return pair<iterator, bool>(cit, true); \ 86 } \ 87 else \ 88 { \ 89 it->second = std::forward<M>(obj); \ 90 return pair<iterator, bool>(it, false); \ 91 } \ 92 } \ 93 template <typename M> \ 94 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) \ 95 { \ 96 auto it = lower_bound(k); \ 97 if (it == end() || \ 98 _DEBUG_LT_PRED(this->_Getcomp(), k, this->_Key(it._Mynode()))) \ 99 { \ 100 /* not found, insert */ \ 101 auto cit = insert(it, value_type(std::move(k), std::forward<M>(obj))); \ 102 return pair<iterator, bool>(cit, true); \ 103 } \ 104 else \ 105 { \ 106 it->second = std::forward<M>(obj); \ 107 return pair<iterator, bool>(it, false); \ 108 } \ 109 } \ 110 const_reverse_iterator crend() /* const _NOEXCEPT ... */ 111 112 #include_next<xtree> 113 #undef crend