Picking the nearest 3 dates out of a list

I am working on a TV-guide app, and am trying to get the nearest 3 dates from an NSArray with NSDictionary's. So far so good, but I have been trying to figure out how I can do this the best way using as little memory as possible and with as little code (hence decreasing the likelihood of bugs or crashes). The array is already sorted.

I have a dictionary with all the channels shows for one day. The dictionary withholds an NSDate (called date).

Lets say a channel has 8 shows and the time is now 11:45. show #3 started at 11:00 and ends at 12:00, show #4 starts at 12:00 and ends at 13:00, show #5 at 13:00 to 14:00 ect.

How could I fetch show #3 (which started in the past!), #4 and #5 the fastest (memory wise) and easiest from my array of dictionaries?

Currently I am doing a for loop fetching each dictionary, and then comparing the dictionaries date with the current date. And thats where I am stuck. Or maybe I just have a brain-fag.

My current code (after a while of testing different things):

- (NSArray*)getCommingProgramsFromDict:(NSArray*)programs amountOfShows:(int)shows
{
    int fetched = 0;
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];
    NSDate *latestDate = [NSDate date];

    for (NSDictionary *program in programs)
    {
        N开发者_如何学PythonSDate *startDate = [program objectForKey:@"date"];

        NSLog(@"Program: %@", program);
        switch ([latestDate compare:startDate]) {
            case NSOrderedAscending:
                NSLog(@"latestDate is older, meaning the show starts in the future from latestDate");
                // do something
                break;
            case NSOrderedSame:
                NSLog(@"latestDate is the same as startDate");
                // do something
                break;
            case NSOrderedDescending:
                NSLog(@"latestDate is more recent, meaning show starts in the past");
                // do something
                break;
        }

        // Now what?
    }

    return resultArray;
}

I am writing it for iOS 5, using ARC.

---

After your EDIT and explanation, here is another answer, hopefully fitting your question better.

The idea is to find the index of the show that is next (startDate after now). Once you have it, it will be easy to get the show at the previous index (on air) and the 2 shows after it.

NSUInteger indexOfNextShow = [arrayOfShows indexOfObjectPassingTest:^BOOL(id program, NSUInteger idx, BOOL *stop) {
    NSDate* startDate = [program objectForKey:@"date"];
    return ([startDate timeIntervalSinceNow] > 0); // startDate after now, so we are after the on-air show
}];

At that stage, indexOfNextShow contains the index of the show in your NSArray that will air after the current show. Thus what you want according to your question is objects at index indexOfNextShow-1 (show on air), indexOfNextShow (next show) and indexOfNextShow+1 (show after the next).

// in practice you should check the range validity before doing this
NSIndexSet* indexes = [NSIndexSet indexSetWithIndexesInRange:NSMakeRange(indexOfNextShow-1,3)];
NSArray* onAirShowAnd2Next = [arrayOfShows objectsAtIndexes:indexes];

Obviously in practice you should add some verifications (like indexOfNextShow being >0 before trying to access object at index indexOfNextShow-1 and indexOfNextShow+1 not being past the total number of shows in your array).

The advantage of this is that since your array of shows is sorted by startDate already, indexOfObjectPassingTest: returns the first object passing the test, and stop iterating as soon as it has found the right object. So this is both concise, easy-to-read code and relatively efficient.

.

---

I'm not sure I understood your model structure, you have an NSArray of shows, each show being a NSDictionary holding the NSDate of the show along with other info, right?

One idea then is to sort this NSArray of show according to the distance between the start time of the show and now.

NSArray* shows = ... // your arraw of NSDictionaries representing each show
NSArray* sortedShows = [shows sortedArrayUsingComparator:^(id show1, id show2) {
    NSTimeInterval ti1 = fabs([[show1 objectForKey:@"startDate"] timeIntervalSinceNow]);
    NSTimeInterval ti2 = fabs([[show2 objectForKey:@"startDate"] timeIntervalSinceNow]);
    return (NSComparisonResult)(ti1-ti2);
}];

Then of course it is easy at that point to only take the 3 first shows of the sortedShows array.

If I've misunderstood your model structure, please edit your question to specify it, but I'm sure you can adapt my code to fit your model then

---

The question asks for the "fastest (memory wise)". Are you looking for the fastest or the most memory/footprint conscious? With algorithms there is often a space vs. time tradeoff so as you make it faster, you typically do it by adding indexes and other lookup data structures which increase the memory footprint.

For this problem the straight forward implementation would be to iterate through each channel and each item comparing each against the top 3 held in memory. But that could be slow.

With additional storage, you could have an additional array which indexes into time slots (one per 15 minutes granularity good enough?) and then daisy chain shows off of those time slots. Given the current time, you could index straight into the current times slot and then look up the next set of shows. The array would have pointers to the same objects that the dictionaries are pointing to. That's an additional data structure to optimize one specific pattern of access but it does it at a cost - more memory.

That would increase your foot print but would be very fast since it's just an array index offset.

Finally, you could store all your shows in a sqlite database or CoreData and solve your problem with one query. Let the sql engine do the hard work. that wold also keep your memory foot print reasonable.

Hope that sparks some ideas.

EDIT:

A crude example showing how you can construct a look table - an array with slots for every 15 minutes. It's instant to jump to the current time slot since it's just an array offset. Then you walk the absolute number of walks - the next three and you're out. So, it's an array offset with 3 iterations.

Most of the code is building date - the lookup table, finding the time slot and the loop is trivial.

NSInteger slotFromTime(NSDate *date)
{
    NSLog(@"date: %@", date);

    NSDateComponents *dateComponents = [[NSCalendar currentCalendar] components:(NSHourCalendarUnit | NSMinuteCalendarUnit) fromDate:date];
    NSInteger hour = [dateComponents hour];
    NSInteger minute = [dateComponents minute];
    NSInteger slot = (hour * 60 + minute)/15;
    NSLog(@"slot: %d", (int)slot);

    return slot;
}

int main (int argc, const char * argv[])
{
    // An array of arrays - the outer array is an index of 15 min time slots.
    NSArray *slots[96];
    NSDate *currentTime = [NSDate date];
    NSInteger currentSlot = slotFromTime(currentTime);

    // populate with shows into the next few slots for demo purpose
    NSInteger index = currentSlot;
    NSArray *shows1 = [NSArray arrayWithObjects:@"Seinfeld", @"Tonight Show", nil];
    slots[++index] = shows1;
    NSArray *shows2 = [NSArray arrayWithObjects:@"Friends", @"Jurassic Park", nil];
    slots[++index] = shows2; 

    // find next three -jump directly to the current slot and only iterate till we find three.
    // we don't have to iterate over the full data set of shows
    NSMutableArray *nextShow = [[NSMutableArray alloc] init];
    for (NSInteger currIndex = currentSlot; currIndex < 96; currIndex++)
    {
        NSArray *shows = slots[currIndex];
        if (shows)
        {
            for (NSString *show in shows)
            {
                NSLog(@"found show: %@", show);
                [nextShow addObject:show];
                if ([nextShow count] == 3) 
                    break;
            }
        }

        if ([nextShow count] == 3) 
            break;        
    }

    return 0;
}

This outputs:

2011-10-01 17:48:10.526 Craplet[946:707] date: 2011-10-01 21:48:10 +0000
2011-10-01 17:48:10.527 Craplet[946:707] slot: 71
2011-10-01 17:48:14.335 Craplet[946:707] found show: Seinfeld
2011-10-01 17:48:14.336 Craplet[946:707] found show: Tonight Show
2011-10-01 17:48:21.335 Craplet[946:707] found show: Friends