1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 #ifndef ARY_SORTEDIDS_HXX 25 #define ARY_SORTEDIDS_HXX 26 27 28 // USED SERVICES 29 #include <algorithm> 30 #include <cosv/tpl/range.hxx> 31 32 33 34 35 namespace ary 36 { 37 38 39 /** Implementation of a set of children to an entity in the Autodoc 40 repository. The children are sorted. 41 42 @tpl COMPARE 43 Needs to provide types: 44 entity_base_type 45 id_type 46 key_type 47 48 and functions: 49 static entity_base_type & 50 EntityOf_( 51 id_type i_id ); 52 static const key_type & 53 KeyOf_( 54 const entity_type & i_entity ); 55 static bool Lesser_( 56 const key_type & i_1, 57 const key_type & i_2 ); 58 */ 59 template<class COMPARE> 60 class SortedIds 61 { 62 public: 63 typedef typename COMPARE::id_type element_t; 64 typedef typename COMPARE::key_type key_t; 65 typedef std::vector<element_t> data_t; 66 typedef typename data_t::const_iterator const_iterator; 67 typedef typename data_t::iterator iterator; 68 typedef csv::range<const_iterator> search_result_t; 69 70 // LIFECYCLE 71 explicit SortedIds( 72 std::size_t i_reserve = 0 ); 73 ~SortedIds(); 74 75 // OPERATIONS 76 void Add( 77 element_t i_elem ); 78 // INQUIRY 79 const_iterator Begin() const; 80 const_iterator End() const; 81 82 element_t Search( 83 const key_t & i_key ) const; 84 search_result_t SearchAll( 85 const key_t & i_key ) const; 86 const_iterator LowerBound( 87 const key_t & i_key ) const; 88 89 private: 90 typedef typename COMPARE::entity_base_type entity_t; 91 92 // Locals 93 iterator LowerBound( 94 const key_t & i_key ); 95 96 static const key_t & 97 KeyOf_( 98 element_t i_child ); 99 template <class ITER> 100 static ITER impl_LowerBound_( 101 ITER i_begin, 102 ITER i_end, 103 const key_t & i_key ); 104 105 // DATA 106 data_t aData; 107 }; 108 109 110 111 112 // IMPLEMENTATION 113 template<class COMPARE> 114 inline const typename SortedIds<COMPARE>::key_t & 115 SortedIds<COMPARE>::KeyOf_(element_t i_child) 116 { 117 return COMPARE::KeyOf_(COMPARE::EntityOf_(i_child)); 118 } 119 120 template<class COMPARE> 121 SortedIds<COMPARE>::SortedIds(std::size_t i_reserve) 122 : aData() 123 { 124 if (i_reserve > 0) 125 aData.reserve(i_reserve); 126 } 127 128 template<class COMPARE> 129 SortedIds<COMPARE>::~SortedIds() 130 { 131 } 132 133 template<class COMPARE> 134 void 135 SortedIds<COMPARE>::Add(element_t i_elem) 136 { 137 aData.insert( LowerBound( KeyOf_(i_elem) ), 138 i_elem ); 139 } 140 141 template<class COMPARE> 142 inline typename SortedIds<COMPARE>::const_iterator 143 SortedIds<COMPARE>::Begin() const 144 { 145 return aData.begin(); 146 } 147 148 template<class COMPARE> 149 inline typename SortedIds<COMPARE>::const_iterator 150 SortedIds<COMPARE>::End() const 151 { 152 return aData.end(); 153 } 154 155 template<class COMPARE> 156 typename SortedIds<COMPARE>::element_t 157 SortedIds<COMPARE>::Search(const key_t & i_key) const 158 { 159 const_iterator 160 ret = LowerBound(i_key); 161 return ret != aData.end() AND NOT COMPARE::Lesser_(i_key, KeyOf_(*ret)) 162 ? *ret 163 : element_t(0); 164 } 165 166 template<class COMPARE> 167 typename SortedIds<COMPARE>::search_result_t 168 SortedIds<COMPARE>::SearchAll(const key_t & i_key) const 169 { 170 const_iterator 171 r1 = LowerBound(i_key); 172 const_iterator 173 r2 = r1; 174 while ( r2 != aData.end() 175 AND NOT COMPARE::Lesser_(i_key, KeyOf_(*r2)) ) 176 { 177 ++r2; 178 } 179 180 return csv::make_range(r1,r2); 181 } 182 183 template<class COMPARE> 184 inline typename SortedIds<COMPARE>::const_iterator 185 SortedIds<COMPARE>::LowerBound(const key_t & i_key) const 186 { 187 return impl_LowerBound_( aData.begin(), 188 aData.end(), 189 i_key ); 190 } 191 192 template<class COMPARE> 193 inline typename SortedIds<COMPARE>::iterator 194 SortedIds<COMPARE>::LowerBound(const key_t & i_key) 195 { 196 return impl_LowerBound_( aData.begin(), 197 aData.end(), 198 i_key ); 199 } 200 201 template<class COMPARE> 202 template <class ITER> 203 ITER 204 SortedIds<COMPARE>::impl_LowerBound_( ITER i_begin, 205 ITER i_end, 206 const key_t & i_key ) 207 { 208 ITER i1 = i_begin; 209 ITER i2 = i_end; 210 211 for ( ITER it = i1 + (i2-i1)/2; 212 i1 != i2; 213 it = i1 + (i2-i1)/2 ) 214 { 215 if ( COMPARE::Lesser_(KeyOf_(*it), i_key) ) 216 { 217 i1 = it; 218 ++i1; 219 } 220 else 221 { 222 i2 = it; 223 } 224 } // end for 225 226 return i1; 227 } 228 229 230 231 232 } // namespace ary 233 #endif 234