FirteX－高性能全文索引和检索平台
API Documentation
|
FirteX－高性能全文索引和检索平台API Documentation |
00001 // 00002 // Copyright(C) 2005--2006 Institute of Computing Tech, Chinese Academy of Sciences. 00003 // All rights reserved. 00004 // This file is part of FirteX (www.firtex.org) 00005 // 00006 // Use of the FirteX is subject to the terms of the software license set forth in 00007 // the LICENSE file included with this software, and also available at 00008 // http://www.firtex.org/license.html 00009 // 00010 // Author : 郭瑞杰(GuoRuijie) 00011 // Email : ruijieguo@software.ict.ac.cn,ruijieguo@gmail.com 00012 // Created : 2006/7/16 00013 // 00014 #ifndef _DYNAMICARRAY_H 00015 #define _DYNAMICARRAY_H 00016 00017 #if _MSC_VER > 1000 00018 #pragma once 00019 #endif // _MSC_VER > 1000 00020 00021 #include "../utility/StdHeader.h" 00022 00023 namespace firtex 00024 { 00025 namespace utility 00026 { 00027 #define DYNARRAY_DEFAULTBLKSIZE 128 00028 00029 template<class T> 00030 class Const_NullValue 00031 { 00032 public: 00033 inline operator T()const{return (T)0;} 00034 }; 00035 00036 template<class ElemT,class NullValue = Const_NullValue<ElemT> > 00037 class CDynamicArray 00038 { 00039 public: 00040 typedef ElemT element_type; 00041 public: 00042 CDynamicArray(void); 00043 CDynamicArray(int32_t blkSize); 00044 CDynamicArray(size_t initSize,int32_t blkSize); 00045 CDynamicArray(const CDynamicArray& src); 00046 ~CDynamicArray(void); 00047 public: 00048 class CDynamicArrayIterator 00049 { 00050 public: 00051 CDynamicArrayIterator(CDynamicArray<ElemT,NullValue>* pParent) 00052 :m_pParent(pParent) 00053 ,m_curBlk(-1) 00054 ,m_curOffset(-1) 00055 { 00056 } 00057 CDynamicArrayIterator(const CDynamicArrayIterator& clone) 00058 :m_pParent(clone.m_pParent) 00059 ,m_curBlk(clone.m_curBlk) 00060 ,m_curOffset(clone.m_curOffset) 00061 { 00062 } 00063 ~CDynamicArrayIterator(){} 00064 public: 00065 bool next() 00066 { 00067 if(m_curBlk == -1) 00068 { 00069 m_curBlk = m_pParent->m_blkBase; 00070 while(!m_pParent->m_blocks[m_curBlk] && (m_curBlk < m_pParent->m_numBlks) ) 00071 m_curBlk++; 00072 if(m_curBlk >= m_pParent->m_numBlks) 00073 return false; 00074 } 00075 do 00076 { 00077 m_curOffset++; 00078 if(m_curOffset >= m_pParent->m_blkSize) 00079 { 00080 m_curBlk++; 00081 while(!m_pParent->m_blocks[m_curBlk] && (m_curBlk < m_pParent->m_numBlks) ) 00082 m_curBlk++; 00083 if(m_curBlk>=m_pParent->m_numBlks) 00084 return false; 00085 m_curOffset = 0; 00086 } 00087 }while(m_pParent->m_blocks[m_curBlk][m_curOffset] == NullValue()); 00088 00089 return true; 00090 } 00091 element_type element() 00092 { 00093 return m_pParent->m_blocks[m_curBlk][m_curOffset]; 00094 } 00095 size_t position() 00096 { 00097 return m_curBlk*m_pParent->m_blkSize + m_curOffset; 00098 } 00099 protected: 00100 CDynamicArray<ElemT,NullValue>* m_pParent; 00101 int32_t m_curBlk; 00102 int32_t m_curOffset; 00103 }; 00104 00105 typedef CDynamicArrayIterator array_iterator; 00106 public: 00107 ElemT& operator[](size_t order); 00108 00114 void insert(size_t order,const ElemT& val); 00115 00120 array_iterator elements(); 00121 00123 size_t length(); 00124 00129 size_t setMaxlength(size_t newMaxLen); 00130 00132 void clear(); 00133 00135 void reset(); 00136 protected: 00137 int32_t block(size_t order); 00138 int32_t offset(size_t order); 00139 00144 void grow(size_t newLen); 00145 00147 void allocBlock(int32_t blk); 00148 private: 00149 ElemT** m_blocks; //块 00150 int32_t m_blkSize; //单个块的长度 00151 int32_t m_blkBase; //块基数 00152 int32_t m_numBlks; //块总数 00153 size_t m_maxLength; //长度 00154 }; 00156 // 00157 template<class ElemT,class NullValue> 00158 CDynamicArray<ElemT,NullValue>::CDynamicArray(void) 00159 :m_blkSize(DYNARRAY_DEFAULTBLKSIZE) 00160 ,m_blkBase(0) 00161 ,m_numBlks(1) 00162 ,m_maxLength(DYNARRAY_DEFAULTBLKSIZE) 00163 { 00164 m_blocks = new ElemT*[m_numBlks]; 00165 m_blocks[0] = NULL; 00166 } 00167 template<class ElemT,class NullValue> 00168 CDynamicArray<ElemT,NullValue>::CDynamicArray(int32_t blkSize) 00169 :m_blkSize(blkSize) 00170 ,m_blkBase(0) 00171 ,m_numBlks(1) 00172 ,m_maxLength(blkSize) 00173 { 00174 m_blocks = new ElemT*[m_numBlks]; 00175 m_blocks[0] = NULL; 00176 } 00177 template<class ElemT,class NullValue> 00178 CDynamicArray<ElemT,NullValue>::CDynamicArray(size_t initSize,int32_t blkSize) 00179 :m_blkSize(blkSize) 00180 ,m_blkBase(0) 00181 ,m_maxLength(initSize) 00182 { 00183 m_numBlks = (int32_t)((initSize + blkSize - 1)/blkSize); 00184 m_blocks = new ElemT*[m_numBlks]; 00185 memset(m_blocks,0,m_numBlks*sizeof(ElemT*)); 00186 } 00187 00188 template<class ElemT,class NullValue> 00189 CDynamicArray<ElemT,NullValue>::CDynamicArray(const CDynamicArray& src) 00190 { 00191 m_blkSize = src.m_blkSize; 00192 m_blkBase = src.m_blkBase; 00193 m_numBlks = src.m_numBlks; 00194 m_maxLength = src.m_maxLength; 00195 m_blocks = new ElemT*[m_numBlks]; //块 00196 memcpy(m_blocks,src.m_blocks,m_numBlks*sizeof(ElemT*)); 00197 for(int32_t i = 0;i<m_numBlks;i++) 00198 { 00199 allocBlock(i); 00200 memcpy(m_blocks[i],src.m_blocks[i],m_blkSize*sizeof(ElemT)); 00201 } 00202 } 00203 00204 template<class ElemT,class NullValue> 00205 CDynamicArray<ElemT,NullValue>::~CDynamicArray(void) 00206 { 00207 clear(); 00208 } 00209 00210 /*template<class ElemT,class NullValue> 00211 ElemT const& CDynamicArray<ElemT,NullValue>::operator[](size_t order)const 00212 { 00213 FIRTEX_ASSERT((order < m_maxLength),_T("out of range")); 00214 00215 int32_t blk = block(order); 00216 FIRTEX_ASSERT((m_blocks[blk]!=NULL),_T("access empty element")); 00217 int32_t off = offset(order); 00218 return m_blocks[blk][off]; 00219 }*/ 00220 00221 template<class ElemT,class NullValue> 00222 ElemT& CDynamicArray<ElemT,NullValue>::operator[](size_t order) 00223 { 00224 if(order >= m_maxLength) 00225 grow(order+1); //增长 00226 int32_t blk = block(order); 00227 int32_t off = offset(order); 00228 if(m_blocks[blk] == NULL) 00229 allocBlock(blk); 00230 return m_blocks[blk][off];// 00231 } 00232 template<class ElemT,class NullValue> 00233 typename CDynamicArray<ElemT,NullValue>::array_iterator CDynamicArray<ElemT,NullValue>::elements() 00234 { 00235 return typename CDynamicArray<ElemT,NullValue>::array_iterator(this); 00236 } 00237 template<class ElemT,class NullValue> 00238 void CDynamicArray<ElemT,NullValue>::insert(size_t order,const ElemT& val) 00239 { 00240 if(order >= m_maxLength) 00241 grow(order+1); //增长 00242 int32_t blk = block(order); 00243 int32_t off = offset(order); 00244 if(m_blocks[blk] == NULL) 00245 allocBlock(blk); 00246 m_blocks[blk][off] = val; 00247 } 00248 00249 template<class ElemT,class NullValue> 00250 void CDynamicArray<ElemT,NullValue>::grow(size_t newLen) 00251 { 00252 int32_t numBlks = (int32_t)((newLen + m_blkSize - 1)/m_blkSize); 00253 ElemT** tmpBlks = new ElemT*[numBlks]; 00254 memset(tmpBlks,0,numBlks*sizeof(ElemT*)); 00255 memcpy(tmpBlks,m_blocks,m_numBlks*sizeof(ElemT*)); 00256 delete[] m_blocks; 00257 m_blocks = tmpBlks; 00258 m_numBlks = numBlks; 00259 m_maxLength = newLen; 00260 } 00261 template<class ElemT,class NullValue> 00262 void CDynamicArray<ElemT,NullValue>::allocBlock(int32_t blk) 00263 { 00264 FIRTEX_ASSERT((blk<m_numBlks),_T("CDynamicArray::allocBlock():ouf of range.")); 00265 m_blocks[blk] = new ElemT[m_blkSize]; 00266 for (int i = 0;i<m_blkSize;i++) 00267 { 00268 m_blocks[blk][i] = NullValue(); 00269 } 00270 //memset(m_blocks[blk],(int)NullValue,m_blkSize*sizeof(ElemT)); 00271 } 00272 00273 template<class ElemT,class NullValue> 00274 void CDynamicArray<ElemT,NullValue>::clear() 00275 { 00276 if(m_blocks) 00277 { 00278 for(int32_t i = 0;i<m_numBlks;i++) 00279 { 00280 if(m_blocks[i]) 00281 delete[] m_blocks[i]; 00282 } 00283 delete[] m_blocks; 00284 m_blocks = NULL; 00285 m_numBlks = 0; 00286 } 00287 m_maxLength = 0; 00288 } 00289 template<class ElemT,class NullValue> 00290 void CDynamicArray<ElemT,NullValue>::reset() 00291 { 00292 if(m_blocks) 00293 { 00294 for(int32_t i = 0;i<m_numBlks;i++) 00295 { 00296 if(m_blocks[i]) 00297 { 00298 memset(m_blocks[i],NullValue(),m_blkSize*sizeof(ElemT)); 00299 } 00300 } 00301 } 00302 } 00304 //inline functions 00305 template<class ElemT,class NullValue> 00306 inline size_t CDynamicArray<ElemT,NullValue>::length() 00307 { 00308 int32_t length = 0; 00309 for(int32_t i = 0;i<m_numBlks;i++) 00310 { 00311 if(m_blocks[i - m_blkBase]) 00312 { 00313 for(int32_t j = 0;j<m_blkSize;j++) 00314 if(m_blocks[i - m_blkBase][j] != NullValue()) 00315 length++; 00316 } 00317 } 00318 return length; 00319 } 00320 template<class ElemT,class NullValue> 00321 inline size_t CDynamicArray<ElemT,NullValue>::setMaxlength(size_t newMaxLen) 00322 { 00323 if(newMaxLen > m_maxLength) 00324 { 00325 grow(newMaxLen); 00326 return newMaxLen; 00327 } 00328 else return m_maxLength; 00329 } 00330 template<class ElemT,class NullValue> 00331 inline int32_t CDynamicArray<ElemT,NullValue>::block(size_t order) 00332 { 00333 return ((int32_t)(order/m_blkSize) - m_blkBase); 00334 } 00335 template<class ElemT,class NullValue> 00336 inline int32_t CDynamicArray<ElemT,NullValue>::offset(size_t order) 00337 { 00338 return (int32_t)(order%m_blkSize); 00339 } 00340 } 00341 } 00342 00343 00344 #endif
http://www.firtex.org http://www.sourceforge.net/projects/firtex