]>
Commit | Line | Data |
---|---|---|
ee9dd372 TT |
1 | // BitSet - A vector of bits. |
2 | ||
3 | /* Copyright (C) 1998, 1999 Cygnus Solutions | |
4 | ||
5 | This file is part of libgcj. | |
6 | ||
7 | This software is copyrighted work licensed under the terms of the | |
8 | Libgcj License. Please consult the file "LIBGCJ_LICENSE" for | |
9 | details. */ | |
10 | ||
11 | package java.util; | |
12 | import java.io.Serializable; | |
13 | ||
14 | /** | |
15 | * @author Tom Tromey <tromey@cygnus.com> | |
16 | * @date October 23, 1998. | |
17 | */ | |
18 | ||
19 | /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 | |
20 | * hashCode algorithm taken from JDK 1.2 docs. | |
21 | */ | |
22 | ||
23 | public final class BitSet implements Cloneable, Serializable | |
24 | { | |
25 | public void and (BitSet bs) | |
26 | { | |
27 | if (bs == null) | |
28 | throw new NullPointerException (); | |
29 | int max = Math.min(bits.length, bs.bits.length); | |
30 | int i; | |
31 | for (i = 0; i < max; ++i) | |
32 | bits[i] &= bs.bits[i]; | |
33 | for ( ; i < bits.length; ++i) | |
34 | bits[i] = 0; | |
35 | } | |
36 | ||
37 | public BitSet () | |
38 | { | |
39 | this (64); | |
40 | } | |
41 | ||
42 | public BitSet (int nbits) | |
43 | { | |
44 | if (nbits < 0) | |
45 | throw new NegativeArraySizeException (); | |
46 | int length = nbits / 64; | |
47 | if (nbits % 64 != 0) | |
48 | ++length; | |
49 | bits = new long[length]; | |
50 | } | |
51 | ||
52 | public void clear (int pos) | |
53 | { | |
54 | if (pos < 0) | |
55 | throw new IndexOutOfBoundsException (); | |
56 | int bit = pos % 64; | |
57 | int offset = pos / 64; | |
58 | ensure (offset); | |
59 | bits[offset] &= ~ (1 << bit); | |
60 | } | |
61 | ||
62 | public Object clone () | |
63 | { | |
64 | BitSet bs = new BitSet (bits.length * 64); | |
65 | System.arraycopy(bits, 0, bs.bits, 0, bits.length); | |
66 | return bs; | |
67 | } | |
68 | ||
69 | public boolean equals (Object obj) | |
70 | { | |
71 | if (! (obj instanceof BitSet)) | |
72 | return false; | |
73 | BitSet bs = (BitSet) obj; | |
74 | int max = Math.min(bits.length, bs.bits.length); | |
75 | int i; | |
76 | for (i = 0; i < max; ++i) | |
77 | if (bits[i] != bs.bits[i]) | |
78 | return false; | |
79 | // If one is larger, check to make sure all extra bits are 0. | |
80 | for (int j = i; j < bits.length; ++j) | |
81 | if (bits[j] != 0) | |
82 | return false; | |
83 | for (int j = i; j < bs.bits.length; ++j) | |
84 | if (bs.bits[j] != 0) | |
85 | return false; | |
86 | return true; | |
87 | } | |
88 | ||
89 | public boolean get (int pos) | |
90 | { | |
91 | if (pos < 0) | |
92 | throw new IndexOutOfBoundsException (); | |
93 | ||
94 | int bit = pos % 64; | |
95 | int offset = pos / 64; | |
96 | ||
97 | if (offset >= bits.length) | |
98 | return false; | |
99 | ||
100 | return (bits[offset] & (1 << bit)) == 0 ? false : true; | |
101 | } | |
102 | ||
103 | public int hashCode () | |
104 | { | |
105 | long h = 1234; | |
106 | for (int i = bits.length - 1; i >= 0; --i) | |
107 | h ^= bits[i] * (i + 1); | |
108 | return (int) ((h >> 32) ^ h); | |
109 | } | |
110 | ||
111 | public void or (BitSet bs) | |
112 | { | |
113 | if (bs == null) | |
114 | throw new NullPointerException (); | |
115 | ensure (bs.bits.length - 1); | |
116 | int i; | |
117 | for (i = 0; i < bs.bits.length; ++i) | |
118 | bits[i] |= bs.bits[i]; | |
119 | } | |
120 | ||
121 | public void set (int pos) | |
122 | { | |
123 | if (pos < 0) | |
124 | throw new IndexOutOfBoundsException (); | |
125 | int bit = pos % 64; | |
126 | int offset = pos / 64; | |
127 | ensure (offset); | |
128 | bits[offset] |= 1 << bit; | |
129 | } | |
130 | ||
131 | public int size () | |
132 | { | |
133 | return bits.length * 64; | |
134 | } | |
135 | ||
136 | public String toString () | |
137 | { | |
138 | StringBuffer result = new StringBuffer ("{"); | |
139 | boolean first = true; | |
140 | for (int i = 0; i < bits.length; ++i) | |
141 | { | |
142 | int bit = 1; | |
143 | long word = bits[i]; | |
144 | for (int j = 0; j < 64; ++j) | |
145 | { | |
146 | if ((word & bit) != 0) | |
147 | { | |
148 | if (! first) | |
149 | result.append(", "); | |
150 | result.append(64 * i + j); | |
151 | first = false; | |
152 | } | |
153 | bit <<= 1; | |
154 | } | |
155 | } | |
156 | ||
157 | return result.append("}").toString(); | |
158 | } | |
159 | ||
160 | public void xor (BitSet bs) | |
161 | { | |
162 | if (bs == null) | |
163 | throw new NullPointerException (); | |
164 | ensure (bs.bits.length - 1); | |
165 | int i; | |
166 | for (i = 0; i < bs.bits.length; ++i) | |
167 | bits[i] ^= bs.bits[i]; | |
168 | } | |
169 | ||
170 | // Make sure the vector is big enough. | |
171 | private final void ensure (int lastElt) | |
172 | { | |
173 | if (lastElt + 1 > bits.length) | |
174 | { | |
175 | long[] nd = new long[lastElt + 1]; | |
176 | System.arraycopy(bits, 0, nd, 0, bits.length); | |
177 | bits = nd; | |
178 | } | |
179 | } | |
180 | ||
181 | // The actual bits. | |
182 | private long[] bits; | |
183 | } |