CLAM-Development
1.1
|
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) 00101 return -1; 00102 upperLimit = guessIndex--; 00103 while ( value < (*mpData)[guessIndex] == ascending) 00104 { 00105 upperLimit = guessIndex; 00106 inc += inc; 00107 if (inc >= upperLimit) { 00108 result = Bisection(value,0,upperLimit); 00109 if(result==0) return -1; 00110 else return result; 00111 } 00112 guessIndex = upperLimit-inc; 00113 } 00114 } 00115 return Bisection(value,guessIndex,upperLimit); 00116 } 00117 00118 template <class U, class T> 00119 inline TIndex Search<U,T>::Bisection( 00120 const T& value,TIndex lowerLimit,TIndex upperLimit) const 00121 { 00122 lowerLimit--; 00123 bool ascending = (*mpData)[mpData->Size()-1] >= (*mpData)[0]; 00124 while (upperLimit-lowerLimit > 1) 00125 { 00126 TIndex midPoint = (upperLimit+lowerLimit)>>1; 00127 if ( value >= (*mpData)[midPoint] == ascending) 00128 lowerLimit = midPoint; 00129 else 00130 upperLimit = midPoint; 00131 } 00132 return lowerLimit; 00133 } 00134 00135 } 00136 00137 #endif 00138