err.no Git - sope/blob - sope-core/NGExtensions/NGBitSet.m

   1 /*
   2   Copyright (C) 2000-2003 SKYRIX Software AG
   3
   4   This file is part of OGo
   5
   6   OGo is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU Lesser General Public License as published by the
   8   Free Software Foundation; either version 2, or (at your option) any
   9   later version.
  10
  11   OGo is distributed in the hope that it will be useful, but WITHOUT ANY
  12   WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14   License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with OGo; see the file COPYING.  If not, write to the
  18   Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19   02111-1307, USA.
  20 */
  21 // $Id$
  22
  23 #import "common.h"
  24 #import "NGMemoryAllocation.h"
  25 #import "NGBitSet.h"
  26
  27 #define NGStorageSize   sizeof(NGBitSetStorage)
  28 #define NGBitsPerEntry  (NGStorageSize * 8)
  29 #define NGByteSize      (universe / 8)
  30
  31 #define NGTestBit(_x)   (((storage[ _x / NGBitsPerEntry ] & \
  32                          (1 << (_x % NGBitsPerEntry))) == 0) ? NO : YES)
  33
  34 @interface NGConcreteBitSetEnumerator : NSEnumerator
  35 {
  36 @public
  37   unsigned int    universe;
  38   unsigned int    count;
  39   NGBitSetStorage *storage;
  40
  41   unsigned int position;
  42   unsigned int found;
  43 }
  44
  45 - (id)nextObject;
  46
  47 @end
  48
  49 @implementation NGBitSet
  50
  51 + (id)bitSet {
  52   return [[[self alloc] init] autorelease];
  53 }
  54 + (id)bitSetWithCapacity:(unsigned)_capacity {
  55   return [[[self alloc] initWithCapacity:_capacity] autorelease];
  56 }
  57 + (id)bitSetWithBitSet:(NGBitSet *)_set {
  58   return [[[self alloc] initWithBitSet:_set] autorelease];
  59 }
  60
  61 - (id)initWithCapacity:(unsigned)_capacity {
  62   if ((self = [super init])) {
  63     self->universe = (_capacity / NGBitsPerEntry + 1) * NGBitsPerEntry;
  64     storage  = NGMallocAtomic(NGByteSize);
  65     memset(storage, 0, NGByteSize);
  66     count = 0;
  67   }
  68   return self;
  69 }
  70
  71 - (id)initWithBitSet:(NGBitSet *)_set {
  72   if ((self = [self initWithCapacity:NGBitsPerEntry])) {
  73     NSEnumerator *enumerator = [_set objectEnumerator];
  74     id obj = nil;
  75
  76     while ((obj = [enumerator nextObject]))
  77       [self addMember:[obj unsignedIntValue]];
  78
  79     enumerator = nil;
  80   }
  81   return self;
  82 }
  83 - (id)init {
  84   return [self initWithCapacity:NGBitsPerEntry];
  85 }
  86 - (id)initWithNullTerminatedArray:(unsigned int *)_array {
  87   if ((self = [self initWithCapacity:NGBitsPerEntry])) {
  88     while (*_array) {
  89       [self addMember:*_array];
  90       _array++;
  91     }
  92   }
  93   return self;
  94 }
  95
  96 - (void)dealloc {
  97   if (self->storage) {
  98     NGFree(self->storage);
  99     self->storage = NULL;
 100   }
 101   [super dealloc];
 102 }
 103
 104 /* storage */
 105
 106 - (void)_expandToInclude:(unsigned int)_element {
 107   unsigned int nu = (_element / NGBitsPerEntry + 1) * NGBitsPerEntry;
 108   if (nu > self->universe) {
 109     void *old = storage;
 110     storage = (NGBitSetStorage *)NGMallocAtomic(nu / 8);
 111     memset(storage, 0, nu / 8);
 112     if (old) {
 113       memcpy(storage, old, NGByteSize);
 114       NGFree(old);
 115       old = NULL;
 116     }
 117     self->universe = nu;
 118   }
 119 }
 120
 121 /* accessors */
 122
 123 - (unsigned int)capacity {
 124   return self->universe;
 125 }
 126 - (unsigned int)count {
 127   return count;
 128 }
 129
 130 /* membership */
 131
 132 - (BOOL)isMember:(unsigned int)_element {
 133   return (_element >= self->universe) ? NO : NGTestBit(_element);
 134 }
 135
 136 - (void)addMember:(unsigned int)_element {
 137   register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
 138
 139   if (_element >= self->universe)
 140     [self _expandToInclude:_element];
 141
 142   if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) == 0) {
 143     storage[ _element / NGBitsPerEntry ] |= subIdxPattern;
 144     count++;
 145   }
 146 }
 147 - (void)addMembersInRange:(NSRange)_range {
 148   register unsigned int from = _range.location;
 149   register unsigned int to   = from + _range.length - 1;
 150
 151   if (to >= self->universe)
 152     [self _expandToInclude:to];
 153
 154   for (; from <= to; from++) {
 155     register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
 156
 157     if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) == 0) {
 158       storage[ from / NGBitsPerEntry ] |= subIdxPattern;
 159       count++;
 160     }
 161   }
 162 }
 163
 164 - (void)addMembersFromBitSet:(NGBitSet *)_set {
 165   unsigned i;
 166
 167   if ([_set capacity] > self->universe)
 168     [self _expandToInclude:[_set capacity]];
 169
 170   for (i = 0; i < [_set capacity]; i++) {
 171     if ([_set isMember:i]) {
 172       register unsigned int subIdxPattern = 1 << (i % NGBitsPerEntry);
 173
 174       if ((storage[ i / NGBitsPerEntry ] & subIdxPattern) == 0) {
 175         storage[ i / NGBitsPerEntry ] |= subIdxPattern;
 176         count++;
 177       }
 178     }
 179   }
 180 }
 181
 182 - (void)removeMember:(unsigned int)_element {
 183   register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
 184
 185   if (_element >= self->universe)
 186     return;
 187
 188   if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) != 0) {
 189     storage[ _element / NGBitsPerEntry ] -= subIdxPattern;
 190     count--;
 191   }
 192 }
 193 - (void)removeMembersInRange:(NSRange)_range {
 194   register unsigned int from = _range.location;
 195   register unsigned int to   = from + _range.length - 1;
 196
 197   if (from >= self->universe)
 198     return;
 199   if (to >= self->universe) to = self->universe - 1;
 200
 201   for (; from <= to; from++) {
 202     register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
 203
 204     if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) != 0) {
 205       storage[ from / NGBitsPerEntry ] -= subIdxPattern;
 206       count--;
 207     }
 208   }
 209 }
 210 - (void)removeAllMembers {
 211   memset(storage, 0, NGByteSize);
 212   count = 0;
 213 }
 214
 215 - (unsigned int)firstMember {
 216   register unsigned int element;
 217
 218   for (element = 0; element < self->universe; element++) {
 219     if (NGTestBit(element))
 220       return element;
 221   }
 222   return NSNotFound;
 223 }
 224
 225 - (unsigned int)lastMember {
 226   register unsigned int element;
 227
 228   for (element = (self->universe - 1); element >= 0; element--) {
 229     if (NGTestBit(element))
 230       return element;
 231   }
 232   return NSNotFound;
 233 }
 234
 235 /* equality */
 236
 237 - (BOOL)isEqual:(id)_object {
 238   if (self == _object) return YES;
 239   if ([self class] != [_object class]) return NO;
 240   return [self isEqualToSet:_object];
 241 }
 242 - (BOOL)isEqualToSet:(NGBitSet *)_set {
 243   if (self == _set) return YES;
 244   if (count != [_set count]) return NO;
 245
 246   {
 247     register unsigned int element;
 248
 249     for (element = 0; element < self->universe; element++) {
 250       if (NGTestBit(element)) {
 251         if (![_set isMember:element])
 252           return NO;
 253       }
 254     }
 255     return YES;
 256   }
 257 }
 258
 259 /* enumerator */
 260
 261 - (NSEnumerator *)objectEnumerator {
 262   if (self->count == 0)
 263     return nil;
 264   else {
 265     NGConcreteBitSetEnumerator *en = [[NGConcreteBitSetEnumerator alloc] init];
 266     en->universe = self->universe;
 267     en->count    = self->count;
 268     en->storage  = self->storage;
 269     return [en autorelease];
 270   }
 271 }
 272
 273 /* NSCopying */
 274
 275 - (id)copy {
 276   return [self copyWithZone:[self zone]];
 277 }
 278 - (id)copyWithZone:(NSZone *)_zone {
 279   return [[NGBitSet alloc] initWithBitSet:self];
 280 }
 281
 282
 283 /* NSCoding */
 284
 285 - (void)encodeWithCoder:(NSCoder *)_coder {
 286   unsigned int element;
 287   register unsigned int found;
 288
 289   [_coder encodeValueOfObjCType:@encode(unsigned int) at:&count];
 290
 291   for (element = 0, found = 0; (element < self->universe) && (found < count); element++) {
 292     if (NGTestBit(element)) {
 293       [_coder encodeValueOfObjCType:@encode(unsigned int) at:&element];
 294       found++;
 295     }
 296   }
 297 }
 298 - (id)initWithCoder:(NSCoder *)_coder {
 299   if ((self = [super init])) {
 300     unsigned int nc;
 301     register unsigned int cnt;
 302
 303     self->universe = NGBitsPerEntry;
 304     storage  = NGMallocAtomic(NGByteSize);
 305     memset(storage, 0, NGByteSize);
 306
 307     [_coder decodeValueOfObjCType:@encode(unsigned int) at:&nc];
 308
 309     for (cnt = 0; cnt < nc; cnt++) {
 310       unsigned int member;
 311       [_coder decodeValueOfObjCType:@encode(unsigned int) at:&member];
 312       [self addMember:member];
 313     }
 314   }
 315   return self;
 316 }
 317
 318 /* description */
 319
 320 - (NSString *)description {
 321   return [NSString stringWithFormat:
 322                      @"<NGBitSet[0x%08X]: capacity=%u count=%u content=%@>",
 323                      (unsigned)self, self->universe, self->count,
 324                      [[self toArray] description]];
 325 }
 326
 327 - (NSArray *)toArray {
 328   NSMutableArray *result = [[NSMutableArray alloc] initWithCapacity:count + 1];
 329   register unsigned int element, found;
 330
 331   for (element = 0, found = 0;
 332        (element < self->universe) && (found < self->count); element++) {
 333
 334     if (NGTestBit(element)) {
 335       [result addObject:[NSNumber numberWithUnsignedInt:element]];
 336       found++;
 337     }
 338   }
 339   return [[[result autorelease] copy] autorelease];
 340 }
 341
 342 @end /* NGBitSet */
 343
 344 @implementation NGConcreteBitSetEnumerator
 345
 346 - (id)nextObject {
 347   if (self->found == self->count)
 348     return nil;
 349   if (self->position >= self->universe)
 350     return nil;
 351
 352   while (!NGTestBit(self->position))
 353     self->position++;
 354
 355   self->found++;
 356   self->position++;
 357
 358   return [NSNumber numberWithUnsignedInt:(self->position - 1)];
 359 }
 360
 361 @end /* NGConcreteBitSetEnumerator */
 362
 363 NSString *stringValueForBitset(unsigned int _set, char _setC, char _unsetC,
 364                                short _wide) {
 365   char           buf[_wide + 1];
 366   register short pos;
 367
 368   for (pos = 0; pos < _wide; pos++) {
 369     register unsigned int v = (1 << pos);
 370     buf[(int)pos] = ((v & _set) == v) ? _setC : _unsetC;
 371   }
 372
 373   buf[_wide] = '\0';
 374   return [NSString stringWithCString:buf];
 375 }
 376
 377 void __link_NGExtensions_NGBitSet() {
 378   __link_NGExtensions_NGBitSet();
 379 }