KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > enhydra > apache > xerces > validators > common > CMStateSet


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 1999 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Xerces" and "Apache Software Foundation" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache",
33  * nor may "Apache" appear in their name, without prior written
34  * permission of the Apache Software Foundation.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation and was
52  * originally based on software copyright (c) 1999, International
53  * Business Machines, Inc., http://www.apache.org. For more
54  * information on the Apache Software Foundation, please see
55  * <http://www.apache.org/>.
56  */
57
58 package org.enhydra.apache.xerces.validators.common;
59
60 import org.enhydra.apache.xerces.utils.ImplementationMessages;
61
62 /**
63  * This class is a very simple bitset class. The DFA content model code needs
64  * to support a bit set, but the java BitSet class is way, way overkill. Our
65  * bitset never needs to be expanded after creation, hash itself, etc...
66  *
67  * Since the vast majority of content models will never require more than 64
68  * bits, and since allocation of anything in Java is expensive, this class
69  * provides a hybrid implementation that uses two ints for instances that use
70  * 64 bits or fewer. It has a byte array reference member which will only be
71  * used if more than 64 bits are required.
72  *
73  * Note that the code that uses this class will never perform operations
74  * on sets of different sizes, so that check does not have to be made here.
75  *
76  * @version
77  */
78 class CMStateSet
79 {
80     // -------------------------------------------------------------------
81 // Constructors
82 // -------------------------------------------------------------------
83 CMStateSet(int bitCount) throws CMException
84     {
85         // Store the required bit count and insure its legal
86 fBitCount = bitCount;
87         if (fBitCount < 0)
88             throw new CMException(ImplementationMessages.VAL_CMSI);
89
90         //
91 // See if we need to allocate the byte array or whether we can live
92 // within the 64 bit high performance scheme.
93 //
94 if (fBitCount > 64)
95         {
96             fByteCount = fBitCount / 8;
97             if (fBitCount % 8 != 0)
98                 fByteCount++;
99             fByteArray = new byte[fByteCount];
100         }
101
102         // Init all the bits to zero
103 zeroBits();
104     }
105
106
107     // -------------------------------------------------------------------
108 // Public inherited methods
109 // -------------------------------------------------------------------
110 public String JavaDoc toString()
111     {
112         StringBuffer JavaDoc strRet = new StringBuffer JavaDoc();
113         try
114         {
115             strRet.append("{");
116             for (int index = 0; index < fBitCount; index++)
117             {
118                 if (getBit(index))
119                     strRet.append(" " + index);
120             }
121             strRet.append(" }");
122         }
123
124         catch(CMException exToCatch)
125         {
126             //
127 // We know this won't happen but we have to catch it to avoid it
128 // having to be in our 'throws' list.
129 //
130 }
131         return strRet.toString();
132     }
133
134
135     // -------------------------------------------------------------------
136 // Package final methods
137 // -------------------------------------------------------------------
138 final void intersection(CMStateSet setToAnd)
139     {
140         if (fBitCount < 65)
141         {
142             fBits1 &= setToAnd.fBits1;
143             fBits2 &= setToAnd.fBits2;
144         }
145          else
146         {
147             for (int index = fByteCount - 1; index >= 0; index--)
148                 fByteArray[index] &= setToAnd.fByteArray[index];
149         }
150     }
151
152     final boolean getBit(int bitToGet) throws CMException
153     {
154         if (bitToGet >= fBitCount)
155             throw new CMException(ImplementationMessages.VAL_CMSI);
156
157         if (fBitCount < 65)
158         {
159             final int mask = (0x1 << (bitToGet % 32));
160             if (bitToGet < 32)
161                 return (fBits1 & mask) != 0;
162             else
163                 return (fBits2 & mask) != 0;
164         }
165          else
166         {
167             // Create the mask and byte values
168 final byte mask = (byte)(0x1 << (bitToGet % 8));
169             final int ofs = bitToGet >> 3;
170
171             // And access the right bit and byte
172 return ((fByteArray[ofs] & mask) != 0);
173         }
174     }
175
176     final boolean isEmpty()
177     {
178         if (fBitCount < 65)
179         {
180             return ((fBits1 == 0) && (fBits2 == 0));
181         }
182          else
183         {
184             for (int index = fByteCount - 1; index >= 0; index--)
185             {
186                 if (fByteArray[index] != 0)
187                     return false;
188             }
189         }
190         return true;
191     }
192
193     final boolean isSameSet(CMStateSet setToCompare)
194     {
195         if (fBitCount != setToCompare.fBitCount)
196             return false;
197
198         if (fBitCount < 65)
199         {
200             return ((fBits1 == setToCompare.fBits1)
201             && (fBits2 == setToCompare.fBits2));
202         }
203
204         for (int index = fByteCount - 1; index >= 0; index--)
205         {
206             if (fByteArray[index] != setToCompare.fByteArray[index])
207                 return false;
208         }
209         return true;
210     }
211
212     final void union(CMStateSet setToOr)
213     {
214         if (fBitCount < 65)
215         {
216             fBits1 |= setToOr.fBits1;
217             fBits2 |= setToOr.fBits2;
218         }
219          else
220         {
221             for (int index = fByteCount - 1; index >= 0; index--)
222                 fByteArray[index] |= setToOr.fByteArray[index];
223         }
224     }
225
226     final void setBit(int bitToSet) throws CMException
227     {
228         if (bitToSet >= fBitCount)
229             throw new CMException(ImplementationMessages.VAL_CMSI);
230
231         if (fBitCount < 65)
232         {
233             final int mask = (0x1 << (bitToSet % 32));
234             if (bitToSet < 32)
235             {
236                 fBits1 &= ~mask;
237                 fBits1 |= mask;
238             }
239              else
240             {
241                 fBits2 &= ~mask;
242                 fBits2 |= mask;
243             }
244         }
245          else
246         {
247             // Create the mask and byte values
248 final byte mask = (byte)(0x1 << (bitToSet % 8));
249             final int ofs = bitToSet >> 3;
250
251             // And access the right bit and byte
252 fByteArray[ofs] &= ~mask;
253             fByteArray[ofs] |= mask;
254         }
255     }
256
257     final void setTo(CMStateSet srcSet) throws CMException
258     {
259         // They have to be the same size
260 if (fBitCount != srcSet.fBitCount)
261             throw new CMException(ImplementationMessages.VAL_CMSI);
262         
263         if (fBitCount < 65)
264         {
265             fBits1 = srcSet.fBits1;
266             fBits2 = srcSet.fBits2;
267         }
268          else
269         {
270             for (int index = fByteCount - 1; index >= 0; index--)
271                 fByteArray[index] = srcSet.fByteArray[index];
272         }
273     }
274
275     final void zeroBits()
276     {
277         if (fBitCount < 65)
278         {
279             fBits1 = 0;
280             fBits2 = 0;
281         }
282          else
283         {
284             for (int index = fByteCount - 1; index >= 0; index--)
285                 fByteArray[index] = 0;
286         }
287     }
288
289
290     // -------------------------------------------------------------------
291 // Private data members
292 //
293 // fBitCount
294 // The count of bits that the outside world wants to support,
295 // so its the max bit index plus one.
296 //
297 // fByteCount
298 // If the bit count is > 64, then we use the fByteArray member to
299 // store the bits, and this indicates its size in bytes. Otherwise
300 // its value is meaningless.
301 //
302 // fBits1
303 // fBits2
304 // When the bit count is < 64 (very common), these hold the bits.
305 // Otherwise, the fByteArray member holds htem.
306 // -------------------------------------------------------------------
307 int fBitCount;
308     int fByteCount;
309     int fBits1;
310     int fBits2;
311     byte[] fByteArray;
312     /* Optimization(Jan, 2001) */
313     public boolean equals(Object JavaDoc o) {
314     if (!(o instanceof CMStateSet)) return false;
315     return isSameSet((CMStateSet)o);
316     }
317
318     public int hashCode() {
319         if (fBitCount < 65)
320         {
321             return fBits1+ fBits2 * 31;
322         }
323          else
324         {
325             int hash = 0;
326             for (int index = fByteCount - 1; index >= 0; index--)
327                 hash = fByteArray[index] + hash * 31;
328             return hash;
329         }
330     }
331    /* Optimization(Jan, 2001) */
332 };
333
Popular Tags