1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.inputmethod.latin.makedict; 18 19 import com.android.inputmethod.annotations.UsedForTesting; 20 import com.android.inputmethod.latin.utils.CollectionUtils; 21 22 import java.io.File; 23 import java.io.FileInputStream; 24 import java.io.FileOutputStream; 25 import java.io.IOException; 26 import java.io.OutputStream; 27 import java.util.ArrayList; 28 import java.util.Collections; 29 30 /** 31 * SparseTable is an extensible map from integer to integer. 32 * This holds one value for every mBlockSize keys, so it uses 1/mBlockSize'th of the full index 33 * memory. 34 */ 35 @UsedForTesting 36 public class SparseTable { 37 38 /** 39 * mLookupTable is indexed by terminal ID, containing exactly one entry for every mBlockSize 40 * terminals. 41 * It contains at index i = j / mBlockSize the index in each ArrayList in mContentsTables where 42 * the values for terminals with IDs j to j + mBlockSize - 1 are stored as an mBlockSize-sized 43 * integer array. 44 */ 45 private final ArrayList<Integer> mLookupTable; 46 private final ArrayList<ArrayList<Integer>> mContentTables; 47 48 private final int mBlockSize; 49 private final int mContentTableCount; 50 public static final int NOT_EXIST = -1; 51 public static final int SIZE_OF_INT_IN_BYTES = 4; 52 53 @UsedForTesting 54 public SparseTable(final int initialCapacity, final int blockSize, 55 final int contentTableCount) { 56 mBlockSize = blockSize; 57 final int lookupTableSize = initialCapacity / mBlockSize 58 + (initialCapacity % mBlockSize > 0 ? 1 : 0); 59 mLookupTable = new ArrayList<Integer>(Collections.nCopies(lookupTableSize, NOT_EXIST)); 60 mContentTableCount = contentTableCount; 61 mContentTables = CollectionUtils.newArrayList(); 62 for (int i = 0; i < mContentTableCount; ++i) { 63 mContentTables.add(new ArrayList<Integer>()); 64 } 65 } 66 67 @UsedForTesting 68 public SparseTable(final ArrayList<Integer> lookupTable, 69 final ArrayList<ArrayList<Integer>> contentTables, final int blockSize) { 70 mBlockSize = blockSize; 71 mContentTableCount = contentTables.size(); 72 mLookupTable = lookupTable; 73 mContentTables = contentTables; 74 } 75 76 /** 77 * Converts an byte array to an int array considering each set of 4 bytes is an int stored in 78 * big-endian. 79 * The length of byteArray must be a multiple of four. 80 * Otherwise, IndexOutOfBoundsException will be raised. 81 */ 82 @UsedForTesting 83 private static ArrayList<Integer> convertByteArrayToIntegerArray(final byte[] byteArray) { 84 final ArrayList<Integer> integerArray = new ArrayList<Integer>(byteArray.length / 4); 85 for (int i = 0; i < byteArray.length; i += 4) { 86 int value = 0; 87 for (int j = i; j < i + 4; ++j) { 88 value <<= 8; 89 value |= byteArray[j] & 0xFF; 90 } 91 integerArray.add(value); 92 } 93 return integerArray; 94 } 95 96 @UsedForTesting 97 public int get(final int contentTableIndex, final int index) { 98 if (!contains(index)) { 99 return NOT_EXIST; 100 } 101 return mContentTables.get(contentTableIndex).get( 102 mLookupTable.get(index / mBlockSize) + (index % mBlockSize)); 103 } 104 105 @UsedForTesting 106 public ArrayList<Integer> getAll(final int index) { 107 final ArrayList<Integer> ret = CollectionUtils.newArrayList(); 108 for (int i = 0; i < mContentTableCount; ++i) { 109 ret.add(get(i, index)); 110 } 111 return ret; 112 } 113 114 @UsedForTesting 115 public void set(final int contentTableIndex, final int index, final int value) { 116 if (mLookupTable.get(index / mBlockSize) == NOT_EXIST) { 117 mLookupTable.set(index / mBlockSize, mContentTables.get(contentTableIndex).size()); 118 for (int i = 0; i < mContentTableCount; ++i) { 119 for (int j = 0; j < mBlockSize; ++j) { 120 mContentTables.get(i).add(NOT_EXIST); 121 } 122 } 123 } 124 mContentTables.get(contentTableIndex).set( 125 mLookupTable.get(index / mBlockSize) + (index % mBlockSize), value); 126 } 127 128 public void remove(final int indexOfContent, final int index) { 129 set(indexOfContent, index, NOT_EXIST); 130 } 131 132 @UsedForTesting 133 public int size() { 134 return mLookupTable.size() * mBlockSize; 135 } 136 137 @UsedForTesting 138 /* package */ int getContentTableSize() { 139 // This class always has at least one content table. 140 return mContentTables.get(0).size(); 141 } 142 143 @UsedForTesting 144 /* package */ int getLookupTableSize() { 145 return mLookupTable.size(); 146 } 147 148 public boolean contains(final int index) { 149 if (index < 0 || index / mBlockSize >= mLookupTable.size() 150 || mLookupTable.get(index / mBlockSize) == NOT_EXIST) { 151 return false; 152 } 153 return true; 154 } 155 156 @UsedForTesting 157 public void write(final OutputStream lookupOutStream, final OutputStream[] contentOutStreams) 158 throws IOException { 159 if (contentOutStreams.length != mContentTableCount) { 160 throw new RuntimeException(contentOutStreams.length + " streams are given, but the" 161 + " table has " + mContentTableCount + " content tables."); 162 } 163 for (final int index : mLookupTable) { 164 BinaryDictEncoderUtils.writeUIntToStream(lookupOutStream, index, SIZE_OF_INT_IN_BYTES); 165 } 166 167 for (int i = 0; i < contentOutStreams.length; ++i) { 168 for (final int data : mContentTables.get(i)) { 169 BinaryDictEncoderUtils.writeUIntToStream(contentOutStreams[i], data, 170 SIZE_OF_INT_IN_BYTES); 171 } 172 } 173 } 174 175 @UsedForTesting 176 public void writeToFiles(final File lookupTableFile, final File[] contentFiles) 177 throws IOException { 178 FileOutputStream lookupTableOutStream = null; 179 final FileOutputStream[] contentTableOutStreams = new FileOutputStream[mContentTableCount]; 180 try { 181 lookupTableOutStream = new FileOutputStream(lookupTableFile); 182 for (int i = 0; i < contentFiles.length; ++i) { 183 contentTableOutStreams[i] = new FileOutputStream(contentFiles[i]); 184 } 185 write(lookupTableOutStream, contentTableOutStreams); 186 } finally { 187 if (lookupTableOutStream != null) { 188 lookupTableOutStream.close(); 189 } 190 for (int i = 0; i < contentTableOutStreams.length; ++i) { 191 if (contentTableOutStreams[i] != null) { 192 contentTableOutStreams[i].close(); 193 } 194 } 195 } 196 } 197 198 private static byte[] readFileToByteArray(final File file) throws IOException { 199 final byte[] contents = new byte[(int) file.length()]; 200 FileInputStream inStream = null; 201 try { 202 inStream = new FileInputStream(file); 203 inStream.read(contents); 204 } finally { 205 if (inStream != null) { 206 inStream.close(); 207 } 208 } 209 return contents; 210 } 211 212 @UsedForTesting 213 public static SparseTable readFromFiles(final File lookupTableFile, final File[] contentFiles, 214 final int blockSize) throws IOException { 215 final ArrayList<ArrayList<Integer>> contentTables = 216 new ArrayList<ArrayList<Integer>>(contentFiles.length); 217 for (int i = 0; i < contentFiles.length; ++i) { 218 contentTables.add(convertByteArrayToIntegerArray(readFileToByteArray(contentFiles[i]))); 219 } 220 return new SparseTable(convertByteArrayToIntegerArray(readFileToByteArray(lookupTableFile)), 221 contentTables, blockSize); 222 } 223 } 224