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); SubsetSequence()19 SubsetSequence() {Init();} ~SubsetSequence()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_ 45