Search.hxx

Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2001-2004 MUSIC TECHNOLOGY GROUP (MTG)
00003  *                         UNIVERSITAT POMPEU FABRA
00004  *
00005  *
00006  * This program is free software; you can redistribute it and/or modify
00007  * it under the terms of the GNU General Public License as published by
00008  * the Free Software Foundation; either version 2 of the License, or
00009  * (at your option) any later version.
00010  *
00011  * This program is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  * GNU General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with this program; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019  *
00020  */
00021 
00022 #ifndef _Search_
00023 #define _Search_
00024 
00025 #include "OSDefines.hxx"
00026 #include "DataTypes.hxx"
00027 
00028 namespace CLAM {
00029 
00030 template <class U, class T> class Search
00031 {
00032 /* Based on locate() and hunt(), Numerical Recipes,second Edition, 117 */
00033 private:
00034         const U* mpData;
00035 public:
00036         Search()
00037         {
00038                 mpData = NULL;
00039         }
00040         Search(const U& array)
00041         {
00042                 Set(array);
00043         }
00044         ~Search()
00045         {
00046 
00047         }
00048         void Set(const U& array)
00049         {
00050                 mpData = &array;
00051         }
00052         TIndex Find(const T& value,TIndex prevIndex=0) const
00053         {
00054                 return Hunt(value,prevIndex);
00055         }
00056         TIndex Hunt(const T& value,TIndex prevIndex=0) const;
00057         
00058         TIndex Bisection(const T& value) const
00059         {
00060                 return Bisection(value,0,mpData->Size());
00061         }
00062         TIndex Bisection(const T& value,TIndex lowerLimit) const
00063         {
00064                 return Bisection(value,lowerLimit,mpData->Size());
00065         }
00066         TIndex Bisection(const T& value,TIndex lowerLimit,TIndex upperLimit) const;
00067 
00068 };
00069 
00070 template <class U, class T> 
00071         inline TIndex Search<U,T>::Hunt(
00072                 const T& value,TIndex guessIndex) const
00073 {
00074         TIndex result;
00075         TIndex n = mpData->Size();
00076         if (guessIndex<0 || guessIndex>=n)
00077         {
00078                 return Bisection(value);
00079         }
00080         bool ascending = (*mpData)[n-1] >= (*mpData)[0];
00081         TIndex inc = 1;
00082         TIndex upperLimit;
00083         if ( (value >= (*mpData)[guessIndex]) == ascending)
00084         {
00085                 if (guessIndex == n-1)
00086                         return -1;//X.A. changed to -1 for consistency
00087                 upperLimit = guessIndex+1;
00088                 while ( (value >= (*mpData)[upperLimit]) == ascending)
00089                 {
00090                         guessIndex = upperLimit;
00091                         inc += inc;
00092                         upperLimit += inc;
00093                         if (upperLimit >= n) {
00094                                 result=Bisection(value,guessIndex);
00095                                 if(result==n-1) return -1;
00096                                 else return result;
00097                         }
00098                 }
00099         } else {
00100                 if (guessIndex==0) return -1;
00101                 upperLimit = guessIndex--;
00102                 while ( (value < (*mpData)[guessIndex]) == ascending)
00103                 {
00104                         upperLimit = guessIndex;
00105                         inc += inc;
00106                         if (inc >= upperLimit) {
00107                                 result = Bisection(value,0,upperLimit);
00108                                 if(result==0) return -1;
00109                                 else return result;
00110                         }
00111                         guessIndex = upperLimit-inc;
00112                 }
00113         }
00114         return Bisection(value,guessIndex,upperLimit);
00115 }
00116 
00117 template <class U, class T> 
00118         inline TIndex Search<U,T>::Bisection(
00119                 const T& value,TIndex lowerLimit,TIndex upperLimit) const
00120 {
00121         lowerLimit--;
00122         bool ascending = (*mpData)[mpData->Size()-1] >= (*mpData)[0];
00123         while (upperLimit-lowerLimit > 1)
00124         {
00125                 TIndex midPoint = (upperLimit+lowerLimit)>>1;
00126                 if ( (value >= (*mpData)[midPoint]) == ascending)
00127                         lowerLimit = midPoint;
00128                 else
00129                         upperLimit = midPoint;
00130         }
00131         return lowerLimit;
00132 }
00133 
00134 }
00135 
00136 #endif
00137 
Generated by  doxygen 1.6.3