SlidingWindow.cpp

class SlidingWindow {
 public:
  explicit SlidingWindow(size_t least_docnum) : least_docnum_(least_docnum) {}

  size_t Add(size_t lcp_len, uint64_t docid) {
    docid_queue_.Push(docid);
    lcp_len_queue_.Push(lcp_len);

    if (docid_queue_.Cardinality() >= least_docnum_) {  // enough docs
      while (docid_queue_.Cardinality() >= least_docnum_) Shrink();
      // LCP DOCID  SEQUENCE Pre-Shrink Window  Shrinked Window
      // 0   1      AXXXX    |
      // 1   0      ABCDX    |
      // 4   1      ABCDY    |                  |
      // 3   2      ABCZ     |                  |
      // expected is 3
      // LCPの先頭は無視したいので「条件を満たさなくなる直前」ではなくて、1つ進めた「条件を満たさなくなった直後」でLCPの最小値を取る。
      return lcp_len_queue_.Min();
    }
    return 0;  // not enough docs
  }

 private:
  void Shrink() {
    docid_queue_.Pop();
    lcp_len_queue_.Pop();
  }

  size_t least_docnum_;
  CardinalityQueue<size_t> docid_queue_;
  MinQueue<size_t> lcp_len_queue_;
};