1 /* 2 * Copyright (C) 2008 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.NoSuchElementException; 20 21 /** 22 * A set of integers, represented by a list 23 */ 24 public class ListIntSet implements IntSet { 25 26 /** also accessed in BitIntSet */ 27 final IntList ints; 28 29 /** 30 * Constructs an instance 31 */ ListIntSet()32 public ListIntSet() { 33 ints = new IntList(); 34 ints.sort(); 35 } 36 37 /** @inheritDoc */ add(int value)38 public void add(int value) { 39 int index = ints.binarysearch(value); 40 41 if (index < 0) { 42 ints.insert(-(index + 1), value); 43 } 44 } 45 46 /** @inheritDoc */ remove(int value)47 public void remove(int value) { 48 int index = ints.indexOf(value); 49 50 if (index >= 0) { 51 ints.removeIndex(index); 52 } 53 } 54 55 /** @inheritDoc */ has(int value)56 public boolean has(int value) { 57 return ints.indexOf(value) >= 0; 58 } 59 60 /** @inheritDoc */ merge(IntSet other)61 public void merge(IntSet other) { 62 if (other instanceof ListIntSet) { 63 ListIntSet o = (ListIntSet) other; 64 int szThis = ints.size(); 65 int szOther = o.ints.size(); 66 67 int i = 0; 68 int j = 0; 69 70 while (j < szOther && i < szThis) { 71 while (j < szOther && o.ints.get(j) < ints.get(i)) { 72 add(o.ints.get(j++)); 73 } 74 if (j == szOther) { 75 break; 76 } 77 while (i < szThis && o.ints.get(j) >= ints.get(i)) { 78 i++; 79 } 80 } 81 82 while (j < szOther) { 83 add(o.ints.get(j++)); 84 } 85 86 ints.sort(); 87 } else if (other instanceof BitIntSet) { 88 BitIntSet o = (BitIntSet) other; 89 90 for (int i = 0; i >= 0; i = Bits.findFirst(o.bits, i + 1)) { 91 ints.add(i); 92 } 93 ints.sort(); 94 } else { 95 IntIterator iter = other.iterator(); 96 while (iter.hasNext()) { 97 add(iter.next()); 98 } 99 } 100 } 101 102 /** @inheritDoc */ elements()103 public int elements() { 104 return ints.size(); 105 } 106 107 /** @inheritDoc */ iterator()108 public IntIterator iterator() { 109 return new IntIterator() { 110 private int idx = 0; 111 112 /** @inheritDoc */ 113 public boolean hasNext() { 114 return idx < ints.size(); 115 } 116 117 /** @inheritDoc */ 118 public int next() { 119 if (!hasNext()) { 120 throw new NoSuchElementException(); 121 } 122 123 return ints.get(idx++); 124 } 125 126 /** @inheritDoc */ 127 public void remove() { 128 throw new UnsupportedOperationException(); 129 } 130 }; 131 } 132 133 /** @inheritDoc */ toString()134 public String toString() { 135 return ints.toString(); 136 } 137 } 138