*****************************************************************************/
#include "CSA.h"
#include "TextCollection.h"
+
+// Conflicts with std::min and std::max
+#undef min
+#undef max
+#include "dcover/bwt.hpp"
+
+#include "HeapProfiler.h" // FIXME remove
+
#include <iostream>
#include <queue>
-#include <iomanip>
#include <set>
#include <vector>
#include <utility>
using std::make_pair;
using std::map;
-using SXSI::TextCollection;
+namespace SXSI
+{
// Save file version info
const uchar CSA::versionFlag = 2;
////////////////////////////////////////////////////////////////////////////
// Class CSA::THuffAlphabetRank
-
+// FIXME Unused code
CSA::THuffAlphabetRank::THuffAlphabetRank(uchar *s, TextPosition n, TCodeEntry *codetable, unsigned level) {
left = NULL;
right = NULL;
delete bitrank;
}
-/**
- * Saving data fields:
- BitRank *bitrank;
- bool leaf;
- uchar ch;
- left child;
- right child;
-*/
-void CSA::THuffAlphabetRank::Save(FILE *file)
-{
-
-}
-
-CSA::THuffAlphabetRank::THuffAlphabetRank(FILE *file)
-{
-
-
-}
-/////////////////////////////////////////////f///////////////////////////////
+////////////////////////////////////////////////////////////////////////////
// Class CSA
/**
* Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE.
*/
CSA::CSA(unsigned samplerate)
- : n(0), samplerate(0), alphabetrank(0), sampled(0), suffixes(0), suffixDocId(0), positions(0),
- codetable(0), dynFMI(0), numberOfTexts(0), numberOfAllTexts(0), maxTextLength(0), endmarkerDocId(0),
- textLength(0), textStartPos(0), emptyTextRank(0)
+ : n(0), samplerate(0), alphabetrank(0), codetable(0), sampled(0), suffixes(0),
+ suffixDocId(0), numberOfTexts(0), numberOfAllTexts(0), maxTextLength(0), endmarkerDocId(0),
+ emptyTextRank(0)
{
this->samplerate = samplerate;
-
+
+#ifdef CSA_TEST_BWT
// FIXME TODO : DynFMI needs distribution of characters before hand
// This will create fully balanced wavelet tree for all chars [0, 255].
uchar temp[256];
uchar *temp = Tools::GetFileContents("data.txt", 0);
dynFMI = new DynFMI(temp,1790000, strlen((char *)temp), false);
delete [] temp;*/
+#endif
}
/**
void CSA::InsertText(uchar const * text)
{
// Sanity check:
+#ifdef CSA_TEST_BWT
assert(dynFMI != 0);
+#endif
TextPosition m = std::strlen((char *)text) + 1;
if (m > maxTextLength)
this->n += m;
this->numberOfTexts ++;
this->numberOfAllTexts ++;
+#ifdef CSA_TEST_BWT
dynFMI->addText(text, m);
+#endif
+
+ texts.append((char *) text);
+ texts.append(1, '\0');
}
else
{
emptyTextId.insert(numberOfAllTexts); // FIXME Using too much space here
- this->numberOfAllTexts ++; // Replace with dynamic bitvector
+ this->numberOfAllTexts ++;
}
}
void CSA::MakeStatic()
{
// Sanity check:
+#ifdef CSA_TEST_BWT
if (dynFMI == 0)
throw std::runtime_error("CSA::MakeStatic(): Data structure is already static (dynFMI == 0).");
+#endif
- // Bitvector of empty texts
+ if (texts.size() == 0) // Empty collection
+ {
+ ++n;
+ ++numberOfTexts;
+ texts.append(1, '\0');
+ }
+
+ // Bitvector of empty texts, FIXME Remove?
{
//std::cout << std::endl << "texts: " << numberOfTexts << ", all texts " << numberOfAllTexts << ", size : " << emptyTextId.size() <<std::endl;
ulong *tempB = new ulong[numberOfAllTexts/W + 1];
emptyTextId.clear();
emptyTextRank = new BSGAP(tempB, numberOfAllTexts, true);
}
-
- uchar *bwt = dynFMI->getBWT();
- /*printf("123456789012345678901234567890123456789\n");
- for (TextPosition i = 0; i < n; i ++)
- if (bwt[i] < 50)
- printf("%d", (int)bwt[i]);
- else
- printf("%c", bwt[i]);
- printf("\n");*/
-
-
-/* for (TextPosition i = 1; i <= n; i ++)
+
+ texts.reserve(0); // Release extra capacity
+
+/* FILE *fp = fopen("texts.txt", "wb");
+ std::cout << "Wrote " << fwrite(texts.c_str(), 1, n, fp) << " bytes into texts.txt." << std::endl;
+ fclose(fp);*/
+
+ uchar *bwt = new uchar[n];
{
- printf("LF[%lu, %c] = %lu\n", i, (*dynFMI)[i], dynFMI->LFmapping(i));
- }*/
+ // More succinct solution via StringIterator, see below.
+/* unsigned* maptexts = new unsigned[n+1];
+ // Map text chars to [0..255+numberOfTexts]
+ unsigned count = 0;
+ for (ulong i = 0; i < n; ++i)
+ if (texts[i] == 0)
+ maptexts[i] = ++count; // endmarkers \in [1..numberOfTexts]
+ else {
+ uchar c = (uchar)texts[i];
+ maptexts[i] = (unsigned)c + numberOfTexts;
+ }
+ maptexts[n] = '\0';
+ assert(count == numberOfTexts);
+
+ std::cout << "maptext: ";
+ for (ulong i = 0; i <= n; ++i)
+ std::cout << maptexts[i] << ", ";
+ std::cout << std::endl;*/
+
+ // Mark endmarker positions into bitvector
+ ulong * endmarkers = new ulong[n/W+1];
+ for (ulong i = 0; i < n/W+1; ++i)
+ endmarkers[i] = 0;
+ for (ulong i = 0; i < n; ++i)
+ if (texts[i] == 0)
+ Tools::SetField(endmarkers, 1, i, 1);
+ BitRank* br = new BitRank(endmarkers, n, true);
+ assert(numberOfTexts == br->rank(n-1));
+
+ // Build iterators, FIXME clean up iterator construction.
+ StringIterator itBegin((uchar const *)texts.c_str(), (uchar const *)texts.c_str(), n, numberOfTexts, br);
+ StringIterator itEnd((uchar const *)texts.c_str() + n,(uchar const *)texts.c_str(), n, numberOfTexts, br);
- // Sanity check
- assert(numberOfTexts == dynFMI->getCollectionSize());
+ bwtEndPos = (ulong)compute_bwt(itBegin, itEnd, //&maptexts[0], &maptexts[n],
+ &bwt[0], numberOfTexts);
- delete dynFMI;
- dynFMI = 0;
+ bwt[--bwtEndPos] = '\0';
+ texts.erase();
+ texts.reserve(0); // Release capacity
+ delete br; // bitvector of endmarkers
+ } // End of bw transform
+// std::cerr << "Time after BWT: " << Tools::GetTime() << std::endl;
- makewavelet(bwt); // Deletes bwt!
- bwt = 0;
+/* fp = fopen("bwt.txt", "wb");
+ std::cout << "Wrote " << fwrite(bwt, 1, n, fp) << " bytes into bwt.txt." << std::endl;
+ fclose(fp);*/
- // Calculate BWT end-marker position (of last inserted text)
- // and the length of the first text (counter l):
- ulong i = 0;
- ulong l = 1;
- uchar c = alphabetrank->access(i);
- while (c != '\0')
- {
- i = C[c]+alphabetrank->rank(c, i)-1;
- ++l;
- c = alphabetrank->access(i);
+#ifdef CSA_TEST_BWT
+ {
+ uchar *bwtTest = dynFMI->getBWT();
+ printf("123456789012345678901234567890123456789\n");
+ for (TextPosition i = 0; i < n && i < 100; i ++)
+ if (bwt[i] < 50)
+ printf("%d", (int)bwt[i]);
+ else
+ printf("%c", bwt[i]);
+ printf("\n");
+ for (TextPosition i = 0; i < n && i < 100; i ++)
+ if (bwtTest[i] < 50)
+ printf("%d", (int)bwtTest[i]);
+ else
+ printf("%c", bwtTest[i]);
+ printf("\n");
+
+ // Sanity check
+ assert(numberOfTexts == dynFMI->getCollectionSize());
+
+ delete dynFMI;
+ dynFMI = 0;
+ for (ulong i = 0; i < n; ++i)
+ if (bwt[i] != bwtTest[i])
+ {
+ std::cout << "i = " << i << ", bwt = " << (unsigned)bwt[i] << ", " << (unsigned)bwtTest[i] << std::endl;
+ assert(0);
+ }
+ delete [] bwtTest;
}
- bwtEndPos = i;
- assert(bwtEndPos < n);
- //printf("bwtEndPos = %lu\n", bwtEndPos);
+#endif // CSA_TEST_BWT
- // Build up arrays for text length and starting positions
- // FIXME Remove, temp data
- textLength = new BlockArray(numberOfTexts, Tools::CeilLog2(maxTextLength));
- textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
- (*textLength)[0] = l;
- (*textStartPos)[0] = 0; // Rest of the values are updated in CSA::maketables().
+ makewavelet(bwt); // Deletes bwt!
+ bwt = 0;
// Make sampling tables
maketables();
return false;
}
+bool CSA::IsPrefix(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return true;
+
+ TextPosition sp = 0, ep = 0;
+ Search(pattern, m, &sp, &ep);
+
+ // Check for end-marker(s) in result interval
+ if (CountEndmarkers(sp, ep, begin, end))
+ return true;
+ return false;
+}
+
+
bool CSA::IsSuffix(uchar const *pattern) const
{
// Here counting is as fast as IsSuffix():
return false;
}
+bool CSA::IsSuffix(uchar const *pattern, DocId begin, DocId end) const
+{
+ // Here counting is as fast as IsSuffix():
+ if (CountSuffix(pattern, begin, end) > 0)
+ return true;
+ return false;
+}
+
bool CSA::IsEqual(uchar const *pattern) const
{
TextPosition m = std::strlen((char *)pattern);
return false;
}
+bool CSA::IsEqual(uchar const *pattern, DocId begin, DocId end) const
+{
+ TextPosition m = std::strlen((char *)pattern);
+ if (m == 0)
+ {
+ if (numberOfAllTexts - numberOfTexts > 0u)
+ return true; // Empty texts exists
+ return false; // No empty texts exists
+ }
+
+ TextPosition sp = 0, ep = 0;
+ // Match including end-marker
+ Search(pattern, m+1, &sp, &ep, begin, end);
+
+ // Check for end-marker(s) in result interval
+ if (CountEndmarkers(sp, ep))
+ return true;
+ return false;
+}
+
bool CSA::IsContains(uchar const * pattern) const
{
TextPosition m = strlen((char *)pattern);
return false;
}
-bool CSA::IsLessThan(uchar const*) const
+bool CSA::IsContains(uchar const * pattern, DocId begin, DocId end) const
+{
+ // Here counting is as fast as existential querying
+ if (CountContains(pattern, begin, end) > 0)
+ return true; // FIXME No need to filter result set
+ return false;
+}
+
+bool CSA::IsLessThan(uchar const * pattern) const
{
- // TODO
- assert(0);
+ if (CountLessThan(pattern) > 0)
+ return true;
+ return false;
+}
+
+bool CSA::IsLessThan(uchar const * pattern, DocId begin, DocId end) const
+{
+ if (CountLessThan(pattern, begin, end) > 0)
+ return true;
return false;
}
/******************************************************************
* Counting queries
*/
+ulong CSA::Count(uchar const * pattern) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return 0;
+
+ TextPosition sp = 0, ep = 0;
+ unsigned count = (unsigned) Search(pattern, m, &sp, &ep);
+ return count;
+}
+
unsigned CSA::CountPrefix(uchar const * pattern) const
{
TextPosition m = strlen((char *)pattern);
return CountEndmarkers(sp, ep);
}
+unsigned CSA::CountPrefix(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return numberOfAllTexts;
+
+ TextPosition sp = 0, ep = 0;
+ Search(pattern, m, &sp, &ep);
+
+ // Count end-markers in result interval
+ return CountEndmarkers(sp, ep, begin, end);
+}
+
unsigned CSA::CountSuffix(uchar const * pattern) const
{
TextPosition m = strlen((char *)pattern);
return count;
}
+unsigned CSA::CountSuffix(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return numberOfAllTexts;
+
+ TextPosition sp = 0, ep = 0;
+ // Search with end-marker
+ unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end);
+
+ return count;
+}
+
unsigned CSA::CountEqual(uchar const *pattern) const
{
TextPosition m = strlen((char const *)pattern);
return CountEndmarkers(sp, ep);
}
+unsigned CSA::CountEqual(uchar const *pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return numberOfAllTexts - numberOfTexts; // Empty texts.
+
+ TextPosition sp = 0, ep = 0;
+ // Match including end-marker
+ Search(pattern, m+1, &sp, &ep, begin, end);
+
+ // Count end-markers in result interval
+ return CountEndmarkers(sp, ep); // Already within [begin, end]
+}
+
unsigned CSA::CountContains(uchar const * pattern) const
{
TextPosition m = strlen((char const *)pattern);
return numberOfAllTexts; // Total number of texts.
// Here counting is as slow as fetching the result set
- // because we would have to filter out occ's that fall within same document.
+ // because we have to filter out occ's that fall within same document.
TextCollection::document_result result = Contains(pattern);
return result.size();
}
+unsigned CSA::CountContains(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return numberOfAllTexts; // Total number of texts.
+
+ // Here counting is as slow as fetching the result set
+ // because we have to filter out occ's that fall within same document.
+ TextCollection::document_result result = Contains(pattern, begin, end);
+ return result.size();
+}
+
+// Less than or equal
unsigned CSA::CountLessThan(uchar const * pattern) const
{
- // TODO
- assert(0);
- return 0;
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return numberOfAllTexts - numberOfTexts; // Empty texts.
+
+ TextPosition sp = 0, ep = 0;
+ SearchLessThan(pattern, m, &sp, &ep);
+
+ // Count end-markers in result interval
+ return CountEndmarkers(sp, ep);
+}
+
+unsigned CSA::CountLessThan(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return numberOfAllTexts - numberOfTexts; // Empty texts.
+
+ TextPosition sp = 0, ep = 0;
+ SearchLessThan(pattern, m, &sp, &ep);
+
+ // Count end-markers in result interval
+ return CountEndmarkers(sp, ep, begin, end);
}
/**
return result;
}
-TextCollection::document_result CSA::Suffix(uchar const * pattern) const
+TextCollection::document_result CSA::Prefix(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // FIXME Should return all 1...k
+
+ TextPosition sp = 0, ep = 0;
+ Search(pattern, m, &sp, &ep);
+
+ TextCollection::document_result result;
+
+ // Report end-markers in result interval
+ unsigned resultSize = CountEndmarkers(sp, ep);
+ if (resultSize == 0)
+ return result;
+
+ result.reserve(resultSize); // Try to avoid reallocation.
+
+ // Iterate through end-markers in [sp,ep] and [begin, end]:
+ unsigned i = 0;
+ if (sp > 0)
+ i = alphabetrank->rank(0, sp - 1);
+ while (resultSize)
+ {
+ // End-marker we found belongs to the "preceeding" doc in the collection
+ DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ if (docId >= begin && docId <= end)
+ result.push_back(docId);
+
+ -- resultSize;
+ ++ i;
+ }
+
+ return result;
+}
+
+TextCollection::document_result CSA::Suffix(uchar const * pattern) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // FIXME Should return all 1...k
+
+ TextPosition sp = 0, ep = 0;
+ // Search with end-marker
+ Search(pattern, m+1, &sp, &ep);
+
+ TextCollection::document_result result;
+ result.reserve(ep-sp+1); // Try to avoid reallocation.
+
+ ulong sampled_rank_i = 0;
+ // Check each occurrence
+ for (; sp <= ep; ++sp)
+ {
+ TextPosition i = sp;
+
+ uchar c = alphabetrank->access(i);
+ while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
+ {
+ i = C[c]+alphabetrank->rank(c,i)-1;
+ c = alphabetrank->access(i);
+ }
+ // Assert: c == '\0' OR sampled->IsBitSet(i)
+
+ if (c == '\0')
+ {
+ // Rank among the end-markers in BWT
+ unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
+
+ // End-marker that we found belongs to the "preceeding" doc in collection:
+ DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId);
+ }
+ else // Sampled position
+ {
+ DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId);
+ }
+ }
+
+ return result;
+}
+
+TextCollection::document_result CSA::Suffix(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // FIXME Should return all 1...k
+
+ TextPosition sp = 0, ep = 0;
+ // Search with end-marker
+ Search(pattern, m+1, &sp, &ep, begin, end);
+
+ TextCollection::document_result result;
+ result.reserve(ep-sp+1); // Try to avoid reallocation.
+
+ ulong sampled_rank_i = 0;
+ // Check each occurrence, already within [begin, end]
+ for (; sp <= ep; ++sp)
+ {
+ TextPosition i = sp;
+
+ uchar c = alphabetrank->access(i);
+ while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
+ {
+ i = C[c]+alphabetrank->rank(c,i)-1;
+ c = alphabetrank->access(i);
+ }
+ // Assert: c == '\0' OR sampled->IsBitSet(i)
+
+ if (c == '\0')
+ {
+ // Rank among the end-markers in BWT
+ unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
+
+ // End-marker that we found belongs to the "preceeding" doc in collection:
+ DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId);
+ }
+ else // Sampled position
+ {
+ DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId);
+ }
+ }
+
+ return result;
+}
+
+
+TextCollection::document_result CSA::Equal(uchar const *pattern) const
+{
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // FIXME Should return all empty texts
+
+ TextPosition sp = 0, ep = 0;
+ // Match including end-marker
+ Search(pattern, m+1, &sp, &ep);
+
+ TextCollection::document_result result;
+
+ // Report end-markers in result interval
+ unsigned resultSize = CountEndmarkers(sp, ep);
+ if (resultSize == 0)
+ return result;
+
+ result.reserve(resultSize); // Try to avoid reallocation.
+
+ unsigned i = 0;
+ if (sp > 0)
+ i = alphabetrank->rank(0, sp - 1);
+ while (resultSize)
+ {
+ // End-marker we found belongs to the "previous" doc in the collection
+ DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId);
+
+ -- resultSize;
+ ++ i;
+ }
+
+ return result;
+}
+
+TextCollection::document_result CSA::Equal(uchar const *pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char const *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // FIXME Should return all empty texts
+
+ TextPosition sp = 0, ep = 0;
+ // Match including end-marker
+ Search(pattern, m+1, &sp, &ep, begin, end);
+
+ TextCollection::document_result result;
+
+ // Report end-markers in result interval
+ unsigned resultSize = CountEndmarkers(sp, ep);
+ if (resultSize == 0)
+ return result;
+
+ result.reserve(resultSize); // Try to avoid reallocation.
+
+ unsigned i = 0;
+ if (sp > 0)
+ i = alphabetrank->rank(0, sp - 1);
+ while (resultSize)
+ {
+ // End-marker we found belongs to the "previous" doc in the collection
+ DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(docId); // already within [begin, end]
+
+ -- resultSize;
+ ++ i;
+ }
+
+ return result;
+}
+
+
+TextCollection::document_result CSA::Contains(uchar const * pattern) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return TextCollection::document_result();
+
+ TextPosition sp = 0, ep = 0;
+ // Search all occurrences
+ Search(pattern, m, &sp, &ep);
+
+ // We want unique document indentifiers, using std::set to collect them
+ std::set<DocId> resultSet;
+
+ ulong sampled_rank_i = 0;
+ // Check each occurrence
+ for (; sp <= ep; ++sp)
+ {
+ TextPosition i = sp;
+ uchar c = alphabetrank->access(i);
+ while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
+ {
+ i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
+ c = alphabetrank->access(i);
+ }
+ if (c == '\0')
+ {
+ // Rank among the end-markers in BWT
+ unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
+
+ // End-marker that we found belongs to the "preceeding" doc in collection:
+ DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
+ resultSet.insert(docId);
+ }
+ else
+ {
+ DocId di = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
+ assert((unsigned)di < numberOfTexts);
+ resultSet.insert(di);
+ }
+ }
+
+ // Convert std::set to std::vector
+ TextCollection::document_result result(resultSet.begin(), resultSet.end());
+ // Map to doc ID's
+ for (document_result::iterator it = result.begin(); it != result.end(); ++it)
+ *it = emptyTextRank->select0(*it+1);
+ return result;
+}
+
+TextCollection::document_result CSA::Contains(uchar const * pattern, DocId begin, DocId end) const
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all 1...k
+ return TextCollection::document_result();
TextPosition sp = 0, ep = 0;
- // Search with end-marker
- Search(pattern, m+1, &sp, &ep);
-
- TextCollection::document_result result;
- result.reserve(ep-sp+1); // Try to avoid reallocation.
+ // Search all occurrences
+ Search(pattern, m, &sp, &ep);
+
+ // We want unique document indentifiers, using std::set to collect them
+ std::set<DocId> resultSet;
ulong sampled_rank_i = 0;
// Check each occurrence
for (; sp <= ep; ++sp)
{
TextPosition i = sp;
-
uchar c = alphabetrank->access(i);
while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
{
- i = C[c]+alphabetrank->rank(c,i)-1;
+ i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
c = alphabetrank->access(i);
}
- // Assert: c == '\0' OR sampled->IsBitSet(i)
-
if (c == '\0')
{
// Rank among the end-markers in BWT
unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
-
+
// End-marker that we found belongs to the "preceeding" doc in collection:
- DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- result.push_back(docId);
+ DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
+ if (docId >= begin && docId <= end)
+ resultSet.insert(docId);
}
- else // Sampled position
+ else
{
DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
- // Map to doc ID:
- docId = emptyTextRank->select0(docId+1);
- result.push_back(docId);
+ assert((unsigned)docId < numberOfTexts);
+ if (docId >= begin && docId <= end)
+ resultSet.insert(docId);
}
}
+ // Convert std::set to std::vector
+ TextCollection::document_result result(resultSet.begin(), resultSet.end());
+ // Map to doc ID's
+ for (document_result::iterator it = result.begin(); it != result.end(); ++it)
+ *it = emptyTextRank->select0(*it+1);
return result;
}
-TextCollection::document_result CSA::Equal(uchar const *pattern) const
+TextCollection::document_result CSA::LessThan(uchar const * pattern) const
{
- TextPosition m = strlen((char const *)pattern);
+ TextPosition m = strlen((char *)pattern);
if (m == 0)
- return TextCollection::document_result(); // FIXME Should return all empty texts
+ return TextCollection::document_result(); // empty result set
TextPosition sp = 0, ep = 0;
- // Match including end-marker
- Search(pattern, m+1, &sp, &ep);
+ SearchLessThan(pattern, m, &sp, &ep);
TextCollection::document_result result;
-
+
// Report end-markers in result interval
unsigned resultSize = CountEndmarkers(sp, ep);
if (resultSize == 0)
result.reserve(resultSize); // Try to avoid reallocation.
+ // Iterate through end-markers in [sp,ep]:
unsigned i = 0;
if (sp > 0)
i = alphabetrank->rank(0, sp - 1);
while (resultSize)
{
- // End-marker we found belongs to the "previous" doc in the collection
+ // End-marker we found belongs to the "preceeding" doc in the collection
DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
// Map to doc ID:
docId = emptyTextRank->select0(docId+1);
return result;
}
+TextCollection::document_result CSA::LessThan(uchar const * pattern, DocId begin, DocId end) const
+{
+ TextPosition m = strlen((char *)pattern);
+ if (m == 0)
+ return TextCollection::document_result(); // empty result set
+
+ TextPosition sp = 0, ep = 0;
+ SearchLessThan(pattern, m, &sp, &ep);
-TextCollection::document_result CSA::Contains(uchar const * pattern) const
+ TextCollection::document_result result;
+
+ // Report end-markers in result interval
+ unsigned resultSize = CountEndmarkers(sp, ep);
+ if (resultSize == 0)
+ return result;
+
+ result.reserve(resultSize); // Try to avoid reallocation.
+
+ // Iterate through end-markers in [sp,ep] and [begin, end]:
+ unsigned i = 0;
+ if (sp > 0)
+ i = alphabetrank->rank(0, sp - 1);
+ while (resultSize)
+ {
+ // End-marker we found belongs to the "preceeding" doc in the collection
+ DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ if (docId >= begin && docId <= end)
+ result.push_back(docId);
+
+ -- resultSize;
+ ++ i;
+ }
+
+ return result;
+}
+
+/**
+ * Full result set queries
+ */
+TextCollection::full_result CSA::FullContains(uchar const * pattern) const
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
- return TextCollection::document_result();
+ return full_result(); // FIXME Throw exception?
TextPosition sp = 0, ep = 0;
// Search all occurrences
Search(pattern, m, &sp, &ep);
+
+ full_result result;
+ result.reserve(ep-sp+1); // Try to avoid reallocation.
- // We want unique document indentifiers, using std::set to collect them
- std::set<DocId> resultSet;
-
- ulong sampled_rank_i = 0;
- // Check each occurrence
+ ulong sampled_rank_i = 0;
+ // Report each occurrence
for (; sp <= ep; ++sp)
{
TextPosition i = sp;
+ TextPosition dist = 0;
uchar c = alphabetrank->access(i);
while (c != '\0' && !sampled->IsBitSet(i, &sampled_rank_i))
{
- i = C[c]+alphabetrank->rank(c,i)-1; // LF-mapping
+ i = C[c]+alphabetrank->rank(c,i)-1;
c = alphabetrank->access(i);
+ ++ dist;
}
if (c == '\0')
{
// End-marker that we found belongs to the "preceeding" doc in collection:
DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
- resultSet.insert(docId);
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(make_pair(docId, dist));
}
else
{
- DocId di = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
- assert((unsigned)di < numberOfTexts);
- resultSet.insert(di);
+ TextPosition textPos = (*suffixes)[sampled_rank_i-1]+dist; //sampled->rank(i)-1] + dist;
+ DocId docId = (*suffixDocId)[sampled_rank_i-1]; //sampled->rank(i)-1];
+// textPos = textPos - (*textStartPos)[docId]; // Offset inside the text
+
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ result.push_back(make_pair(docId, textPos));
}
}
- // Convert std::set to std::vector
- TextCollection::document_result result(resultSet.begin(), resultSet.end());
- // Map to doc ID's
- for (document_result::iterator it = result.begin(); it != result.end(); ++it)
- *it = emptyTextRank->select0(*it+1);
return result;
}
-TextCollection::document_result CSA::LessThan(uchar const * pattern) const
-{
- // TODO
- assert(0);
- return document_result();
-}
-
-/**
- * Full result set queries
- */
-TextCollection::full_result CSA::FullContains(uchar const * pattern) const
+TextCollection::full_result CSA::FullContains(uchar const * pattern, DocId begin, DocId end) const
{
TextPosition m = strlen((char *)pattern);
if (m == 0)
DocId docId = ((*endmarkerDocId)[endmarkerRank] + 1) % numberOfTexts;
// Map to doc ID:
docId = emptyTextRank->select0(docId+1);
- result.push_back(make_pair(docId, dist));
+ if (docId >= begin && docId <= end)
+ result.push_back(make_pair(docId, dist));
}
else
{
// Map to doc ID:
docId = emptyTextRank->select0(docId+1);
- result.push_back(make_pair(docId, textPos));
+ if (docId >= begin && docId <= end)
+ result.push_back(make_pair(docId, textPos));
}
}
if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
throw std::runtime_error("CSA::Save(): file write error (bwt end position).");
-
+
alphabetrank->save(file);
sampled->Save(file);
suffixes->Save(file);
suffixDocId->Save(file);
-
+
if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
throw std::runtime_error("CSA::Save(): file write error (numberOfTexts).");
if (std::fwrite(&(this->numberOfAllTexts), sizeof(unsigned), 1, file) != 1)
endmarkerDocId->Save(file);
emptyTextRank->Save(file);
+ fflush(file);
}
void CSA::Load(FILE *file, unsigned samplerate)
{
// Delete everything
+#ifdef CSA_TEST_BWT
delete dynFMI; dynFMI = 0;
+#endif
delete alphabetrank; alphabetrank = 0;
delete sampled; sampled = 0;
delete suffixes; suffixes = 0;
delete suffixDocId; suffixDocId = 0;
- delete positions; positions = 0;
delete [] codetable; codetable = 0;
delete endmarkerDocId; endmarkerDocId = 0;
delete emptyTextRank; emptyTextRank = 0;
- // FIXME Remove following:
- delete textLength; textLength = 0;
- delete textStartPos; textStartPos = 0;
this->maxTextLength = 0;
this->numberOfTexts = 0;
emptyTextRank = new BSGAP(file);
// FIXME Construct data structures with new samplerate
- //maketables(); // FIXME: this will redo text length tables
+ //maketables();
}
* Rest of the functions follow...
*/
-/*
- * Not supported
-uchar * CSA::Substring(TextPosition i, TextPosition l) const
+
+// FIXME Use 2D-search structure
+unsigned CSA::CountEndmarkers(TextPosition sp, TextPosition ep, DocId begin, DocId end) const
{
- uchar *result = new uchar[l + 1];
- if (l == 0)
- {
- result[0] = 0u;
- return result;
- }
-
- TextPosition dist;
- TextPosition k = i + l - 1;
- // Check for end of the string
- if (k > n - 1)
- {
- l -= k - n + 1;
- k = n - 1;
- }
+ if (sp > ep)
+ return 0;
- TextPosition skip = samplerate - k % samplerate - 1;
- TextPosition j;
- if (k / samplerate + 1 >= n / samplerate)
- {
- j = bwtEndPos;
- skip = n - k - 1;
- }
- else
- {
- j = (*positions)[k/samplerate+1];
- //cout << samplerate << ' ' << j << '\n';
- }
+ ulong ranksp = 0;
+ if (sp != 0)
+ ranksp = alphabetrank->rank(0, sp - 1);
- for (dist = 0; dist < skip + l; dist++)
+ unsigned resultSize = alphabetrank->rank(0, ep) - ranksp;
+ if (resultSize == 0)
+ return 0;
+
+ // Count end-markers in result interval and within [begin, end]
+ unsigned count = 0;
+ unsigned i = ranksp;
+ while (resultSize)
{
- int c = alphabetrank->access(j); //charAtPos(j, &alphabetrank_tmp);
- if (c == '\0')
- {
- // Rank among the end-markers in BWT
- unsigned endmarkerRank = alphabetrank->rank(0, j) - 1;
- j = (*endmarkerDocId)[endmarkerRank]; // LF-mapping for end-marker
- }
- else
- j = C[c]+alphabetrank->rank(c,j)-1; // LF-mapping
- if (dist >= skip)
- result[l + skip - dist - 1] = c;
+ // End-marker we found belongs to the "previous" doc in the collection
+ DocId docId = ((*endmarkerDocId)[i] + 1) % numberOfTexts;
+ // Map to doc ID:
+ docId = emptyTextRank->select0(docId+1);
+ if (docId >= begin && docId <= end)
+ ++ count;
+
+ -- resultSize;
+ ++ i;
}
- result[l] = 0u;
- return result;
+ return count;
}
-*/
- /*TextPosition CSA::inverse(TextPosition i)
-{
- TextPosition skip = samplerate - i % samplerate;
- TextPosition j;
- if (i / samplerate + 1 >= n / samplerate)
- {
- j = bwtEndPos;
- skip = n - i;
- }
- else
- {
- j = (*positions)[i/samplerate+1];
- //cout << samplerate << ' ' << j << '\n';
- }
-
- while (skip > 0)
- {
- int c = alphabetrank->charAtPos(j);
- j = C[c]+alphabetrank->rank(c,j)-1; // LF-mapping
- skip --;
- }
- return j;
- }*/
ulong CSA::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
{
return 0;
}
- /*TextPosition CSA::LF(uchar c, TextPosition &sp, TextPosition &ep)
+ulong CSA::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const
{
- sp = C[(int)c]+alphabetrank->rank(c,sp-1);
- ep = C[(int)c]+alphabetrank->rank(c,ep)-1;
-
+ // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
+ int c = (int)pattern[m-1];
+ assert(c == 0); // Start from endmarkers
+ TextPosition i=m-1;
+ TextPosition sp = begin;
+ TextPosition ep = end;
+ while (sp<=ep && i>=1)
+ {
+// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
+ c = (int)pattern[--i];
+ sp = C[c]+alphabetrank->rank(c,sp-1);
+ ep = C[c]+alphabetrank->rank(c,ep)-1;
+ }
+ *spResult = sp;
+ *epResult = ep;
if (sp<=ep)
return ep - sp + 1;
else
return 0;
- }*/
+}
-CSA::TextPosition CSA::Lookup(TextPosition i) const
+
+ulong CSA::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
{
- TextPosition dist=0;
- while (!sampled->IsBitSet(i))
+ // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
+ uint c = (int)pattern[m-1];
+ TextPosition i=m-1;
+ TextPosition sp = 1;
+ TextPosition ep = C[c+1]-1;
+ while (sp<=ep && i>=1)
{
-
- int c = alphabetrank->access(i);
- if (c == '\0')
- {
- // End-markers are sampled
- unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
- DocId docId = (*endmarkerDocId)[endmarkerRank];
- return (*textStartPos)[docId] + dist;
- }
- i = C[c]+alphabetrank->rank(c,i)-1;
- ++dist;
+// printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
+ c = (int)pattern[--i];
+ uint result = alphabetrank->rank(c,ep);
+ if (result == ~0u)
+ ep = 0;
+ else
+ ep = C[c]+result-1;
}
-
- return (*suffixes)[sampled->rank(i)-1]+dist;
+ *spResult = sp;
+ *epResult = ep;
+ if (sp<=ep)
+ return ep - sp + 1;
+ else
+ return 0;
}
+
CSA::~CSA() {
+#ifdef CSA_TEST_BWT
delete dynFMI;
+#endif
delete alphabetrank;
delete sampled;
delete suffixes;
delete suffixDocId;
- delete positions;
- delete [] codetable;
+ delete [] codetable; // FIXME remove
delete endmarkerDocId;
- delete textLength;
- delete textStartPos;
delete emptyTextRank;
}
for (i=255;i>=min;--i)
if (C[i]>0) {max = i; break;}
- // Print frequencies
- /*for(i = 0; i < 256; i++)
- if (C[i]>0) printf("C[%lu] = %lu\n", i, C[i]);
- fflush(stdout);*/
-
ulong prev=C[0], temp;
C[0]=0;
for (i=1;i<256;i++) {
// alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0);
// delete [] bwt;
//alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt!
+// std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
+// std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
- uint *text = new uint[n];
- for (i = 0; i < n; ++i) // Silly
- text[i] = bwt[i];
- delete [] bwt;
- bwt = 0;
+ HeapProfiler::ResetMaxHeapConsumption(); // FIXME remove
alphabet_mapper * am = new alphabet_mapper_none();
- static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(16); // FIXME samplerate?
-
- //cout << "Building Huffman table..."; cout.flush();
-
- wt_coder * wtc = new wt_coder_huff(text,n,am);
-
- //cout << "done" << endl; cout.flush();
- //cout << "Building static_sequence..."; cout.flush();
-
- alphabetrank = new static_sequence_wvtree(text,n,wtc,bmb,am);
- delete [] text;
- text = 0;
-
-/* for (i = 0; i < n; ++i)
- {
- uchar c = alphabetrank->charAtPos(i);
- TextPosition j = C[c]+alphabetrank->rank(c, i)-1;
- printf("LF[%lu] = %lu\n", i, j);
- }*/
+ static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(8); // FIXME samplerate?
+// static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(16); // FIXME samplerate?
+ wt_coder * wtc = new wt_coder_binary(bwt,n,am);
+ alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am);
+ delete bmb;
+ bwt = 0; // already deleted
+
+// std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
+// std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
}
void CSA::maketables()
{
+ // Calculate BWT end-marker position (of last inserted text)
+ // Note: bwtEndPos already set!
+ // and the length of the first text (counter l):
+#ifdef CSA_TEST_BWT
+ {
+ ulong i = 0;
+ ulong l = 1;
+ uint alphabetrank_i_tmp = 0;
+ uchar c = alphabetrank->access(i, alphabetrank_i_tmp);
+ while (c != '\0')
+ {
+ i = C[c]+alphabetrank_i_tmp-1;
+ ++l;
+ c = alphabetrank->access(i, alphabetrank_i_tmp);
+ }
+
+ if (i != bwtEndPos) // compare result
+ {
+ std::cout << "i = " << i << ", bwtendpos = " << bwtEndPos << std::endl;
+ exit(0);
+ }
+ }
+#endif
+
+ // Build up arrays for text length and starting positions
+ // FIXME Temp, remove
+ //BlockArray* textLength = new BlockArray(numberOfTexts, Tools::CeilLog2(maxTextLength));
+ BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
+ //(*textLength)[0] = l;
+ (*textStartPos)[0] = 0;
+
+ // Construct samples
ulong sampleLength = (n%samplerate==0) ? n/samplerate : n/samplerate+1;
-
- ulong *sampledpositions = new ulong[n/W+1];
unsigned ceilLog2n = Tools::CeilLog2(n);
- positions = new BlockArray(sampleLength, ceilLog2n);
+ BlockArray* positions = new BlockArray(sampleLength, ceilLog2n);
BlockArray* tmpSuffix = new BlockArray(sampleLength, ceilLog2n);
// Mapping from end-markers to doc ID's:
endmarkerDocId = new BlockArray(numberOfTexts, Tools::CeilLog2(numberOfTexts));
- ulong i,j=0;
- for (i=0;i<n/W+1;i++)
+ ulong *sampledpositions = new ulong[n/W+1];
+ for (ulong i=0;i<n/W+1;i++)
sampledpositions[i]=0lu;
ulong x,p=bwtEndPos;
ulong sampleCount = 0;
- // Keeping track of text position of end-markers seen
+ // Keeping track of text position of prev. end-marker seen
ulong posOfSuccEndmarker = n;
DocId textId = numberOfTexts;
ulong ulongmax = 0;
ulongmax--;
+ uint alphabetrank_i_tmp =0;
//positions:
- for (i=n-1;i<ulongmax;i--) { // TODO bad solution with ulongmax?
+ for (
ulong i=n-1;i<ulongmax;i--) { // TODO bad solution with ulongmax?
// i substitutes SA->GetPos(i)
x=(i==n-1)?0:i+1;
sampleCount ++;
}
- uchar c = alphabetrank->access(p);
+ uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
if (c == '\0')
{
--textId;
// Record the order of end-markers in BWT:
- ulong endmarkerRank = alphabetrank->rank(0, p) - 1;
+ ulong endmarkerRank = alphabetrank_i_tmp - 1;
(*endmarkerDocId)[endmarkerRank] = textId;
// Store text length and text start position:
if (textId < (DocId)numberOfTexts - 1)
{
- (*textLength)[textId + 1] = posOfSuccEndmarker - x;
+ //(*textLength)[textId + 1] = posOfSuccEndmarker - x;
(*textStartPos)[textId + 1] = x; // x is the position of end-marker.
posOfSuccEndmarker = x;
}
p = textId; // Correct LF-mapping to the last char of the previous text.
}
else
- p = C[c]+alphabetrank->rank(c, p)-1;
+ p = C[c]+alphabetrank_i_tmp-1;
}
assert(textId == 0);
- /*i = 0;
- for (map<ulong, pair<DocId, ulong> >::iterator it = endmarkers.begin(); it != endmarkers.end(); ++it, ++i)
- {
- int docc = (*endmarkerDocId)[i];
- ulong poss = (*endmarkerPos)[i];
- printf("endm[%u] = %lu (text pos: %lu) (recorded: %d, %lu)\n", (it->second).first, it->first, (it->second).second, docc, poss);
- }*/
-/*
- for (i = 0; i < numberOfTexts; ++ i)
- {
- //std::cout << "textlength = " << dynTextLength[i].first << " vs " << (*textLength)[i] << ", textStartPos = " << dynTextLength[i].second << " vs " << (*textStartPos)[i] << std::endl;
- assert(dynTextLength[i].first == (*textLength)[i]);
- assert(dynTextLength[i].second == (*textStartPos)[i]);
- }
-*/
sampled = new BSGAP(sampledpositions,n,true);
sampleLength = sampled->rank(n-1);
assert(sampleCount == sampleLength);
-// std::cout << ";sampleLength;" << sampleLength << std::endl;
- // Suffixes == offset from text start position
+
+ // Suffixes store an offset from the text start position
suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength));
suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts));
- //suffixes:
- for(i=0; i<sampleLength; i++) {
+ for(ulong i=0; i<sampleLength; i++) {
assert((*positions)[i] < n);
- j = sampled->rank((*positions)[i]);
+ ulong j = sampled->rank((*positions)[i]);
if (j==0) j=sampleLength;
- TextPosition textPos = (*tmpSuffix)[i]; //(i*samplerate==n)?0:i*samplerate;
- (*suffixDocId)[j-1] = DocIdAtTextPos(textPos); // (*suffixes)[j-1]);
+ TextPosition textPos = (*tmpSuffix)[i];
+ (*suffixDocId)[j-1] = DocIdAtTextPos(textStartPos, textPos);
- assert((unsigned)DocIdAtTextPos(textPos) < numberOfTexts);
+ assert((unsigned)DocIdAtTextPos(textStartPos, textPos) < numberOfTexts);
assert((*suffixDocId)[j-1] < numberOfTexts);
// calculate offset from text start:
(*suffixes)[j-1] = textPos - (*textStartPos)[(*suffixDocId)[j-1]];
}
// FIXME Temp, remove
delete tmpSuffix;
- tmpSuffix=0;
delete positions;
- positions =0;
- delete textLength;
- textLength = 0;
+// delete textLength;
delete textStartPos;
- textStartPos = 0;
}
* Starting text position of the document is stored into second parameter.
* Binary searching on text starting positions.
*/
-TextCollection::DocId CSA::DocIdAtTextPos(TextPosition i) const
+TextCollection::DocId CSA::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const
{
assert(i < n);
return x | (bit << pos);
}
+} // namespace SXSI
+
projects / SXSI / TextCollection.git / blobdiff