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