xref: /aosp_15_r20/external/libtextclassifier/native/utils/container/bit-vector.cc (revision 993b0882672172b81d12fad7a7ac0c3e5c824a12)
1*993b0882SAndroid Build Coastguard Worker /*
2*993b0882SAndroid Build Coastguard Worker  * Copyright (C) 2018 The Android Open Source Project
3*993b0882SAndroid Build Coastguard Worker  *
4*993b0882SAndroid Build Coastguard Worker  * Licensed under the Apache License, Version 2.0 (the "License");
5*993b0882SAndroid Build Coastguard Worker  * you may not use this file except in compliance with the License.
6*993b0882SAndroid Build Coastguard Worker  * You may obtain a copy of the License at
7*993b0882SAndroid Build Coastguard Worker  *
8*993b0882SAndroid Build Coastguard Worker  *      http://www.apache.org/licenses/LICENSE-2.0
9*993b0882SAndroid Build Coastguard Worker  *
10*993b0882SAndroid Build Coastguard Worker  * Unless required by applicable law or agreed to in writing, software
11*993b0882SAndroid Build Coastguard Worker  * distributed under the License is distributed on an "AS IS" BASIS,
12*993b0882SAndroid Build Coastguard Worker  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13*993b0882SAndroid Build Coastguard Worker  * See the License for the specific language governing permissions and
14*993b0882SAndroid Build Coastguard Worker  * limitations under the License.
15*993b0882SAndroid Build Coastguard Worker  */
16*993b0882SAndroid Build Coastguard Worker 
17*993b0882SAndroid Build Coastguard Worker #include "utils/container/bit-vector.h"
18*993b0882SAndroid Build Coastguard Worker 
19*993b0882SAndroid Build Coastguard Worker #include <math.h>
20*993b0882SAndroid Build Coastguard Worker 
21*993b0882SAndroid Build Coastguard Worker #include <algorithm>
22*993b0882SAndroid Build Coastguard Worker #include <memory>
23*993b0882SAndroid Build Coastguard Worker #include <vector>
24*993b0882SAndroid Build Coastguard Worker 
25*993b0882SAndroid Build Coastguard Worker #include "utils/base/logging.h"
26*993b0882SAndroid Build Coastguard Worker #include "utils/container/bit-vector_generated.h"
27*993b0882SAndroid Build Coastguard Worker 
28*993b0882SAndroid Build Coastguard Worker namespace libtextclassifier3 {
29*993b0882SAndroid Build Coastguard Worker 
BitVector(const BitVectorData * bit_vector_data)30*993b0882SAndroid Build Coastguard Worker BitVector::BitVector(const BitVectorData* bit_vector_data)
31*993b0882SAndroid Build Coastguard Worker     : bit_vector_data_(bit_vector_data) {}
32*993b0882SAndroid Build Coastguard Worker 
GetFromSparseData(int32 index) const33*993b0882SAndroid Build Coastguard Worker bool BitVector::GetFromSparseData(int32 index) const {
34*993b0882SAndroid Build Coastguard Worker   return std::binary_search(
35*993b0882SAndroid Build Coastguard Worker       bit_vector_data_->sparse_data()->sorted_indices_32()->begin(),
36*993b0882SAndroid Build Coastguard Worker       bit_vector_data_->sparse_data()->sorted_indices_32()->end(), index);
37*993b0882SAndroid Build Coastguard Worker }
38*993b0882SAndroid Build Coastguard Worker 
GetFromDenseData(int32 index) const39*993b0882SAndroid Build Coastguard Worker bool BitVector::GetFromDenseData(int32 index) const {
40*993b0882SAndroid Build Coastguard Worker   if (index >= bit_vector_data_->dense_data()->size()) {
41*993b0882SAndroid Build Coastguard Worker     return false;
42*993b0882SAndroid Build Coastguard Worker   }
43*993b0882SAndroid Build Coastguard Worker   int32 byte_index = index / 8;
44*993b0882SAndroid Build Coastguard Worker   uint8 extracted_byte =
45*993b0882SAndroid Build Coastguard Worker       bit_vector_data_->dense_data()->data()->Get(byte_index);
46*993b0882SAndroid Build Coastguard Worker   uint8 bit_index = index % 8;
47*993b0882SAndroid Build Coastguard Worker   return extracted_byte & (1 << bit_index);
48*993b0882SAndroid Build Coastguard Worker }
49*993b0882SAndroid Build Coastguard Worker 
Get(int32 index) const50*993b0882SAndroid Build Coastguard Worker bool BitVector::Get(int32 index) const {
51*993b0882SAndroid Build Coastguard Worker   TC3_DCHECK(index >= 0);
52*993b0882SAndroid Build Coastguard Worker 
53*993b0882SAndroid Build Coastguard Worker   if (bit_vector_data_ == nullptr) {
54*993b0882SAndroid Build Coastguard Worker     return false;
55*993b0882SAndroid Build Coastguard Worker   }
56*993b0882SAndroid Build Coastguard Worker   if (bit_vector_data_->dense_data() != nullptr) {
57*993b0882SAndroid Build Coastguard Worker     return GetFromDenseData(index);
58*993b0882SAndroid Build Coastguard Worker   }
59*993b0882SAndroid Build Coastguard Worker   return GetFromSparseData(index);
60*993b0882SAndroid Build Coastguard Worker }
61*993b0882SAndroid Build Coastguard Worker 
CreateSparseBitVectorData(const std::vector<int32> & indices)62*993b0882SAndroid Build Coastguard Worker std::unique_ptr<BitVectorDataT> BitVector::CreateSparseBitVectorData(
63*993b0882SAndroid Build Coastguard Worker     const std::vector<int32>& indices) {
64*993b0882SAndroid Build Coastguard Worker   auto bit_vector_data = std::make_unique<BitVectorDataT>();
65*993b0882SAndroid Build Coastguard Worker   bit_vector_data->sparse_data =
66*993b0882SAndroid Build Coastguard Worker       std::make_unique<libtextclassifier3::SparseBitVectorDataT>();
67*993b0882SAndroid Build Coastguard Worker   bit_vector_data->sparse_data->sorted_indices_32 = indices;
68*993b0882SAndroid Build Coastguard Worker   return bit_vector_data;
69*993b0882SAndroid Build Coastguard Worker }
70*993b0882SAndroid Build Coastguard Worker 
CreateDenseBitVectorData(const std::vector<bool> & data)71*993b0882SAndroid Build Coastguard Worker std::unique_ptr<BitVectorDataT> BitVector::CreateDenseBitVectorData(
72*993b0882SAndroid Build Coastguard Worker     const std::vector<bool>& data) {
73*993b0882SAndroid Build Coastguard Worker   uint8_t temp = 0;
74*993b0882SAndroid Build Coastguard Worker   std::vector<uint8_t> result;
75*993b0882SAndroid Build Coastguard Worker   for (int i = 0; i < data.size(); i++) {
76*993b0882SAndroid Build Coastguard Worker     if (i != 0 && (i % 8) == 0) {
77*993b0882SAndroid Build Coastguard Worker       result.push_back(temp);
78*993b0882SAndroid Build Coastguard Worker       temp = 0;
79*993b0882SAndroid Build Coastguard Worker     }
80*993b0882SAndroid Build Coastguard Worker     if (data[i]) {
81*993b0882SAndroid Build Coastguard Worker       temp += (1 << (i % 8));
82*993b0882SAndroid Build Coastguard Worker     }
83*993b0882SAndroid Build Coastguard Worker   }
84*993b0882SAndroid Build Coastguard Worker   if ((data.size() % 8) != 0) {
85*993b0882SAndroid Build Coastguard Worker     result.push_back(temp);
86*993b0882SAndroid Build Coastguard Worker   }
87*993b0882SAndroid Build Coastguard Worker 
88*993b0882SAndroid Build Coastguard Worker   auto bit_vector_data = std::make_unique<BitVectorDataT>();
89*993b0882SAndroid Build Coastguard Worker   bit_vector_data->dense_data =
90*993b0882SAndroid Build Coastguard Worker       std::make_unique<libtextclassifier3::DenseBitVectorDataT>();
91*993b0882SAndroid Build Coastguard Worker   bit_vector_data->dense_data->data = result;
92*993b0882SAndroid Build Coastguard Worker   bit_vector_data->dense_data->size = data.size();
93*993b0882SAndroid Build Coastguard Worker   return bit_vector_data;
94*993b0882SAndroid Build Coastguard Worker }
95*993b0882SAndroid Build Coastguard Worker 
96*993b0882SAndroid Build Coastguard Worker }  // namespace libtextclassifier3
97