IntSet


1   /*
2    * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3    *
4    * This file is part of Resin(R) Open Source
5    *
6    * Each copy or derived work must preserve the copyright notice and this
7    * notice unmodified.
8    *
9    * Resin Open Source is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU General Public License as published by
11   * the Free Software Foundation; either version 2 of the License, or
12   * (at your option) any later version.
13   *
14   * Resin Open Source is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17   * of NON-INFRINGEMENT.  See the GNU General Public License for more
18   * details.
19   *
20   * You should have received a copy of the GNU General Public License
21   * along with Resin Open Source; if not, write to the
22   *   Free SoftwareFoundation, Inc.
23   *   59 Temple Place, Suite 330
24   *   Boston, MA 02111-1307  USA
25   *
26   * @author Scott Ferguson
27   */
28  
29  package com.caucho.util;
30  
31  public class IntSet {
32    int []data;
33    int size;
34  
35    public void clear() {
36      size = 0;
37    }
38    
39    private void expand(int max) {
40      while (max > data.length) {
41        int []next = new int[data.length * 2];
42  
43        for (int i = 0; i < data.length; i++)
44      next[i] = data[i];
45  
46        data = next;
47      }
48    }
49  
50    public int length() { return size / 2; }
51    public int size() { return size / 2; }
52  
53    public int getMin(int i) { return data[2 * i]; } 
54    public int getMax(int i) { return data[2 * i + 1]; } 
55  
56    private void insert(int i, int min, int max) {
57      expand(size + 2);
58  
59      System.arraycopy(data, i, data, i + 2, size - i);
60  
61      data[i] = min;
62      data[i + 1] = max;
63  
64      size += 2; 
65    }
66  
67    private void delete(int i) {
68      System.arraycopy(data, i + 2, data, i, size - i - 2);
69  
70      size -= 2; 
71    }
72  
73    /**
74     * Adds the range [min,max] to the set.
75     */
76    public void union(int min, int max) {
77      for (int i = 1; i < size; i += 2) {
78        if (max < data[i - 1] - 1) {
79      insert(i - 1, min, max);
80      return;
81        }
82  
83        if (min > data[i] + 1)
84      continue;
85  
86        if (min < data[i - 1])
87      data[i - 1] = min;
88        if (max > data[i])
89      data[i] = max;
90  
91        int j = i + 2;
92        while (j < size && max > data[j - 1] + 1) {
93      if (max < data[j - 1])
94        data[i] = data[j - 1];
95  
96      delete(j - 1);
97        }
98        return;
99      }
100 
101     insert(size, min, max);
102   }
103 
104   /**
105    * Adds a point to the set
106    */
107   public void union(int value) {
108     union(value, value);
109   }
110 
111   /**
112    * The union of two sets.
113    */
114   public void union(IntSet set) {
115     for (int i = 1; i < set.size; i += 2)
116       union(set.data[i - 1], set.data[i]);
117   }
118 
119   /**
120    * The union with the negation of the 2nd set
121    */
122   public void unionNegate(IntSet set, int min, int max) {
123     for (int i = 1; i < set.size; i += 2) {
124       union(min, set.data[i - 1] - 1);
125       min = set.data[i] + 1;
126     }
127     union(min, max);
128   }
129 
130   /**
131    * Negate the set within a universe
132    */
133   public void negate(int minValue, int maxValue) {
134     int max = minValue;
135 
136     if (size > 0 && data[0] == minValue) {
137       max = data[1];
138       delete(0);
139       if (max == maxValue)
140     return;
141       else
142     max++;
143     }
144 
145     for (int i = 1; i < size; i += 2) {
146       int newMax = data[i];
147       data[i] = data[i - 1] - 1;
148       data[i - 1] = max;
149 
150       if (newMax == maxValue)
151     return;
152       max = newMax + 1;
153     }
154 
155     insert(size, max, maxValue);
156   }
157 
158   /**
159    * Negate the set
160    */
161   public void negate() {
162     negate(Integer.MIN_VALUE, Integer.MAX_VALUE);
163   }
164 
165   /**
166    * Calculates the set difference from a and b
167    *
168    * @return true if the original set is not contained in the 2nd
169    */
170   public boolean difference(IntSet set)
171   {
172     int i = 1;
173     int j = 1;
174 
175     while (i < size && j < set.size) {
176       int aMin = data[i - 1];
177       int aMax = data[i];
178 
179       int bMin = set.data[j - 1];
180       int bMax = set.data[j];
181 
182       //       aaaa
183       //  bbbb
184       if (bMax < aMin) {
185     j += 2;
186       }
187       //  aaaa
188       //       bbbb
189       else if (aMax < bMin) {
190     i += 2;
191       }
192       //   aaaa
193       //  bbbbbb
194       else if (bMin <= aMin && aMax <= bMax) {
195     delete(i - 1);
196       }
197       //  aaaaaa
198       //   bbbb
199       else if (aMin < bMin && bMax < aMax) {
200     insert(i + 1, bMax + 1, aMax);
201     data[i] = bMin - 1;
202     i += 2;
203     j += 2;
204       }
205       //  aaaa
206       //   bbbb
207       else if (aMin < bMin) {
208     data[i] = bMin - 1;
209     i += 2;
210       }
211       //  aaaa
212       // bbbb
213       else if (aMax > bMax) {
214     data[i - 1] = bMax + 1;
215     j += 2;
216       } 
217       else {
218     throw new RuntimeException  ("Impossible case");
219       }
220     }
221 
222     return size != 0;
223   }
224 
225   /**
226    * Calculates the set intersection of a and b
227    *
228    * @return true if not disjoint
229    */
230   public boolean intersection(IntSet set)
231   {
232     int i = 1;
233     int j = 1;
234 
235     while (i < size && j < set.size) {
236       int aMin = data[i - 1];
237       int aMax = data[i];
238 
239       int bMin = set.data[j - 1];
240       int bMax = set.data[j];
241 
242       //       aaaa
243       //  bbbb
244       if (bMax < aMin) {
245     j += 2;
246       }
247       //  aaaa
248       //       bbbb
249       else if (aMax < bMin) {
250     delete(i - 1);
251       }
252       //   aaaa
253       //  bbbbbb
254       else if (bMin <= aMin && aMax <= bMax) {
255     i += 2;
256       }
257       //  aaaaaa
258       //   bbbb
259       else if (aMin <= bMin && bMax <= aMax) {
260     data[i - 1] = bMin;
261     data[i] = bMax;
262     if (bMax < aMax)
263       insert(i + 1, bMax + 1, aMax);
264     i += 2;
265     j += 2;
266       }
267       //  aaaa
268       //   bbbb
269       else if (aMin <= bMin) {
270     data[i - 1] = bMin;
271     i += 2;
272       }
273       //  aaaa
274       // bbbb
275       else if (bMin < aMin) {
276     data[i] = bMax;
277     insert(i + 1, bMax + 1, aMax);
278     i += 2;
279       }
280       else {
281     throw new RuntimeException  ("case");
282       }
283     }
284 
285     while (i < size)
286       delete(i - 1);
287 
288     return size != 0;
289   }
290 
291   /**
292    * True if the set contains the element
293    */
294   public boolean contains(int test)
295   {
296     for (int i = 1; i < size; i += 2) {
297       if (test < data[i - 1])
298     return false;
299       if (test <= data[i])
300     return true;
301     }
302 
303     return false;
304   }
305 
306   /**
307    * True if the argument is a subset of the set
308    */
309   public boolean isSubset(IntSet subset)
310   {
311     int i = 1;
312     int j = 1;
313 
314     while (i < size && j < subset.size) {
315       if (data[i] < subset.data[j - 1])
316     i += 2;
317       else if (subset.data[j - 1] < data[i - 1] || subset.data[j] > data[i])
318     return false;
319       else
320     j += 2;
321     }
322 
323     return true;
324   }
325 
326   /**
327    * True if the two sets are disjoint.
328    */
329   public boolean isDisjoint(IntSet set)
330   {
331     int i = 1;
332     int j = 1;
333 
334     while (i < size && j < set.size) {
335       if (data[i] < set.data[j - 1])
336     i += 2;
337       else if (set.data[j] < data[i - 1])
338     j += 2;
339       else
340     return false;
341     }
342 
343     return true;
344   }
345 
346   /**
347    * Returns a visible.
348    */
349   public String   toString()
350   {
351     StringBuffer   sbuf = new StringBuffer  ();
352     
353     sbuf.append("IntSet[");
354     for (int i = 1; i < size; i += 1) {
355       if (i != 1)
356     sbuf.append(" ");
357 
358       sbuf.append(data[i - 1]);
359       if (data[i - 1] != data[i]) {
360     sbuf.append(",");
361     sbuf.append(data[i]);
362       }
363     }
364     sbuf.append("]");
365 
366     return sbuf.toString();
367   }
368 
369   /**
370    * Returns a clone of the set.
371    */
372   public Object   clone()
373   {
374     IntSet set = new IntSet(false);
375 
376     set.data = new int[data.length];
377     set.size = size;
378     
379     System.arraycopy(data, 0, set.data, 0, size);
380 
381     return set;
382   }
383 
384   private IntSet(boolean dummy) { 
385   }
386 
387   /**
388    * Creates an empty set.
389    */
390   public IntSet() { 
391     data = new int[16];
392     size = 0;
393   }
394 }
395
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags