1917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/* 2917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Copyright (C) 2008 The Android Open Source Project 3917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 4917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Licensed under the Apache License, Version 2.0 (the "License"); 5917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * you may not use this file except in compliance with the License. 6917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * You may obtain a copy of the License at 7917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 8917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * http://www.apache.org/licenses/LICENSE-2.0 9917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 10917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Unless required by applicable law or agreed to in writing, software 11917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * distributed under the License is distributed on an "AS IS" BASIS, 12917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * See the License for the specific language governing permissions and 14917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * limitations under the License. 15917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 16917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 17917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpackage com.android.dexgen.util; 18917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 19917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport java.util.NoSuchElementException; 20917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 21917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/** 22917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * A set of integers, represented by a list 23917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 24917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpublic class ListIntSet implements IntSet { 25917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 26917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** also accessed in BitIntSet */ 27917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul final IntList ints; 28917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 29917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 30917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an instance 31917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 32917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public ListIntSet() { 33917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints = new IntList(); 34917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.sort(); 35917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 36917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 37917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 38917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void add(int value) { 39917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int index = ints.binarysearch(value); 40917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 41917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (index < 0) { 42917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.insert(-(index + 1), value); 43917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 44917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 45917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 46917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 47917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void remove(int value) { 48917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int index = ints.indexOf(value); 49917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 50917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (index >= 0) { 51917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.removeIndex(index); 52917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 53917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 54917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 55917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 56917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean has(int value) { 57917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ints.indexOf(value) >= 0; 58917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 59917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 60917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 61917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void merge(IntSet other) { 62917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (other instanceof ListIntSet) { 63917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ListIntSet o = (ListIntSet) other; 64917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int szThis = ints.size(); 65917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int szOther = o.ints.size(); 66917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 67917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int i = 0; 68917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int j = 0; 69917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 70917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (j < szOther && i < szThis) { 71917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (j < szOther && o.ints.get(j) < ints.get(i)) { 72917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul add(o.ints.get(j++)); 73917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 74917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (j == szOther) { 75917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul break; 76917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 77917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (i < szThis && o.ints.get(j) >= ints.get(i)) { 78917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul i++; 79917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 80917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 81917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 82917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (j < szOther) { 83917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul add(o.ints.get(j++)); 84917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 85917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 86917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.sort(); 87917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else if (other instanceof BitIntSet) { 88917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul BitIntSet o = (BitIntSet) other; 89917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 90917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i >= 0; i = Bits.findFirst(o.bits, i + 1)) { 91917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.add(i); 92917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 93917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ints.sort(); 94917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else { 95917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntIterator iter = other.iterator(); 96917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (iter.hasNext()) { 97917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul add(iter.next()); 98917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 99917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 100917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 101917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 102917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 103917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int elements() { 104917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ints.size(); 105917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 106917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 107917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 108917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntIterator iterator() { 109917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return new IntIterator() { 110917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private int idx = 0; 111917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 112917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 113917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean hasNext() { 114917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return idx < ints.size(); 115917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 116917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 117917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 118917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int next() { 119917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!hasNext()) { 120917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new NoSuchElementException(); 121917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 122917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 123917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ints.get(idx++); 124917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 125917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul }; 126917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 127917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 128917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 129917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public String toString() { 130917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ints.toString(); 131917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 132917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul} 133