Home | History | Annotate | Download | only in util 
      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 */
     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      */
     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      */
     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      */
     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      */
     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      */
    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      */
    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
    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      */
    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      */
    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