TCImplementation.cpp

   1 /******************************************************************************
   2  *   Copyright (C) 2006-2008 by Veli Mäkinen and Niko Välimäki                *
   3  *                                                                            *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  19  *****************************************************************************/
  20 #include "TCImplementation.h"
  21
  22 //#define DEBUG_MEMUSAGE
  23 #ifdef DEBUG_MEMUSAGE
  24 #include "HeapProfiler.h" // FIXME remove
  25 #endif
  26
  27 #include <iostream>
  28 #include <map>
  29 #include <set>
  30 #include <vector>
  31 #include <utility>
  32 #include <stdexcept>
  33 #include <cassert>
  34 #include <cstring> // For strlen()
  35 using std::vector;
  36 using std::pair;
  37 using std::make_pair;
  38 using std::map;
  39 using std::string;
  40 namespace SXSI
  41 {
  42
  43 // Save file version info
  44 const uchar TCImplementation::versionFlag = 8;
  45
  46 /**
  47  * Constructor inits an empty dynamic FM-index.
  48  * Samplerate defaults to TEXTCOLLECTION_DEFAULT_SAMPLERATE.
  49  */
  50 TCImplementation::TCImplementation(uchar * bwt, ulong length, unsigned samplerate_,
  51                      unsigned numberOfTexts_, ulong maxTextLength_, ulong numberOfSamples_,
  52                      CSA::DeltaVector & notIndexed, const string & niText, char tsType)
  53     : n(length), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
  54       suffixDocId(0), numberOfTexts(numberOfTexts_), maxTextLength(maxTextLength_), Doc(0)
  55 {
  56     makewavelet(bwt); // Deletes bwt!
  57     bwt = 0;
  58
  59     // Make sampling tables
  60     maketables(numberOfSamples_, tsType, notIndexed, niText);
  61 }
  62
  63 bool TCImplementation::EmptyText(DocId k) const
  64 {
  65     assert(k < (DocId)numberOfTexts);
  66     return false; // Empty texts are not indexed
  67 }
  68
  69 uchar * TCImplementation::GetText(DocId k) const
  70 {
  71     assert(k < (DocId)numberOfTexts);
  72
  73     return textStorage->GetText(k);
  74 /*    TextPosition i = k;
  75
  76     string result;
  77     // Reserve average string length to avoid reallocs
  78     result.reserve(n/numberOfTexts);
  79
  80     uchar c = alphabetrank->access(i);
  81     while (c != '\0')
  82     {
  83         result.push_back(c);
  84         i = C[c]+alphabetrank->rank(c,i)-1;
  85
  86         c = alphabetrank->access(i); // "next" char.
  87     }
  88
  89     // Convert to uchar (FIXME return string?)
  90     i = result.size();
  91     uchar* res = new uchar[i+1];
  92     res[i] = '\0';
  93     for (ulong j = 0; j < i; ++j)
  94         res[i-j-1] = result[j];
  95         return res;*/
  96 }
  97
  98 /*
  99  * Substring queries are supported via the pointer returned by TextStorage::GetText
 100 uchar* TCImplementation::GetText(DocId k, TextPosition i, TextPosition j) const
 101 {
 102     assert(k < (DocId)numberOfTexts);
 103     assert(j < (*textLength)[k]);
 104     assert(i <= j);
 105
 106     ulong textRank = 0;
 107
 108     // Start position of k'th text
 109     ulong start = (*textStartPos)[k];
 110
 111     return Substring(i + start, j-i+1);
 112     }*/
 113
 114
 115
 116 /******************************************************************
 117  * Existential queries
 118  */
 119 bool TCImplementation::IsPrefix(uchar const * pattern) const
 120 {
 121     TextPosition m = strlen((char *)pattern);
 122     if (m == 0)
 123         return true;
 124
 125     TextPosition sp = 0, ep = 0;
 126     Search(pattern, m, &sp, &ep);
 127
 128     // Check for end-marker(s) in result interval
 129     if (CountEndmarkers(sp, ep))
 130         return true;
 131     return false;
 132 }
 133
 134 bool TCImplementation::IsPrefix(uchar const * pattern, DocId begin, DocId end) const
 135 {
 136     TextPosition m = strlen((char *)pattern);
 137     if (m == 0)
 138         return true;
 139
 140     TextPosition sp = 0, ep = 0;
 141     Search(pattern, m, &sp, &ep);
 142
 143     // Check for end-marker(s) in result interval
 144     if (CountEndmarkers(sp, ep, begin, end))
 145         return true;
 146     return false;
 147 }
 148
 149
 150 bool TCImplementation::IsSuffix(uchar const *pattern) const
 151 {
 152     // Here counting is as fast as IsSuffix():
 153     if (CountSuffix(pattern) > 0)
 154         return true;
 155     return false;
 156 }
 157
 158 bool TCImplementation::IsSuffix(uchar const *pattern, DocId begin, DocId end) const
 159 {
 160     // Here counting is as fast as IsSuffix():
 161     if (CountSuffix(pattern, begin, end) > 0)
 162         return true;
 163     return false;
 164 }
 165
 166 bool TCImplementation::IsEqual(uchar const *pattern) const
 167 {
 168     TextPosition m = std::strlen((char *)pattern);
 169     if (m == 0)
 170         return false; // No empty texts exists
 171
 172     TextPosition sp = 0, ep = 0;
 173     // Match including end-marker
 174     Search(pattern, m+1, &sp, &ep);
 175
 176     // Check for end-marker(s) in result interval
 177     if (CountEndmarkers(sp, ep))
 178         return true;
 179     return false;
 180 }
 181
 182 bool TCImplementation::IsEqual(uchar const *pattern, DocId begin, DocId end) const
 183 {
 184     TextPosition m = std::strlen((char *)pattern);
 185     if (m == 0)
 186         return false; // No empty texts exists
 187
 188     TextPosition sp = 0, ep = 0;
 189     // Match including end-marker
 190     Search(pattern, m+1, &sp, &ep, begin, end);
 191
 192     // Check for end-marker(s) in result interval
 193     if (CountEndmarkers(sp, ep))
 194         return true;
 195     return false;
 196 }
 197
 198 bool TCImplementation::IsContains(uchar const * pattern) const
 199 {
 200     TextPosition m = strlen((char *)pattern);
 201     if (m == 0)
 202         return true;
 203
 204     TextPosition sp = 0, ep = 0;
 205     // Just check if pattern exists somewhere
 206     ulong count = Search(pattern, m, &sp, &ep);
 207
 208     if (count > 0)
 209         return true;
 210     return false;
 211 }
 212
 213 bool TCImplementation::IsContains(uchar const * pattern, DocId begin, DocId end) const
 214 {
 215     // Here counting is as fast as existential querying
 216     if (CountContains(pattern, begin, end) > 0)
 217         return true; // FIXME No need to filter result set
 218     return false;
 219 }
 220
 221 bool TCImplementation::IsLessThan(uchar const * pattern) const
 222 {
 223     if (CountLessThan(pattern) > 0)
 224         return true;
 225     return false;
 226 }
 227
 228 bool TCImplementation::IsLessThan(uchar const * pattern, DocId begin, DocId end) const
 229 {
 230     if (CountLessThan(pattern, begin, end) > 0)
 231         return true;
 232     return false;
 233 }
 234
 235 /******************************************************************
 236  * Counting queries
 237  */
 238 ulong TCImplementation::Count(uchar const * pattern) const
 239 {
 240     TextPosition m = strlen((char *)pattern);
 241     if (m == 0)
 242         return 0;
 243
 244     TextPosition sp = 0, ep = 0;
 245     unsigned count = (unsigned) Search(pattern, m, &sp, &ep);
 246     return count;
 247 }
 248
 249 unsigned TCImplementation::CountPrefix(uchar const * pattern) const
 250 {
 251     TextPosition m = strlen((char *)pattern);
 252     if (m == 0)
 253         return numberOfTexts;
 254
 255     TextPosition sp = 0, ep = 0;
 256     Search(pattern, m, &sp, &ep);
 257
 258     // Count end-markers in result interval
 259     return CountEndmarkers(sp, ep);
 260 }
 261
 262 unsigned TCImplementation::CountPrefix(uchar const * pattern, DocId begin, DocId end) const
 263 {
 264     TextPosition m = strlen((char *)pattern);
 265     if (m == 0)
 266         return numberOfTexts;
 267
 268     TextPosition sp = 0, ep = 0;
 269     Search(pattern, m, &sp, &ep);
 270
 271     // Count end-markers in result interval
 272     return CountEndmarkers(sp, ep, begin, end);
 273 }
 274
 275 unsigned TCImplementation::CountSuffix(uchar const * pattern) const
 276 {
 277     TextPosition m = strlen((char *)pattern);
 278     if (m == 0)
 279         return numberOfTexts;
 280
 281     TextPosition sp = 0, ep = 0;
 282     // Search with end-marker
 283     unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep);
 284
 285     return count;
 286 }
 287
 288 unsigned TCImplementation::CountSuffix(uchar const * pattern, DocId begin, DocId end) const
 289 {
 290     TextPosition m = strlen((char *)pattern);
 291     if (m == 0)
 292         return numberOfTexts;
 293
 294     TextPosition sp = 0, ep = 0;
 295     // Search with end-marker
 296     unsigned count = (unsigned) Search(pattern, m+1, &sp, &ep, begin, end);
 297
 298     return count;
 299 }
 300
 301 unsigned TCImplementation::CountEqual(uchar const *pattern) const
 302 {
 303     TextPosition m = strlen((char const *)pattern);
 304     if (m == 0)
 305         return 0; // No empty texts.
 306
 307     TextPosition sp = 0, ep = 0;
 308     // Match including end-marker
 309     Search(pattern, m+1, &sp, &ep);
 310
 311     // Count end-markers in result interval
 312     return CountEndmarkers(sp, ep);
 313 }
 314
 315 unsigned TCImplementation::CountEqual(uchar const *pattern, DocId begin, DocId end) const
 316 {
 317     TextPosition m = strlen((char const *)pattern);
 318     if (m == 0)
 319         return 0; // No empty texts.
 320
 321     TextPosition sp = 0, ep = 0;
 322     // Match including end-marker
 323     Search(pattern, m+1, &sp, &ep, begin, end);
 324
 325     // Count end-markers in result interval
 326     return CountEndmarkers(sp, ep); // Already within [begin, end]
 327 }
 328
 329 unsigned TCImplementation::CountContains(uchar const * pattern) const
 330 {
 331     TextPosition m = strlen((char const *)pattern);
 332     if (m == 0)
 333         return numberOfTexts; // Total number of texts.
 334
 335     // Here counting is as slow as fetching the result set
 336     // because we have to filter out occ's that fall within same document.
 337     TextCollection::document_result result = Contains(pattern);
 338     return result.size();
 339 }
 340
 341 unsigned TCImplementation::CountContains(uchar const * pattern, DocId begin, DocId end) const
 342 {
 343     TextPosition m = strlen((char const *)pattern);
 344     if (m == 0)
 345         return numberOfTexts; // Total number of texts.
 346
 347     // Here counting is as slow as fetching the result set
 348     // because we have to filter out occ's that fall within same document.
 349     TextCollection::document_result result = Contains(pattern, begin, end);
 350     return result.size();
 351 }
 352
 353 // Less than or equal
 354 unsigned TCImplementation::CountLessThan(uchar const * pattern) const
 355 {
 356     TextPosition m = strlen((char const *)pattern);
 357     if (m == 0)
 358         return 0; // No empty texts.
 359
 360     TextPosition sp = 0, ep = 0;
 361     SearchLessThan(pattern, m, &sp, &ep);
 362
 363     // Count end-markers in result interval
 364     return CountEndmarkers(sp, ep);
 365 }
 366
 367 unsigned TCImplementation::CountLessThan(uchar const * pattern, DocId begin, DocId end) const
 368 {
 369     TextPosition m = strlen((char const *)pattern);
 370     if (m == 0)
 371         return 0; // No empty texts.
 372
 373     TextPosition sp = 0, ep = 0;
 374     SearchLessThan(pattern, m, &sp, &ep);
 375
 376     // Count end-markers in result interval
 377     return CountEndmarkers(sp, ep, begin, end);
 378 }
 379
 380 /**
 381  * Document reporting queries
 382  */
 383 TextCollection::document_result TCImplementation::Prefix(uchar const * pattern) const
 384 {
 385     TextPosition m = strlen((char *)pattern);
 386     if (m == 0)
 387         return TextCollection::document_result(); // FIXME Should return all 1...k
 388
 389     TextPosition sp = 0, ep = 0;
 390     Search(pattern, m, &sp, &ep);
 391
 392     // Iterate through end-markers in [sp,ep]:
 393     return EnumerateEndmarkers(sp, ep);
 394 }
 395
 396 TextCollection::document_result TCImplementation::Prefix(uchar const * pattern, DocId begin, DocId end) const
 397 {
 398     TextPosition m = strlen((char *)pattern);
 399     if (m == 0)
 400         return TextCollection::document_result(); // FIXME Should return all 1...k
 401
 402     TextPosition sp = 0, ep = 0;
 403     Search(pattern, m, &sp, &ep);
 404
 405     // Return end-markers in [sp,ep] and [begin, end]:
 406     return EnumerateEndmarkers(sp, ep, begin, end);
 407 }
 408
 409 TextCollection::document_result TCImplementation::Suffix(uchar const * pattern) const
 410 {
 411     TextPosition m = strlen((char *)pattern);
 412     if (m == 0)
 413         return TextCollection::document_result(); // FIXME Should return all 1...k
 414
 415     TextPosition sp = 0, ep = 0;
 416     // Search with end-marker
 417     Search(pattern, m+1, &sp, &ep);
 418
 419     TextCollection::document_result result;
 420     result.reserve(ep-sp+1); // Try to avoid reallocation.
 421
 422     // Check each occurrence
 423     for (; sp <= ep; ++sp)
 424     {
 425         TextPosition i = sp;
 426
 427         uchar c = alphabetrank->access(i);
 428         while (c != '\0' && !sampled->access(i))
 429         {
 430             i = C[c]+alphabetrank->rank(c,i)-1;
 431             c = alphabetrank->access(i);
 432         }
 433         // Assert: c == '\0'  OR  sampled->IsBitSet(i)
 434
 435         if (c == '\0')
 436         {
 437             // Rank among the end-markers in BWT
 438             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 439             result.push_back(Doc->access(endmarkerRank));
 440         }
 441         else // Sampled position
 442         {
 443             DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
 444             result.push_back(docId);
 445         }
 446     }
 447
 448     return result;
 449 }
 450
 451 TextCollection::document_result TCImplementation::Suffix(uchar const * pattern, DocId begin, DocId end) const
 452 {
 453     TextPosition m = strlen((char *)pattern);
 454     if (m == 0)
 455         return TextCollection::document_result(); // FIXME Should return all 1...k
 456
 457     TextPosition sp = 0, ep = 0;
 458     // Search with end-marker
 459     Search(pattern, m+1, &sp, &ep, begin, end);
 460
 461     TextCollection::document_result result;
 462     result.reserve(ep-sp+1); // Try to avoid reallocation.
 463
 464     // Check each occurrence, already within [begin, end]
 465     for (; sp <= ep; ++sp)
 466     {
 467         TextPosition i = sp;
 468
 469         uchar c = alphabetrank->access(i);
 470         while (c != '\0' && !sampled->access(i))
 471         {
 472             i = C[c]+alphabetrank->rank(c,i)-1;
 473             c = alphabetrank->access(i);
 474         }
 475         // Assert: c == '\0'  OR  sampled->IsBitSet(i)
 476
 477         if (c == '\0')
 478         {
 479             // Rank among the end-markers in BWT
 480             unsigned endmarkerRank = alphabetrank->rank(0, i) - 1;
 481             result.push_back(Doc->access(endmarkerRank));
 482         }
 483         else // Sampled position
 484         {
 485             DocId docId = (*suffixDocId)[sampled->rank1(i)-1];
 486             result.push_back(docId);
 487         }
 488     }
 489
 490     return result;
 491 }
 492
 493
 494 TextCollection::document_result TCImplementation::Equal(uchar const *pattern) const
 495 {
 496     TextPosition m = strlen((char const *)pattern);
 497     if (m == 0)
 498         return TextCollection::document_result(); // FIXME Should return all empty texts
 499
 500     TextPosition sp = 0, ep = 0;
 501     // Match including end-marker
 502     Search(pattern, m+1, &sp, &ep);
 503
 504     // Report end-markers in result interval
 505     return EnumerateEndmarkers(sp, ep);
 506 }
 507
 508 TextCollection::document_result TCImplementation::Equal(uchar const *pattern, DocId begin, DocId end) const
 509 {
 510     TextPosition m = strlen((char const *)pattern);
 511     if (m == 0)
 512         return TextCollection::document_result(); // FIXME Should return all empty texts
 513
 514     TextPosition sp = 0, ep = 0;
 515     // Match including end-marker
 516     Search(pattern, m+1, &sp, &ep, begin, end);
 517
 518     // Report end-markers in result interval
 519     return EnumerateEndmarkers(sp, ep, begin, end);
 520 }
 521
 522
 523 TextCollection::document_result TCImplementation::Contains(uchar const * pattern) const
 524 {
 525     TextPosition m = strlen((char *)pattern);
 526     if (m == 0)
 527         return TextCollection::document_result();
 528
 529     TextPosition sp = 0, ep = 0;
 530     // Search all occurrences
 531     Search(pattern, m, &sp, &ep);
 532
 533     // We want unique document indentifiers, using std::set to collect them
 534     std::set<DocId> resultSet;
 535     EnumerateDocuments(resultSet, sp, ep);
 536
 537     // Convert std::set to std::vector
 538     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 539     return result;
 540 }
 541
 542 TextCollection::document_result TCImplementation::Contains(uchar const * pattern, DocId begin, DocId end) const
 543 {
 544     TextPosition m = strlen((char *)pattern);
 545     if (m == 0)
 546         return TextCollection::document_result();
 547
 548     TextPosition sp = 0, ep = 0;
 549     // Search all occurrences
 550     Search(pattern, m, &sp, &ep);
 551
 552     // We want unique document indentifiers, using std::set to collect them
 553     std::set<DocId> resultSet;
 554     EnumerateDocuments(resultSet, sp, ep, begin, end);
 555
 556     // Convert std::set to std::vector
 557     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 558     return result;
 559 }
 560
 561
 562 /**
 563  ***
 564 * * FIXME Lessthan or equal
 565  */
 566 TextCollection::document_result TCImplementation::LessThan(uchar const * pattern) const
 567 {
 568     TextPosition m = strlen((char *)pattern);
 569     if (m == 0)
 570         return TextCollection::document_result(); // empty result set
 571
 572     TextPosition sp = 0, ep = 0;
 573     SearchLessThan(pattern, m, &sp, &ep);
 574
 575     // Report end-markers in result interval
 576     return EnumerateEndmarkers(sp, ep);
 577 }
 578
 579 TextCollection::document_result TCImplementation::LessThan(uchar const * pattern, DocId begin, DocId end) const
 580 {
 581     TextPosition m = strlen((char *)pattern);
 582     if (m == 0)
 583         return TextCollection::document_result(); // empty result set
 584
 585     TextPosition sp = 0, ep = 0;
 586     SearchLessThan(pattern, m, &sp, &ep);
 587
 588     // Iterate through end-markers in [sp,ep] and [begin, end]:
 589     return EnumerateEndmarkers(sp, ep, begin, end);
 590 }
 591
 592
 593 TextCollection::document_result TCImplementation::KMismaches(uchar const * pattern, unsigned k) const
 594 {
 595     TextPosition m = strlen((char *)pattern);
 596     if (m == 0)
 597         return TextCollection::document_result(); // empty result set
 598
 599     suffix_range_vector ranges;
 600     kmismatches(ranges, pattern, 0, n-1, m, k);
 601     std::set<DocId> resultSet;
 602
 603     for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
 604         // Iterate through docs in [sp,ep]:
 605         EnumerateDocuments(resultSet, (*it).first, (*it).second);
 606
 607     // Convert std::set to std::vector
 608     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 609     return result;
 610 }
 611
 612 TextCollection::document_result TCImplementation::KErrors(uchar const * pattern, unsigned k) const
 613 {
 614     TextPosition m = strlen((char *)pattern);
 615     if (m == 0)
 616         return TextCollection::document_result(); // empty result set
 617
 618     suffix_range_vector ranges;
 619     ulong *dd = new ulong[m+1];
 620     for (ulong i=0;i<m+1;i++)
 621         dd[i]=i;
 622     kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
 623     delete [] dd;
 624
 625     std::set<DocId> resultSet;
 626     for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
 627         // Iterate through docs in [sp,ep]:
 628         EnumerateDocuments(resultSet, (*it).first, (*it).second);
 629
 630     // Convert std::set to std::vector
 631     TextCollection::document_result result(resultSet.begin(), resultSet.end());
 632     return result;
 633 }
 634
 635
 636 /**
 637  * Full result set queries
 638  */
 639 TextCollection::full_result TCImplementation::FullContains(uchar const * pattern) const
 640 {
 641     TextPosition m = strlen((char *)pattern);
 642     if (m == 0)
 643         return full_result(); // FIXME Throw exception?
 644
 645     TextPosition sp = 0, ep = 0;
 646     // Search all occurrences
 647     Search(pattern, m, &sp, &ep);
 648
 649     full_result result;
 650     result.reserve(ep-sp+1); // Try to avoid reallocation.
 651     EnumeratePositions(result, sp, ep);
 652
 653     return result;
 654 }
 655
 656 TextCollection::full_result TCImplementation::FullContains(uchar const * pattern, DocId begin, DocId end) const
 657 {
 658     TextPosition m = strlen((char *)pattern);
 659     if (m == 0)
 660         return full_result(); // FIXME Throw exception?
 661
 662     TextPosition sp = 0, ep = 0;
 663     // Search all occurrences
 664     Search(pattern, m, &sp, &ep);
 665
 666     full_result result;
 667     result.reserve(ep-sp+1); // Try to avoid reallocation.
 668     EnumeratePositions(result, sp, ep, begin, end);
 669
 670     return result;
 671 }
 672
 673 TextCollection::full_result TCImplementation::FullKMismatches(uchar const * pattern, unsigned k) const
 674 {
 675     TextPosition m = strlen((char *)pattern);
 676     if (m == 0)
 677         return TextCollection::full_result(); // empty result set
 678
 679     suffix_range_vector ranges;
 680     ulong count = kmismatches(ranges, pattern, 0, n-1, m, k);
 681
 682     TextCollection::full_result result;
 683     result.reserve(count); // avoid reallocation.
 684     for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
 685         // Iterate through docs in [sp,ep]:
 686         EnumeratePositions(result, (*it).first, (*it).second);
 687     return result;
 688 }
 689
 690 TextCollection::full_result TCImplementation::FullKErrors(uchar const * pattern, unsigned k) const
 691 {
 692     TextPosition m = strlen((char *)pattern);
 693     if (m == 0)
 694         return TextCollection::full_result(); // empty result set
 695
 696     suffix_range_vector ranges;
 697     ulong *dd = new ulong[m+1];
 698     for (unsigned i=0;i<m+1;i++)
 699         dd[i]=i;
 700     ulong count = kerrors(ranges, pattern, 0, n-1, m+k, k, dd, m);
 701     delete [] dd;
 702
 703     TextCollection::full_result result;
 704     result.reserve(count); // avoid reallocation.
 705     for (suffix_range_vector::iterator it = ranges.begin(); it != ranges.end(); ++it)
 706         // Iterate through docs in [sp,ep]:
 707         EnumeratePositions(result, (*it).first, (*it).second);
 708     return result;
 709 }
 710
 711
 712 /**
 713  * Save index to a file handle
 714  *
 715  * Throws a std::runtime_error exception on i/o error.
 716  * First byte that is saved represents the version number of the save file.
 717  * In version 2 files, the data fields are:
 718  *  uchar versionFlag;
 719     TextPosition n;
 720     unsigned samplerate;
 721     unsigned C[256];
 722     TextPosition bwtEndPos;
 723     static_sequence * alphabetrank;
 724     BSGAP *sampled;
 725     BlockArray *suffixes;
 726     BlockArray *suffixDocId;
 727     unsigned numberOfTexts;
 728     ulong maxTextLength;
 729     static_sequence *docId;
 730  */
 731 void TCImplementation::Save(FILE *file) const
 732 {
 733     // Saving version info:
 734     if (std::fwrite(&versionFlag, 1, 1, file) != 1)
 735         throw std::runtime_error("TCImplementation::Save(): file write error (version flag).");
 736
 737     if (std::fwrite(&(this->n), sizeof(TextPosition), 1, file) != 1)
 738         throw std::runtime_error("TCImplementation::Save(): file write error (n).");
 739     if (std::fwrite(&(this->samplerate), sizeof(unsigned), 1, file) != 1)
 740         throw std::runtime_error("TCImplementation::Save(): file write error (samplerate).");
 741
 742     for(ulong i = 0; i < 256; ++i)
 743         if (std::fwrite(this->C + i, sizeof(unsigned), 1, file) != 1)
 744             throw std::runtime_error("TCImplementation::Save(): file write error (C table).");
 745
 746     if (std::fwrite(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
 747         throw std::runtime_error("TCImplementation::Save(): file write error (bwt end position).");
 748
 749     alphabetrank->save(file);
 750     sampled->save(file);
 751     suffixes->Save(file);
 752     suffixDocId->Save(file);
 753
 754     if (std::fwrite(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 755         throw std::runtime_error("TCImplementation::Save(): file write error (numberOfTexts).");
 756     if (std::fwrite(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
 757         throw std::runtime_error("TCImplementation::Save(): file write error (maxTextLength).");
 758
 759     Doc->save(file);
 760     textStorage->Save(file);
 761     fflush(file);
 762 }
 763
 764
 765 /**
 766  * Load index from a file handle
 767  *
 768  * Throws a std::runtime_error exception on i/o error.
 769  * For more info, see TCImplementation::Save().
 770  *
 771  * index_mode_t is defined in TextCollection.h and
 772  * defaults to both the index and "naive" text.
 773  *
 774  * Note: Samplerate can not be changed during load.
 775  */
 776 TCImplementation::TCImplementation(FILE *file, index_mode_t im, unsigned samplerate_)
 777     : n(0), samplerate(samplerate_), alphabetrank(0), sampled(0), suffixes(0),
 778       suffixDocId(0), numberOfTexts(0), maxTextLength(0), Doc(0)
 779 {
 780     uchar verFlag = 0;
 781     if (std::fread(&verFlag, 1, 1, file) != 1)
 782         throw std::runtime_error("TCImplementation::Load(): file read error (version flag).");
 783     if (verFlag != TCImplementation::versionFlag)
 784         throw std::runtime_error("TCImplementation::Load(): invalid save file version.");
 785
 786     if (std::fread(&(this->n), sizeof(TextPosition), 1, file) != 1)
 787         throw std::runtime_error("TCImplementation::Load(): file read error (n).");
 788     if (std::fread(&samplerate, sizeof(unsigned), 1, file) != 1)
 789         throw std::runtime_error("TCImplementation::Load(): file read error (samplerate).");
 790 // FIXME samplerate can not be changed during load.
 791 //    if (this->samplerate == 0)
 792 //        this->samplerate = samplerate;
 793
 794     for(ulong i = 0; i < 256; ++i)
 795         if (std::fread(this->C + i, sizeof(unsigned), 1, file) != 1)
 796             throw std::runtime_error("TCImplementation::Load(): file read error (C table).");
 797
 798     if (std::fread(&(this->bwtEndPos), sizeof(TextPosition), 1, file) != 1)
 799         throw std::runtime_error("TCImplementation::Load(): file read error (bwt end position).");
 800
 801     alphabetrank = static_sequence::load(file);
 802     if (im == index_mode_text_only) { delete alphabetrank; alphabetrank = 0; }
 803
 804     sampled = static_bitsequence::load(file);
 805     if (im == index_mode_text_only) { delete sampled; sampled = 0; }
 806     suffixes = new BlockArray(file);
 807     if (im == index_mode_text_only) { delete suffixes; suffixes = 0; }
 808     suffixDocId = new BlockArray(file);
 809     if (im == index_mode_text_only) { delete suffixDocId; suffixDocId = 0; }
 810
 811     if (std::fread(&(this->numberOfTexts), sizeof(unsigned), 1, file) != 1)
 812         throw std::runtime_error("TCImplementation::Load(): file read error (numberOfTexts).");
 813     if (std::fread(&(this->maxTextLength), sizeof(ulong), 1, file) != 1)
 814         throw std::runtime_error("TCImplementation::Load(): file read error (maxTextLength).");
 815
 816     Doc = new ArrayDoc(file); //static_sequence::load(file);
 817     if (im == index_mode_text_only) { delete Doc; Doc = 0; }
 818
 819     textStorage = TextStorage::Load(file);
 820
 821     // FIXME Construct data structures with new samplerate
 822     //maketables();
 823 }
 824
 825
 826
 827 /**
 828  * Rest of the functions follow...
 829  */
 830 ulong TCImplementation::searchPrefix(uchar const *pattern, ulong i, ulong *sp, ulong *ep) const
 831 {
 832     int c;
 833     while (*sp<=*ep && i>=1)
 834     {
 835         c = (int)pattern[--i];
 836         *sp = C[c]+alphabetrank->rank(c,*sp-1);
 837         *ep = C[c]+alphabetrank->rank(c,*ep)-1;
 838     }
 839     if (*sp<=*ep)
 840         return *ep - *sp + 1;
 841     else
 842         return 0;
 843 }
 844
 845
 846 ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const
 847 {
 848     if (sp>ep) return 0;
 849     if (j == 0)
 850     {
 851         result.push_back(std::make_pair(sp,ep));
 852         return ep-sp+1;
 853     }
 854     int c;
 855     ulong spnew;
 856     ulong epnew;
 857     int knew;
 858     ulong sum=0;
 859     if (k==0)
 860     {
 861         sum = searchPrefix(pattern, j, &sp, &ep);
 862         if (sp<=ep)
 863             result.push_back(std::make_pair(sp, ep));
 864         return sum;
 865     }
 866     vector<int> chars = alphabetrank->accessAll(sp, ep);
 867     for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
 868     {
 869         if (*it == 0)
 870             continue; // skip '\0'
 871         c = *it;
 872         spnew = C[c]+alphabetrank->rank(c,sp-1);
 873         epnew = C[c]+alphabetrank->rank(c,ep)-1;
 874         if (c!=pattern[j-1]) knew = (int)k-1; else knew = k;
 875         if (knew>=0) sum += kmismatches(result, pattern, spnew, epnew, j-1, knew);
 876     }
 877     return sum;
 878 }
 879
 880 //first call kerrors(pattern,1,n,m+k,k,d,m), where d[i]=i
 881 ulong TCImplementation::kerrors(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k, ulong const *d, ulong m) const
 882 {
 883     ulong sum=0;
 884     if (d[m]<=k) // range of suffixes with at most k-errors found
 885     {
 886         if (sp<=ep)
 887             result.push_back(std::make_pair(sp, ep));
 888         sum += (sp<=ep)?ep-sp+1:0ul;
 889     }
 890     if (sp>ep || j==0)
 891         return sum;
 892     ulong *dnew = new ulong[m+1];
 893     int c;
 894     ulong spnew;
 895     ulong p,lowerbound;
 896     ulong epnew;
 897     vector<int> chars = alphabetrank->accessAll(sp, ep);
 898     for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
 899     {
 900         if (*it == 0)
 901             continue; // skip '\0'
 902         c = *it;
 903         spnew = C[c]+alphabetrank->rank(c,sp-1);
 904         epnew = C[c]+alphabetrank->rank(c,ep)-1;
 905         if (spnew>epnew) continue;
 906         dnew[0]=m+k-j+1;
 907         lowerbound=k+1;
 908         for (p=1; p<=m; p++) {
 909             dnew[p]=myminofthree(d[p]+1,dnew[p-1]+1,(c==pattern[m-p])?d[p-1]:(d[p-1]+1));
 910             if (dnew[p]<lowerbound)
 911                 lowerbound = dnew[p];
 912         }
 913         if (lowerbound<=k)
 914             sum += kerrors(result, pattern, spnew, epnew, j-1, k,dnew,m);
 915     }
 916     delete [] dnew;
 917     return sum;
 918 }
 919
 920
 921 ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
 922 {
 923     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 924     int c = (int)pattern[m-1];
 925     TextPosition i=m-1;
 926     TextPosition sp = C[c];
 927     TextPosition ep = C[c+1]-1;
 928     while (sp<=ep && i>=1)
 929     {
 930 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 931         c = (int)pattern[--i];
 932         sp = C[c]+alphabetrank->rank(c,sp-1);
 933         ep = C[c]+alphabetrank->rank(c,ep)-1;
 934     }
 935     *spResult = sp;
 936     *epResult = ep;
 937     if (sp<=ep)
 938         return ep - sp + 1;
 939     else
 940         return 0;
 941 }
 942
 943 ulong TCImplementation::Search(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult, DocId begin, DocId end) const
 944 {
 945     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 946     int c = (int)pattern[m-1];
 947     assert(c == 0); // Start from endmarkers
 948     TextPosition i=m-1;
 949     TextPosition sp = begin;
 950     TextPosition ep = end;
 951     while (sp<=ep && i>=1)
 952     {
 953 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 954         c = (int)pattern[--i];
 955         sp = C[c]+alphabetrank->rank(c,sp-1);
 956         ep = C[c]+alphabetrank->rank(c,ep)-1;
 957     }
 958     *spResult = sp;
 959     *epResult = ep;
 960     if (sp<=ep)
 961         return ep - sp + 1;
 962     else
 963         return 0;
 964 }
 965
 966
 967 ulong TCImplementation::SearchLessThan(uchar const * pattern, TextPosition m, TextPosition *spResult, TextPosition *epResult) const
 968 {
 969     // use the FM-search replacing function Occ(c,1,i) with alphabetrank->rank(c,i)
 970     uint c = (int)pattern[m-1];
 971     TextPosition i=m-1;
 972     TextPosition sp = 1;
 973     TextPosition ep = C[c+1]-1;
 974     while (sp<=ep && i>=1)
 975     {
 976 //         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 977         c = (int)pattern[--i];
 978         uint result = alphabetrank->rankLessThan(c,ep);
 979         if (result == ~0u)
 980             ep = 0;
 981         else
 982             ep = C[c]+result-1;
 983     }
 984     *spResult = sp;
 985     *epResult = ep;
 986     if (sp<=ep)
 987         return ep - sp + 1;
 988     else
 989         return 0;
 990 }
 991
 992
 993 TCImplementation::~TCImplementation() {
 994     delete alphabetrank;
 995     delete sampled;
 996     delete suffixes;
 997     delete suffixDocId;
 998     delete Doc;
 999     delete textStorage;
1000 }
1001
1002 void TCImplementation::makewavelet(uchar *bwt)
1003 {
1004     ulong i, min = 0,
1005              max;
1006     for (i=0;i<256;i++)
1007         C[i]=0;
1008     for (i=0;i<n;++i)
1009         C[(int)bwt[i]]++;
1010     for (i=0;i<256;i++)
1011         if (C[i]>0) {min = i; break;}
1012     for (i=255;i>=min;--i)
1013         if (C[i]>0) {max = i; break;}
1014
1015     ulong prev=C[0], temp;
1016     C[0]=0;
1017     for (i=1;i<256;i++) {
1018         temp = C[i];
1019         C[i]=C[i-1]+prev;
1020         prev = temp;
1021     }
1022 //    this->codetable = node::makecodetable(bwt,n);
1023 //    alphabetrank = new THuffAlphabetRank(bwt,n, this->codetable,0);
1024 //    delete [] bwt;
1025     //alphabetrank = new RLWaveletTree(bwt, n); // Deletes bwt!
1026 //  std::cerr << "heap usage: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1027
1028 #ifdef DEBUG_MEMUSAGE
1029     std::cerr << "max heap usage before WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1030     HeapProfiler::ResetMaxHeapConsumption();
1031 #endif
1032
1033     alphabet_mapper * am = new alphabet_mapper_none();
1034     static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(8); //rrr02(8); // FIXME samplerate?
1035     wt_coder * wtc = new wt_coder_huff(bwt,n,am);//binary(bwt,n,am); // FIXME Huffman shape
1036     alphabetrank = new static_sequence_wvtree(bwt,n,wtc,bmb,am);
1037     delete bmb;
1038     bwt = 0; // already deleted
1039
1040 #ifdef DEBUG_MEMUSAGE
1041     std::cerr << "heap usage after WT: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1042     std::cerr << "max heap usage after WT: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1043 #endif
1044 }
1045
1046 void TCImplementation::maketables(ulong sampleLength, char tsType, CSA::DeltaVector & notIndexed, const string & niText)
1047 {
1048     // Calculate BWT end-marker position (of last inserted text)
1049     {
1050         ulong i = 0;
1051         uint alphabetrank_i_tmp = 0;
1052         uchar c  = alphabetrank->access(i, alphabetrank_i_tmp);
1053         while (c != '\0')
1054         {
1055             i = C[c]+alphabetrank_i_tmp-1;
1056             c = alphabetrank->access(i, alphabetrank_i_tmp);
1057         }
1058
1059         this->bwtEndPos = i;
1060     }
1061
1062 #ifdef DEBUG_MEMUSAGE
1063     std::cerr << "heap usage before BWT traverse: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " <<  HeapProfiler::GetHeapConsumption() << " / " <<  HeapProfiler::GetMaxHeapConsumption() << std::endl;
1064     HeapProfiler::ResetMaxHeapConsumption();
1065 #endif
1066
1067     // Build up array for text starting positions
1068 //    BlockArray* textStartPos = new BlockArray(numberOfTexts, Tools::CeilLog2(this->n));
1069 //    (*textStartPos)[0] = 0;
1070
1071     // Mapping from end-markers to doc ID's:
1072     unsigned logNumberOfTexts = Tools::CeilLog2(numberOfTexts);
1073 //    uint *endmarkerDocId = new uint[(numberOfTexts * logNumberOfTexts)/(8*sizeof(uint)) + 1];
1074     BlockArray *endmarkerDocId = new BlockArray(numberOfTexts, logNumberOfTexts);
1075
1076     BlockArray* positions = new BlockArray(sampleLength, Tools::CeilLog2(this->n));
1077     uint *sampledpositions = new uint[n/(sizeof(uint)*8)+1];
1078     for (ulong i = 0; i < n / (sizeof(uint)*8) + 1; i++)
1079         sampledpositions[i] = 0;
1080
1081     ulong x,p=bwtEndPos;
1082     ulong sampleCount = 0;
1083     // Keeping track of text position of prev. end-marker seen
1084     ulong posOfSuccEndmarker = n-1;
1085     DocId textId = numberOfTexts;
1086     ulong ulongmax = 0;
1087     ulongmax--;
1088     uint alphabetrank_i_tmp =0;
1089
1090     // Text length = n + number of bytes not indexed.
1091     TextStorageBuilder tsbuilder(n + niText.length());
1092     ulong tsb_i = n + niText.length(); // Iterator from text length to 0.
1093     string::const_reverse_iterator nit_i = niText.rbegin(); // Iterator through non-indexed texts
1094
1095     for (ulong i=n-1;i<ulongmax;i--) {
1096         // i substitutes SA->GetPos(i)
1097         x=(i==n-1)?0:i+1;
1098
1099         uchar c = alphabetrank->access(p, alphabetrank_i_tmp);
1100
1101         tsbuilder[--tsb_i] = c; // Build TextStorage
1102
1103         if ((posOfSuccEndmarker - i) % samplerate == 0 && c != '\0')
1104         {
1105             set_field(sampledpositions,1,p,1);
1106             (*positions)[sampleCount] = p;
1107             sampleCount ++;
1108         }
1109
1110         if (c == '\0')
1111         {
1112             unsigned prevTextId = textId; // Cache textId value.
1113             --textId;
1114             /**
1115              * At first c == '\0' it holds that (prevTextId == numberOfTexts), thus,
1116              * we have to search for the first text that is actually *indexed*
1117              * to get correct prevTextId.
1118              */
1119             if (prevTextId == numberOfTexts)
1120             {
1121                 prevTextId = 0;
1122                 while (notIndexed.isSet(prevTextId))
1123                     ++ prevTextId;
1124                 // Now prevTextId points to the first indexed Doc ID.
1125             }
1126
1127             /**
1128              * Insert non-indexed texts
1129              */
1130             while (notIndexed.isSet(textId))
1131             {
1132                 do {
1133                     tsbuilder[tsb_i] = *nit_i;
1134                     -- tsb_i;
1135                     ++ nit_i;
1136                 } while (nit_i != niText.rend() && *nit_i != '\0');
1137
1138                 tsbuilder[tsb_i] = '\0';
1139
1140                 if (textId == 0)
1141                     break;
1142                 --textId;
1143             }
1144
1145             // Record the order of end-markers in BWT:
1146             ulong endmarkerRank = alphabetrank_i_tmp - 1;
1147             //set_field(endmarkerDocId, logNumberOfTexts, endmarkerRank, (textId + 1) % numberOfTexts);
1148             (*endmarkerDocId)[endmarkerRank] = prevTextId % numberOfTexts;
1149
1150             // Store text length and text start position:
1151             if (textId < (DocId)numberOfTexts - 1)
1152             {
1153 //                (*textStartPos)[textId + 1] = x;  // x-1 is text position of end-marker.
1154
1155                 posOfSuccEndmarker = i;
1156             }
1157
1158             // LF-mapping from '\0' does not work with this (pseudo) BWT.
1159             // Correct LF-mapping to the last char of the previous text:
1160             p = textId - notIndexed.rank(textId);
1161         }
1162         else // Now c != '\0', do LF-mapping:
1163             p = C[c]+alphabetrank_i_tmp-1;
1164     }
1165     while (textId > 0 && notIndexed.isSet(textId-1))
1166     {
1167         do {
1168             -- tsb_i;
1169             tsbuilder[tsb_i] = *nit_i;
1170             ++ nit_i;
1171         } while (nit_i != niText.rend() && *nit_i != '\0');
1172         --textId;
1173     }
1174     assert(textId == 0);
1175     assert(tsb_i == 0);
1176     assert(nit_i == niText.rend());
1177
1178 #ifdef DEBUG_MEMUSAGE
1179     std::cerr << "heap usage before tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " <<  HeapProfiler::GetHeapConsumption() << " / " <<  HeapProfiler::GetMaxHeapConsumption() << std::endl;
1180     HeapProfiler::ResetMaxHeapConsumption();
1181 #endif
1182
1183     textStorage = tsbuilder.InitTextStorage(tsType);
1184
1185 #ifdef DEBUG_MEMUSAGE
1186     std::cerr << "heap usage after tsbuilder init: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " <<  HeapProfiler::GetHeapConsumption() << " / " <<  HeapProfiler::GetMaxHeapConsumption() << std::endl;
1187     HeapProfiler::ResetMaxHeapConsumption();
1188 #endif
1189
1190     sampled = new static_bitsequence_rrr02(sampledpositions, n, 16);
1191     delete [] sampledpositions;
1192     assert(sampleCount == sampleLength);
1193     assert(sampled->rank1(n-1) == sampleLength);
1194
1195 #ifdef DEBUG_MEMUSAGE
1196     std::cerr << "heap usage after sampled bit vector: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " <<  HeapProfiler::GetHeapConsumption() << " / " <<  HeapProfiler::GetMaxHeapConsumption() << std::endl;
1197     HeapProfiler::ResetMaxHeapConsumption();
1198 #endif
1199
1200     // Suffixes store an offset from the text start position
1201     suffixes = new BlockArray(sampleLength, Tools::CeilLog2(maxTextLength));
1202     suffixDocId = new BlockArray(sampleLength, Tools::CeilLog2(numberOfTexts));
1203
1204     x = n + niText.length() - 2;
1205     textId = numberOfTexts - 1;
1206     posOfSuccEndmarker = x + 1;
1207     for(ulong i = 0; i < sampleLength; i ++) {
1208         // Find next sampled text position
1209         while ((posOfSuccEndmarker - x) % samplerate != 0
1210                || notIndexed.isSet(textId)) // Loop over non-indexed
1211         {
1212             --x;
1213             assert(x != ~0lu);
1214             if (textStorage->IsEndmarker(x))
1215             {
1216                 posOfSuccEndmarker = x--;
1217                 -- textId;
1218             }
1219         }
1220         assert((*positions)[i] < n);
1221         ulong j = sampled->rank1((*positions)[i]);
1222
1223         assert(j != 0); // if (j==0) j=sampleLength;
1224
1225         TextPosition textPos = (x==n-1)?0:x+1;
1226         (*suffixDocId)[j-1] = textId; // textStorage->DocIdAtTextPos(textPos);
1227         assert(textStorage->DocIdAtTextPos(textPos) == textId);
1228
1229         assert((*suffixDocId)[j-1] < numberOfTexts);
1230         // calculate offset from text start:
1231         (*suffixes)[j-1] = textPos - textStorage->TextStartPos((*suffixDocId)[j-1]);
1232         --x;
1233         if (x != ~0lu && textStorage->IsEndmarker(x))
1234         {
1235             posOfSuccEndmarker = x--;
1236             -- textId;
1237         }
1238     }
1239
1240     delete positions;
1241
1242 #ifdef DEBUG_MEMUSAGE
1243     std::cerr << "heap usage after sampled arrays: " << HeapProfiler::GetHeapConsumption()/(1024*1024) << " / " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes, " <<  HeapProfiler::GetHeapConsumption() << " / " <<  HeapProfiler::GetMaxHeapConsumption() << std::endl;
1244     HeapProfiler::ResetMaxHeapConsumption();
1245 #endif
1246
1247 #ifdef DEBUG_MEMUSAGE
1248     std::cerr << "max heap usage before Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1249     HeapProfiler::ResetMaxHeapConsumption();
1250 #endif
1251
1252     /*alphabet_mapper * am = new alphabet_mapper_none();
1253     static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); // FIXME samplerate?
1254     Doc = new static_sequence_wvtree_noptrs(endmarkerDocId, numberOfTexts, logNumberOfTexts, bmb, am, true);
1255     delete bmb;*/
1256     // delete [] endmarkerDocId; // already deleted in static_sequence_wvtree_noptrs!
1257
1258     Doc = new ArrayDoc(endmarkerDocId);
1259
1260 #ifdef DEBUG_MEMUSAGE
1261     std::cerr << "max heap usage after Doc: " << HeapProfiler::GetMaxHeapConsumption()/(1024*1024) << " Mbytes" << std::endl;
1262 #endif
1263 }
1264
1265
1266 /**
1267  * Finds document identifier for given text position
1268  *
1269  * Starting text position of the document is stored into second parameter.
1270  * Binary searching on text starting positions.
1271  */
1272 TextCollection::DocId TCImplementation::DocIdAtTextPos(BlockArray* textStartPos, TextPosition i) const
1273 {
1274     assert(i < n);
1275
1276     DocId a = 0;
1277     DocId b = numberOfTexts - 1;
1278     while (a < b)
1279     {
1280         DocId c = a + (b - a)/2;
1281         if ((*textStartPos)[c] > i)
1282             b = c - 1;
1283         else if ((*textStartPos)[c+1] > i)
1284             return c;
1285         else
1286             a = c + 1;
1287     }
1288
1289     assert(a < (DocId)numberOfTexts);
1290     assert(i >= (*textStartPos)[a]);
1291     assert(i < (a == (DocId)numberOfTexts - 1 ? n : (*textStartPos)[a+1]));
1292     return a;
1293 }
1294
1295
1296 } // namespace SXSI
1297