Branch data Line data Source code
1 : : /*
2 : : * Copyright 2006-2009 Savarese Software Research Corporation
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at
7 : : *
8 : : * https://www.savarese.com/software/ApacheLicense-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : /**
18 : : * @file
19 : : * This header defines the CircularFind class.
20 : : */
21 : :
22 : : #ifndef __SSRC_WSPR_UTILITY_CIRCULAR_FIND_H
23 : : #define __SSRC_WSPR_UTILITY_CIRCULAR_FIND_H
24 : :
25 : : #include <algorithm>
26 : :
27 : : #include <ssrc/wispers-packages.h>
28 : :
29 : : __BEGIN_NS_SSRC_WSPR_UTILITY
30 : :
31 : : /**
32 : : * CircularFind is a function object for searching sequences that remembers
33 : : * and starts its search from the last position it visited. This allows it
34 : : * to perform searches in the manner of a circular linked list. Such
35 : : * linear searches are often more efficient than maps for a set of items
36 : : * less than 10 in number.
37 : : */
38 : : template<typename Iterator>
39 : : class CircularFind {
40 : :
41 : : Iterator _begin, _end;
42 : : mutable Iterator _pos;
43 : :
44 : : public:
45 : : typedef Iterator iterator;
46 : : typedef typename std::iterator_traits<iterator>::value_type value_type;
47 : :
48 : 4 : CircularFind(const iterator & begin, const iterator & end) :
49 : 4 : _begin(begin), _end(end), _pos(begin)
50 : 4 : { }
51 : :
52 : 2 : const iterator & begin() const {
53 : 2 : return _begin;
54 : : }
55 : :
56 : 7 : const iterator & end() const {
57 : 7 : return _end;
58 : : }
59 : :
60 : 9 : const iterator & find(const value_type & value) const {
61 : 9 : _pos = std::find(_pos, _end, value);
62 : :
63 [ + + + + ]: 9 : if(_pos == _end) {
64 : 6 : _pos = std::find(_begin, _end, value);
65 : :
66 [ + - + + ]: 6 : if(_pos == _end) {
67 : 2 : _pos = _begin;
68 : 2 : return _end;
69 : : }
70 : : }
71 : :
72 : 7 : return _pos;
73 : : }
74 : :
75 : : template<typename Predicate>
76 : 5 : const iterator & find_if(const Predicate & predicate) const {
77 : 5 : _pos = std::find_if(_pos, _end, predicate);
78 : :
79 [ + + ]: 5 : if(_pos == _end) {
80 : 4 : _pos = std::find_if(_begin, _end, predicate);
81 : :
82 [ - + ]: 4 : if(_pos == _end) {
83 : 0 : _pos = _begin;
84 : 0 : return _end;
85 : : }
86 : : }
87 : :
88 : 5 : return _pos;
89 : : }
90 : : };
91 : :
92 : : __END_NS_SSRC_WSPR_UTILITY
93 : :
94 : : #endif
|