KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > iapi > services > io > FormatableBitSet


1 /*
2
3    Derby - Class org.apache.derby.iapi.services.io.FormatableBitSet
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */

21
22 package org.apache.derby.iapi.services.io;
23
24 import org.apache.derby.iapi.services.sanity.SanityManager;
25
26 import java.io.InputStream JavaDoc;
27 import java.io.ObjectOutput JavaDoc;
28 import java.io.ObjectInput JavaDoc;
29 import java.io.IOException JavaDoc;
30
31 /**
32  * FormatableBitSet is implemented as a packed array of bytes.
33  *
34  * @author Jamie -- originally coded by Jeff
35  */

36
37 public final class FormatableBitSet implements Formatable, Cloneable JavaDoc
38 {
39
40     /********************************************************
41     **
42     ** This class implements Formatable. That means that it
43     ** can write itself to and from a formatted stream. If
44     ** you add more fields to this class, make sure that you
45     ** also write/read them with the writeExternal()/readExternal()
46     ** methods.
47     **
48     ** If, inbetween releases, you add more fields to this class,
49     ** then you should bump the version number emitted by the getTypeFormatId()
50     ** method.
51     **
52     ********************************************************/

53
54     /**
55     ** Bits are stored as an array of bytes.
56     ** Bits are numbered starting at 0. Bits
57     ** 0..7 go in byte[0], 8..15 in byte[1] and so on.
58     ** The number of bytes is tracked as part
59     ** of the byte array. The number of bits
60     ** being used is derived by the number of
61     ** bytes being used and the number of bits
62     ** being used by the last byte. The partially
63     ** unused byte is always byte[byte.length] with the
64     ** lowest bits being unused.
65     **
66     ** Zero length bits are stored using a
67     ** zero length byte array, with all bits
68     ** marked as unused.
69     */

70     private byte[] value;
71     private short bitsInLastByte;
72
73     private transient int lengthAsBits;
74
75     /**
76      * Niladic Constructor
77      */

78     public FormatableBitSet()
79     {
80     }
81
82     /**
83      * Constructs a Bit with the initial number of bits
84      */

85     public FormatableBitSet(int numBits)
86     {
87         initializeBits(numBits);
88     }
89
90     private void initializeBits(int numBits)
91     {
92         int numBytes = numBytesFromBits(numBits);
93
94         // the byte array is zero'ed out by the new operator
95
value = new byte[numBytes];
96         bitsInLastByte = numBitsInLastByte(numBits);
97         lengthAsBits = numBits;
98     }
99
100     /**
101      * Constructs a Bit from an array of bytes. Assume
102      * bytes are all being used.
103      *
104      * @param newValue The array of bytes to make up the new Bit
105      */

106     public FormatableBitSet(byte[] newValue)
107     {
108         value = newValue;
109         bitsInLastByte = 8;
110         lengthAsBits = calculateLength(newValue.length);
111     }
112
113     /**
114      * Constructs a Bit from an array of bytes.
115      *
116      * @param newValue The array of bytes to make up the new Bit
117      * @param numBits The number of bits
118      */

119     public FormatableBitSet(byte[] newValue, int numBits)
120     {
121         bitsInLastByte = numBitsInLastByte(numBits);
122         lengthAsBits = numBits;
123
124         int lenInBytes = numBytesFromBits(numBits);
125
126         if (lenInBytes == newValue.length) {
127             value = newValue;
128         } else {
129             value = new byte[lenInBytes];
130             System.arraycopy(newValue, 0, value, 0, newValue.length);
131         }
132     }
133
134     /**
135      * Copy constructor
136      *
137      * @param original the FormatableBitSet to make a copy from
138      */

139     public FormatableBitSet (FormatableBitSet original)
140     {
141         if (SanityManager.DEBUG)
142             SanityManager.ASSERT(
143                 original != null, "cannot make copy from a null FormatableBitSet");
144
145         bitsInLastByte = original.bitsInLastByte;
146         lengthAsBits = original.lengthAsBits;
147
148         int lenInBytes = FormatableBitSet.numBytesFromBits(original.lengthAsBits);
149         value = new byte[lenInBytes];
150         if (lenInBytes > 0)
151             System.arraycopy(original.value, 0, value, 0, lenInBytes);
152     }
153             
154     /*
155      * Cloneable
156      */

157     public Object JavaDoc clone()
158     {
159         return new FormatableBitSet(this);
160     }
161
162
163     /**
164      * Get the length in bytes of a Bit value
165      *
166      * @return The length in bytes of this value
167      */

168     public int getLengthInBytes()
169     {
170         if (value == null)
171         {
172             return 0;
173         }
174
175         return FormatableBitSet.numBytesFromBits(lengthAsBits);
176     }
177
178     /**
179     ** Get the length in bits
180     **
181     ** @return The length in bits for this value
182     **
183     ** NOTE: could possibly be changed to a long. As is
184     ** we are restricted to 2^(31-3) -> 256meg instead
185     ** of 2^31 (Integer.MAX_VALUE) like other datatypes
186     ** (or 2 gig). If it is ever changed to a long
187     ** be sure to change read/writeExternal which write
188     ** out the length in bits.
189     */

190     public int getLength() {
191         return lengthAsBits;
192     }
193
194     private int calculateLength(int realByteLength)
195     {
196         if (realByteLength == 0)
197         {
198             return 0;
199         }
200
201         return ((realByteLength - 1) * 8) + bitsInLastByte;
202     }
203
204     /**
205      * Get the length in bits -- alias for getLength()
206      *
207      * @return The length in bits for this value
208      */

209     public int size()
210     {
211         return getLength();
212     }
213
214     /**
215      * Get the value of the byte array
216      *
217      * @return The value of the byte array
218      */

219
220     public byte[] getByteArray()
221     {
222         if (value == null)
223             return null;
224
225         // In some cases the array is bigger than the actual number
226
// of valid bytes.
227
int realByteLength = getLengthInBytes();
228
229         // Currently the case is that the return from this
230
// call only includes the valid bytes.
231
if (value.length != realByteLength) {
232             byte[] data = new byte[realByteLength];
233             System.arraycopy(value, 0, data, 0, realByteLength);
234
235             value = data;
236         }
237
238         return value;
239     }
240
241     /**
242      * Set the value of the byte array
243      *
244      * @return The value of the byte array
245      */

246     public boolean isNull()
247     {
248         return this.value == null;
249     }
250
251     /**
252      * Grow (widen) a FormatableBitSet to N bis
253      *
254      * @param n The number of bits you want. The bits are
255      * always added as 0 and are appended to the
256      * least significant end of the bit array.
257      *
258      * ASSUMPTIONS: that all extra bits in the last byte
259      * are zero.
260      */

261     public void grow(int n)
262     {
263         if (n <= this.getLength())
264             return;
265
266         if (value == null)
267         {
268             initializeBits(n);
269             return;
270         }
271
272         int delta = n - this.getLength();
273
274
275         int oldNumBytes = getLengthInBytes();
276
277         /*
278         ** If we have enough space in the left over bits,
279         ** then all we need to do is change the modulo.
280         */

281         if ((oldNumBytes != 0) &&
282             (8 - this.bitsInLastByte) >= delta)
283         {
284             this.bitsInLastByte += delta;
285             lengthAsBits = n;
286             return;
287         }
288
289         int newNumBytes = FormatableBitSet.numBytesFromBits(n);
290
291         // is there enough room in the existing array
292
if (newNumBytes <= value.length) {
293             // ensure the bits are zeroed
294
for (int i = oldNumBytes; i < newNumBytes; i++)
295                 value[i] = 0;
296         } else {
297
298
299             /*
300             ** We didn't have enough bytes in value, so we need
301             ** to create a bigger byte array and use that.
302             */

303             byte[] newValue = new byte[newNumBytes];
304
305             System.arraycopy(value, 0, newValue, 0, oldNumBytes);
306
307             value = newValue;
308         }
309         bitsInLastByte = numBitsInLastByte(n);
310         lengthAsBits = n;
311     }
312
313     /**
314      * Shrink (narrow) a FormatableBitSet to N bits
315      *
316      * @param n The number of bits the caller wants. The
317      * bits are always removed from the
318      * least significant end of the bit array.
319      */

320     public FormatableBitSet shrink(int n)
321     {
322         int numBytes;
323         int lastByteNum;
324
325         /*
326         ** Sanity check: we shouldn't shrink down to
327         ** nothing.
328         */

329         if (SanityManager.DEBUG)
330         {
331             if (value == null)
332             {
333                 SanityManager.THROWASSERT("Attempt to shrink a null Bit"+
334                         " -- caller should have known better probably");
335                 return null;
336             }
337         }
338
339         if (n >= this.getLength())
340         {
341             return this;
342         }
343
344
345         lastByteNum = numBytesFromBits(n) - 1;
346         bitsInLastByte = numBitsInLastByte(n);
347         lengthAsBits = n;
348
349         /*
350         ** Mask out any left over bits in the
351         ** last byte. Retain the highest bits.
352         */

353         if (bitsInLastByte != 8)
354         {
355             value[lastByteNum] &= 0xFF00 >> bitsInLastByte;
356         }
357
358         return this;
359     }
360
361     /*
362     ** Some of the operators required by SQL. These could alternatively
363     ** be in SQLBit, but since they are so tightly bound to the implementation
364     ** rather than return something that undermines the encapsulation
365     ** of this type, i have chosen to put them in here.
366     */

367
368     /**
369      * Bit equivalence. Compare this with other.
370      * If the length is different, then cannot be
371      * equal so short circuit. Otherwise, rely on
372      * compare(). Note that two zero length bits are
373      * considered equal.
374      *
375      * @param other the other bit to compare to
376      *
377      * @return TRUE|FALSE
378      */

379     public boolean equals(FormatableBitSet other)
380     {
381         if (this.getLength() != other.getLength())
382         {
383             return false;
384         }
385
386         return (this.compare(other) == 0);
387     }
388
389     /**
390      * Bit comparison. Compare this with other.
391      * Will always do a byte by byte compare.
392      *
393      * Given 2 similar bits of unequal lengths (x and y),
394      * where x.getLength() < y.getLength() but where:
395      *
396      * x[0..x.getLength()] == y[0..x.getLength()]
397      *
398      * then x < y.
399      *
400      *
401      * @param other the other bit to compare to
402      *
403      * @return -1 - if other < this
404      * 0 - if other == this
405      * 1 - if other > this
406      *
407      */

408     public int compare(FormatableBitSet other)
409     {
410
411         int otherCount, thisCount;
412         int otherLen, thisLen;
413         byte[] otherb;
414
415         otherb = other.value;
416         /*
417         ** By convention, nulls sort low, and null == null
418         */

419         if (this.value == null || otherb == null)
420         {
421             if (this.value != null) // otherb == null
422
return 1;
423             if (otherb != null) // this.value == null
424
return -1;
425             return 0; // both null
426
}
427
428         otherLen = other.getLengthInBytes();
429         thisLen = getLengthInBytes();
430         for (otherCount = 0, thisCount = 0;
431                 otherCount < otherLen && thisCount < thisLen;
432                 otherCount++, thisCount++)
433         {
434             if (otherb[otherCount] != this.value[thisCount])
435                 break;
436         }
437
438         /*
439         ** '==' if byte by byte comparison is identical and
440         ** exact same length in bits (not bytes).
441         */

442         if ((otherCount == otherLen) && (thisCount == thisLen))
443         {
444                 if (this.getLength() == other.getLength())
445                 {
446                     return 0;
447                 }
448
449                 /*
450                 ** If subset of bits is identical, return 1
451                 ** if other.getLength() > this.getLength(); otherwise,
452                 ** -1
453                 */

454                 return (other.getLength() < this.getLength()) ? 1 : -1;
455         }
456
457         if (otherCount == otherLen)
458         {
459             return 1;
460         }
461         else if (thisCount == thisLen)
462         {
463             return -1;
464         }
465         else
466         {
467             /*
468             ** Ok, we have a difference somewhere. Now
469             ** we have to go to the trouble of converting
470             ** to a int and masking out the sign to get
471             ** a valid comparision because bytes are signed.
472             */

473             int otherInt, thisInt;
474
475             otherInt = (int)otherb[otherCount];
476             otherInt &= (0x100 - 1);
477
478             thisInt = (int)this.value[thisCount];
479             thisInt &= (0x100 - 1);
480
481             return (thisInt > otherInt) ? 1 : -1;
482
483         }
484     }
485
486     /**
487      * Bit concatenation.
488      *
489      * @param other the other bit to append to this
490      *
491      * @return Bit -- the newly concatenated bit
492      *
493      */

494     public FormatableBitSet concatenate(FormatableBitSet other)
495     {
496         int newLen;
497         int otherLen;
498         int prevLen;
499         int prevLenBytes;
500         int newLenBytes;
501         int otherLenBytes;
502         int i, j;
503         byte[] newValue;
504         byte[] otherValue;
505         int shiftBits;
506         int inByte;
507
508
509         prevLen = this.getLength();
510         prevLenBytes = this.getLengthInBytes();
511         otherLen = other.getLength();
512         otherValue = other.getByteArray();
513         otherLenBytes = other.getLengthInBytes();
514         newLen = prevLen + otherLen;
515         newLenBytes = numBytesFromBits(newLen);
516         newValue = new byte[newLenBytes];
517
518
519         /*
520         ** Copy over the entire array in this.value
521         ** to newLenBytes.
522         */

523         for (i = 0; i < prevLenBytes; i++)
524         {
525             newValue[i] = this.value[i];
526         }
527
528         /*
529         ** Now if we have any bits left over
530         ** we need to shift them, and keep
531         ** shifting everything down. Be careful
532         ** to handle the case where the bit
533         ** used to have length 0.
534         */

535         shiftBits = (prevLen == 0) ? 8 : this.bitsInLastByte;
536         for (j = 0; j < otherLenBytes; j++, i++)
537         {
538             if (shiftBits == 8)
539             {
540                 newValue[i] = otherValue[j];
541             }
542             else
543             {
544                 /*
545                 ** Convert to an int because it will get converted
546                 ** on the shift anyway.
547                 */

548                 inByte = (int)otherValue[j];
549
550                 /*
551                 ** Mask off the high bits in case they are now
552                 ** turned on if we had the sign bit on.
553                 */

554                 inByte &= (0x100 - 1);
555
556                 /*
557                 ** Use the high order bits to finish off
558                 ** the last byte
559                 */

560                 newValue[i-1] |= (inByte >>> shiftBits);
561
562                 /*
563                 ** Start the next one with whatever is left, unless
564                 ** there is nothing left.
565                 */

566                 if (i < newLenBytes)
567                 {
568                     newValue[i] |= (inByte << (8 - shiftBits));
569                 }
570             }
571         }
572
573         return new FormatableBitSet(newValue, newLen);
574     }
575
576     /**
577      * Produce a hash code by putting the value bytes into an int, exclusive OR'ing
578      * if there are more than 4 bytes.
579      *
580      * @return the hash code
581      */

582     public int hashCode()
583     {
584         if( null == value)
585             return 0;
586         
587         int code = 0;
588         int i;
589         int shift = 0;
590
591         int byteLength = getLengthInBytes();
592         for( i = 0; i < byteLength; i++)
593         {
594             code ^= (value[i] & 0xff)<<shift;
595             shift += 8;
596             if( 32 <= shift)
597                 shift = 0;
598         }
599         return code;
600     }
601     
602     /**
603      * Bit isSet
604      *
605      * @param position the bit to check
606      *
607      */

608     public final boolean isSet(int position)
609     {
610         if (SanityManager.DEBUG)
611         {
612             if (position >= this.getLength())
613             {
614                 SanityManager.THROWASSERT(
615                    "Attempt to get a bit position (" + position +
616                    ")" +
617                    "that exceeds the max length (" + this.getLength() + ")");
618             }
619         }
620
621         try {
622
623             int bytepos = position / 8;
624             int bitpos = 7 - (position % 8);
625
626             return ((value[bytepos] & (1 << bitpos)) != 0);
627
628         } catch (ArrayIndexOutOfBoundsException JavaDoc e) {
629             // Should not happen, handle it just in case not all cases are tested
630
// by insane server.
631
return false;
632         }
633     }
634
635     /**
636      * Bit get -- alias for isSet()
637      *
638      * @param position the bit to check
639      *
640      */

641     public final boolean get(int position)
642     {
643         return isSet(position);
644     }
645     
646     /**
647      * Bit set
648      *
649      * @param position the bit to set
650      *
651      */

652     public void set(int position)
653     {
654
655         if (SanityManager.DEBUG)
656         {
657             if (position >= this.getLength())
658             {
659                 SanityManager.THROWASSERT(
660                    "Attempt to set a bit position that exceeds the max length ("
661                    + this.getLength() + ")");
662             }
663         }
664
665         // Should not happen, handle it just in case not all cases are tested
666
// by insane server.
667
if (position >= getLength())
668             grow(position);
669
670         int bytepos = position / 8;
671         int bitpos = 7 - (position % 8);
672
673         value[bytepos] |= (1 << bitpos);
674     }
675
676     /**
677      * Bit clear
678      *
679      * @param position the bit to clear
680      *
681      */

682     public void clear(int position)
683     {
684         int bytepos;
685         int bitpos;
686
687         if (SanityManager.DEBUG)
688         {
689             if (position >= this.getLength())
690             {
691                 SanityManager.THROWASSERT(
692                    "Attempt to set a bit position that exceeds the max length ("
693                    + this.getLength() + ")");
694             }
695         }
696
697         // Should not happen, handle it just in case not all cases are tested
698
// by insane server.
699
if (position >= getLength())
700             grow(position);
701
702         bytepos = position / 8;
703         bitpos = 7 - (position % 8);
704
705         value[bytepos] &= ~(1 << bitpos);
706     }
707
708     /**
709       Clear all the bits in this FormatableBitSet
710       */

711     public void clear()
712     {
713         if (value == null)
714             return;
715
716         int byteLength = getLengthInBytes();
717         for (int ix=0; ix < byteLength; ix++)
718             value[ix] = 0;
719     }
720
721
722     /**
723     * Figure out how many bytes are needed to
724     * store the input number of bits.
725     *
726     * @param bits bits
727     *
728     * @return the number of bytes
729     */

730     protected static int
731     numBytesFromBits(int bits)
732     {
733         return (bits == 0) ? 0 : ((bits - 1) / 8) + 1;
734     }
735
736     /**
737     * Figure out how many bits are in the last
738     * byte from the total number of bits.
739     *
740     * @param bits bits
741     *
742     * @return the number of bits
743     */

744     private static short
745     numBitsInLastByte(int bits)
746     {
747         int modulo = bits % 8;
748         return (short)((modulo == 0) ?
749                 ((bits == 0) ? 0 : 8) :
750                 modulo);
751     }
752
753     /**
754      * Translate a hex character to a byte.
755      *
756      * @param hexChar A character with the value [0-9a-fA-F].
757      *
758      * @return A byte with the numeric value corresponding to the hex character
759      */

760     private static byte
761     hexCharToByte(char hexChar)
762     {
763         byte byteValue;
764
765         switch (hexChar)
766         {
767           case '0':
768             byteValue = 0;
769             break;
770
771           case '1':
772             byteValue = 1;
773             break;
774
775           case '2':
776             byteValue = 2;
777             break;
778
779           case '3':
780             byteValue = 3;
781             break;
782
783           case '4':
784             byteValue = 4;
785             break;
786
787           case '5':
788             byteValue = 5;
789             break;
790
791           case '6':
792             byteValue = 6;
793             break;
794
795           case '7':
796             byteValue = 7;
797             break;
798
799           case '8':
800             byteValue = 8;
801             break;
802
803           case '9':
804             byteValue = 9;
805             break;
806
807           case 'a':
808           case 'A':
809             byteValue = 0xA;
810             break;
811
812           case 'b':
813           case 'B':
814             byteValue = 0xB;
815             break;
816
817           case 'c':
818           case 'C':
819             byteValue = 0xC;
820             break;
821
822           case 'd':
823           case 'D':
824             byteValue = 0xD;
825             break;
826
827           case 'e':
828           case 'E':
829             byteValue = 0xE;
830             break;
831
832           case 'f':
833           case 'F':
834             byteValue = 0xF;
835             break;
836
837           default:
838               if (SanityManager.DEBUG)
839               {
840                   SanityManager.THROWASSERT("illegal char = " + hexChar);
841               }
842             throw new IllegalArgumentException JavaDoc();
843         }
844
845         return byteValue;
846     }
847
848 private static char[] decodeArray = {'0', '1', '2', '3', '4', '5', '6', '7',
849                                 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
850
851     /**
852      * Format the string into BitSet format: {0, 2, 4, 8} if bits 0, 2, 4, 8
853      * are set.
854      *
855      * @return A new String containing the formatted Bit value
856      */

857     public String JavaDoc toString()
858     {
859         char[] outChars;
860         int inPosition;
861         int outPosition;
862         int inByte;
863
864         if (value == null)
865         {
866             return null;
867         }
868         {
869             // give it a reasonable size
870
StringBuffer JavaDoc str = new StringBuffer JavaDoc(getLength()*8*3);
871             str.append("{");
872             boolean first = true;
873             for (inPosition = 0; inPosition < getLength(); inPosition++)
874             {
875                 if (isSet(inPosition))
876                 {
877                     if (!first)
878                         str.append(", ");
879                     first = false;
880                     str.append(inPosition);
881                 }
882             }
883             str.append("}");
884             return new String JavaDoc(str);
885         }
886     }
887
888
889
890     /**
891      * Statically calculates how many bits can fit into the number of
892      * bytes if this Bit object is externalized. Only valid for this
893      * implementation of Bit.
894      */

895     public static int maxBitsForSpace(int numBytes)
896     {
897         return (numBytes - 4)*8;
898         
899     }
900
901     /**
902      * If any bit is set, return the bit number of a bit that is set.
903      * If no bit is set, return -1;
904      *
905      * @return the bit number of a bit that is set, or -1 if no bit is set
906      */

907     public int anySetBit()
908     {
909         int numbytes = getLengthInBytes();
910         int bitpos;
911
912         for (int i = 0; i < numbytes-1; i++)
913         {
914             if (value[i] != 0)
915             {
916                 for (int j = 0; j < 8; j++)
917                 {
918                     bitpos = 7-j;
919                     if (((1 << bitpos) & value[i]) != 0)
920                         return ((i*8)+j);
921                 }
922             }
923         }
924
925
926         // only the top part of the last byte is relevant
927
byte mask = (byte)(0xFF << (8-bitsInLastByte));
928         if ((value[numbytes-1] & mask) != 0)
929         {
930             for (int j = 0; j < bitsInLastByte; j++)
931             {
932                 bitpos = 7-j;
933                 if (((1 << bitpos) & value[numbytes-1]) != 0)
934                     return ((numbytes-1)*8)+j;
935             }
936         }
937
938         return -1;
939     }
940
941     /**
942      * Like anySetBit(), but return any set bit whose number is bigger than
943      * beyondBit. If no bit is set after beyondBit, -1 is returned.
944      * By using anySetBit() and anySetBit(beyondBit), one can quickly go
945      * thru the entire bit array to return all set bit.
946      *
947      * @param beyondBit only look at bit that is greater than this bit number
948      * @return the bit number of a bit that is set, or -1 if no bit after
949      * beyondBit is set
950      */

951     public int anySetBit(int beyondBit)
952     {
953         if (SanityManager.DEBUG)
954         {
955             if (beyondBit >= this.getLength())
956                 SanityManager.THROWASSERT(
957                    "Attempt to access bit position that exceeds the max length ("
958                     + this.getLength() + ")");
959         }
960
961         int startingBit = (beyondBit+1);
962
963         // we have seen the last bit.
964
if (startingBit >= this.getLength())
965             return -1;
966
967         int numbytes = getLengthInBytes();
968         int startingByte = startingBit / 8;
969         int startingBitpos = startingBit % 8;
970         int bitpos;
971         byte mask;
972
973         // see if any bits in this byte is set, only the bottom part of the
974
// first byte is relevant
975
mask = (byte)(0xFF >> startingBitpos);
976
977         if (startingByte == numbytes-1) // starting byte == last byte
978
mask &= (byte)(0xFF << (8-bitsInLastByte));
979
980         if ((value[startingByte] & mask ) != 0)
981         {
982             // I know we will see the bit before bitsInLastByte even if we are
983
// at the last byte, no harm in going up to 8 in the loop
984
for (int j = startingBitpos; j < 8; j++)
985             {
986                 if (SanityManager.DEBUG)
987                 {
988                     if (startingByte == numbytes-1)
989                         SanityManager.ASSERT(j < bitsInLastByte,
990                                  "going beyond the last bit");
991                 }
992                 bitpos = 7-j;
993                 if (((1 << bitpos) & value[startingByte]) != 0)
994                 {
995                     return (startingByte*8+j);
996                 }
997             }
998         }
999
1000        for (int i = (startingByte+1); i < numbytes-1; i++)
1001        {
1002            if (value[i] != 0)
1003            {
1004                for (int j = 0; j < 8; j++)
1005                {
1006                    bitpos = 7-j;
1007                    if (((1 << bitpos) & value[i]) != 0)
1008                    {
1009                        return ((i*8)+j);
1010                    }
1011                }
1012            }
1013        }
1014        
1015        // Last byte if there are more than one bytes. Only the top part of
1016
// the last byte is relevant
1017
if (startingByte != numbytes-1)
1018        {
1019            mask = (byte)(0xFF << (8-bitsInLastByte));
1020
1021            if ((value[numbytes-1] & mask) != 0)
1022            {
1023                for (int j = 0; j < bitsInLastByte; j++)
1024                {
1025                    bitpos = 7-j;
1026                    if (((1 << bitpos) & value[numbytes-1]) != 0)
1027                    {
1028                        return ((numbytes-1)*8)+j;
1029                    }
1030                }
1031            }
1032        }
1033
1034        return -1;
1035
1036    }
1037
1038    /**
1039     * Bitwise OR this Bit with another Bit.
1040     *
1041     * @param otherBit the other Bit
1042     */

1043    public void or(FormatableBitSet otherBit)
1044    {
1045        if (otherBit == null || otherBit.getLength() == 0)
1046            return;
1047
1048        int otherLength = otherBit.getLength();
1049
1050        if (otherLength > getLength())
1051            grow(otherLength); // expand this bit
1052

1053        if (otherBit instanceof FormatableBitSet)
1054        {
1055            // we know the bit ordering, optimize this
1056
FormatableBitSet ob = (FormatableBitSet)otherBit;
1057            int obByteLen = ob.getLengthInBytes();
1058            for (int i = 0; i < obByteLen-1; i++)
1059                value[i] |= ob.value[i];
1060
1061            // do the last byte bit by bit
1062
for (int i = (obByteLen-1)*8; i < otherLength; i++)
1063                if (otherBit.isSet(i))
1064                    set(i);
1065        }
1066        else
1067        {
1068            // we don't know the bit ordering, call thru the interface and go
1069
// thru bit by bit
1070
// this bit impl's length >= other bit's length
1071

1072            for (int i = 0; i < otherLength; i++)
1073            {
1074                if (otherBit.isSet(i))
1075                    set(i);
1076            }
1077        }
1078    }
1079
1080    /**
1081     * Bitwise AND this Bit with another Bit.
1082     *
1083     * @param otherBit the other Bit
1084     */

1085    public void and(FormatableBitSet otherBit)
1086    {
1087        if (SanityManager.DEBUG)
1088            SanityManager.ASSERT(otherBit != null, "cannot AND null with a FormatableBitSet");
1089
1090        int otherLength = otherBit.getLength();
1091
1092        // Supposedly cannot happen, but handle it just in case.
1093
if (otherLength > getLength())
1094            grow(otherLength); // expand this bit
1095

1096        if (otherLength < getLength())
1097        {
1098            // clear all bits that are not in the other bit
1099
int startingByte = (otherLength * 8) + 1;
1100            int len = getLengthInBytes();
1101            for (int i = startingByte; i < len; i++)
1102                value[i] = 0;
1103
1104            for (int i = otherLength; i < startingByte*8; i++)
1105            {
1106                if (i < getLength())
1107                    clear(i);
1108                else
1109                    break;
1110            }
1111        }
1112
1113        if (otherLength == 0)
1114            return;
1115            
1116        int length = otherBit.getLengthInBytes() < getLengthInBytes() ?
1117            otherBit.getLengthInBytes() : getLengthInBytes();
1118
1119        for (int i = 0; i < length; i++)
1120            value[i] &= otherBit.value[i];
1121    }
1122
1123    /**
1124     * Logically XORs this FormatableBitSet with the specified FormatableBitSet.
1125     * @param set The FormatableBitSet to be XORed with.
1126     */

1127    public void xor(FormatableBitSet set)
1128    {
1129        if (SanityManager.DEBUG)
1130        {
1131            if (getLength() != set.getLength())
1132            {
1133                SanityManager.THROWASSERT("getLength() (" + getLength() +
1134                    ") and set.getLength() (" +
1135                    set.getLength() +
1136                    ") expected to be the same");
1137            }
1138        }
1139
1140        int setLength = set.getLength();
1141        for (int i = setLength; i-- > 0; )
1142        {
1143            if (isSet(i) && set.isSet(i))
1144            {
1145                clear(i);
1146            }
1147            else if (isSet(i) || set.isSet(i))
1148            {
1149                set(i);
1150            }
1151        }
1152    }
1153
1154    /**
1155     * Get a count of the number of bits that are set.
1156     *
1157     * @return The number of bits that are set.
1158     */

1159    public int getNumBitsSet()
1160    {
1161        int count = 0;
1162
1163        for (int index = getLength() - 1; index >= 0; index--)
1164        {
1165            if (isSet(index))
1166            {
1167                count++;
1168            }
1169        }
1170
1171        return count;
1172    }
1173
1174    /////////////////////////////////////////////////////////
1175
//
1176
// EXTERNALIZABLE
1177
//
1178
/////////////////////////////////////////////////////////
1179
/**
1180     * Format: <UL>
1181     * <LI>int length in bits </LI>
1182     * <LI>byte[] </LI></UL>
1183     *
1184     * @see java.io.Externalizable#writeExternal
1185    */

1186    public void writeExternal(ObjectOutput JavaDoc out) throws IOException JavaDoc
1187    {
1188        // never called when value is null
1189
if (SanityManager.DEBUG)
1190            SanityManager.ASSERT(value != null);
1191
1192        out.writeInt(getLength());
1193        int byteLen = getLengthInBytes();
1194        if (byteLen > 0)
1195        {
1196            out.write(value, 0, byteLen);
1197        }
1198    }
1199
1200    /**
1201     * Note: gracefully handles zero length
1202     * bits -- will create a zero length array
1203     * with no bits being used. Fortunately
1204     * in.read() is ok with a zero length array
1205     * so no special code.
1206     * <p>
1207     * WARNING: this method cannot be changed w/o
1208     * changing SQLBit because SQLBit calls this
1209     * directly w/o calling read/writeObject(), so
1210     * the format id is not stored in that case.
1211     *
1212     * @see java.io.Externalizable#readExternal
1213     */

1214    public void readExternal(ObjectInput JavaDoc in) throws IOException JavaDoc
1215    {
1216        int lenInBits;
1217        int lenInBytes;
1218
1219        lenInBits = in.readInt();
1220
1221        lenInBytes = FormatableBitSet.numBytesFromBits(lenInBits);
1222
1223
1224        /*
1225        ** How can lenInBytes be zero? The implication is
1226        ** that lenInBits is zero. Well, the reason this can
1227        ** happen is that the store will reset our stream
1228        ** out from underneath us if we are a Bit column that
1229        ** overflows onto another page because it assumes that
1230        ** we want to stream it in specially. Because of this warped
1231        ** API, our readInt() will return 0 even though our
1232        ** writeExternal() did a writeInt(xxx). The upshot
1233        ** is that you should leave the following alone.
1234        */

1235
1236            value = new byte[lenInBytes];
1237
1238            in.readFully(value);
1239
1240            bitsInLastByte = numBitsInLastByte(lenInBits);
1241
1242            lengthAsBits = lenInBits;
1243    }
1244
1245    public void readExternalFromArray(ArrayInputStream in) throws IOException JavaDoc
1246    {
1247        int lenInBits = in.readInt();
1248
1249        int lenInBytes = FormatableBitSet.numBytesFromBits(lenInBits);
1250
1251        value = new byte[lenInBytes];
1252
1253        in.readFully(value);
1254
1255        bitsInLastByte = numBitsInLastByte(lenInBits);
1256
1257        lengthAsBits = lenInBits;
1258    }
1259
1260    /**
1261     * Get the formatID which corresponds to this class.
1262     *
1263     * @return the formatID of this class
1264     */

1265    public int getTypeFormatId() { return StoredFormatIds.BITIMPL_V01_ID; }
1266}
1267
Popular Tags