15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Remember a subset of a sequence of values, using a modest amount of memory 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_ 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_ 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/win/cld_basictypes.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/win/cld_google.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SubsetSequence { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Init(); 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Add(uint8 e); 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Extract(int n, uint8* dst); 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubsetSequence() {Init();} 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SubsetSequence() {}; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 Median3(int sub); 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void NewLevel(); 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void DoCarries(); 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Flush(); 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMaxLevel_ = 16; // 3**16 ~= 43M (3**20 ~= 3.4B) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMaxSeq_ = 128; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int k_; 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int next_e_; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int limit_e_; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int level_limit_e_; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 seq_[kMaxSeq_]; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 count_[kMaxLevel_ + 1]; // +1 allows graceful overflow 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_EVIL_CONSTRUCTORS(SubsetSequence); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Require enough room to end up with 40 entries plus carrying space 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMaxSeq_ >= (kMaxLevel_ * 2 + 40), kMaxSeq__is_too_small); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // ENCODINGS_COMPACT_LANG_DET_SUBSETSEQUENCE_H_ 45