1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 #ifndef ARY_SORTEDIDS_HXX 29 #define ARY_SORTEDIDS_HXX 30 31 32 // USED SERVICES 33 #include <algorithm> 34 #include <cosv/tpl/range.hxx> 35 36 37 38 39 namespace ary 40 { 41 42 43 /** Implementation of a set of children to an entity in the Autodoc 44 repository. The children are sorted. 45 46 @tpl COMPARE 47 Needs to provide types: 48 entity_base_type 49 id_type 50 key_type 51 52 and functions: 53 static entity_base_type & 54 EntityOf_( 55 id_type i_id ); 56 static const key_type & 57 KeyOf_( 58 const entity_type & i_entity ); 59 static bool Lesser_( 60 const key_type & i_1, 61 const key_type & i_2 ); 62 */ 63 template<class COMPARE> 64 class SortedIds 65 { 66 public: 67 typedef typename COMPARE::id_type element_t; 68 typedef typename COMPARE::key_type key_t; 69 typedef std::vector<element_t> data_t; 70 typedef typename data_t::const_iterator const_iterator; 71 typedef typename data_t::iterator iterator; 72 typedef csv::range<const_iterator> search_result_t; 73 74 // LIFECYCLE 75 explicit SortedIds( 76 std::size_t i_reserve = 0 ); 77 ~SortedIds(); 78 79 // OPERATIONS 80 void Add( 81 element_t i_elem ); 82 // INQUIRY 83 const_iterator Begin() const; 84 const_iterator End() const; 85 86 element_t Search( 87 const key_t & i_key ) const; 88 search_result_t SearchAll( 89 const key_t & i_key ) const; 90 const_iterator LowerBound( 91 const key_t & i_key ) const; 92 93 private: 94 typedef typename COMPARE::entity_base_type entity_t; 95 96 // Locals 97 iterator LowerBound( 98 const key_t & i_key ); 99 100 static const key_t & 101 KeyOf_( 102 element_t i_child ); 103 template <class ITER> 104 static ITER impl_LowerBound_( 105 ITER i_begin, 106 ITER i_end, 107 const key_t & i_key ); 108 109 // DATA 110 data_t aData; 111 }; 112 113 114 115 116 // IMPLEMENTATION 117 template<class COMPARE> 118 inline const typename SortedIds<COMPARE>::key_t & 119 SortedIds<COMPARE>::KeyOf_(element_t i_child) 120 { 121 return COMPARE::KeyOf_(COMPARE::EntityOf_(i_child)); 122 } 123 124 template<class COMPARE> 125 SortedIds<COMPARE>::SortedIds(std::size_t i_reserve) 126 : aData() 127 { 128 if (i_reserve > 0) 129 aData.reserve(i_reserve); 130 } 131 132 template<class COMPARE> 133 SortedIds<COMPARE>::~SortedIds() 134 { 135 } 136 137 template<class COMPARE> 138 void 139 SortedIds<COMPARE>::Add(element_t i_elem) 140 { 141 aData.insert( LowerBound( KeyOf_(i_elem) ), 142 i_elem ); 143 } 144 145 template<class COMPARE> 146 inline typename SortedIds<COMPARE>::const_iterator 147 SortedIds<COMPARE>::Begin() const 148 { 149 return aData.begin(); 150 } 151 152 template<class COMPARE> 153 inline typename SortedIds<COMPARE>::const_iterator 154 SortedIds<COMPARE>::End() const 155 { 156 return aData.end(); 157 } 158 159 template<class COMPARE> 160 typename SortedIds<COMPARE>::element_t 161 SortedIds<COMPARE>::Search(const key_t & i_key) const 162 { 163 const_iterator 164 ret = LowerBound(i_key); 165 return ret != aData.end() AND NOT COMPARE::Lesser_(i_key, KeyOf_(*ret)) 166 ? *ret 167 : element_t(0); 168 } 169 170 template<class COMPARE> 171 typename SortedIds<COMPARE>::search_result_t 172 SortedIds<COMPARE>::SearchAll(const key_t & i_key) const 173 { 174 const_iterator 175 r1 = LowerBound(i_key); 176 const_iterator 177 r2 = r1; 178 while ( r2 != aData.end() 179 AND NOT COMPARE::Lesser_(i_key, KeyOf_(*r2)) ) 180 { 181 ++r2; 182 } 183 184 return csv::make_range(r1,r2); 185 } 186 187 template<class COMPARE> 188 inline typename SortedIds<COMPARE>::const_iterator 189 SortedIds<COMPARE>::LowerBound(const key_t & i_key) const 190 { 191 return impl_LowerBound_( aData.begin(), 192 aData.end(), 193 i_key ); 194 } 195 196 template<class COMPARE> 197 inline typename SortedIds<COMPARE>::iterator 198 SortedIds<COMPARE>::LowerBound(const key_t & i_key) 199 { 200 return impl_LowerBound_( aData.begin(), 201 aData.end(), 202 i_key ); 203 } 204 205 template<class COMPARE> 206 template <class ITER> 207 ITER 208 SortedIds<COMPARE>::impl_LowerBound_( ITER i_begin, 209 ITER i_end, 210 const key_t & i_key ) 211 { 212 ITER i1 = i_begin; 213 ITER i2 = i_end; 214 215 for ( ITER it = i1 + (i2-i1)/2; 216 i1 != i2; 217 it = i1 + (i2-i1)/2 ) 218 { 219 if ( COMPARE::Lesser_(KeyOf_(*it), i_key) ) 220 { 221 i1 = it; 222 ++i1; 223 } 224 else 225 { 226 i2 = it; 227 } 228 } // end for 229 230 return i1; 231 } 232 233 234 235 236 } // namespace ary 237 #endif 238