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 _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