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
14class 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_
45