Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -71,13 +71,16 @@ macros.h \ objfw-defs.h \ ${THREADING_H} SRCS += OFArray_adjacent.m \ + OFCountedSet_hashtable.m \ OFDictionary_hashtable.m \ OFMutableArray_adjacent.m \ OFMutableDictionary_hashtable.m \ + OFMutableSet_hashtable.m \ + OFSet_hashtable.m \ ${ASPRINTF_M} \ ${FOUNDATION_COMPAT_M} \ iso_8859_15.m \ windows_1252.m \ ${OBJC_PROPERTIES_M} \ Index: src/OFCountedSet.h ================================================================== --- src/OFCountedSet.h +++ src/OFCountedSet.h @@ -40,5 +40,8 @@ */ - (void)enumerateObjectsAndCountUsingBlock: (of_counted_set_enumeration_block_t)block; #endif @end + +@interface OFCountedSet_placeholder: OFCountedSet +@end Index: src/OFCountedSet.m ================================================================== --- src/OFCountedSet.m +++ src/OFCountedSet.m @@ -14,100 +14,134 @@ * file. */ #include "config.h" -#define OF_COUNTED_SET_M - #import "OFCountedSet.h" -#import "OFMutableDictionary_hashtable.h" +#import "OFCountedSet_hashtable.h" #import "OFNumber.h" -#import "OFArray.h" #import "OFString.h" #import "OFAutoreleasePool.h" -@implementation OFCountedSet +#import "OFNotImplementedException.h" + +static struct { + Class isa; +} placeholder; + +@implementation OFCountedSet_placeholder +- init +{ + return (id)[[OFCountedSet_hashtable alloc] init]; +} + - initWithSet: (OFSet*)set { - self = [super init]; - - @try { - [dictionary release]; - dictionary = nil; - dictionary = [[OFMutableDictionary_hashtable alloc] - _initWithDictionary: set->dictionary - copyKeys: NO]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + return (id)[[OFCountedSet_hashtable alloc] initWithSet: set]; } - initWithArray: (OFArray*)array { - self = [super init]; - - @try { - id *cArray = [array cArray]; - size_t i, count = [array count]; - - for (i = 0; i < count; i++) - [self addObject: cArray[i]]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + return (id)[[OFCountedSet_hashtable alloc] initWithArray: array]; +} + +- initWithObjects: (id)firstObject, ... +{ + id ret; + va_list arguments; + + va_start(arguments, firstObject); + ret = [[OFCountedSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; + va_end(arguments); + + return ret; } - initWithObject: (id)firstObject arguments: (va_list)arguments { - self = [super init]; - - @try { - id object; - - [self addObject: firstObject]; - - while ((object = va_arg(arguments, id)) != nil) - [self addObject: object]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + return [[OFCountedSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; +} + +- retain +{ + return self; +} + +- autorelease +{ + return self; +} + +- (void)release +{ +} + +- (void)dealloc +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; + [super dealloc]; /* Get rid of a stupid warning */ +} +@end + +@implementation OFCountedSet ++ (void)initialize +{ + if (self == [OFCountedSet class]) + placeholder.isa = [OFCountedSet_placeholder class]; +} + ++ alloc +{ + if (self == [OFCountedSet class]) + return (id)&placeholder; + + return [super alloc]; +} + +- init +{ + if (isa == [OFCountedSet class]) { + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; + } + + return [super init]; +} + +- (size_t)countForObject: (id)object +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (OFString*)description { OFMutableString *ret; OFAutoreleasePool *pool, *pool2; - OFEnumerator *keyEnumerator, *objectEnumerator; - size_t i, count = [dictionary count]; - id key, object; + OFEnumerator *enumerator; + size_t i, count = [self count]; + id object; if (count == 0) return @"{()}"; ret = [OFMutableString stringWithString: @"{(\n"]; pool = [[OFAutoreleasePool alloc] init]; - keyEnumerator = [dictionary keyEnumerator]; - objectEnumerator = [dictionary objectEnumerator]; + enumerator = [self objectEnumerator]; i = 0; pool2 = [[OFAutoreleasePool alloc] init]; - while ((key = [keyEnumerator nextObject]) != nil && - (object = [objectEnumerator nextObject]) != nil) { - [ret appendString: [key description]]; - [ret appendString: @": "]; - [ret appendString: [object description]]; + while ((object = [enumerator nextObject]) != nil) { + [ret appendString: object]; + [ret appendFormat: @": %zu", [self countForObject: object]]; if (++i < count) [ret appendString: @",\n"]; [pool2 releaseObjects]; @@ -131,121 +165,67 @@ - mutableCopy { return [[OFCountedSet alloc] initWithSet: self]; } -- (size_t)countForObject: (id)object -{ - return [[dictionary objectForKey: object] sizeValue]; -} - #ifdef OF_HAVE_BLOCKS - (void)enumerateObjectsAndCountUsingBlock: (of_counted_set_enumeration_block_t)block { - [dictionary enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, - BOOL *stop) { - block(key, [object sizeValue], stop); + [self enumerateObjectsUsingBlock: ^ (id object, BOOL *stop) { + block(object, [self countForObject: object], stop); }]; } #endif -- (void)addObject: (id)object +- (void)minusSet: (OFSet*)set { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFNumber *count; - - count = [[dictionary objectForKey: object] numberByIncreasing]; - - if (count == nil) - count = [OFNumber numberWithSize: 1]; - - [dictionary _setObject: count - forKey: object - copyKey: NO]; - - mutations++; - - [pool release]; -} - -- (void)removeObject: (id)object -{ - OFNumber *count = [dictionary objectForKey: object]; - OFAutoreleasePool *pool; - - if (count == nil) - return; - - pool = [[OFAutoreleasePool alloc] init]; - count = [count numberByDecreasing]; - - if ([count sizeValue] > 0) - [dictionary _setObject: count - forKey: object - copyKey: NO]; - else - [dictionary removeObjectForKey: object]; - - mutations++; - - [pool release]; -} - -- (void)minusSet: (OFSet*)set -{ - OFCountedSet *countedSet; - OFAutoreleasePool *pool; - OFEnumerator *enumerator; - id object; - - if (![set isKindOfClass: [OFCountedSet class]]) { - [super minusSet: set]; - return; - } - - countedSet = (OFCountedSet*)set; - - pool = [[OFAutoreleasePool alloc] init]; - enumerator = [countedSet objectEnumerator]; - - while ((object = [enumerator nextObject]) != nil) { - size_t i, count = [countedSet countForObject: object]; - - for (i = 0; i < count; i++) + + if ([set isKindOfClass: [OFCountedSet class]]) { + OFCountedSet *countedSet = (OFCountedSet*)set; + OFEnumerator *enumerator = [countedSet objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) { + size_t i, count = [countedSet countForObject: object]; + + for (i = 0; i < count; i++) + [self removeObject: object]; + } + } else { + OFEnumerator *enumerator = [set objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) [self removeObject: object]; } [pool release]; } - (void)unionSet: (OFSet*)set { - OFCountedSet *countedSet; - OFAutoreleasePool *pool; - OFEnumerator *enumerator; - id object; - - if (![set isKindOfClass: [OFCountedSet class]]) { - [super unionSet: set]; - return; - } - - countedSet = (OFCountedSet*)set; - - pool = [[OFAutoreleasePool alloc] init]; - enumerator = [countedSet objectEnumerator]; - - while ((object = [enumerator nextObject]) != nil) { - size_t i, count = [countedSet countForObject: object]; - - for (i = 0; i < count; i++) + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + + if ([set isKindOfClass: [OFCountedSet class]]) { + OFCountedSet *countedSet = (OFCountedSet*)set; + OFEnumerator *enumerator = [countedSet objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) { + size_t i, count = [countedSet countForObject: object]; + + for (i = 0; i < count; i++) + [self addObject: object]; + } + } else { + OFEnumerator *enumerator = [set objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) [self addObject: object]; } [pool release]; -} - -- (void)makeImmutable -{ } @end ADDED src/OFCountedSet_hashtable.h Index: src/OFCountedSet_hashtable.h ================================================================== --- src/OFCountedSet_hashtable.h +++ src/OFCountedSet_hashtable.h @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#import "OFCountedSet.h" + +@class OFDictionary_hashtable; + +@interface OFCountedSet_hashtable: OFCountedSet +{ + OFDictionary_hashtable *dictionary; + unsigned long mutations; +} +@end ADDED src/OFCountedSet_hashtable.m Index: src/OFCountedSet_hashtable.m ================================================================== --- src/OFCountedSet_hashtable.m +++ src/OFCountedSet_hashtable.m @@ -0,0 +1,172 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#include "config.h" + +#define OF_COUNTED_SET_HASHTABLE_M + +#import "OFMutableSet_hashtable.h" +#import "OFCountedSet_hashtable.h" +#import "OFMutableDictionary_hashtable.h" +#import "OFNumber.h" +#import "OFArray.h" +#import "OFAutoreleasePool.h" + +@implementation OFCountedSet_hashtable ++ (void)initialize +{ + if (self == [OFCountedSet_hashtable class]) + [self inheritMethodsFromClass: [OFMutableSet_hashtable class]]; +} + +- initWithSet: (OFSet*)set +{ + self = [self init]; + + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + + if ([set isKindOfClass: [OFCountedSet class]]) { + OFCountedSet *countedSet = (OFCountedSet*)countedSet; + OFEnumerator *enumerator = + [countedSet objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) { + size_t i, count; + + count = [countedSet countForObject: object]; + + for (i = 0; i < count; i++) + [self addObject: object]; + } + } else { + OFEnumerator *enumerator = [set objectEnumerator]; + id object; + + while ((object = [enumerator nextObject]) != nil) + [self addObject: object]; + } + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithArray: (OFArray*)array +{ + self = [self init]; + + @try { + id *cArray = [array cArray]; + size_t i, count = [array count]; + + for (i = 0; i < count; i++) + [self addObject: cArray[i]]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithObject: (id)firstObject + arguments: (va_list)arguments +{ + self = [self init]; + + @try { + id object; + + [self addObject: firstObject]; + + while ((object = va_arg(arguments, id)) != nil) + [self addObject: object]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- (size_t)countForObject: (id)object +{ + return [[dictionary objectForKey: object] sizeValue]; +} + +#ifdef OF_HAVE_BLOCKS +- (void)enumerateObjectsAndCountUsingBlock: + (of_counted_set_enumeration_block_t)block +{ + [dictionary enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, + BOOL *stop) { + block(key, [object sizeValue], stop); + }]; +} +#endif + +- (void)addObject: (id)object +{ + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFNumber *count; + + count = [[dictionary objectForKey: object] numberByIncreasing]; + + if (count == nil) + count = [OFNumber numberWithSize: 1]; + + [dictionary _setObject: count + forKey: object + copyKey: NO]; + + mutations++; + + [pool release]; +} + +- (void)removeObject: (id)object +{ + OFNumber *count = [dictionary objectForKey: object]; + OFAutoreleasePool *pool; + + if (count == nil) + return; + + pool = [[OFAutoreleasePool alloc] init]; + count = [count numberByDecreasing]; + + if ([count sizeValue] > 0) + [dictionary _setObject: count + forKey: object + copyKey: NO]; + else + [dictionary removeObjectForKey: object]; + + mutations++; + + [pool release]; +} + +- (void)makeImmutable +{ +} +@end Index: src/OFDictionary.m ================================================================== --- src/OFDictionary.m +++ src/OFDictionary.m @@ -25,12 +25,10 @@ #import "OFXMLElement.h" #import "OFAutoreleasePool.h" #import "OFNotImplementedException.h" -#import "macros.h" - static struct { Class isa; } placeholder; @implementation OFDictionary_placeholder Index: src/OFDictionary_hashtable.h ================================================================== --- src/OFDictionary_hashtable.h +++ src/OFDictionary_hashtable.h @@ -27,11 +27,11 @@ struct of_dictionary_hashtable_bucket **data; uint32_t size; size_t count; } -#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) +#if defined(OF_SET_HASHTABLE_M) || defined(OF_COUNTED_SET_HASHTABLE_M) - _initWithDictionary: (OFDictionary*)dictionary copyKeys: (BOOL)copyKeys; #endif @end Index: src/OFMutableDictionary.m ================================================================== --- src/OFMutableDictionary.m +++ src/OFMutableDictionary.m @@ -19,12 +19,10 @@ #import "OFMutableDictionary_hashtable.h" #import "OFAutoreleasePool.h" #import "OFNotImplementedException.h" -#import "macros.h" - static struct { Class isa; } placeholder; @implementation OFMutableDictionary_placeholder Index: src/OFMutableDictionary_hashtable.h ================================================================== --- src/OFMutableDictionary_hashtable.h +++ src/OFMutableDictionary_hashtable.h @@ -22,16 +22,17 @@ uint32_t size; size_t count; unsigned long mutations; } -#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) +#if defined(OF_SET_HASHTABLE_M) || defined(OF_COUNTED_SET_HASHTABLE_M) - _initWithDictionary: (OFDictionary*)dictionary copyKeys: (BOOL)copyKeys; #endif -#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M) +#if defined(OF_SET_HASHTABLE_M) || defined(OF_MUTABLE_SET_HASHTABLE_M) || \ + defined(OF_COUNTED_SET_HASHTABLE_M) - (void)_setObject: (id)object forKey: (id)key copyKey: (BOOL)copyKey; #endif @end Index: src/OFMutableSet.h ================================================================== --- src/OFMutableSet.h +++ src/OFMutableSet.h @@ -18,14 +18,10 @@ /** * \brief An mutable unordered set of unique objects. */ @interface OFMutableSet: OFSet -{ - unsigned long mutations; -} - /** * \brief Adds the specified object to the set. * * \param object The object to add to the set */ @@ -63,5 +59,8 @@ /** * \brief Converts the mutable set to an immutable set. */ - (void)makeImmutable; @end + +@interface OFMutableSet_placeholder: OFMutableSet +@end Index: src/OFMutableSet.m ================================================================== --- src/OFMutableSet.m +++ src/OFMutableSet.m @@ -14,33 +14,117 @@ * file. */ #include "config.h" -#define OF_MUTABLE_SET_M +#include #import "OFMutableSet.h" -#import "OFMutableDictionary_hashtable.h" -#import "OFArray.h" -#import "OFNumber.h" +#import "OFMutableSet_hashtable.h" #import "OFAutoreleasePool.h" + +#import "OFNotImplementedException.h" + +static struct { + Class isa; +} placeholder; + +@implementation OFMutableSet_placeholder +- init +{ + return (id)[[OFMutableSet_hashtable alloc] init]; +} + +- initWithSet: (OFSet*)set +{ + return (id)[[OFMutableSet_hashtable alloc] initWithSet: set]; +} + +- initWithArray: (OFArray*)array +{ + return (id)[[OFMutableSet_hashtable alloc] initWithArray: array]; +} + +- initWithObjects: (id)firstObject, ... +{ + id ret; + va_list arguments; + + va_start(arguments, firstObject); + ret = [[OFMutableSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; + va_end(arguments); + + return ret; +} + +- initWithObject: (id)firstObject + arguments: (va_list)arguments +{ + return [[OFMutableSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; +} + +- retain +{ + return self; +} + +- autorelease +{ + return self; +} + +- (void)release +{ +} + +- (void)dealloc +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; + [super dealloc]; /* Get rid of a stupid warning */ +} +@end @implementation OFMutableSet ++ (void)initialize +{ + if (self == [OFMutableSet class]) + placeholder.isa = [OFMutableSet_placeholder class]; +} + ++ alloc +{ + if (self == [OFMutableSet class]) + return (id)&placeholder; + + return [super alloc]; +} + +- init +{ + if (isa == [OFMutableSet class]) { + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; + } + + return [super init]; +} + - (void)addObject: (id)object { - [dictionary _setObject: [OFNumber numberWithSize: 1] - forKey: object - copyKey: NO]; - - mutations++; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (void)removeObject: (id)object { - [dictionary removeObjectForKey: object]; - - mutations++; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (void)minusSet: (OFSet*)set { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; @@ -54,18 +138,32 @@ } - (void)intersectSet: (OFSet*)set { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFArray *objects = [dictionary allKeys]; - id *cArray = [objects cArray]; - size_t count = [objects count]; - size_t i; - - for (i = 0; i < count; i++) - if (![set containsObject: cArray[i]]) - [dictionary removeObjectForKey: cArray[i]]; + size_t count = [self count]; + id *cArray; + + cArray = [self allocMemoryForNItems: count + withSize: sizeof(id)]; + + @try { + OFEnumerator *enumerator = [self objectEnumerator]; + id object; + size_t i = 0; + + while ((object = [enumerator nextObject]) != nil) { + assert(i < count); + cArray[i++] = object; + } + + for (i = 0; i < count; i++) + if (![set containsObject: cArray[i]]) + [self removeObject: cArray[i]]; + } @finally { + [self freeMemory: cArray]; + } [pool release]; } - (void)unionSet: (OFSet*)set @@ -80,8 +178,7 @@ [pool release]; } - (void)makeImmutable { - isa = [OFSet class]; } @end ADDED src/OFMutableSet_hashtable.h Index: src/OFMutableSet_hashtable.h ================================================================== --- src/OFMutableSet_hashtable.h +++ src/OFMutableSet_hashtable.h @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#import "OFMutableSet.h" + +@class OFDictionary_hashtable; + +@interface OFMutableSet_hashtable: OFMutableSet +{ + OFDictionary_hashtable *dictionary; + unsigned long mutations; +} +@end ADDED src/OFMutableSet_hashtable.m Index: src/OFMutableSet_hashtable.m ================================================================== --- src/OFMutableSet_hashtable.m +++ src/OFMutableSet_hashtable.m @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#include "config.h" + +#define OF_MUTABLE_SET_HASHTABLE_M + +#import "OFSet_hashtable.h" +#import "OFMutableSet_hashtable.h" +#import "OFMutableDictionary_hashtable.h" +#import "OFNumber.h" +#import "OFAutoreleasePool.h" + +@implementation OFMutableSet_hashtable ++ (void)initialize +{ + if (self == [OFMutableSet_hashtable class]) + [self inheritMethodsFromClass: [OFSet_hashtable class]]; +} + +- (void)addObject: (id)object +{ + [dictionary _setObject: [OFNumber numberWithSize: 1] + forKey: object + copyKey: NO]; + + mutations++; +} + +- (void)removeObject: (id)object +{ + [dictionary removeObjectForKey: object]; + + mutations++; +} + +- (void)makeImmutable +{ + isa = [OFSet_hashtable class]; +} +@end Index: src/OFSet.h ================================================================== --- src/OFSet.h +++ src/OFSet.h @@ -17,11 +17,10 @@ #include #import "OFObject.h" #import "OFCollection.h" -@class OFMutableDictionary_hashtable; @class OFArray; #ifdef OF_HAVE_BLOCKS typedef void (^of_set_enumeration_block_t)(id object, BOOL *stop); typedef BOOL (^of_set_filter_block_t)(id object); @@ -29,14 +28,10 @@ /** * \brief An unordered set of unique objects. */ @interface OFSet: OFObject -{ - OFMutableDictionary_hashtable *dictionary; -} - /** * \brief Returns a new, autoreleased set. * * \return A new, autoreleased set */ @@ -133,7 +128,10 @@ * \return A new, autoreleased OFSet */ - (OFSet*)filteredSetUsingBlock: (of_set_filter_block_t)block; #endif @end + +@interface OFSet_placeholder: OFSet +@end #import "OFMutableSet.h" Index: src/OFSet.m ================================================================== --- src/OFSet.m +++ src/OFSet.m @@ -14,20 +14,94 @@ * file. */ #include "config.h" -#define OF_SET_M - #import "OFSet.h" -#import "OFMutableDictionary_hashtable.h" -#import "OFArray.h" +#import "OFSet_hashtable.h" #import "OFString.h" -#import "OFNumber.h" #import "OFAutoreleasePool.h" + +#import "OFNotImplementedException.h" + +static struct { + Class isa; +} placeholder; + +@implementation OFSet_placeholder +- init +{ + return (id)[[OFSet_hashtable alloc] init]; +} + +- initWithSet: (OFSet*)set +{ + return (id)[[OFSet_hashtable alloc] initWithSet: set]; +} + +- initWithArray: (OFArray*)array +{ + return (id)[[OFSet_hashtable alloc] initWithArray: array]; +} + +- initWithObjects: (id)firstObject, ... +{ + id ret; + va_list arguments; + + va_start(arguments, firstObject); + ret = [[OFSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; + va_end(arguments); + + return ret; +} + +- initWithObject: (id)firstObject + arguments: (va_list)arguments +{ + return [[OFSet_hashtable alloc] initWithObject: firstObject + arguments: arguments]; +} + +- retain +{ + return self; +} + +- autorelease +{ + return self; +} + +- (void)release +{ +} + +- (void)dealloc +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; + [super dealloc]; /* Get rid of a stupid warning */ +} +@end @implementation OFSet ++ (void)initialize +{ + if (self == [OFSet class]) + placeholder.isa = [OFSet_placeholder class]; +} + ++ alloc +{ + if (self == [OFSet class]) + return (id)&placeholder; + + return [super alloc]; +} + + set { return [[[self alloc] init] autorelease]; } @@ -54,72 +128,34 @@ return ret; } - init { - self = [super init]; - - @try { - dictionary = [[OFMutableDictionary_hashtable alloc] init]; - } @catch (id e) { + if (isa == [OFSet class]) { + Class c = isa; [self release]; - @throw e; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - return self; + return [super init]; } - initWithSet: (OFSet*)set { - self = [self init]; - - @try { - OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFNumber *one = [OFNumber numberWithSize: 1]; - OFEnumerator *enumerator = [set objectEnumerator]; - id object; - - /* - * We can't just copy the dictionary as the specified set might - * be a counted set, but we're just a normal set. - */ - while ((object = [enumerator nextObject]) != nil) - [dictionary _setObject: one - forKey: object - copyKey: NO]; - - [pool release]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - initWithArray: (OFArray*)array { - self = [self init]; - - @try { - OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFNumber *one = [OFNumber numberWithSize: 1]; - id *cArray = [array cArray]; - size_t i, count = [array count]; - - for (i = 0; i < count; i++) - [dictionary _setObject: one - forKey: cArray[i] - copyKey: NO]; - - [pool release]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - (id)initWithObjects:(id)firstObject, ... { id ret; @@ -134,40 +170,40 @@ } - initWithObject: (id)firstObject arguments: (va_list)arguments { - self = [self init]; - - @try { - OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFNumber *one = [OFNumber numberWithSize: 1]; - id object; - - [dictionary _setObject: one - forKey: firstObject - copyKey: NO]; - - while ((object = va_arg(arguments, id)) != nil) - [dictionary _setObject: one - forKey: object - copyKey: NO]; - - [pool release]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; -} - -- (void)dealloc -{ - [dictionary release]; - - [super dealloc]; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; +} + +- (size_t)count +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; +} + +- (BOOL)containsObject: (id)object +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; +} + +- (OFEnumerator*)objectEnumerator +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; +} + +- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state + objects: (id*)objects + count: (int)count +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (BOOL)isEqual: (id)object { OFSet *otherSet; @@ -175,32 +211,45 @@ if (![object isKindOfClass: [OFSet class]]) return NO; otherSet = object; - return [otherSet->dictionary isEqual: dictionary]; + if ([otherSet count] != [self count]) + return NO; + + return [otherSet isSubsetOfSet: self]; } - (uint32_t)hash { - return [dictionary hash]; + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self objectEnumerator]; + id object; + uint32_t hash = 0; + + while ((object = [enumerator nextObject]) != nil) + hash += [object hash]; + + [pool release]; + + return hash; } - (OFString*)description { OFMutableString *ret; OFAutoreleasePool *pool, *pool2; OFEnumerator *enumerator; - size_t i, count = [dictionary count]; + size_t i, count = [self count]; id object; if (count == 0) return @"{()}"; ret = [OFMutableString stringWithString: @"{(\n"]; pool = [[OFAutoreleasePool alloc] init]; - enumerator = [dictionary keyEnumerator]; + enumerator = [self objectEnumerator]; i = 0; pool2 = [[OFAutoreleasePool alloc] init]; while ((object = [enumerator nextObject]) != nil) { @@ -222,32 +271,22 @@ return ret; } - copy { - return [[OFSet alloc] initWithSet: self]; + return [self retain]; } - mutableCopy { return [[OFMutableSet alloc] initWithSet: self]; } -- (size_t)count -{ - return [dictionary count]; -} - -- (BOOL)containsObject: (id)object -{ - return ([dictionary objectForKey: object] != nil); -} - - (BOOL)isSubsetOfSet: (OFSet*)set { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFEnumerator *enumerator = [dictionary keyEnumerator]; + OFEnumerator *enumerator = [self objectEnumerator]; id object; while ((object = [enumerator nextObject]) != nil) { if (![set containsObject: object]) { [pool release]; @@ -261,11 +300,11 @@ } - (BOOL)intersectsSet: (OFSet*)set { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFEnumerator *enumerator = [dictionary keyEnumerator]; + OFEnumerator *enumerator = [self objectEnumerator]; id object; while ((object = [enumerator nextObject]) != nil) { if ([set containsObject: object]) { [pool release]; @@ -276,44 +315,34 @@ [pool release]; return NO; } -- (OFEnumerator*)objectEnumerator -{ - return [dictionary keyEnumerator]; -} - -- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state - objects: (id*)objects - count: (int)count -{ - return [dictionary countByEnumeratingWithState: state - objects: objects - count: count]; -} - #ifdef OF_HAVE_BLOCKS - (void)enumerateObjectsUsingBlock: (of_set_enumeration_block_t)block { - [dictionary enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, - BOOL *stop) { - block(key, stop); - }]; + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self objectEnumerator]; + id object; + BOOL stop = NO; + + while (!stop && (object = [enumerator nextObject]) != nil) + block(object, &stop); + + [pool release]; } - (OFSet*)filteredSetUsingBlock: (of_set_filter_block_t)block { OFMutableSet *ret = [OFMutableSet set]; - [dictionary enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, - BOOL *stop) { - if (block(key)) - [ret addObject: key]; + [self enumerateObjectsUsingBlock: ^ (id object, BOOL *stop) { + if (block(object)) + [ret addObject: object]; }]; [ret makeImmutable]; return ret; } #endif @end ADDED src/OFSet_hashtable.h Index: src/OFSet_hashtable.h ================================================================== --- src/OFSet_hashtable.h +++ src/OFSet_hashtable.h @@ -0,0 +1,25 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#import "OFSet.h" + +@class OFMutableDictionary_hashtable; + +@interface OFSet_hashtable: OFSet +{ + OFMutableDictionary_hashtable *dictionary; +} +@end ADDED src/OFSet_hashtable.m Index: src/OFSet_hashtable.m ================================================================== --- src/OFSet_hashtable.m +++ src/OFSet_hashtable.m @@ -0,0 +1,177 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#include "config.h" + +#define OF_SET_HASHTABLE_M + +#import "OFSet_hashtable.h" +#import "OFMutableDictionary_hashtable.h" +#import "OFArray.h" +#import "OFString.h" +#import "OFNumber.h" +#import "OFAutoreleasePool.h" + +@implementation OFSet_hashtable +- init +{ + self = [super init]; + + @try { + dictionary = [[OFMutableDictionary_hashtable alloc] init]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithSet: (OFSet*)set +{ + self = [self init]; + + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFNumber *one = [OFNumber numberWithSize: 1]; + OFEnumerator *enumerator = [set objectEnumerator]; + id object; + + /* + * We can't just copy the dictionary as the specified set might + * be a counted set, but we're just a normal set. + */ + while ((object = [enumerator nextObject]) != nil) + [dictionary _setObject: one + forKey: object + copyKey: NO]; + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithArray: (OFArray*)array +{ + self = [self init]; + + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFNumber *one = [OFNumber numberWithSize: 1]; + id *cArray = [array cArray]; + size_t i, count = [array count]; + + for (i = 0; i < count; i++) + [dictionary _setObject: one + forKey: cArray[i] + copyKey: NO]; + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithObject: (id)firstObject + arguments: (va_list)arguments +{ + self = [self init]; + + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFNumber *one = [OFNumber numberWithSize: 1]; + id object; + + [dictionary _setObject: one + forKey: firstObject + copyKey: NO]; + + while ((object = va_arg(arguments, id)) != nil) + [dictionary _setObject: one + forKey: object + copyKey: NO]; + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- (void)dealloc +{ + [dictionary release]; + + [super dealloc]; +} + +- (size_t)count +{ + return [dictionary count]; +} + +- (BOOL)containsObject: (id)object +{ + return ([dictionary objectForKey: object] != nil); +} + +- (BOOL)isEqual: (id)object +{ + OFSet_hashtable *otherSet; + + if (![object isKindOfClass: [OFSet_hashtable class]] /*&& + ![object isKindOfClass: [OFMutableSet_hashtable class]] && + ![object isKindOfClass: [OFCountedSet_hashtable class]]*/) + return [super isEqual: object]; + + otherSet = object; + + return [otherSet->dictionary isEqual: dictionary]; +} + +- (OFEnumerator*)objectEnumerator +{ + return [dictionary keyEnumerator]; +} + +- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state + objects: (id*)objects + count: (int)count +{ + return [dictionary countByEnumeratingWithState: state + objects: objects + count: count]; +} + +#ifdef OF_HAVE_BLOCKS +- (void)enumerateObjectsUsingBlock: (of_set_enumeration_block_t)block +{ + [dictionary enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, + BOOL *stop) { + block(key, stop); + }]; +} +#endif +@end