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.
77 lines
4.2 KiB
C++
77 lines
4.2 KiB
C++
// -*- c++ -*-
|
|
|
|
#pragma once
|
|
|
|
// 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: \
|
|
const_reverse_iterator crend() /* const _NOEXCEPT ... */
|
|
|
|
#include_next<xtree>
|
|
#undef crend
|