Home | History | Annotate | Download | only in util 
      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      */
     32     public ListIntSet() {
     33         ints = new IntList();
     34         ints.sort();
     35     }
     36 
     37     /** @inheritDoc */
     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 */
     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 */
     56     public boolean has(int value) {
     57         return ints.indexOf(value) >= 0;
     58     }
     59 
     60     /** @inheritDoc */
     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 */
    103     public int elements() {
    104         return ints.size();
    105     }
    106 
    107     /** @inheritDoc */
    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     }
    127 
    128     /** @inheritDoc */
    129     public String toString() {
    130         return ints.toString();
    131     }
    132 }
    133