You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
114 lines
6.5 KiB
C++
114 lines
6.5 KiB
C++
// -*- c++ -*-
|
|
|
|
#pragma once
|
|
|
|
#include <xmemory>
|
|
#include <stdexcept>
|
|
|
|
// patch (multi_)?(map|set) to support is_transparent in find method
|
|
// other methods not patched...
|
|
|
|
// similiarities with some code in the original xtree is not a coincidence...
|
|
// it has these lovingly written copyright notices:
|
|
|
|
/*
|
|
* This file is derived from software bearing the following
|
|
* restrictions:
|
|
*
|
|
* Copyright (c) 1994
|
|
* Hewlett-Packard Company
|
|
*
|
|
* Permission to use, copy, modify, distribute and sell this
|
|
* software and its documentation for any purpose is hereby
|
|
* granted without fee, provided that the above copyright notice
|
|
* appear in all copies and that both that copyright notice and
|
|
* this permission notice appear in supporting documentation.
|
|
* Hewlett-Packard Company makes no representations about the
|
|
* suitability of this software for any purpose. It is provided
|
|
* "as is" without express or implied warranty.
|
|
*/
|
|
|
|
/*
|
|
* Copyright (c) 1992-2012 by P.J. Plauger. ALL RIGHTS RESERVED.
|
|
* Consult your license regarding permissions and restrictions.
|
|
V6.00:0009 */
|
|
|
|
|
|
// not noexcept because standard doesn't say it and std::less isn't noexcept
|
|
#define crend() __ignore_this_function_msvc_header_hack_move_along(); \
|
|
template <typename K, typename Comp = key_compare, \
|
|
typename = typename Comp::is_transparent> \
|
|
iterator find(const K& key) \
|
|
{ \
|
|
iterator it(transparent_lbound(key), this); \
|
|
if (it == end() || \
|
|
_DEBUG_LT_PRED(this->_Getcomp(), key, this->_Key(it._Mynode()))) \
|
|
return end(); \
|
|
return it; \
|
|
} \
|
|
template <typename K, typename Comp = key_compare, \
|
|
typename = typename Comp::is_transparent> \
|
|
const_iterator find(const K& key) const \
|
|
{ \
|
|
const_iterator it(transparent_lbound(key), this); \
|
|
if (it == end() || \
|
|
_DEBUG_LT_PRED(this->_Getcomp(), key, this->_Key(it._Mynode()))) \
|
|
return end(); \
|
|
return it; \
|
|
} \
|
|
private: \
|
|
template <typename K> \
|
|
_Nodeptr transparent_lbound(const K& k) const \
|
|
{ \
|
|
auto node = _Root(); \
|
|
auto head = _Myhead; /* aka end() */ \
|
|
while (!_Isnil(node)) \
|
|
if (_DEBUG_LT_PRED(_Getcomp(), _Key(node), k)) \
|
|
node = _Right(node); \
|
|
else \
|
|
{ \
|
|
head = node; \
|
|
node = _Left(node); \
|
|
} \
|
|
return head; \
|
|
} \
|
|
public: \
|
|
template <typename M> \
|
|
pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) \
|
|
{ \
|
|
auto it = lower_bound(k); \
|
|
if (it == end() || \
|
|
_DEBUG_LT_PRED(this->_Getcomp(), k, this->_Key(it._Mynode()))) \
|
|
{ \
|
|
/* not found, insert */ \
|
|
auto cit = emplace_hint(it, k, std::forward<M>(obj)); \
|
|
return pair<iterator, bool>(cit, true); \
|
|
} \
|
|
else \
|
|
{ \
|
|
it->second = std::forward<M>(obj); \
|
|
return pair<iterator, bool>(it, false); \
|
|
} \
|
|
} \
|
|
template <typename M> \
|
|
pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) \
|
|
{ \
|
|
auto it = lower_bound(k); \
|
|
if (it == end() || \
|
|
_DEBUG_LT_PRED(this->_Getcomp(), k, this->_Key(it._Mynode()))) \
|
|
{ \
|
|
/* not found, insert */ \
|
|
auto cit = insert(it, value_type(std::move(k), std::forward<M>(obj))); \
|
|
return pair<iterator, bool>(cit, true); \
|
|
} \
|
|
else \
|
|
{ \
|
|
it->second = std::forward<M>(obj); \
|
|
return pair<iterator, bool>(it, false); \
|
|
} \
|
|
} \
|
|
const_reverse_iterator crend() /* const _NOEXCEPT ... */
|
|
|
|
#include_next<xtree>
|
|
#undef crend
|