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
17package com.android.dx.util;
18
19import com.android.dx.cf.code.ByteBlock;
20
21/**
22 * A list of labeled items, allowing easy lookup by label.
23 */
24public class LabeledList extends FixedSizeList {
25
26    /**
27     * Sparse array indexed by label to FixedSizeList index.
28     * -1 = invalid label.
29     */
30    private final IntList labelToIndex;
31
32    /** @inheritDoc */
33    public LabeledList(int size) {
34        super(size);
35
36        labelToIndex = new IntList(size);
37    }
38
39    /**
40     * Constructs a new instance that is a copy of the old instance.
41     *
42     * @param old instance to copy
43     */
44    protected LabeledList(LabeledList old) {
45        super(old.size());
46        labelToIndex = old.labelToIndex.mutableCopy();
47
48        int sz = old.size();
49
50        for (int i = 0; i < sz; i++) {
51            Object one = old.get0(i);
52            if (one != null) {
53                set0(i, one);
54            }
55        }
56    }
57
58    /**
59     * Gets the maximum label (exclusive) of any block added to this instance.
60     *
61     * @return {@code >= 0;} the maximum label
62     */
63    public int getMaxLabel() {
64        int sz = labelToIndex.size();
65
66        // Gobble any deleted labels that may be at the end...
67        int i;
68        for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--)
69            ;
70
71        int newSize = i+1;
72
73        labelToIndex.shrink(newSize);
74
75        return newSize;
76    }
77
78    /**
79     * Removes a label from the label-to-index mapping
80     * @param oldLabel label to remove
81     */
82    protected 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     * @param label new label
89     * @param index index of block.
90     */
91    protected void addLabelIndex(int label, int index) {
92        int origSz = labelToIndex.size();
93
94        for (int i = 0; i <= (label - origSz); i++) {
95            labelToIndex.add(-1);
96        }
97
98        labelToIndex.set(label, index);
99    }
100
101    /**
102     * Gets the index of the first item in the list with the given
103     * label, if any.
104     *
105     * @param label {@code >= 0;} the label to look for
106     * @return {@code >= -1;} the index of the so-labelled item, or {@code -1}
107     * if none is found
108     */
109    public int indexOfLabel(int label) {
110        if (label >= labelToIndex.size()) {
111            return -1;
112        } else {
113            return labelToIndex.get(label);
114        }
115    }
116
117    /** @inheritDoc */
118    @Override
119    public void shrinkToFit() {
120        super.shrinkToFit();
121
122        rebuildLabelToIndex();
123    }
124
125    /**
126     * Rebuilds the label-to-index mapping after a shrinkToFit().
127     * Note: assumes that the labels that are in the list are the same
128     * although the indicies may have changed.
129     */
130    protected void rebuildLabelToIndex() {
131        int szItems = size();
132
133        for (int i = 0; i < szItems; i++) {
134            LabeledItem li = (LabeledItem)get0(i);
135
136            if (li != null) {
137                labelToIndex.set(li.getLabel(), i);
138            }
139        }
140    }
141
142    /**
143     * Sets the element at the given index.
144     *
145     * @param n {@code >= 0, < size();} which element
146     * @param item {@code null-ok;} the value to store
147     */
148    protected void set(int n, LabeledItem item) {
149        LabeledItem old = (LabeledItem) getOrNull0(n);
150
151        set0(n, item);
152
153        if (old != null) {
154            removeLabel(old.getLabel());
155        }
156
157        if (item != null) {
158            addLabelIndex(item.getLabel(), n);
159        }
160    }
161}
162