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} */ 38 @Override add(int value)39 public void add(int value) { 40 int index = ints.binarysearch(value); 41 42 if (index < 0) { 43 ints.insert(-(index + 1), value); 44 } 45 } 46 47 /** {@inheritDoc} */ 48 @Override remove(int value)49 public void remove(int value) { 50 int index = ints.indexOf(value); 51 52 if (index >= 0) { 53 ints.removeIndex(index); 54 } 55 } 56 57 /** {@inheritDoc} */ 58 @Override has(int value)59 public boolean has(int value) { 60 return ints.indexOf(value) >= 0; 61 } 62 63 /** {@inheritDoc} */ 64 @Override merge(IntSet other)65 public void merge(IntSet other) { 66 if (other instanceof ListIntSet) { 67 ListIntSet o = (ListIntSet) other; 68 int szThis = ints.size(); 69 int szOther = o.ints.size(); 70 71 int i = 0; 72 int j = 0; 73 74 while (j < szOther && i < szThis) { 75 while (j < szOther && o.ints.get(j) < ints.get(i)) { 76 add(o.ints.get(j++)); 77 } 78 if (j == szOther) { 79 break; 80 } 81 while (i < szThis && o.ints.get(j) >= ints.get(i)) { 82 i++; 83 } 84 } 85 86 while (j < szOther) { 87 add(o.ints.get(j++)); 88 } 89 90 ints.sort(); 91 } else if (other instanceof BitIntSet) { 92 BitIntSet o = (BitIntSet) other; 93 94 for (int i = 0; i >= 0; i = Bits.findFirst(o.bits, i + 1)) { 95 ints.add(i); 96 } 97 ints.sort(); 98 } else { 99 IntIterator iter = other.iterator(); 100 while (iter.hasNext()) { 101 add(iter.next()); 102 } 103 } 104 } 105 106 /** {@inheritDoc} */ 107 @Override elements()108 public int elements() { 109 return ints.size(); 110 } 111 112 /** {@inheritDoc} */ 113 @Override iterator()114 public IntIterator iterator() { 115 return new IntIterator() { 116 private int idx = 0; 117 118 /** {@inheritDoc} */ 119 @Override 120 public boolean hasNext() { 121 return idx < ints.size(); 122 } 123 124 /** {@inheritDoc} */ 125 @Override 126 public int next() { 127 if (!hasNext()) { 128 throw new NoSuchElementException(); 129 } 130 131 return ints.get(idx++); 132 } 133 }; 134 } 135 136 /** {@inheritDoc} */ 137 @Override toString()138 public String toString() { 139 return ints.toString(); 140 } 141 } 142