1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.util; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.cf.code.ByteBlock; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A list of labeled items, allowing easy lookup by label. 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class LabeledList extends FixedSizeList { 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sparse array indexed by label to FixedSizeList index. 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * -1 = invalid label. 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final IntList labelToIndex; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public LabeledList(int size) { 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(size); 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex = new IntList(size); 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs a new instance that is a copy of the old instance. 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param old instance to copy 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected LabeledList(LabeledList old) { 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(old.size()); 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex = old.labelToIndex.mutableCopy(); 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = old.size(); 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Object one = old.get0(i); 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set0(i, one); 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the maximum label (exclusive) of any block added to this instance. 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 6199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the maximum label 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getMaxLabel() { 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = labelToIndex.size(); 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Gobble any deleted labels that may be at the end... 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--) 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newSize = i+1; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.shrink(newSize); 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newSize; 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Removes a label from the label-to-index mapping 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldLabel label to remove 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected void removeLabel(int oldLabel) { 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.set(oldLabel, -1); 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds a label and index to the label-to-index mapping 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label new label 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param index index of block. 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected void addLabelIndex(int label, int index) { 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origSz = labelToIndex.size(); 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i <= (label - origSz); i++) { 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.add(-1); 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.set(label, index); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the index of the first item in the list with the given 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label, if any. 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} the label to look for 10699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= -1;} the index of the so-labelled item, or {@code -1} 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if none is found 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int indexOfLabel(int label) { 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= labelToIndex.size()) { 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return labelToIndex.get(label); 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void shrinkToFit() { 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super.shrinkToFit(); 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rebuildLabelToIndex(); 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Rebuilds the label-to-index mapping after a shrinkToFit(). 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Note: assumes that the labels that are in the list are the same 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * although the indicies may have changed. 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected void rebuildLabelToIndex() { 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szItems = size(); 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szItems; i++) { 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LabeledItem li = (LabeledItem)get0(i); 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (li != null) { 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.set(li.getLabel(), i); 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the element at the given index. 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 14599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which element 14699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param item {@code null-ok;} the value to store 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected void set(int n, LabeledItem item) { 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LabeledItem old = (LabeledItem) getOrNull0(n); 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set0(n, item); 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (old != null) { 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeLabel(old.getLabel()); 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (item != null) { 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addLabelIndex(item.getLabel(), n); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 162