Line data Source code
1 0 : /*
2 :
3 : OOProbabilitySet.m
4 :
5 :
6 : Copyright (C) 2008-2013 Jens Ayton
7 :
8 : Permission is hereby granted, free of charge, to any person obtaining a copy
9 : of this software and associated documentation files (the "Software"), to deal
10 : in the Software without restriction, including without limitation the rights
11 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : copies of the Software, and to permit persons to whom the Software is
13 : furnished to do so, subject to the following conditions:
14 :
15 : The above copyright notice and this permission notice shall be included in all
16 : copies or substantial portions of the Software.
17 :
18 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 : SOFTWARE.
25 :
26 :
27 : IMPLEMENTATION NOTES
28 : OOProbabilitySet is implemented as a class cluster with two abstract classes,
29 : two special-case implementations for immutable sets with zero or one object,
30 : and two general implementations (one mutable and one immutable). The general
31 : implementations are the only non-trivial ones.
32 :
33 : The general immutable implementation, OOConcreteProbabilitySet, consists of
34 : two parallel arrays, one of objects and one of cumulative weights. The
35 : "cumulative weight" for an entry is the sum of its weight and the cumulative
36 : weight of the entry to the left (i.e., with a lower index), with the implicit
37 : entry -1 having a cumulative weight of 0. Since weight cannot be negative,
38 : this means that cumulative weights increase to the right (not strictly
39 : increasing, though, since weights may be zero). We can thus find an object
40 : with a given cumulative weight through a binary search.
41 :
42 : OOConcreteMutableProbabilitySet is a naïve implementation using arrays. It
43 : could be optimized, but isn't expected to be used much except for building
44 : sets that will then be immutablized.
45 :
46 : */
47 :
48 : #import "OOProbabilitySet.h"
49 : #import "OOFunctionAttributes.h"
50 : #import "OOCollectionExtractors.h"
51 : #import "legacy_random.h"
52 :
53 :
54 0 : static NSString * const kObjectsKey = @"objects";
55 0 : static NSString * const kWeightsKey = @"weights";
56 :
57 :
58 : @protocol OOProbabilitySetEnumerable <NSObject>
59 :
60 0 : - (id) privObjectAtIndex:(NSUInteger)index;
61 :
62 : @end
63 :
64 :
65 : @interface OOProbabilitySet (OOPrivate)
66 :
67 : // Designated initializer. This must be used by subclasses, since init is overriden for public use.
68 0 : - (id) initPriv;
69 :
70 : @end
71 :
72 :
73 0 : @interface OOEmptyProbabilitySet: OOProbabilitySet
74 :
75 0 : + (OOEmptyProbabilitySet *) singleton OO_RETURNS_RETAINED;
76 :
77 : @end
78 :
79 :
80 0 : @interface OOSingleObjectProbabilitySet: OOProbabilitySet
81 : {
82 : @private
83 0 : id _object;
84 0 : float _weight;
85 : }
86 :
87 0 : - (id) initWithObject:(id)object weight:(float)weight;
88 :
89 : @end
90 :
91 :
92 0 : @interface OOConcreteProbabilitySet: OOProbabilitySet <OOProbabilitySetEnumerable>
93 : {
94 : @private
95 : NSUInteger _count;
96 0 : id *_objects;
97 0 : float *_cumulativeWeights; // Each cumulative weight is weight of object at this index + weight of all objects to left.
98 0 : float _sumOfWeights;
99 0 : }
100 : @end
101 :
102 :
103 : @interface OOConcreteMutableProbabilitySet: OOMutableProbabilitySet
104 0 : {
105 : @private
106 : NSMutableArray *_objects;
107 0 : NSMutableArray *_weights;
108 0 : float _sumOfWeights;
109 0 : }
110 :
111 : - (id) initPrivWithObjectArray:(NSMutableArray *)objects weightsArray:(NSMutableArray *)weights sum:(float)sumOfWeights;
112 0 :
113 : @end
114 :
115 :
116 : @interface OOProbabilitySetEnumerator: NSEnumerator
117 0 : {
118 : @private
119 : id _enumerable;
120 0 : NSUInteger _index;
121 0 : }
122 :
123 : - (id) initWithEnumerable:(id<OOProbabilitySetEnumerable>)enumerable;
124 0 :
125 : @end
126 :
127 :
128 : static void ThrowAbstractionViolationException(id obj) GCC_ATTR((noreturn));
129 :
130 :
131 : @implementation OOProbabilitySet
132 :
133 : // Abstract class just tosses allocations over to concrete class, and throws exception if you try to use it directly.
134 :
135 : + (id) probabilitySet
136 : {
137 : return [[OOEmptyProbabilitySet singleton] autorelease];
138 : }
139 :
140 :
141 : + (id) probabilitySetWithObjects:(id *)objects weights:(float *)weights count:(NSUInteger)count
142 : {
143 : return [[[self alloc] initWithObjects:objects weights:weights count:count] autorelease];
144 : }
145 :
146 :
147 : + (id) probabilitySetWithPropertyListRepresentation:(NSDictionary *)plist
148 : {
149 : return [[[self alloc] initWithPropertyListRepresentation:plist] autorelease];
150 : }
151 :
152 :
153 : - (id) init
154 : {
155 : [self release];
156 : return [OOEmptyProbabilitySet singleton];
157 : }
158 :
159 :
160 : - (id) initWithObjects:(id *)objects weights:(float *)weights count:(NSUInteger)count
161 : {
162 : NSZone *zone = [self zone];
163 : DESTROY(self);
164 :
165 : // Zero objects: return empty-set singleton.
166 : if (count == 0) return [OOEmptyProbabilitySet singleton];
167 :
168 : // If count is not zero and one of the paramters is nil, we've got us a programming error.
169 : if (objects == NULL || weights == NULL)
170 : {
171 : [NSException raise:NSInvalidArgumentException format:@"Attempt to create %@ with non-zero count but nil objects or weights.", @"OOProbabilitySet"];
172 : }
173 :
174 : // Single object: simple one-object set. Expected to be quite common.
175 : if (count == 1) return [[OOSingleObjectProbabilitySet allocWithZone:zone] initWithObject:objects[0] weight:weights[0]];
176 :
177 : // Otherwise, use general implementation.
178 : return [[OOConcreteProbabilitySet allocWithZone:zone] initWithObjects:objects weights:weights count:count];
179 : }
180 :
181 :
182 : - (id) initWithPropertyListRepresentation:(NSDictionary *)plist
183 : {
184 : NSArray *objects = nil;
185 : NSArray *weights = nil;
186 : NSUInteger i = 0, count = 0;
187 : id *rawObjects = NULL;
188 : float *rawWeights = NULL;
189 :
190 : objects = [plist oo_arrayForKey:kObjectsKey];
191 : weights = [plist oo_arrayForKey:kWeightsKey];
192 :
193 : // Validate
194 : if (objects == nil || weights == nil)
195 : {
196 : [self release];
197 : return nil;
198 : }
199 : count = [objects count];
200 : if (count != [weights count])
201 : {
202 : [self release];
203 : return nil;
204 : }
205 :
206 : // Extract contents.
207 : rawObjects = malloc(sizeof *rawObjects * count);
208 : rawWeights = malloc(sizeof *rawWeights * count);
209 :
210 : if (rawObjects != NULL || rawWeights != NULL)
211 : {
212 : // Extract objects.
213 : [objects getObjects:rawObjects];
214 :
215 : // Extract and convert weights.
216 : for (i = 0; i < count; ++i)
217 : {
218 : rawWeights[i] = fmax([weights oo_floatAtIndex:i], 0.0f);
219 : }
220 :
221 : self = [self initWithObjects:rawObjects weights:rawWeights count:count];
222 : }
223 : else
224 : {
225 : [self release];
226 : self = nil;
227 : }
228 :
229 : // Clean up.
230 : free(rawObjects);
231 : free(rawWeights);
232 :
233 : return self;
234 : }
235 :
236 :
237 : - (id) initPriv
238 0 : {
239 : return [super init];
240 : }
241 :
242 :
243 : - (NSString *) descriptionComponents
244 0 : {
245 : return [NSString stringWithFormat:@"count=%lu", [self count]];
246 : }
247 :
248 :
249 : - (NSDictionary *) propertyListRepresentation
250 : {
251 : ThrowAbstractionViolationException(self);
252 : }
253 :
254 : - (id) randomObject
255 : {
256 : ThrowAbstractionViolationException(self);
257 : }
258 :
259 :
260 : - (float) weightForObject:(id)object
261 : {
262 : ThrowAbstractionViolationException(self);
263 : }
264 :
265 :
266 : - (float) sumOfWeights
267 : {
268 : ThrowAbstractionViolationException(self);
269 : }
270 :
271 :
272 : - (NSUInteger) count
273 : {
274 : ThrowAbstractionViolationException(self);
275 : }
276 :
277 :
278 : - (NSArray *) allObjects
279 : {
280 : ThrowAbstractionViolationException(self);
281 : }
282 :
283 :
284 : - (id) copyWithZone:(NSZone *)zone
285 0 : {
286 : if (zone == [self zone])
287 : {
288 : return [self retain];
289 : }
290 : else
291 : {
292 : return [[OOProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[self propertyListRepresentation]];
293 : }
294 : }
295 :
296 :
297 : - (id) mutableCopyWithZone:(NSZone *)zone
298 0 : {
299 : return [[OOMutableProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[self propertyListRepresentation]];
300 : }
301 :
302 : @end
303 :
304 :
305 : @implementation OOProbabilitySet (OOExtendedProbabilitySet)
306 :
307 : - (BOOL) containsObject:(id)object
308 : {
309 : return [self weightForObject:object] >= 0.0f;
310 : }
311 :
312 :
313 : - (NSEnumerator *) objectEnumerator
314 : {
315 : return [[self allObjects] objectEnumerator];
316 : }
317 :
318 :
319 : - (float) probabilityForObject:(id)object
320 0 : {
321 : float weight = [self weightForObject:object];
322 : if (weight > 0) weight /= [self sumOfWeights];
323 :
324 : return weight;
325 : }
326 :
327 : @end
328 :
329 :
330 : static OOEmptyProbabilitySet *sOOEmptyProbabilitySetSingleton = nil;
331 0 :
332 : @implementation OOEmptyProbabilitySet: OOProbabilitySet
333 :
334 : + (OOEmptyProbabilitySet *) singleton
335 : {
336 : if (sOOEmptyProbabilitySetSingleton == nil)
337 : {
338 : sOOEmptyProbabilitySetSingleton = [[self alloc] init];
339 : }
340 :
341 : return sOOEmptyProbabilitySetSingleton;
342 0 : }
343 :
344 :
345 : - (NSDictionary *) propertyListRepresentation
346 0 : {
347 : NSArray *empty = [NSArray array];
348 : return [NSDictionary dictionaryWithObjectsAndKeys:empty, kObjectsKey, empty, kWeightsKey, nil];
349 : }
350 :
351 :
352 : - (id) randomObject
353 0 : {
354 : return nil;
355 : }
356 :
357 :
358 : - (float) weightForObject:(id)object
359 0 : {
360 : return -1.0f;
361 : }
362 :
363 :
364 : - (float) sumOfWeights
365 0 : {
366 : return 0.0f;
367 : }
368 :
369 :
370 : - (NSUInteger) count
371 0 : {
372 : return 0;
373 : }
374 :
375 :
376 : - (NSArray *) allObjects
377 0 : {
378 : return [NSArray array];
379 : }
380 :
381 :
382 : - (id) mutableCopyWithZone:(NSZone *)zone
383 0 : {
384 : // A mutable copy of an empty probability set is equivalent to a new empty mutable probability set.
385 : return [[OOConcreteMutableProbabilitySet allocWithZone:zone] initPriv];
386 : }
387 :
388 : @end
389 :
390 :
391 : @implementation OOEmptyProbabilitySet (Singleton)
392 :
393 : /* Canonical singleton boilerplate.
394 : See Cocoa Fundamentals Guide: Creating a Singleton Instance.
395 : See also +singleton above.
396 :
397 : NOTE: assumes single-threaded access.
398 : */
399 :
400 : + (id) allocWithZone:(NSZone *)inZone
401 0 : {
402 : if (sOOEmptyProbabilitySetSingleton == nil)
403 : {
404 : sOOEmptyProbabilitySetSingleton = [super allocWithZone:inZone];
405 : return sOOEmptyProbabilitySetSingleton;
406 : }
407 : return nil;
408 : }
409 :
410 :
411 : - (id) copyWithZone:(NSZone *)inZone
412 0 : {
413 : return self;
414 : }
415 :
416 :
417 : - (id) retain
418 0 : {
419 : return self;
420 : }
421 :
422 :
423 : - (NSUInteger) retainCount
424 0 : {
425 : return UINT_MAX;
426 : }
427 :
428 :
429 : - (void) release
430 0 : {}
431 :
432 :
433 : - (id) autorelease
434 0 : {
435 : return self;
436 : }
437 :
438 : @end
439 :
440 :
441 : @implementation OOSingleObjectProbabilitySet: OOProbabilitySet
442 :
443 : - (id) initWithObject:(id)object weight:(float)weight
444 : {
445 : if (object == nil)
446 : {
447 : [self release];
448 : return nil;
449 0 : }
450 :
451 : if ((self = [super initPriv]))
452 0 : {
453 : _object = [object retain];
454 : _weight = fmax(weight, 0.0f);
455 : }
456 :
457 : return self;
458 0 : }
459 :
460 :
461 : - (void) dealloc
462 0 : {
463 : [_object release];
464 :
465 : [super dealloc];
466 : }
467 :
468 :
469 : - (NSDictionary *) propertyListRepresentation
470 0 : {
471 : return [NSDictionary dictionaryWithObjectsAndKeys:
472 : [NSArray arrayWithObject:_object], kObjectsKey,
473 : [NSArray arrayWithObject:[NSNumber numberWithFloat:_weight]], kWeightsKey,
474 : nil];
475 : }
476 :
477 :
478 : - (id) randomObject
479 0 : {
480 : return _object;
481 : }
482 :
483 :
484 : - (float) weightForObject:(id)object
485 0 : {
486 : if ([_object isEqual:object]) return _weight;
487 : else return -1.0f;
488 : }
489 :
490 :
491 : - (float) sumOfWeights
492 0 : {
493 : return _weight;
494 : }
495 :
496 :
497 : - (NSUInteger) count
498 0 : {
499 : return 1;
500 : }
501 :
502 :
503 : - (NSArray *) allObjects
504 0 : {
505 : return [NSArray arrayWithObject:_object];
506 : }
507 :
508 :
509 : - (id) mutableCopyWithZone:(NSZone *)zone
510 0 : {
511 : return [[OOConcreteMutableProbabilitySet allocWithZone:zone] initWithObjects:&_object weights:&_weight count:1];
512 : }
513 :
514 : @end
515 :
516 :
517 : @implementation OOConcreteProbabilitySet
518 :
519 : - (id) initWithObjects:(id *)objects weights:(float *)weights count:(NSUInteger)count
520 0 : {
521 : NSUInteger i = 0;
522 : float cuWeight = 0.0f;
523 :
524 : assert(count > 1 && objects != NULL && weights != NULL);
525 :
526 : if ((self = [super initPriv]))
527 : {
528 : // Allocate arrays
529 : _objects = malloc(sizeof *objects * count);
530 : _cumulativeWeights = malloc(sizeof *_cumulativeWeights * count);
531 : if (_objects == NULL || _cumulativeWeights == NULL)
532 : {
533 : [self release];
534 : return nil;
535 : }
536 :
537 : // Fill in arrays, retain objects, add up weights.
538 : for (i = 0; i != count; ++i)
539 : {
540 : _objects[i] = [objects[i] retain];
541 : cuWeight += weights[i];
542 : _cumulativeWeights[i] = cuWeight;
543 : }
544 : _count = count;
545 : _sumOfWeights = cuWeight;
546 : }
547 :
548 : return self;
549 : }
550 :
551 :
552 : - (void) dealloc
553 0 : {
554 : NSUInteger i = 0;
555 :
556 : if (_objects != NULL)
557 : {
558 : for (i = 0; i < _count; ++i)
559 : {
560 : [_objects[i] release];
561 : }
562 : free(_objects);
563 : _objects = NULL;
564 : }
565 :
566 : if (_cumulativeWeights != NULL)
567 : {
568 : free(_cumulativeWeights);
569 : _cumulativeWeights = NULL;
570 : }
571 :
572 : [super dealloc];
573 : }
574 :
575 :
576 : - (NSDictionary *) propertyListRepresentation
577 0 : {
578 : NSArray *objects = nil;
579 : NSMutableArray *weights = nil;
580 : float cuWeight = 0.0f, sum = 0.0f;
581 : NSUInteger i = 0;
582 :
583 : objects = [NSArray arrayWithObjects:_objects count:_count];
584 : weights = [NSMutableArray arrayWithCapacity:_count];
585 : for (i = 0; i < _count; ++i)
586 : {
587 : cuWeight = _cumulativeWeights[i];
588 : [weights oo_addFloat:cuWeight - sum];
589 : sum = cuWeight;
590 : }
591 :
592 : return [NSDictionary dictionaryWithObjectsAndKeys:
593 : objects, kObjectsKey,
594 : [[weights copy] autorelease], kWeightsKey,
595 : nil];
596 : }
597 :
598 : - (NSUInteger) count
599 0 : {
600 : return _count;
601 : }
602 :
603 :
604 : - (id) privObjectForWeight:(float)target
605 0 : {
606 : /* Select an object at random. This is a binary search in the cumulative
607 : weights array. Since weights of zero are allowed, there may be several
608 : objects with the same cumulative weight, in which case we select the
609 : leftmost, i.e. the one where the delta is non-zero.
610 : */
611 :
612 : NSUInteger low = 0, high = _count - 1, idx = 0;
613 : float weight = 0.0f;
614 :
615 : while (low < high)
616 : {
617 : idx = (low + high) / 2;
618 : weight = _cumulativeWeights[idx];
619 : if (weight > target)
620 : {
621 : if (EXPECT_NOT(idx == 0)) break;
622 : high = idx - 1;
623 : }
624 : else if (weight < target) low = idx + 1;
625 : else break;
626 : }
627 :
628 : if (weight > target)
629 : {
630 : while (idx > 0 && _cumulativeWeights[idx - 1] >= target) --idx;
631 : }
632 : else
633 : {
634 : while (idx < (_count - 1) && _cumulativeWeights[idx] < target) ++idx;
635 : }
636 :
637 : assert(idx < _count);
638 : id result = _objects[idx];
639 : return result;
640 : }
641 :
642 :
643 : - (id) randomObject
644 0 : {
645 : if (_sumOfWeights <= 0.0f) return nil;
646 : return [self privObjectForWeight:randf() * _sumOfWeights];
647 : }
648 :
649 :
650 : - (float) weightForObject:(id)object
651 0 : {
652 : NSUInteger i;
653 :
654 : // Can't have nil in collection.
655 : if (object == nil) return -1.0f;
656 :
657 : // Perform linear search, then get weight by subtracting cumulative weight from cumulative weight to left.
658 : for (i = 0; i < _count; ++i)
659 : {
660 : if ([_objects[i] isEqual:object])
661 : {
662 : float leftWeight = (i != 0) ? _cumulativeWeights[i - 1] : 0.0f;
663 : return _cumulativeWeights[i] - leftWeight;
664 : }
665 : }
666 :
667 : // If we got here, object not found.
668 : return -1.0f;
669 : }
670 :
671 :
672 : - (float) sumOfWeights
673 0 : {
674 : return _sumOfWeights;
675 : }
676 :
677 :
678 : - (NSArray *) allObjects
679 0 : {
680 : return [NSArray arrayWithObjects:_objects count:_count];
681 : }
682 :
683 :
684 : - (NSEnumerator *) objectEnumerator
685 0 : {
686 : return [[[OOProbabilitySetEnumerator alloc] initWithEnumerable:self] autorelease];
687 : }
688 :
689 :
690 : - (id) privObjectAtIndex:(NSUInteger)index
691 0 : {
692 : return (index < _count) ? _objects[index] : nil;
693 : }
694 :
695 :
696 : - (id) mutableCopyWithZone:(NSZone *)zone
697 0 : {
698 : id result = nil;
699 : float *weights = NULL;
700 : NSUInteger i = 0;
701 : float weight = 0.0f, sum = 0.0f;
702 :
703 : // Convert cumulative weights to "plain" weights.
704 : weights = malloc(sizeof *weights * _count);
705 : if (weights == NULL) return nil;
706 :
707 : for (i = 0; i < _count; ++i)
708 : {
709 : weight = _cumulativeWeights[i];
710 : weights[i] = weight - sum;
711 : sum += weights[i];
712 : }
713 :
714 : result = [[OOConcreteMutableProbabilitySet allocWithZone:zone] initWithObjects:_objects weights:weights count:_count];
715 : free(weights);
716 :
717 : return result;
718 : }
719 :
720 : @end
721 :
722 :
723 : @implementation OOMutableProbabilitySet
724 :
725 : + (id) probabilitySet
726 0 : {
727 : return [[[OOConcreteMutableProbabilitySet alloc] initPriv] autorelease];
728 : }
729 :
730 :
731 : - (id) init
732 0 : {
733 : NSZone *zone = [self zone];
734 : [self release];
735 : return [[OOConcreteMutableProbabilitySet allocWithZone:zone] initPriv];
736 : }
737 :
738 :
739 : - (id) initWithObjects:(id *)objects weights:(float *)weights count:(NSUInteger)count
740 0 : {
741 : NSZone *zone = [self zone];
742 : [self release];
743 : return [[OOConcreteMutableProbabilitySet allocWithZone:zone] initWithObjects:objects weights:weights count:count];
744 : }
745 :
746 :
747 : - (id) initWithPropertyListRepresentation:(NSDictionary *)plist
748 0 : {
749 : NSZone *zone = [self zone];
750 : [self release];
751 : return [[OOConcreteMutableProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:plist];
752 : }
753 :
754 :
755 : - (id) copyWithZone:(NSZone *)zone
756 0 : {
757 : return [[OOProbabilitySet allocWithZone:zone] initWithPropertyListRepresentation:[self propertyListRepresentation]];
758 : }
759 :
760 :
761 : - (void) setWeight:(float)weight forObject:(id)object
762 : {
763 : ThrowAbstractionViolationException(self);
764 : }
765 :
766 :
767 : - (void) removeObject:(id)object
768 : {
769 : ThrowAbstractionViolationException(self);
770 : }
771 :
772 : @end
773 :
774 :
775 : @implementation OOConcreteMutableProbabilitySet
776 :
777 : - (id) initPriv
778 0 : {
779 : if ((self = [super initPriv]))
780 : {
781 : _objects = [[NSMutableArray alloc] init];
782 : _weights = [[NSMutableArray alloc] init];
783 : }
784 :
785 : return self;
786 : }
787 :
788 :
789 : // For internal use by mutableCopy
790 : - (id) initPrivWithObjectArray:(NSMutableArray *)objects weightsArray:(NSMutableArray *)weights sum:(float)sumOfWeights
791 : {
792 : assert(objects != nil && weights != nil && [objects count] == [weights count] && sumOfWeights >= 0.0f);
793 :
794 : if ((self = [super initPriv]))
795 : {
796 : _objects = [objects retain];
797 : _weights = [weights retain];
798 : _sumOfWeights = sumOfWeights;
799 : }
800 :
801 : return self;
802 : }
803 :
804 :
805 : - (id) initWithObjects:(id *)objects weights:(float *)weights count:(NSUInteger)count
806 0 : {
807 : NSUInteger i = 0;
808 :
809 : // Validate parameters.
810 : if (count != 0 && (objects == NULL || weights == NULL))
811 : {
812 : [self release];
813 : [NSException raise:NSInvalidArgumentException format:@"Attempt to create %@ with non-zero count but nil objects or weights.", @"OOMutableProbabilitySet"];
814 : }
815 :
816 : // Set up & go.
817 : if ((self = [self initPriv]))
818 : {
819 : for (i = 0; i != count; ++i)
820 : {
821 : [self setWeight:fmax(weights[i], 0.0f) forObject:objects[i]];
822 : }
823 : }
824 :
825 : return self;
826 : }
827 :
828 :
829 : - (id) initWithPropertyListRepresentation:(NSDictionary *)plist
830 0 : {
831 : BOOL OK = YES;
832 : NSArray *objects = nil;
833 : NSArray *weights = nil;
834 : NSUInteger i = 0, count = 0;
835 :
836 : if (!(self = [super initPriv])) OK = NO;
837 :
838 : if (OK)
839 : {
840 : objects = [plist oo_arrayForKey:kObjectsKey];
841 : weights = [plist oo_arrayForKey:kWeightsKey];
842 :
843 : // Validate
844 : if (objects == nil || weights == nil) OK = NO;
845 : count = [objects count];
846 : if (count != [weights count]) OK = NO;
847 : }
848 :
849 : if (OK)
850 : {
851 : for (i = 0; i < count; ++i)
852 : {
853 : [self setWeight:[weights oo_floatAtIndex:i] forObject:[objects objectAtIndex:i]];
854 : }
855 : }
856 :
857 : if (!OK)
858 : {
859 : [self release];
860 : self = nil;
861 : }
862 :
863 : return self;
864 : }
865 :
866 :
867 : - (void) dealloc
868 0 : {
869 : [_objects release];
870 : [_weights release];
871 :
872 : [super dealloc];
873 : }
874 :
875 :
876 : - (NSDictionary *) propertyListRepresentation
877 0 : {
878 : return [NSDictionary dictionaryWithObjectsAndKeys:
879 : _objects, kObjectsKey,
880 : _weights, kWeightsKey,
881 : nil];
882 : }
883 :
884 :
885 : - (NSUInteger) count
886 0 : {
887 : return [_objects count];
888 : }
889 :
890 :
891 : - (id) randomObject
892 0 : {
893 : float target = 0.0f, sum = 0.0f, sumOfWeights;
894 : NSUInteger i = 0, count = 0;
895 :
896 : sumOfWeights = [self sumOfWeights];
897 : target = randf() * sumOfWeights;
898 : count = [_objects count];
899 : if (count == 0 || sumOfWeights <= 0.0f) return nil;
900 :
901 : for (i = 0; i < count; ++i)
902 : {
903 : sum += [_weights oo_floatAtIndex:i];
904 : if (sum >= target) return [_objects objectAtIndex:i];
905 : }
906 :
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];
909 : }
910 :
911 :
912 : - (float) weightForObject:(id)object
913 0 : {
914 : float result = -1.0f;
915 :
916 : if (object != nil)
917 : {
918 : NSUInteger index = [_objects indexOfObject:object];
919 : if (index != NSNotFound)
920 : {
921 : result = [_weights oo_floatAtIndex:index];
922 : if (index != 0) result -= [_weights oo_floatAtIndex:index - 1];
923 : }
924 : }
925 : return result;
926 : }
927 :
928 :
929 : - (float) sumOfWeights
930 0 : {
931 : if (_sumOfWeights < 0.0f)
932 : {
933 : NSUInteger i, count;
934 : count = [self count];
935 :
936 : _sumOfWeights = 0.0f;
937 : for (i = 0; i < count; ++i)
938 : {
939 : _sumOfWeights += [_weights oo_floatAtIndex:i];
940 : }
941 : }
942 : return _sumOfWeights;
943 : }
944 :
945 :
946 : - (NSArray *) allObjects
947 0 : {
948 : return [[_objects copy] autorelease];
949 : }
950 :
951 :
952 : - (NSEnumerator *) objectEnumerator
953 0 : {
954 : return [_objects objectEnumerator];
955 : }
956 :
957 :
958 : - (void) setWeight:(float)weight forObject:(id)object
959 0 : {
960 : if (object == nil) return;
961 :
962 : weight = fmax(weight, 0.0f);
963 : NSUInteger index = [_objects indexOfObject:object];
964 : if (index == NSNotFound)
965 : {
966 : [_objects addObject:object];
967 : [_weights oo_addFloat:weight];
968 : if (_sumOfWeights >= 0)
969 : {
970 : _sumOfWeights += weight;
971 : }
972 : // Else, _sumOfWeights is invalid and will need to be recalculated on demand.
973 : }
974 : else
975 : {
976 : _sumOfWeights = -1.0f; // Simply subtracting the relevant weight doesn't work if the weight is large, due to floating-point precision issues.
977 : [_weights replaceObjectAtIndex:index withObject:[NSNumber numberWithFloat:weight]];
978 : }
979 : }
980 :
981 :
982 : - (void) removeObject:(id)object
983 0 : {
984 : if (object == nil) return;
985 :
986 : NSUInteger index = [_objects indexOfObject:object];
987 : if (index != NSNotFound)
988 : {
989 : [_objects removeObjectAtIndex:index];
990 : _sumOfWeights = -1.0f; // Simply subtracting the relevant weight doesn't work if the weight is large, due to floating-point precision issues.
991 : [_weights removeObjectAtIndex:index];
992 : }
993 : }
994 :
995 :
996 : - (id) copyWithZone:(NSZone *)zone
997 0 : {
998 : id result = nil;
999 : id *objects = NULL;
1000 : float *weights = NULL;
1001 : NSUInteger i = 0, count = 0;
1002 :
1003 : count = [_objects count];
1004 : if (EXPECT_NOT(count == 0)) return [OOEmptyProbabilitySet singleton];
1005 :
1006 : objects = malloc(sizeof *objects * count);
1007 : weights = malloc(sizeof *weights * count);
1008 : if (objects != NULL && weights != NULL)
1009 : {
1010 : [_objects getObjects:objects];
1011 :
1012 : for (i = 0; i < count; ++i)
1013 : {
1014 : weights[i] = [_weights oo_floatAtIndex:i];
1015 : }
1016 :
1017 : result = [[OOProbabilitySet probabilitySetWithObjects:objects weights:weights count:count] retain];
1018 : }
1019 :
1020 : if (objects != NULL) free(objects);
1021 : if (weights != NULL) free(weights);
1022 :
1023 : return result;
1024 : }
1025 :
1026 :
1027 : - (id) mutableCopyWithZone:(NSZone *)zone
1028 0 : {
1029 : return [[OOConcreteMutableProbabilitySet alloc] initPrivWithObjectArray:[[_objects mutableCopyWithZone:zone] autorelease]
1030 : weightsArray:[[_weights mutableCopyWithZone:zone] autorelease]
1031 : sum:_sumOfWeights];
1032 : }
1033 :
1034 : @end
1035 :
1036 :
1037 : @implementation OOProbabilitySetEnumerator
1038 :
1039 : - (id) initWithEnumerable:(id<OOProbabilitySetEnumerable>)enumerable
1040 : {
1041 : if ((self = [super init]))
1042 : {
1043 : _enumerable = [enumerable retain];
1044 : }
1045 :
1046 : return self;
1047 : }
1048 :
1049 :
1050 : - (void) dealloc
1051 0 : {
1052 : [_enumerable release];
1053 :
1054 : [super dealloc];
1055 : }
1056 :
1057 :
1058 : - (id) nextObject
1059 0 : {
1060 : if (_index < [_enumerable count])
1061 : {
1062 : return [_enumerable privObjectAtIndex:_index++];
1063 : }
1064 : else
1065 : {
1066 : [_enumerable release];
1067 : _enumerable = nil;
1068 : return nil;
1069 : }
1070 : }
1071 :
1072 : @end
1073 :
1074 :
1075 : static void ThrowAbstractionViolationException(id obj)
1076 0 : {
1077 : [NSException raise:NSGenericException format:@"Attempt to use abstract class %@ - this indicates an incorrect initialization.", [obj class]];
1078 : abort(); // unreachable
1079 : }
|
