58@protocol OOProbabilitySetEnumerable <NSObject>
60- (id) privObjectAtIndex:(NSUInteger)index;
65@interface OOProbabilitySet (OOPrivate)
87- (id) initWithObject:(
id)object weight:(
float)weight;
97 float *_cumulativeWeights;
106 NSMutableArray *_objects;
107 NSMutableArray *_weights;
111- (id) initPrivWithObjectArray:(NSMutableArray *)objects weightsArray:(NSMutableArray *)weights sum:(
float)sumOfWeights;
123- (id) initWithEnumerable:(
id<OOProbabilitySetEnumerable>)enumerable;
141+ (id) probabilitySetWithObjects:(
id *)objects weights:(
float *)weights count:(NSUInteger)count
143 return [[[
self alloc] initWithObjects:objects weights:weights count:count] autorelease];
147+ (id) probabilitySetWithPropertyListRepresentation:(NSDictionary *)plist
149 return [[[
self alloc] initWithPropertyListRepresentation:plist] autorelease];
160- (id) initWithObjects:(
id *)objects weights:(
float *)weights count:(NSUInteger)count
162 NSZone *zone = [
self zone];
169 if (objects == NULL || weights == NULL)
171 [NSException raise:NSInvalidArgumentException format:@"Attempt to create %@ with non-zero count but nil objects or weights.", @"OOProbabilitySet"];
182- (id) initWithPropertyListRepresentation:(NSDictionary *)plist
184 NSArray *objects =
nil;
185 NSArray *weights =
nil;
186 NSUInteger i = 0,
count = 0;
187 id *rawObjects = NULL;
188 float *rawWeights = NULL;
190 objects = [plist oo_arrayForKey:kObjectsKey];
191 weights = [plist oo_arrayForKey:kWeightsKey];
194 if (objects ==
nil || weights ==
nil)
199 count = [objects count];
207 rawObjects = malloc(
sizeof *rawObjects *
count);
208 rawWeights = malloc(
sizeof *rawWeights *
count);
210 if (rawObjects != NULL || rawWeights != NULL)
213 [objects getObjects:rawObjects];
216 for (i = 0; i <
count; ++i)
218 rawWeights[i] = fmax([weights oo_floatAtIndex:i], 0.0f);
221 self = [
self initWithObjects:rawObjects weights:rawWeights count:count];
243- (NSString *) descriptionComponents
245 return [NSString stringWithFormat:@"count=%lu", [
self count]];
249- (NSDictionary *) propertyListRepresentation
260- (float) weightForObject:(
id)object
266- (float) sumOfWeights
278- (NSArray *) allObjects
284- (id) copyWithZone:(NSZone *)zone
286 if (zone == [
self zone])
288 return [
self retain];
292 return [[
OOProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[
self propertyListRepresentation]];
297- (id) mutableCopyWithZone:(NSZone *)zone
299 return [[
OOMutableProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[
self propertyListRepresentation]];
305@implementation OOProbabilitySet (OOExtendedProbabilitySet)
307- (BOOL) containsObject:(
id)object
309 return [
self weightForObject:object] >= 0.0f;
313- (NSEnumerator *) objectEnumerator
315 return [[
self allObjects] objectEnumerator];
319- (float) probabilityForObject:(
id)object
321 float weight = [
self weightForObject:object];
322 if (weight > 0) weight /= [
self sumOfWeights];
345- (NSDictionary *) propertyListRepresentation
347 NSArray *empty = [NSArray array];
348 return [NSDictionary dictionaryWithObjectsAndKeys:empty, kObjectsKey, empty, kWeightsKey, nil];
358- (float) weightForObject:(
id)object
364- (float) sumOfWeights
376- (NSArray *) allObjects
378 return [NSArray array];
382- (id) mutableCopyWithZone:(NSZone *)zone
391@implementation OOEmptyProbabilitySet (Singleton)
400+ (id) allocWithZone:(NSZone *)inZone
411- (id) copyWithZone:(NSZone *)inZone
423- (NSUInteger) retainCount
443- (id) initWithObject:(
id)object weight:(
float)weight
451 if ((
self = [super initPriv]))
453 _object = [object retain];
454 _weight = fmax(weight, 0.0f);
469- (NSDictionary *) propertyListRepresentation
471 return [NSDictionary dictionaryWithObjectsAndKeys:
472 [NSArray arrayWithObject:_object], kObjectsKey,
473 [NSArray arrayWithObject:[NSNumber numberWithFloat:_weight]], kWeightsKey,
484- (float) weightForObject:(
id)object
486 if ([_object isEqual:
object])
return _weight;
491- (float) sumOfWeights
503- (NSArray *) allObjects
505 return [NSArray arrayWithObject:_object];
509- (id) mutableCopyWithZone:(NSZone *)zone
519- (id) initWithObjects:(
id *)objects weights:(
float *)weights count:(NSUInteger)count
522 float cuWeight = 0.0f;
524 assert(
count > 1 && objects != NULL && weights != NULL);
526 if ((
self = [super initPriv]))
529 _objects = malloc(
sizeof *objects *
count);
530 _cumulativeWeights = malloc(
sizeof *_cumulativeWeights *
count);
531 if (_objects == NULL || _cumulativeWeights == NULL)
538 for (i = 0; i !=
count; ++i)
540 _objects[i] = [objects[i] retain];
541 cuWeight += weights[i];
542 _cumulativeWeights[i] = cuWeight;
545 _sumOfWeights = cuWeight;
556 if (_objects != NULL)
558 for (i = 0; i < _count; ++i)
560 [_objects[i] release];
566 if (_cumulativeWeights != NULL)
568 free(_cumulativeWeights);
569 _cumulativeWeights = NULL;
576- (NSDictionary *) propertyListRepresentation
578 NSArray *objects =
nil;
579 NSMutableArray *weights =
nil;
580 float cuWeight = 0.0f, sum = 0.0f;
583 objects = [NSArray arrayWithObjects:_objects count:_count];
584 weights = [NSMutableArray arrayWithCapacity:_count];
585 for (i = 0; i < _count; ++i)
587 cuWeight = _cumulativeWeights[i];
588 [weights oo_addFloat:cuWeight - sum];
592 return [NSDictionary dictionaryWithObjectsAndKeys:
593 objects, kObjectsKey,
594 [[weights copy] autorelease], kWeightsKey,
604- (id) privObjectForWeight:(
float)target
612 NSUInteger low = 0, high = _count - 1, idx = 0;
617 idx = (low + high) / 2;
618 weight = _cumulativeWeights[idx];
624 else if (weight < target) low = idx + 1;
630 while (idx > 0 && _cumulativeWeights[idx - 1] >= target) --idx;
634 while (idx < (_count - 1) && _cumulativeWeights[idx] < target) ++idx;
637 assert(idx < _count);
638 id result = _objects[idx];
645 if (_sumOfWeights <= 0.0f)
return nil;
646 return [
self privObjectForWeight:randf() * _sumOfWeights];
650- (float) weightForObject:(
id)object
655 if (
object ==
nil)
return -1.0f;
658 for (i = 0; i < _count; ++i)
660 if ([_objects[i] isEqual:
object])
662 float leftWeight = (i != 0) ? _cumulativeWeights[i - 1] : 0.0f;
663 return _cumulativeWeights[i] - leftWeight;
672- (float) sumOfWeights
674 return _sumOfWeights;
678- (NSArray *) allObjects
680 return [NSArray arrayWithObjects:_objects count:_count];
684- (NSEnumerator *) objectEnumerator
690- (id) privObjectAtIndex:(NSUInteger)index
692 return (index < _count) ? _objects[index] :
nil;
696- (id) mutableCopyWithZone:(NSZone *)zone
699 float *weights = NULL;
701 float weight = 0.0f, sum = 0.0f;
704 weights = malloc(
sizeof *weights * _count);
705 if (weights == NULL)
return nil;
707 for (i = 0; i < _count; ++i)
709 weight = _cumulativeWeights[i];
710 weights[i] = weight - sum;
733 NSZone *zone = [
self zone];
739- (id) initWithObjects:(
id *)objects weights:(
float *)weights count:(NSUInteger)count
741 NSZone *zone = [
self zone];
747- (id) initWithPropertyListRepresentation:(NSDictionary *)plist
749 NSZone *zone = [
self zone];
755- (id) copyWithZone:(NSZone *)zone
757 return [[
OOProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[
self propertyListRepresentation]];
761- (void) setWeight:(
float)weight forObject:(
id)object
767- (void) removeObject:(
id)object
779 if ((
self = [super initPriv]))
781 _objects = [[NSMutableArray alloc] init];
782 _weights = [[NSMutableArray alloc] init];
790- (id) initPrivWithObjectArray:(NSMutableArray *)objects weightsArray:(NSMutableArray *)weights sum:(
float)sumOfWeights
792 assert(objects !=
nil && weights !=
nil && [objects
count] == [weights
count] && sumOfWeights >= 0.0f);
794 if ((
self = [super initPriv]))
796 _objects = [objects retain];
797 _weights = [weights retain];
798 _sumOfWeights = sumOfWeights;
805- (id) initWithObjects:(
id *)objects weights:(
float *)weights count:(NSUInteger)count
810 if (
count != 0 && (objects == NULL || weights == NULL))
813 [NSException raise:NSInvalidArgumentException format:@"Attempt to create %@ with non-zero count but nil objects or weights.", @"OOMutableProbabilitySet"];
817 if ((
self = [
self initPriv]))
819 for (i = 0; i !=
count; ++i)
821 [
self setWeight:fmax(weights[i], 0.0f) forObject:objects[i]];
829- (id) initWithPropertyListRepresentation:(NSDictionary *)plist
832 NSArray *objects =
nil;
833 NSArray *weights =
nil;
834 NSUInteger i = 0,
count = 0;
836 if (!(
self = [super initPriv])) OK = NO;
840 objects = [plist oo_arrayForKey:kObjectsKey];
841 weights = [plist oo_arrayForKey:kWeightsKey];
844 if (objects ==
nil || weights ==
nil) OK = NO;
845 count = [objects count];
851 for (i = 0; i <
count; ++i)
853 [
self setWeight:[weights oo_floatAtIndex:i] forObject:[objects objectAtIndex:i]];
876- (NSDictionary *) propertyListRepresentation
878 return [NSDictionary dictionaryWithObjectsAndKeys:
879 _objects, kObjectsKey,
880 _weights, kWeightsKey,
887 return [_objects count];
893 float target = 0.0f, sum = 0.0f, sumOfWeights;
894 NSUInteger i = 0,
count = 0;
896 sumOfWeights = [
self sumOfWeights];
897 target =
randf() * sumOfWeights;
898 count = [_objects count];
899 if (
count == 0 || sumOfWeights <= 0.0f)
return nil;
901 for (i = 0; i <
count; ++i)
903 sum += [_weights oo_floatAtIndex:i];
904 if (sum >= target)
return [_objects objectAtIndex:i];
907 OOLog(
@"probabilitySet.broken",
@"%s fell off end, returning first object. Nominal sum = %f, target = %f, actual sum = %f, count = %lu. %@", __PRETTY_FUNCTION__, sumOfWeights, target, sum,
count,
@"This is an internal error, please report it.");
908 return [_objects objectAtIndex:0];
912- (float) weightForObject:(
id)object
914 float result = -1.0f;
918 NSUInteger index = [_objects indexOfObject:object];
919 if (index != NSNotFound)
921 result = [_weights oo_floatAtIndex:index];
922 if (index != 0) result -= [_weights oo_floatAtIndex:index - 1];
929- (float) sumOfWeights
931 if (_sumOfWeights < 0.0f)
934 count = [
self count];
936 _sumOfWeights = 0.0f;
937 for (i = 0; i <
count; ++i)
939 _sumOfWeights += [_weights oo_floatAtIndex:i];
942 return _sumOfWeights;
946- (NSArray *) allObjects
948 return [[_objects copy] autorelease];
952- (NSEnumerator *) objectEnumerator
954 return [_objects objectEnumerator];
958- (void) setWeight:(
float)weight forObject:(
id)object
960 if (
object ==
nil)
return;
962 weight = fmax(weight, 0.0f);
963 NSUInteger index = [_objects indexOfObject:object];
964 if (index == NSNotFound)
966 [_objects addObject:object];
967 [_weights oo_addFloat:weight];
968 if (_sumOfWeights >= 0)
970 _sumOfWeights += weight;
976 _sumOfWeights = -1.0f;
977 [_weights replaceObjectAtIndex:index withObject:[NSNumber numberWithFloat:weight]];
982- (void) removeObject:(
id)object
984 if (
object ==
nil)
return;
986 NSUInteger index = [_objects indexOfObject:object];
987 if (index != NSNotFound)
989 [_objects removeObjectAtIndex:index];
990 _sumOfWeights = -1.0f;
991 [_weights removeObjectAtIndex:index];
996- (id) copyWithZone:(NSZone *)zone
1000 float *weights = NULL;
1001 NSUInteger i = 0,
count = 0;
1003 count = [_objects count];
1006 objects = malloc(
sizeof *objects *
count);
1007 weights = malloc(
sizeof *weights *
count);
1008 if (objects != NULL && weights != NULL)
1010 [_objects getObjects:objects];
1012 for (i = 0; i <
count; ++i)
1014 weights[i] = [_weights oo_floatAtIndex:i];
1020 if (objects != NULL) free(objects);
1021 if (weights != NULL) free(weights);
1027- (id) mutableCopyWithZone:(NSZone *)zone
1030 weightsArray:[[_weights mutableCopyWithZone:zone] autorelease]
1039- (id) initWithEnumerable:(
id<OOProbabilitySetEnumerable>)enumerable
1041 if ((
self = [super init]))
1043 _enumerable = [enumerable retain];
1052 [_enumerable release];
1060 if (_index < [_enumerable
count])
1062 return [_enumerable privObjectAtIndex:_index++];
1066 [_enumerable release];
1077 [NSException raise:NSGenericException format:@"Attempt to use abstract class %@ - this indicates an incorrect initialization.", [obj class]];
#define OO_RETURNS_RETAINED
#define OOLog(class, format,...)
static OOEmptyProbabilitySet * sOOEmptyProbabilitySetSingleton
static NSString *const kObjectsKey
static void ThrowAbstractionViolationException(id obj) GCC_ATTR((noreturn))
static NSString *const kWeightsKey
id probabilitySetWithObjects:weights:count:(id *objects,[weights] float *weights,[count] NSUInteger count)