GNUstep on 64-bit Linux - what a pain in the ass!

Oh good lord how much of a pain in the ass this has been. Just trying to get GNUstep on the Linux cluster so I can run my stuff. I decided to do my RPE in Objective-C, which is an (old) language Apple has been pushing for a while. I knew gcc would compile Objective-C code, so I figured why not? MISTAKE! Objective-C is not the problem, having the free Cocoa user-space environment (GNUstep) around it is! It's compiling now for maybe the billionth time. Hopefully it'll finish this time. Then I can post how do it (it's easy - if you find the right web page).

Cocoa / Objective-C Priority Queue

K - one more problem. For my project, I was looking for a quick Objective-C or Cocoa priority queue implementation. You'd think they'd have one, but no. I tried googling, and I did find some stuff, but everything was zip files you had to download to open. Too much of a pain in the ass for me. So I broke open the CLRS book to find priority queues. Here's my quick implementation of a priority queue in Cocoa / Objective-C.

-(id)init
{
    [super init];
    q = [[NSMutableArray alloc] init];
    return self;
}

- (void)insertEvent:(Event *)item
{
    int index;
    
    [q addObject:item];
    
    index = [q count] - 1;
    
    // Maintain heap-ness
    while(YES) {
        if([q objectAtIndex:index] < [q objectAtIndex:((index - 1)/ 2)]) {
            [q exchangeObjectAtIndex:index withObjectAtIndex:((index - 1)/ 2)];
            index = (index - 1)/ 2;
        }
        else
            break;
    }
}

- (id)getNextEvent
{
    // Exchange the first element with the last element to save
    // the cost of moving them all forward and then re-heaping it
    Event *e;

    int size;
    
    size = [q count];
    
    if(size == 0) 
        return nil;
    
    [q exchangeObjectAtIndex:0 withObjectAtIndex:(size - 1)];
    e = [[q objectAtIndex:(size - 1)] retain];
    
    [q removeLastObject];

    // Now one of 0 or 1 are the next min...
    // If there are 0 or 1
    [self heapify:0];
    // Do the update to maintain heap property
    return e;
}

- (void)heapify:(int)i
{
    int left, right;
    int min;
    int max_index = [q count] - 1;
    
    left = 2 * i + 1;
    right = 2 * i + 2;
    
    if(left < max_index && [q objectAtIndex:left] < [q objectAtIndex:i]) {
        min = left;
    }
    else
    {
        min = i;
    }
    
    if(right < max_index && [q objectAtIndex:right] < [q objectAtIndex:min]) {
        min = right;
    }
    
    if(min != i) {
        [q exchangeObjectAtIndex:i withObjectAtIndex:min];
        [self heapify:min];
    }
}

Hopefully I didn't make any mistakes - I modified this slightly from my code because there was a little more stuff in my priority queue than I put here, but overall, it should be enough to get you started.

As an aside, priority queues are really neat and are a clear example of the usefulness of analysis and big-oh notation. For example, insertEvent is O(log n), getNextEvent is O(1) but it calls heapify which is O(log n). So actually any operation you do on a priority queue is an O(log n) operation - a very attractive property.

I could have used this priority queue implementation but I would have had to download a .zip file which is a pain in the ass. This guy left it as an exercise to the reader which is nice but didn't help me much. So... here's my solution. Let me know if it helps and for God's sakes if there's any bugs PLEASE let me know! Thanks.