1 /*
2 * Copyright (C) 2007-2008 Anael Orlinski
3 *
4 * This file is part of Panomatic.
5 *
6 * Panomatic is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * Panomatic is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with Panomatic; if not, write to the Free Software
18 * <http://www.gnu.org/licenses/>.
19 */
20
21 #ifndef __lfeat_sieve_h
22 #define __lfeat_sieve_h
23
24 #include "BoundedSet.h"
25
26 namespace lfeat
27 {
28
29 template <typename _Key>
30 class SieveExtractor
31 {
32 public:
33 virtual void operator()(const _Key& k) = 0;
34 };
35
36 template <typename _Key, typename _Compare = std::less<_Key> >
37 class Sieve
38 {
39
40 public:
41 Sieve(int iWidth, int iHeight, int iLength);
42 void insert(_Key& iElem, int iWidth, int iHeight);
43
44 // extract
45 void extract(SieveExtractor<_Key>& iEx);
46
47 private:
48 std::vector<lfeat::bounded_set< _Key, _Compare > > _buckets;
49 int _width, _height;
50
51
52 };
53
54 template <typename _Key, typename _Compare>
Sieve(int iWidth,int iHeight,int iLength)55 Sieve<_Key, _Compare>::Sieve(int iWidth, int iHeight, int iLength) :
56 _buckets(std::vector<bounded_set< _Key, _Compare > >(iWidth* iHeight)),
57 _width(iWidth), _height(iHeight)
58 {
59 typename std::vector<bounded_set< _Key, _Compare > >::iterator aVB, aVE;
60 aVB = _buckets.begin();
61 aVE = _buckets.end();
62 for (; aVB != aVE; ++aVB)
63 {
64 aVB->setMaxSize(iLength);
65 }
66 }
67
68 template <typename _Key, typename _Compare>
insert(_Key & iElem,int iWidth,int iHeight)69 void Sieve<_Key, _Compare>::insert(_Key& iElem, int iWidth, int iHeight)
70 {
71 _buckets[iWidth * _height + iHeight].insert(iElem);
72 }
73
74 template <typename _Key, typename _Compare>
extract(SieveExtractor<_Key> & iEx)75 void Sieve<_Key, _Compare>::extract(SieveExtractor<_Key>& iEx)
76 {
77 typename std::vector<bounded_set< _Key, _Compare > >::iterator aVB, aVE;
78 aVB = _buckets.begin();
79 aVE = _buckets.end();
80 for (; aVB != aVE; ++aVB)
81 {
82 typename std::set<_Key, _Compare>::iterator aSB, aSE;
83 std::set<_Key, _Compare>& aS = aVB->getSet();
84 aSB = aS.begin();
85 aSE = aS.end();
86 for (; aSB != aSE; ++aSB)
87 {
88 iEx(*aSB);
89 }
90 }
91 }
92
93 }
94
95 #endif // __lfeat_sieve_h
96