SearchArray.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 _SearchArray_
00023 #define _SearchArray_
00024 
00025 #include "OSDefines.hxx"
00026 #include "DataTypes.hxx"
00027 #include "Array.hxx"
00028 
00029 namespace CLAM {
00030 
00031 template <class T> class SearchArray
00032 {
00033 /* Based on locate() and hunt(), Numerical Recipes,second Edition, 117 */
00034 private:
00035         const Array<T>* mpArray;
00036 public:
00037         SearchArray()
00038         {
00039                 mpArray = NULL;
00040         }
00041         SearchArray(const Array<T>& array)
00042         {
00043                 Set(array);
00044         }
00045 
00046         ~SearchArray()
00047         {
00048 
00049         }
00050         void Set(const Array<T>& array)
00051         {
00052                 mpArray = &array;
00053         }
00054         TIndex Find(const T& value,TIndex prevIndex=0) const
00055         {
00056                 return Hunt(value,prevIndex);
00057         }
00058         TIndex Hunt(const T& value,TIndex prevIndex=0) const;
00059 
00060         TIndex Bisection(const T& value) const
00061         {
00062                 return Bisection(value,0,mpArray->Size());
00063         }
00064 
00065         TIndex Bisection(const T& value,TIndex lowerLimit) const
00066         {
00067                 return Bisection(value,lowerLimit,mpArray->Size());
00068         }
00069         TIndex Bisection(const T& value,TIndex lowerLimit,TIndex upperLimit) const;
00070 
00071 };
00072 
00073 template <class T> 
00074         inline TIndex SearchArray<T>::Hunt(
00075                 const T& value,TIndex guessIndex) const
00076 {
00077         TIndex result;
00078         TIndex n = mpArray->Size();
00079 
00080         if (guessIndex<0 || guessIndex>=n)
00081         {
00082                 return Bisection(value);
00083         }
00084 
00085         bool ascending = (*mpArray)[n-1] >= (*mpArray)[0];
00086         TIndex inc = 1;
00087         TIndex upperLimit;
00088 
00089         if ( (value >= (*mpArray)[guessIndex]) == ascending)
00090         {
00091                 if (guessIndex == n-1)
00092                         return -1;//X.A. changed to -1 for consistency
00093 
00094                 upperLimit = guessIndex+1;
00095                 while ( (value >= (*mpArray)[upperLimit]) == ascending)
00096                 {
00097                         guessIndex = upperLimit;
00098                         inc += inc;
00099                         upperLimit += inc;
00100                         if (upperLimit >= n) 
00101                         {
00102                                 result=Bisection(value,guessIndex);
00103                                 if(result==n-1) 
00104                                         return -1;
00105                                 else 
00106                                         return result;
00107                         }
00108                 }
00109         } 
00110         else 
00111         {
00112                 if (guessIndex==0) 
00113                         return -1;
00114                 
00115                 upperLimit = guessIndex--;
00116                 while ( (value < (*mpArray)[guessIndex]) == ascending)
00117                 {
00118                         upperLimit = guessIndex;
00119                         inc += inc;
00120                         if (inc >= upperLimit) 
00121                         {
00122                                 result = Bisection(value,0,upperLimit);
00123 
00124                                 if(result==0) 
00125                                         return -1;
00126                                 else 
00127                                         return result;
00128                         }
00129                         guessIndex = upperLimit-inc;
00130                 }
00131         }
00132         return Bisection(value,guessIndex,upperLimit);
00133 }
00134 
00135 template <class T> 
00136         inline TIndex SearchArray<T>::Bisection(
00137                 const T& value,TIndex lowerLimit,TIndex upperLimit) const
00138 {
00139         lowerLimit--;
00140         bool ascending = (*mpArray)[mpArray->Size()-1] >= (*mpArray)[0];
00141         while (upperLimit-lowerLimit > 1)
00142         {
00143                 TIndex midPoint = (upperLimit+lowerLimit)>>1;
00144                 if ( (value >= (*mpArray)[midPoint]) == ascending)
00145                         lowerLimit = midPoint;
00146                 else
00147                         upperLimit = midPoint;
00148         }
00149         return lowerLimit;
00150 }
00151 
00152 }
00153 
00154 #endif
00155 
Generated by  doxygen 1.6.3