CLAM-Development  1.4.0
Search.hxx
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2001-2004 MUSIC TECHNOLOGY GROUP (MTG)
3  * UNIVERSITAT POMPEU FABRA
4  *
5  *
6  * This program 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  * This program 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 this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19  *
20  */
21 
22 #ifndef _Search_
23 #define _Search_
24 
25 #include "OSDefines.hxx"
26 #include "DataTypes.hxx"
27 
28 namespace CLAM {
29 
30 template <class U, class T> class Search
31 {
32 /* Based on locate() and hunt(), Numerical Recipes,second Edition, 117 */
33 private:
34  const U* mpData;
35 public:
37  {
38  mpData = NULL;
39  }
40  Search(const U& array)
41  {
42  Set(array);
43  }
45  {
46 
47  }
48  void Set(const U& array)
49  {
50  mpData = &array;
51  }
52  TIndex Find(const T& value,TIndex prevIndex=0) const
53  {
54  return Hunt(value,prevIndex);
55  }
56  TIndex Hunt(const T& value,TIndex prevIndex=0) const;
57 
58  TIndex Bisection(const T& value) const
59  {
60  return Bisection(value,0,mpData->Size());
61  }
62  TIndex Bisection(const T& value,TIndex lowerLimit) const
63  {
64  return Bisection(value,lowerLimit,mpData->Size());
65  }
66  TIndex Bisection(const T& value,TIndex lowerLimit,TIndex upperLimit) const;
67 
68 };
69 
70 template <class U, class T>
72  const T& value,TIndex guessIndex) const
73 {
74  TIndex result;
75  TIndex n = mpData->Size();
76  if (guessIndex<0 || guessIndex>=n)
77  {
78  return Bisection(value);
79  }
80  bool ascending = (*mpData)[n-1] >= (*mpData)[0];
81  TIndex inc = 1;
82  TIndex upperLimit;
83  if ( (value >= (*mpData)[guessIndex]) == ascending)
84  {
85  if (guessIndex == n-1)
86  return -1;//X.A. changed to -1 for consistency
87  upperLimit = guessIndex+1;
88  while ( (value >= (*mpData)[upperLimit]) == ascending)
89  {
90  guessIndex = upperLimit;
91  inc += inc;
92  upperLimit += inc;
93  if (upperLimit >= n) {
94  result=Bisection(value,guessIndex);
95  if(result==n-1) return -1;
96  else return result;
97  }
98  }
99  } else {
100  if (guessIndex==0) return -1;
101  upperLimit = guessIndex--;
102  while ( (value < (*mpData)[guessIndex]) == ascending)
103  {
104  upperLimit = guessIndex;
105  inc += inc;
106  if (inc >= upperLimit) {
107  result = Bisection(value,0,upperLimit);
108  if(result==0) return -1;
109  else return result;
110  }
111  guessIndex = upperLimit-inc;
112  }
113  }
114  return Bisection(value,guessIndex,upperLimit);
115 }
116 
117 template <class U, class T>
119  const T& value,TIndex lowerLimit,TIndex upperLimit) const
120 {
121  lowerLimit--;
122  bool ascending = (*mpData)[mpData->Size()-1] >= (*mpData)[0];
123  while (upperLimit-lowerLimit > 1)
124  {
125  TIndex midPoint = (upperLimit+lowerLimit)>>1;
126  if ( (value >= (*mpData)[midPoint]) == ascending)
127  lowerLimit = midPoint;
128  else
129  upperLimit = midPoint;
130  }
131  return lowerLimit;
132 }
133 
134 }
135 
136 #endif
137