| /* |
| * Copyright (C) 2008 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dexgen.util; |
| |
| import java.util.NoSuchElementException; |
| |
| /** |
| * A set of integers, represented by a list |
| */ |
| public class ListIntSet implements IntSet { |
| |
| /** also accessed in BitIntSet */ |
| final IntList ints; |
| |
| /** |
| * Constructs an instance |
| */ |
| public ListIntSet() { |
| ints = new IntList(); |
| ints.sort(); |
| } |
| |
| /** @inheritDoc */ |
| public void add(int value) { |
| int index = ints.binarysearch(value); |
| |
| if (index < 0) { |
| ints.insert(-(index + 1), value); |
| } |
| } |
| |
| /** @inheritDoc */ |
| public void remove(int value) { |
| int index = ints.indexOf(value); |
| |
| if (index >= 0) { |
| ints.removeIndex(index); |
| } |
| } |
| |
| /** @inheritDoc */ |
| public boolean has(int value) { |
| return ints.indexOf(value) >= 0; |
| } |
| |
| /** @inheritDoc */ |
| public void merge(IntSet other) { |
| if (other instanceof ListIntSet) { |
| ListIntSet o = (ListIntSet) other; |
| int szThis = ints.size(); |
| int szOther = o.ints.size(); |
| |
| int i = 0; |
| int j = 0; |
| |
| while (j < szOther && i < szThis) { |
| while (j < szOther && o.ints.get(j) < ints.get(i)) { |
| add(o.ints.get(j++)); |
| } |
| if (j == szOther) { |
| break; |
| } |
| while (i < szThis && o.ints.get(j) >= ints.get(i)) { |
| i++; |
| } |
| } |
| |
| while (j < szOther) { |
| add(o.ints.get(j++)); |
| } |
| |
| ints.sort(); |
| } else if (other instanceof BitIntSet) { |
| BitIntSet o = (BitIntSet) other; |
| |
| for (int i = 0; i >= 0; i = Bits.findFirst(o.bits, i + 1)) { |
| ints.add(i); |
| } |
| ints.sort(); |
| } else { |
| IntIterator iter = other.iterator(); |
| while (iter.hasNext()) { |
| add(iter.next()); |
| } |
| } |
| } |
| |
| /** @inheritDoc */ |
| public int elements() { |
| return ints.size(); |
| } |
| |
| /** @inheritDoc */ |
| public IntIterator iterator() { |
| return new IntIterator() { |
| private int idx = 0; |
| |
| /** @inheritDoc */ |
| public boolean hasNext() { |
| return idx < ints.size(); |
| } |
| |
| /** @inheritDoc */ |
| public int next() { |
| if (!hasNext()) { |
| throw new NoSuchElementException(); |
| } |
| |
| return ints.get(idx++); |
| } |
| }; |
| } |
| |
| /** @inheritDoc */ |
| public String toString() { |
| return ints.toString(); |
| } |
| } |