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 19ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornsteinimport java.util.Arrays; 20ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein 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 /** 26893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * Sparse array indexed by label to FixedSizeList index; 27893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * {@code -1} for an invalid label. 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final IntList labelToIndex; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public LabeledList(int size) { 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(size); 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex = new IntList(size); 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs a new instance that is a copy of the old instance. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param old instance to copy 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 43893ea594be06711902de7a484c0eecb910356f42Dan Bornstein public LabeledList(LabeledList old) { 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(old.size()); 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex = old.labelToIndex.mutableCopy(); 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = old.size(); 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Object one = old.get0(i); 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set0(i, one); 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 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 * Gets the maximum label (exclusive) of any block added to this instance. 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 6099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the maximum label 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 62ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein public final int getMaxLabel() { 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = labelToIndex.size(); 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65893ea594be06711902de7a484c0eecb910356f42Dan Bornstein // Gobble any deleted labels that may be at the end. 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--) 68893ea594be06711902de7a484c0eecb910356f42Dan Bornstein /*empty*/ ; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70893ea594be06711902de7a484c0eecb910356f42Dan Bornstein int newSize = i + 1; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.shrink(newSize); 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newSize; 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 78893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * Removes a label from the label-to-index mapping. 79893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldLabel label to remove 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 82893ea594be06711902de7a484c0eecb910356f42Dan Bornstein private 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 /** 87893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * Adds a label and index to the label-to-index mapping. 88893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param label new label 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param index index of block. 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 92893ea594be06711902de7a484c0eecb910356f42Dan Bornstein private void addLabelIndex(int label, int index) { 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int origSz = labelToIndex.size(); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i <= (label - origSz); i++) { 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.add(-1); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.set(label, index); 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the index of the first item in the list with the given 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * label, if any. 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} the label to look for 10799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= -1;} the index of the so-labelled item, or {@code -1} 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if none is found 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 110ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein public final int indexOfLabel(int label) { 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label >= labelToIndex.size()) { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return labelToIndex.get(label); 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 118ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein /** 119ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * Gets an array containing all of the labels used in this instance, 120ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * in order. The returned array is freshly-allocated and so may be 121ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * modified safely by the caller without impacting this instance. 122ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * 123ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @return {@code non-null;} ordered array of labels 124ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @throws NullPointerException thrown if there are any {@code null} 125ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * items in this instance 126ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein */ 127ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein public final int[] getLabelsInOrder() { 128ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein int sz = size(); 129ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein int[] result = new int[sz]; 130ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein 131ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein for (int i = 0; i < sz; i++) { 132ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein LabeledItem li = (LabeledItem) get0(i); 133ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein if (li == null) { 134ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein throw new NullPointerException("null at index " + i); 135ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein } 136ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein result[i] = li.getLabel(); 137ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein } 138ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein 139ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein Arrays.sort(result); 140ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein return result; 141ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein } 142ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void shrinkToFit() { 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super.shrinkToFit(); 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project rebuildLabelToIndex(); 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 152893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * Rebuilds the label-to-index mapping after a {@code shrinkToFit()}. 153893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * Note: This assumes that the labels that are in the list are the 154893ea594be06711902de7a484c0eecb910356f42Dan Bornstein * same, although the indicies may have changed. 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 156893ea594be06711902de7a484c0eecb910356f42Dan Bornstein private void rebuildLabelToIndex() { 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szItems = size(); 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szItems; i++) { 160ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein LabeledItem li = (LabeledItem) get0(i); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (li != null) { 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project labelToIndex.set(li.getLabel(), i); 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the element at the given index. 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 17199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which element 17299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param item {@code null-ok;} the value to store 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected void set(int n, LabeledItem item) { 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LabeledItem old = (LabeledItem) getOrNull0(n); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project set0(n, item); 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (old != null) { 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project removeLabel(old.getLabel()); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (item != null) { 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addLabelIndex(item.getLabel(), n); 185de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro } 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 188