CLAM-Development  1.4.0
SearchArray.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 _SearchArray_
23 #define _SearchArray_
24 
25 #include "OSDefines.hxx"
26 #include "DataTypes.hxx"
27 #include "Array.hxx"
28 
29 namespace CLAM {
30 
31 template <class T> class SearchArray
32 {
33 /* Based on locate() and hunt(), Numerical Recipes,second Edition, 117 */
34 private:
35  const Array<T>* mpArray;
36 public:
38  {
39  mpArray = NULL;
40  }
41  SearchArray(const Array<T>& array)
42  {
43  Set(array);
44  }
45 
47  {
48 
49  }
50  void Set(const Array<T>& array)
51  {
52  mpArray = &array;
53  }
54  TIndex Find(const T& value,TIndex prevIndex=0) const
55  {
56  return Hunt(value,prevIndex);
57  }
58  TIndex Hunt(const T& value,TIndex prevIndex=0) const;
59 
60  TIndex Bisection(const T& value) const
61  {
62  return Bisection(value,0,mpArray->Size());
63  }
64 
65  TIndex Bisection(const T& value,TIndex lowerLimit) const
66  {
67  return Bisection(value,lowerLimit,mpArray->Size());
68  }
69  TIndex Bisection(const T& value,TIndex lowerLimit,TIndex upperLimit) const;
70 
71 };
72 
73 template <class T>
75  const T& value,TIndex guessIndex) const
76 {
77  TIndex result;
78  TIndex n = mpArray->Size();
79 
80  if (guessIndex<0 || guessIndex>=n)
81  {
82  return Bisection(value);
83  }
84 
85  bool ascending = (*mpArray)[n-1] >= (*mpArray)[0];
86  TIndex inc = 1;
87  TIndex upperLimit;
88 
89  if ( (value >= (*mpArray)[guessIndex]) == ascending)
90  {
91  if (guessIndex == n-1)
92  return -1;//X.A. changed to -1 for consistency
93 
94  upperLimit = guessIndex+1;
95  while ( (value >= (*mpArray)[upperLimit]) == ascending)
96  {
97  guessIndex = upperLimit;
98  inc += inc;
99  upperLimit += inc;
100  if (upperLimit >= n)
101  {
102  result=Bisection(value,guessIndex);
103  if(result==n-1)
104  return -1;
105  else
106  return result;
107  }
108  }
109  }
110  else
111  {
112  if (guessIndex==0)
113  return -1;
114 
115  upperLimit = guessIndex--;
116  while ( (value < (*mpArray)[guessIndex]) == ascending)
117  {
118  upperLimit = guessIndex;
119  inc += inc;
120  if (inc >= upperLimit)
121  {
122  result = Bisection(value,0,upperLimit);
123 
124  if(result==0)
125  return -1;
126  else
127  return result;
128  }
129  guessIndex = upperLimit-inc;
130  }
131  }
132  return Bisection(value,guessIndex,upperLimit);
133 }
134 
135 template <class T>
137  const T& value,TIndex lowerLimit,TIndex upperLimit) const
138 {
139  lowerLimit--;
140  bool ascending = (*mpArray)[mpArray->Size()-1] >= (*mpArray)[0];
141  while (upperLimit-lowerLimit > 1)
142  {
143  TIndex midPoint = (upperLimit+lowerLimit)>>1;
144  if ( (value >= (*mpArray)[midPoint]) == ascending)
145  lowerLimit = midPoint;
146  else
147  upperLimit = midPoint;
148  }
149  return lowerLimit;
150 }
151 
152 }
153 
154 #endif
155