1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
/*
* Copyright (C) 2013 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.android.inputmethod.latin.makedict;
import com.android.inputmethod.annotations.UsedForTesting;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Collections;
/**
* SparseTable is an extensible map from integer to integer.
* This holds one value for every mBlockSize keys, so it uses 1/mBlockSize'th of the full index
* memory.
*/
@UsedForTesting
public class SparseTable {
/**
* mLookupTable is indexed by terminal ID, containing exactly one entry for every mBlockSize
* terminals.
* It contains at index i = j / mBlockSize the index in mContentsTable where the values for
* terminals with IDs j to j + mBlockSize - 1 are stored as an mBlockSize-sized integer array.
*/
private final ArrayList<Integer> mLookupTable;
private final ArrayList<Integer> mContentTable;
private final int mBlockSize;
public static final int NOT_EXIST = -1;
@UsedForTesting
public SparseTable(final int initialCapacity, final int blockSize) {
mBlockSize = blockSize;
final int lookupTableSize = initialCapacity / mBlockSize
+ (initialCapacity % mBlockSize > 0 ? 1 : 0);
mLookupTable = new ArrayList<Integer>(Collections.nCopies(lookupTableSize, NOT_EXIST));
mContentTable = new ArrayList<Integer>();
}
@UsedForTesting
public SparseTable(final int[] lookupTable, final int[] contentTable, final int blockSize) {
mBlockSize = blockSize;
mLookupTable = new ArrayList<Integer>(lookupTable.length);
for (int i = 0; i < lookupTable.length; ++i) {
mLookupTable.add(lookupTable[i]);
}
mContentTable = new ArrayList<Integer>(contentTable.length);
for (int i = 0; i < contentTable.length; ++i) {
mContentTable.add(contentTable[i]);
}
}
/**
* Converts an byte array to an int array considering each set of 4 bytes is an int stored in
* big-endian.
* The length of byteArray must be a multiple of four.
* Otherwise, IndexOutOfBoundsException will be raised.
*/
@UsedForTesting
private static void convertByteArrayToIntegerArray(final byte[] byteArray,
final ArrayList<Integer> integerArray) {
for (int i = 0; i < byteArray.length; i += 4) {
int value = 0;
for (int j = i; j < i + 4; ++j) {
value <<= 8;
value |= byteArray[j] & 0xFF;
}
integerArray.add(value);
}
}
@UsedForTesting
public SparseTable(final byte[] lookupTable, final byte[] contentTable, final int blockSize) {
mBlockSize = blockSize;
mLookupTable = new ArrayList<Integer>(lookupTable.length / 4);
mContentTable = new ArrayList<Integer>(contentTable.length / 4);
convertByteArrayToIntegerArray(lookupTable, mLookupTable);
convertByteArrayToIntegerArray(contentTable, mContentTable);
}
@UsedForTesting
public int get(final int index) {
if (index < 0 || index / mBlockSize >= mLookupTable.size()
|| mLookupTable.get(index / mBlockSize) == NOT_EXIST) {
return NOT_EXIST;
}
return mContentTable.get(mLookupTable.get(index / mBlockSize) + (index % mBlockSize));
}
@UsedForTesting
public void set(final int index, final int value) {
if (mLookupTable.get(index / mBlockSize) == NOT_EXIST) {
mLookupTable.set(index / mBlockSize, mContentTable.size());
for (int i = 0; i < mBlockSize; ++i) {
mContentTable.add(NOT_EXIST);
}
}
mContentTable.set(mLookupTable.get(index / mBlockSize) + (index % mBlockSize), value);
}
public void remove(final int index) {
set(index, NOT_EXIST);
}
@UsedForTesting
public int size() {
return mLookupTable.size() * mBlockSize;
}
@UsedForTesting
/* package */ int getContentTableSize() {
return mContentTable.size();
}
@UsedForTesting
/* package */ int getLookupTableSize() {
return mLookupTable.size();
}
public boolean contains(final int index) {
return get(index) != NOT_EXIST;
}
@UsedForTesting
public void write(final OutputStream lookupOutStream, final OutputStream contentOutStream)
throws IOException {
for (final int index : mLookupTable) {
BinaryDictEncoderUtils.writeUIntToStream(lookupOutStream, index, 4);
}
for (final int index : mContentTable) {
BinaryDictEncoderUtils.writeUIntToStream(contentOutStream, index, 4);
}
}
}
|
