Use Python's bisect in C/Objective-C
Question: I'm looking to port this class written in Python
<http://stackoverflow.com/a/4113400/129202> into Objective-C, or C.

It uses something called `bisect.bisect_right`. I'm not terribly experienced
with Python, so how would one implement that in C/obj-c?


Answer: This is the class I came up with. I just tested it one million times and it
gives expected results. Not exactly binary search I guess but it does the job.
No outside libraries needed.

The header file:

    
    
    //
    //  Mjweightedtuple2.h
    //  orixnknk
    //
    //  Created by Jonny Bergström on 3/7/14.
    //  Copyright (c) 2014 Jonny Bergstrom. All rights reserved.
    //
    
    #import <Foundation/Foundation.h>
    
    @interface Mjweightedtuple2 : NSObject
    -(id)initWithItems:(NSDictionary*)items;
    -(id)randomValue;
    @end
    

The implementation file:

    
    
    //
    //  Mjweightedtuple2.m
    //  orixnknk
    //
    //  Created by Jonny Bergström on 3/7/14.
    //  Copyright (c) 2014 Jonny Bergstrom. All rights reserved.
    //
    
    #import "Mjweightedtuple2.h"
    
    @interface Valueandlength : NSObject
    @property (nonatomic, retain) id value;
    @property NSInteger high;
    @end
    @implementation Valueandlength
    @synthesize value; // retain
    -(void)dealloc {
        self.value = nil;
        [super dealloc];
    }
    @end
    
    @interface Mjweightedtuple2 ()
    @property (nonatomic, retain) NSArray* thearray;
    @property NSInteger length;
    @end
    
    @implementation Mjweightedtuple2
    @synthesize thearray;
    @synthesize length; // assign
    -(void)dealloc {
        self.thearray = nil;
        [super dealloc];
    }
    -(id)initWithItems:(NSDictionary*)items {
        self = [super init];
        if (self) {
    //      NSDictionary items = @{
    //              @"pear": [NSNumber numberWithInteger:1],
    //              @"banana": [NSNumber numberWithInteger:100],
    //              @"apple": [NSNumber numberWithInteger:15],
    //              };
    
            NSMutableArray* temparray = [NSMutableArray array];
            //NSMutableSet* tempset = [NSMutableSet set];
    
            NSInteger maxval = 0;
            Valueandlength* val;
            NSNumber* numberValue;
            for (NSString* key in items.allKeys) {
                numberValue = items[key];
                const NSInteger VALUE = [numberValue integerValue];
                maxval += VALUE;
    
                val = [[Valueandlength alloc] init];
                val.value = key;
                val.high = maxval;
    
                [temparray addObject:val];
    
                [val release];
            }
            self.thearray = [NSArray arrayWithArray:temparray];
    
            self.length = maxval;
        }
        return self;
    }
    -(id)randomValue {
        const NSInteger INDEXTOLOOKFOR = arc4random_uniform(self.length);
    
        for (Valueandlength* val in self.thearray) {
            if (INDEXTOLOOKFOR < val.high)
                return val.value;
        }
        return nil;
    }
    @end
    

This is how I tested:

    
    
    NSDictionary* items = @{
                            @"pear": [NSNumber numberWithInteger:1],
                            @"banana": [NSNumber numberWithInteger:1],
                            @"apple": [NSNumber numberWithInteger:1],
                            };
    
    Mjweightedtuple2* r = [[Mjweightedtuple2 alloc] initWithItems:items];
    DLog(@"Mjweightedtuple2 test");
    NSMutableDictionary* dicresult = [NSMutableDictionary dictionary];
    for (NSString* key in items.allKeys) {
        [dicresult setObject:[NSNumber numberWithInteger:0] forKey:key];
    }
    const NSInteger TIMES = 1000000;
    for (NSInteger i = 0; i < TIMES; i++) {
        //DLog(@"%d: %@", i + 1, [r randomValue]);
        NSString* selectedkey = [r randomValue];
        NSNumber* number = dicresult[selectedkey];
        [dicresult setObject:[NSNumber numberWithInteger:1 + number.integerValue] forKey:selectedkey];
    }
    const double DTIMES = TIMES;
    for (NSString* key in dicresult.allKeys) {
        const NSInteger FINALCOUNT = [dicresult[key] integerValue];
        DLog(@"%@: %d = %.1f%%", key, FINALCOUNT, ((double)FINALCOUNT / DTIMES) * 100.0);
    }
    

Results:

> banana: 333560 = 33.4% apple: 333540 = 33.4% pear: 332900 = 33.3%

Then I prefer bananas 90% of the times...

    
    
    NSDictionary* items = @{
                            @"pear": [NSNumber numberWithInteger:5000],
                            @"banana": [NSNumber numberWithInteger:90000],
                            @"apple": [NSNumber numberWithInteger:5000],
                            };
    

> banana: 899258 = 89.9% apple: 50362 = 5.0% pear: 50380 = 5.0%

