← Back to branch summary

~ubuntu-branches/ubuntu/saucy/abyss/saucy

« back to all changes in this revision

Viewing changes to FMIndex/bit_array.h

  • Committer: Package Import Robot
  • Author(s): Shaun Jackman
  • Date: 2011-09-11 10:00:13 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: package-import@ubuntu.com-20110911100013-oa4m5fi036mjuwc8
Tags: 1.3.0-1
* New upstream release.
* Add libboost-graph-dev to Build-Depends.

Show diffs side-by-side

added added

removed removed

Lines of Context:
FMIndex/bit_array.h
 
1
/*
 
2
 *  Copyright (c) 2010 Daisuke Okanohara
 
3
 *
 
4
 *   Redistribution and use in source and binary forms, with or without
 
5
 *   modification, are permitted provided that the following conditions
 
6
 *   are met:
 
7
 *
 
8
 *   1. Redistributions of source code must retain the above Copyright
 
9
 *      notice, this list of conditions and the following disclaimer.
 
10
 *
 
11
 *   2. Redistributions in binary form must reproduce the above Copyright
 
12
 *      notice, this list of conditions and the following disclaimer in the
 
13
 *      documentation and/or other materials provided with the distribution.
 
14
 *
 
15
 *   3. Neither the name of the authors nor the names of its contributors
 
16
 *      may be used to endorse or promote products derived from this
 
17
 *      software without specific prior written permission.
 
18
 */
 
19
 
 
20
#ifndef WAT_ARRAY_BIT_ARRAY_HPP_
 
21
#define WAT_ARRAY_BIT_ARRAY_HPP_
 
22
 
 
23
#include <stdint.h>
 
24
#include <vector>
 
25
#include <iostream>
 
26
 
 
27
namespace wat_array {
 
28
 
 
29
enum {
 
30
  NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU
 
31
};
 
32
 
 
33
class BitArray {
 
34
 
 
35
private:
 
36
enum {
 
37
  BLOCK_BITNUM = 64,
 
38
  TABLE_INTERVAL = 4
 
39
};
 
40
 
 
41
public:
 
42
  BitArray();
 
43
  ~BitArray();
 
44
  BitArray(uint64_t size);
 
45
  uint64_t length() const;
 
46
  uint64_t one_num() const;
 
47
 
 
48
  void Init(uint64_t size);
 
49
  void Clear();
 
50
  void SetBit(uint64_t bit, uint64_t pos);
 
51
  void Build();
 
52
  uint64_t Rank(uint64_t bit, uint64_t pos) const;
 
53
  uint64_t Select(uint64_t bit, uint64_t rank) const;
 
54
  uint64_t Lookup(uint64_t pos) const;
 
55
 
 
56
  static uint64_t PopCount(uint64_t x);
 
57
  static uint64_t PopCountMask(uint64_t x, uint64_t offset);
 
58
  static uint64_t SelectInBlock(uint64_t x, uint64_t rank);
 
59
  static uint64_t GetBitNum(uint64_t one_num, uint64_t num, uint64_t bit);
 
60
  void PrintForDebug(std::ostream& os) const;
 
61
 
 
62
  void Save(std::ostream& os) const;
 
63
  void Load(std::istream& is);
 
64
 
 
65
private:
 
66
  uint64_t RankOne(uint64_t pos) const;
 
67
  uint64_t SelectOutBlock(uint64_t bit, uint64_t& rank) const;
 
68
 
 
69
private:
 
70
  std::vector<uint64_t> bit_blocks_;
 
71
  std::vector<uint64_t> rank_tables_;
 
72
  uint64_t length_;
 
73
  uint64_t one_num_;
 
74
};
 
75
 
 
76
}
 
77
 
 
78
#endif // WAT_ARRAY_BIT_ARRAY_HPP_