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 &
KeyOf_(element_t i_child)115 SortedIds<COMPARE>::KeyOf_(element_t i_child)
116 {
117 return COMPARE::KeyOf_(COMPARE::EntityOf_(i_child));
118 }
119
120 template<class COMPARE>
SortedIds(std::size_t i_reserve)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>
~SortedIds()129 SortedIds<COMPARE>::~SortedIds()
130 {
131 }
132
133 template<class COMPARE>
134 void
Add(element_t i_elem)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
Begin() const143 SortedIds<COMPARE>::Begin() const
144 {
145 return aData.begin();
146 }
147
148 template<class COMPARE>
149 inline typename SortedIds<COMPARE>::const_iterator
End() const150 SortedIds<COMPARE>::End() const
151 {
152 return aData.end();
153 }
154
155 template<class COMPARE>
156 typename SortedIds<COMPARE>::element_t
Search(const key_t & i_key) const157 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
SearchAll(const key_t & i_key) const168 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
LowerBound(const key_t & i_key) const185 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
LowerBound(const key_t & i_key)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
impl_LowerBound_(ITER i_begin,ITER i_end,const key_t & i_key)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