source: NonGTP/Boost/boost/multi_index/detail/ord_index_ops.hpp @ 857

Revision 857, 3.4 KB checked in by igarcia, 18 years ago (diff)
Line 
1/* Copyright 2003-2005 Joaquín M López Muñoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
5 *
6 * See http://www.boost.org/libs/multi_index for library home page.
7 *
8 * The internal implementation of red-black trees is based on that of SGI STL
9 * stl_tree.h file:
10 *
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
13 *
14 * Permission to use, copy, modify, distribute and sell this software
15 * and its documentation for any purpose is hereby granted without fee,
16 * provided that the above copyright notice appear in all copies and
17 * that both that copyright notice and this permission notice appear
18 * in supporting documentation.  Silicon Graphics makes no
19 * representations about the suitability of this software for any
20 * purpose.  It is provided "as is" without express or implied warranty.
21 *
22 *
23 * Copyright (c) 1994
24 * Hewlett-Packard Company
25 *
26 * Permission to use, copy, modify, distribute and sell this software
27 * and its documentation for any purpose is hereby granted without fee,
28 * provided that the above copyright notice appear in all copies and
29 * that both that copyright notice and this permission notice appear
30 * in supporting documentation.  Hewlett-Packard Company makes no
31 * representations about the suitability of this software for any
32 * purpose.  It is provided "as is" without express or implied warranty.
33 *
34 */
35
36#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
37#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
38
39#if defined(_MSC_VER)&&(_MSC_VER>=1200)
40#pragma once
41#endif
42
43namespace boost{
44
45namespace multi_index{
46
47namespace detail{
48
49/* Common code for index memfuns having templatized and
50 * non-templatized versions.
51 */
52
53template<
54  typename Node,typename KeyFromValue,
55  typename CompatibleKey,typename CompatibleCompare
56>
57inline Node* ordered_index_find(
58  Node* header,const KeyFromValue& key,const CompatibleKey& x,
59  const CompatibleCompare& comp)
60{
61  Node* y=header;
62  Node* z=Node::from_impl(header->parent());
63   
64  while (z){
65    if(!comp(key(z->value),x)){
66      y=z;
67      z=Node::from_impl(z->left());
68    }
69    else z=Node::from_impl(z->right());
70  }
71   
72  return (y==header||comp(x,key(y->value)))?header:y;
73}
74
75template<
76  typename Node,typename KeyFromValue,
77  typename CompatibleKey,typename CompatibleCompare
78>
79inline Node* ordered_index_lower_bound(
80  Node* header,const KeyFromValue& key,const CompatibleKey& x,
81  const CompatibleCompare& comp)
82{
83  Node* y=header;
84  Node* z=Node::from_impl(header->parent());
85
86  while(z){
87    if(!comp(key(z->value),x)){
88      y=z;
89      z=Node::from_impl(z->left());
90    }
91    else z=Node::from_impl(z->right());
92  }
93
94  return y;
95}
96
97template<
98  typename Node,typename KeyFromValue,
99  typename CompatibleKey,typename CompatibleCompare
100>
101inline Node* ordered_index_upper_bound(
102  Node* header,const KeyFromValue& key,const CompatibleKey& x,
103  const CompatibleCompare& comp)
104{
105  Node* y=header;
106  Node* z=Node::from_impl(header->parent());
107
108  while(z){
109    if(comp(x,key(z->value))){
110      y=z;
111      z=Node::from_impl(z->left());
112    }
113    else z=Node::from_impl(z->right());
114  }
115
116  return y;
117}
118
119} /* namespace multi_index::detail */
120
121} /* namespace multi_index */
122
123} /* namespace boost */
124
125#endif
Note: See TracBrowser for help on using the repository browser.