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
17package com.android.dx.util;
18
19import java.util.NoSuchElementException;
20
21/**
22 * A set of integers, represented by a list
23 */
24public 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