1 /* 2 * Copyright (C) 2007 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.dx.util; 18 19 import java.util.Arrays; 20 21 /** 22 * A list of labeled items, allowing easy lookup by label. 23 */ 24 public class LabeledList extends FixedSizeList { 25 /** 26 * Sparse array indexed by label to FixedSizeList index; 27 * {@code -1} for an invalid label. 28 */ 29 private final IntList labelToIndex; 30 31 /** @inheritDoc */ LabeledList(int size)32 public LabeledList(int size) { 33 super(size); 34 35 labelToIndex = new IntList(size); 36 } 37 38 /** 39 * Constructs a new instance that is a copy of the old instance. 40 * 41 * @param old instance to copy 42 */ LabeledList(LabeledList old)43 public LabeledList(LabeledList old) { 44 super(old.size()); 45 labelToIndex = old.labelToIndex.mutableCopy(); 46 47 int sz = old.size(); 48 49 for (int i = 0; i < sz; i++) { 50 Object one = old.get0(i); 51 if (one != null) { 52 set0(i, one); 53 } 54 } 55 } 56 57 /** 58 * Gets the maximum label (exclusive) of any block added to this instance. 59 * 60 * @return {@code >= 0;} the maximum label 61 */ getMaxLabel()62 public final int getMaxLabel() { 63 int sz = labelToIndex.size(); 64 65 // Gobble any deleted labels that may be at the end. 66 int i; 67 for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--) 68 /*empty*/ ; 69 70 int newSize = i + 1; 71 72 labelToIndex.shrink(newSize); 73 74 return newSize; 75 } 76 77 /** 78 * Removes a label from the label-to-index mapping. 79 * 80 * @param oldLabel label to remove 81 */ removeLabel(int oldLabel)82 private void removeLabel(int oldLabel) { 83 labelToIndex.set(oldLabel, -1); 84 } 85 86 /** 87 * Adds a label and index to the label-to-index mapping. 88 * 89 * @param label new label 90 * @param index index of block. 91 */ addLabelIndex(int label, int index)92 private void addLabelIndex(int label, int index) { 93 int origSz = labelToIndex.size(); 94 95 for (int i = 0; i <= (label - origSz); i++) { 96 labelToIndex.add(-1); 97 } 98 99 labelToIndex.set(label, index); 100 } 101 102 /** 103 * Gets the index of the first item in the list with the given 104 * label, if any. 105 * 106 * @param label {@code >= 0;} the label to look for 107 * @return {@code >= -1;} the index of the so-labelled item, or {@code -1} 108 * if none is found 109 */ indexOfLabel(int label)110 public final int indexOfLabel(int label) { 111 if (label >= labelToIndex.size()) { 112 return -1; 113 } else { 114 return labelToIndex.get(label); 115 } 116 } 117 118 /** 119 * Gets an array containing all of the labels used in this instance, 120 * in order. The returned array is freshly-allocated and so may be 121 * modified safely by the caller without impacting this instance. 122 * 123 * @return {@code non-null;} ordered array of labels 124 * @throws NullPointerException thrown if there are any {@code null} 125 * items in this instance 126 */ getLabelsInOrder()127 public final int[] getLabelsInOrder() { 128 int sz = size(); 129 int[] result = new int[sz]; 130 131 for (int i = 0; i < sz; i++) { 132 LabeledItem li = (LabeledItem) get0(i); 133 if (li == null) { 134 throw new NullPointerException("null at index " + i); 135 } 136 result[i] = li.getLabel(); 137 } 138 139 Arrays.sort(result); 140 return result; 141 } 142 143 /** @inheritDoc */ 144 @Override shrinkToFit()145 public void shrinkToFit() { 146 super.shrinkToFit(); 147 148 rebuildLabelToIndex(); 149 } 150 151 /** 152 * Rebuilds the label-to-index mapping after a {@code shrinkToFit()}. 153 * Note: This assumes that the labels that are in the list are the 154 * same, although the indicies may have changed. 155 */ rebuildLabelToIndex()156 private void rebuildLabelToIndex() { 157 int szItems = size(); 158 159 for (int i = 0; i < szItems; i++) { 160 LabeledItem li = (LabeledItem) get0(i); 161 162 if (li != null) { 163 labelToIndex.set(li.getLabel(), i); 164 } 165 } 166 } 167 168 /** 169 * Sets the element at the given index. 170 * 171 * @param n {@code >= 0, < size();} which element 172 * @param item {@code null-ok;} the value to store 173 */ set(int n, LabeledItem item)174 protected void set(int n, LabeledItem item) { 175 LabeledItem old = (LabeledItem) getOrNull0(n); 176 177 set0(n, item); 178 179 if (old != null) { 180 removeLabel(old.getLabel()); 181 } 182 183 if (item != null) { 184 addLabelIndex(item.getLabel(), n); 185 } 186 } 187 } 188