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/6/3 00013 // 00014 #ifndef _BITVECTOR_H 00015 #define _BITVECTOR_H 00016 00017 00018 #if _MSC_VER > 1000 00019 #pragma once 00020 #endif // _MSC_VER > 1000 00021 00022 #include "../utility/StdHeader.h" 00023 #include <stddef.h> 00024 #include <limits.h> 00025 #include <string> 00026 #include <ostream> 00027 #include <istream> 00028 #include "../store/Directory.h" 00029 00030 using namespace firtex::store; 00031 using namespace std; 00032 00033 00034 namespace firtex 00035 { 00036 namespace utility 00037 { 00038 const size_t NPOS = (size_t) -1; // "SIZE_T_MAX" 00039 00040 class CBitVector 00041 { 00042 public: 00043 CBitVector(); 00044 CBitVector(CDirectory* pDirectory,const char* name); 00045 CBitVector(CIndexInput* pInput); 00046 CBitVector(size_t n); 00047 CBitVector(size_t n,uint32_t val); 00048 CBitVector(const string& s); 00049 CBitVector(const CBitVector& b); 00050 ~CBitVector(); 00051 00052 // Conversions 00053 string toString() const; 00054 00055 // Assignment 00056 CBitVector& operator=(const CBitVector& b); 00057 00058 // Equality 00059 bool operator==(const CBitVector&) const; 00060 bool operator!=(const CBitVector&) const; 00061 00062 // Basic bit operations 00063 CBitVector& set(size_t, bool = true); 00064 CBitVector& set(); 00065 CBitVector& reset(size_t); 00066 CBitVector& reset(); 00067 CBitVector& toggle(size_t); 00068 CBitVector& toggle(); 00069 bool test(size_t) const; 00070 bool any() const; 00071 bool none() const; 00072 CBitVector operator~() const; 00073 00077 size_t count(); 00078 00079 void read(CDirectory* pDirectory,const char* name); 00080 void write(CDirectory* pDirectory,const char* name); 00081 00082 void read(CIndexInput* pInput); 00083 void write(CIndexOutput* pOutput); 00084 00085 // Bitwise operators 00086 CBitVector& operator&=(const CBitVector& b); 00087 CBitVector& operator|=(const CBitVector& b); 00088 CBitVector& operator^=(const CBitVector& b); 00089 CBitVector& operator>>=(size_t n); 00090 CBitVector& operator<<=(size_t n); 00091 CBitVector operator>>(size_t n) const; 00092 CBitVector operator<<(size_t n) const; 00093 00094 // String operations 00095 CBitVector& operator+=(const CBitVector&); 00096 CBitVector& insert(size_t pos, const CBitVector& b); 00097 CBitVector& remove(size_t pos, size_t n); 00098 CBitVector& replace(size_t pos, size_t n, const CBitVector& b); 00099 size_t find(int val, size_t pos = 0) const; 00100 size_t rfind(int val, size_t pos = NPOS) const; 00101 CBitVector substr(size_t pos, size_t n) const; 00105 size_t length() const; 00111 size_t length(size_t n, bool val = 0); 00112 00116 size_t trim(); 00117 00118 private: 00119 typedef uint32_t Block; 00120 00121 Block* m_bits; //基数组 00122 size_t m_nBits; //位数 00123 size_t m_nBlks; //基数组中块数 00124 int64_t m_count; //总置位数 00125 Block m_cleanmask; //用来隐藏不常使用的位 00126 00127 enum {BLKSIZ = CHAR_BIT * sizeof(Block)}; 00128 00129 static Block word(size_t b) 00130 {return (Block)(b / BLKSIZ);} 00131 static Block offset(size_t b) 00132 {return (Block)(BLKSIZ - b%BLKSIZ - 1);} 00133 static Block mask1(size_t b) 00134 {return Block(1) << offset(b);} 00135 static Block mask0(size_t b) 00136 {return ~(Block(1) << offset(b));} 00137 static size_t nblks(size_t nb) 00138 {return (nb+BLKSIZ-1) / BLKSIZ;} 00139 00140 void make_cleanmask(); 00141 void cleanup(); 00142 void set_(size_t n); 00143 void set_(size_t n, bool val); 00144 void reset_(size_t b); 00145 bool test_(size_t b) const; 00146 void fromString(const string& s); 00147 void init(size_t n); 00148 void equalize(CBitVector& b); 00149 00150 friend istream& operator>>(istream& is, CBitVector& b); 00151 }; 00152 00153 // Global Functions: 00154 ostream& operator<<(ostream& os, const CBitVector& b); 00155 istream& operator>>(istream& is, CBitVector& b); 00156 CBitVector operator& (const CBitVector& x, const CBitVector& y); 00157 CBitVector operator|(const CBitVector& x, const CBitVector& y); 00158 CBitVector operator^ (const CBitVector& x, const CBitVector& y); 00159 CBitVector operator+ (const CBitVector& x, const CBitVector& y); 00160 00162 // Inline publics: 00163 inline CBitVector::CBitVector() 00164 { 00165 init(0); 00166 } 00167 inline CBitVector::CBitVector(size_t n) 00168 { 00169 init(n); 00170 } 00171 00172 inline CBitVector::~CBitVector() 00173 { 00174 delete [] m_bits; 00175 } 00176 00177 inline CBitVector& CBitVector::toggle(size_t pos) 00178 { 00179 if(pos < 0 || pos >= m_nBits) 00180 FIRTEX_THROW2(OUTOFRANGE_ERROR,"bool CBitVector::test(size_t pos) const"); 00181 00182 m_bits[word(pos)] ^= mask1(pos); 00183 m_count = -1; 00184 return *this; 00185 } 00186 00187 inline bool CBitVector::test(size_t pos) const 00188 { 00189 if(pos < 0) 00190 FIRTEX_THROW2(OUTOFRANGE_ERROR,"bool CBitVector::test(size_t pos) const"); 00191 if(pos >= m_nBits) 00192 return false; 00193 00194 return test_(pos); 00195 } 00196 00197 inline CBitVector CBitVector::operator~() const 00198 { 00199 CBitVector b(*this); 00200 b.toggle(); 00201 return b; 00202 } 00203 00204 inline bool CBitVector::operator!=(const CBitVector& b) const 00205 { 00206 return !operator==(b); 00207 } 00208 00209 inline bool CBitVector::none() const 00210 { 00211 return !any(); 00212 } 00213 00214 inline size_t CBitVector::length() const 00215 { 00216 return m_nBits; 00217 } 00218 00219 inline CBitVector 00220 operator&(const CBitVector& x, const CBitVector& y) 00221 { 00222 CBitVector b(x); 00223 return b &= y; 00224 } 00225 00226 inline CBitVector 00227 operator|(const CBitVector& x, const CBitVector& y) 00228 { 00229 CBitVector b(x); 00230 return b |= y; 00231 } 00232 00233 inline CBitVector 00234 operator^(const CBitVector& x, const CBitVector& y) 00235 { 00236 CBitVector b(y); 00237 return b ^= x; 00238 } 00239 00240 inline CBitVector CBitVector::operator<<(size_t n) const 00241 { 00242 CBitVector r(*this); 00243 return r <<= n; 00244 } 00245 00246 inline CBitVector CBitVector::operator>>(size_t n) const 00247 { 00248 CBitVector r(*this); 00249 return r >>= n; 00250 } 00251 00252 inline CBitVector 00253 operator+(const CBitVector& b1, const CBitVector& b2) 00254 { 00255 CBitVector b(b1); 00256 return b.operator+=(b2); 00257 } 00258 00259 // Inline privates: 00260 inline void CBitVector::make_cleanmask() 00261 { 00262 m_cleanmask = ~Block(0) << (m_nBlks * BLKSIZ - m_nBits); 00263 } 00264 00265 inline void CBitVector::cleanup() 00266 { 00267 // Make sure unused bits don't get set 00268 if (m_nBits % BLKSIZ) 00269 m_bits[m_nBlks - 1] &= m_cleanmask; 00270 } 00271 inline void CBitVector::set_(size_t b) 00272 { 00273 m_bits[word(b)] |= mask1(b); 00274 } 00275 00276 inline void CBitVector::reset_(size_t b) 00277 { 00278 m_bits[word(b)] &= mask0(b); 00279 } 00280 00281 inline bool CBitVector::test_(size_t b) const 00282 { 00283 return !!(m_bits[word(b)] & mask1(b)); 00284 } 00285 00286 } 00287 } 00288 00289 #endif
http://www.firtex.org http://www.sourceforge.net/projects/firtex