third_party/cld/encodings/compact_lang_det/subsetsequence.h

   1 // Copyright (c) 2006-2009 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // Remember a subset of a sequence of values, using a modest amount of memory
   6
   7 #ifndef ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_
   8 #define ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_
   9
  10 #include "encodings/compact_lang_det/win/cld_basictypes.h"
  11 #include "encodings/compact_lang_det/win/cld_google.h"
  12
  13
  14 class SubsetSequence {
  15  public:
  16    void Init();
  17    void Add(uint8 e);
  18    void Extract(int n, uint8* dst);
  19    SubsetSequence() {Init();}
  20    ~SubsetSequence() {};
  21
  22  private:
  23    uint8 Median3(int sub);
  24    void NewLevel();
  25    void DoCarries();
  26    void Flush();
  27
  28    static const int kMaxLevel_ = 16;    // 3**16 ~=  43M (3**20 ~= 3.4B)
  29    static const int kMaxSeq_ = 128;
  30
  31    int k_;
  32    int next_e_;
  33    int limit_e_;
  34    int level_limit_e_;
  35    uint8 seq_[kMaxSeq_];
  36    uint8 count_[kMaxLevel_ + 1];        // +1 allows graceful overflow
  37
  38    DISALLOW_EVIL_CONSTRUCTORS(SubsetSequence);
  39
  40    // Require enough room to end up with 40 entries plus carrying space
  41    COMPILE_ASSERT(kMaxSeq_ >= (kMaxLevel_ * 2 + 40), kMaxSeq__is_too_small);
  42 };
  43
  44 #endif  // ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_