1// [The "BSD licence"]
2// Copyright (c) 2006-2007 Kay Roepke 2010 Alan Condit
3// All rights reserved.
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions
7// are met:
8// 1. Redistributions of source code must retain the above copyright
9//    notice, this list of conditions and the following disclaimer.
10// 2. Redistributions in binary form must reproduce the above copyright
11//    notice, this list of conditions and the following disclaimer in the
12//    documentation and/or other materials provided with the distribution.
13// 3. The name of the author may not be used to endorse or promote products
14//    derived from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27#import "ANTLRBitSet.h"
28
29@implementation ANTLRBitSet
30#pragma mark Class Methods
31
32+ (ANTLRBitSet *) newANTLRBitSet
33{
34    return [[ANTLRBitSet alloc] init];
35}
36
37+ (ANTLRBitSet *) newANTLRBitSetWithType:(ANTLRTokenType)type
38{
39    return [[ANTLRBitSet alloc] initWithType:type];
40}
41
42/** Construct a ANTLRBitSet given the size
43 * @param nbits The size of the ANTLRBitSet in bits
44 */
45+ (ANTLRBitSet *) newANTLRBitSetWithNBits:(NSUInteger)nbits
46{
47    return [[ANTLRBitSet alloc] initWithNBits:nbits];
48}
49
50+ (ANTLRBitSet *) newANTLRBitSetWithArray:(AMutableArray *)types
51{
52    return [[ANTLRBitSet alloc] initWithArrayOfBits:types];
53}
54
55+ (ANTLRBitSet *) newANTLRBitSetWithBits:(const unsigned long long *)theBits Count:(NSUInteger)longCount
56{
57    return [[ANTLRBitSet alloc] initWithBits:theBits Count:longCount];
58}
59
60
61+ (ANTLRBitSet *) of:(NSUInteger) el
62{
63    ANTLRBitSet *s = [ANTLRBitSet newANTLRBitSetWithNBits:(el + 1)];
64    [s add:el];
65    return s;
66}
67
68+ (ANTLRBitSet *) of:(NSUInteger) a And2:(NSUInteger) b
69{
70    NSInteger c = (((a>b)?a:b)+1);
71    ANTLRBitSet *s = [ANTLRBitSet newANTLRBitSetWithNBits:c];
72    [s add:a];
73    [s add:b];
74    return s;
75}
76
77+ (ANTLRBitSet *) of:(NSUInteger)a And2:(NSUInteger)b And3:(NSUInteger)c
78{
79    NSUInteger d = ((a>b)?a:b);
80    d = ((c>d)?c:d)+1;
81    ANTLRBitSet *s = [ANTLRBitSet newANTLRBitSetWithNBits:d];
82    [s add:a];
83    [s add:b];
84    [s add:c];
85    return s;
86}
87
88+ (ANTLRBitSet *) of:(NSUInteger)a And2:(NSUInteger)b And3:(NSUInteger)c And4:(NSUInteger)d
89{
90    NSUInteger e = ((a>b)?a:b);
91    NSUInteger f = ((c>d)?c:d);
92    e = ((e>f)?e:f)+1;
93    ANTLRBitSet *s = [ANTLRBitSet newANTLRBitSetWithNBits:e];
94    [s add:a];
95    [s add:b];
96    [s add:c];
97    [s add:d];
98    return s;
99}
100
101// initializer
102#pragma mark Initializer
103
104- (ANTLRBitSet *) init
105{
106	if ((self = [super init]) != nil) {
107		bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0);
108	}
109	return self;
110}
111
112- (ANTLRBitSet *) initWithType:(ANTLRTokenType)type
113{
114	if ((self = [super init]) != nil) {
115		bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0);
116        if ((CFIndex)type >= CFBitVectorGetCount(bitVector))
117            CFBitVectorSetCount(bitVector, type+1);
118        CFBitVectorSetBitAtIndex(bitVector, type, 1);
119	}
120	return self;
121}
122
123- (ANTLRBitSet *) initWithNBits:(NSUInteger)nbits
124{
125	if ((self = [super init]) != nil) {
126        bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0);
127        CFBitVectorSetCount( bitVector, nbits );
128	}
129	return self;
130}
131
132- (ANTLRBitSet *) initWithBitVector:(CFMutableBitVectorRef)theBitVector
133{
134	if ((self = [super init]) != nil) {
135		bitVector = theBitVector;
136	}
137	return self;
138}
139
140// Initialize the bit vector with a constant array of ulonglongs like ANTLR generates.
141// Converts to big endian, because the underlying CFBitVector works like that.
142- (ANTLRBitSet *) initWithBits:(const unsigned long long *)theBits Count:(NSUInteger)longCount
143{
144	if ((self = [super init]) != nil) {
145		unsigned int longNo;
146		CFIndex bitIdx;
147        bitVector = CFBitVectorCreateMutable ( kCFAllocatorDefault, 0 );
148		CFBitVectorSetCount( bitVector, sizeof(unsigned long long)*8*longCount );
149
150		for (longNo = 0; longNo < longCount; longNo++) {
151			for (bitIdx = 0; bitIdx < (CFIndex)sizeof(unsigned long long)*8; bitIdx++) {
152				unsigned long long swappedBits = CFSwapInt64HostToBig(theBits[longNo]);
153				if (swappedBits & (1LL << bitIdx)) {
154					CFBitVectorSetBitAtIndex(bitVector, bitIdx+(longNo*(sizeof(unsigned long long)*8)), 1);
155				}
156			}
157		}
158	}
159	return self;
160}
161
162// Initialize bit vector with an array of anything. Just test the boolValue and set the corresponding bit.
163// Note: This is big-endian!
164- (ANTLRBitSet *) initWithArrayOfBits:(NSArray *)theArray
165{
166	if ((self = [super init]) != nil) {
167        bitVector = CFBitVectorCreateMutable ( kCFAllocatorDefault, 0 );
168		id value;
169		int bit = 0;
170		for (value in theArray) {
171			if ([value boolValue] == YES) {
172                [self add:bit];
173				//CFBitVectorSetBitAtIndex(bitVector, bit, 1);
174			}
175			bit++;
176		}
177	}
178	return self;
179}
180
181- (void)dealloc
182{
183#ifdef DEBUG_DEALLOC
184    NSLog( @"called dealloc in ANTLRBitSet" );
185#endif
186	CFRelease(bitVector);
187	[super dealloc];
188}
189
190	// operations
191#pragma mark Operations
192// return a copy of (self|aBitSet)
193- (ANTLRBitSet *) or:(ANTLRBitSet *) aBitSet
194{
195	ANTLRBitSet *bitsetCopy = [self mutableCopyWithZone:nil];
196	[bitsetCopy orInPlace:aBitSet];
197	return bitsetCopy;
198}
199
200// perform a bitwise OR operation in place by changing underlying bit vector, growing it if necessary
201- (void) orInPlace:(ANTLRBitSet *) aBitSet
202{
203	CFIndex selfCnt = CFBitVectorGetCount(bitVector);
204	CFMutableBitVectorRef otherBitVector = [aBitSet _bitVector];
205	CFIndex otherCnt = CFBitVectorGetCount(otherBitVector);
206	CFIndex maxBitCnt = selfCnt > otherCnt ? selfCnt : otherCnt;
207	CFBitVectorSetCount(bitVector,maxBitCnt);		// be sure to grow the CFBitVector manually!
208	
209	CFIndex currIdx;
210	for (currIdx = 0; currIdx < maxBitCnt; currIdx++) {
211		if (CFBitVectorGetBitAtIndex(bitVector, currIdx) | CFBitVectorGetBitAtIndex(otherBitVector, currIdx)) {
212			CFBitVectorSetBitAtIndex(bitVector, currIdx, 1);
213		}
214	}
215}
216
217// set a bit, grow the bit vector if necessary
218- (void) add:(NSUInteger) bit
219{
220	if ((CFIndex)bit >= CFBitVectorGetCount(bitVector))
221		CFBitVectorSetCount(bitVector, bit+1);
222	CFBitVectorSetBitAtIndex(bitVector, bit, 1);
223}
224
225// unset a bit
226- (void) remove:(NSUInteger) bit
227{
228	CFBitVectorSetBitAtIndex(bitVector, bit, 0);
229}
230
231- (void) setAllBits:(BOOL) aState
232{
233    for( NSInteger bit=0; bit < CFBitVectorGetCount(bitVector); bit++ ) {
234        CFBitVectorSetBitAtIndex(bitVector, bit, aState);
235    }
236}
237
238// returns the number of bits in the bit vector.
239- (NSInteger) numBits
240{
241    // return CFBitVectorGetCount(bitVector);
242    return CFBitVectorGetCountOfBit(bitVector, CFRangeMake(0, CFBitVectorGetCount(bitVector)), 1);
243}
244
245// returns the number of bits in the bit vector.
246- (NSUInteger) size
247{
248    return CFBitVectorGetCount(bitVector);
249}
250
251- (void) setSize:(NSUInteger) nBits
252{
253    CFBitVectorSetCount( bitVector, nBits );
254}
255
256#pragma mark Informational
257// return a bitmask representation of this bitvector for easy operations
258- (unsigned long long) bitMask:(NSUInteger) bitNumber
259{
260	return 1LL << bitNumber;
261}
262
263// test a bit (no pun intended)
264- (BOOL) member:(NSUInteger) bitNumber
265{
266	return CFBitVectorGetBitAtIndex(bitVector,bitNumber) ? YES : NO;
267}
268
269// are all bits off?
270- (BOOL) isNil
271{
272	return ((CFBitVectorGetCountOfBit(bitVector, CFRangeMake(0,CFBitVectorGetCount(bitVector)), 1) == 0) ? YES : NO);
273}
274
275// return a string representation of the bit vector, indicating by their bitnumber which bits are set
276- (NSString *) toString
277{
278	CFIndex length = CFBitVectorGetCount(bitVector);
279	CFIndex currBit;
280	NSMutableString *descString = [NSMutableString  stringWithString:@"{"];
281	BOOL haveInsertedBit = NO;
282	for (currBit = 0; currBit < length; currBit++) {
283		if ( CFBitVectorGetBitAtIndex(bitVector, currBit) ) {
284			if (haveInsertedBit) {
285				[descString appendString:@","];
286			}
287			[descString appendFormat:@"%d", currBit];
288			haveInsertedBit = YES;
289		}
290	}
291	[descString appendString:@"}"];
292	return descString;
293}
294
295// debugging aid. GDB invokes this automagically
296- (NSString *) description
297{
298	return [self toString];
299}
300
301	// NSCopying
302#pragma mark NSCopying support
303
304- (id) mutableCopyWithZone:(NSZone *) theZone
305{
306	ANTLRBitSet *newBitSet = [[ANTLRBitSet allocWithZone:theZone] initWithBitVector:CFBitVectorCreateMutableCopy(kCFAllocatorDefault,0,bitVector)];
307	return newBitSet;
308}
309
310- (CFMutableBitVectorRef) _bitVector
311{
312	return bitVector;
313}
314
315@synthesize bitVector;
316@end
317
318NSInteger max(NSInteger a, NSInteger b)
319{
320    return (a>b)?a:b;
321}
322
323