Mercurial > hg > Members > kono > jpf-core
annotate src/main/gov/nasa/jpf/util/BitSetN.java @ 0:61d41facf527
initial v8 import (history reset)
author | Peter Mehlitz <Peter.C.Mehlitz@nasa.gov> |
---|---|
date | Fri, 23 Jan 2015 10:14:01 -0800 |
parents | |
children |
rev | line source |
---|---|
0
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
1 /* |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
2 * Copyright (C) 2014, United States Government, as represented by the |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
3 * Administrator of the National Aeronautics and Space Administration. |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
4 * All rights reserved. |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
5 * |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
6 * The Java Pathfinder core (jpf-core) platform is licensed under the |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
7 * Apache License, Version 2.0 (the "License"); you may not use this file except |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
8 * in compliance with the License. You may obtain a copy of the License at |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
9 * |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
10 * http://www.apache.org/licenses/LICENSE-2.0. |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
11 * |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
12 * Unless required by applicable law or agreed to in writing, software |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
13 * distributed under the License is distributed on an "AS IS" BASIS, |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
15 * See the License for the specific language governing permissions and |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
16 * limitations under the License. |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
17 */ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
18 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
19 package gov.nasa.jpf.util; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
20 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
21 import java.util.BitSet; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
22 import java.util.NoSuchElementException; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
23 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
24 /** |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
25 * a FixedBitSet implementation that is based on java.util.BitSet |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
26 */ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
27 public class BitSetN extends BitSet implements FixedBitSet { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
28 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
29 class SetBitIterator implements IntIterator { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
30 int cur = 0; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
31 int nBits; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
32 int cardinality; // <2do> this should be lifted since it makes the iterator brittle |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
33 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
34 SetBitIterator (){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
35 cardinality = cardinality(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
36 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
37 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
38 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
39 public void remove() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
40 if (cur >0){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
41 clear(cur-1); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
42 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
43 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
44 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
45 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
46 public boolean hasNext() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
47 return nBits < cardinality; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
48 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
49 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
50 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
51 public int next() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
52 if (nBits < cardinality){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
53 int idx = nextSetBit(cur); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
54 if (idx >= 0){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
55 nBits++; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
56 cur = idx+1; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
57 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
58 return idx; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
59 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
60 } else { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
61 throw new NoSuchElementException(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
62 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
63 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
64 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
65 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
66 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
67 public BitSetN (int nBits){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
68 super(nBits); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
69 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
70 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
71 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
72 public FixedBitSet clone() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
73 return (FixedBitSet) super.clone(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
74 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
75 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
76 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
77 public int capacity() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
78 return size(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
79 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
80 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
81 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
82 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
83 public void hash (HashData hd){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
84 long[] data = toLongArray(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
85 for (int i=0; i<data.length; i++){ |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
86 hd.add(data[i]); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
87 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
88 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
89 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
90 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
91 //--- IntSet interface |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
92 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
93 public boolean add(int i) { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
94 if (get(i)) { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
95 return false; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
96 } else { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
97 set(i); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
98 return true; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
99 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
100 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
101 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
102 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
103 public boolean remove(int i) { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
104 if (get(i)) { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
105 clear(i); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
106 return true; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
107 } else { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
108 return false; |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
109 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
110 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
111 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
112 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
113 public boolean contains(int i) { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
114 return get(i); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
115 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
116 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
117 @Override |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
118 public IntIterator intIterator() { |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
119 return new SetBitIterator(); |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
120 } |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
121 |
61d41facf527
initial v8 import (history reset)
Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
parents:
diff
changeset
|
122 } |