Using Objective-C's dynamic runtime behaviour

Originally posted by Dan on 08:09 Wed 19 September 2007, last modified 12:43 Thu 6 November 2008.

File under: objective-c os x programming

I need to store some objects in a linked list. Objective-C has a number of container classes NSArray, NSDictionary and NSSet - but I really want a linked list. As I come to Objective-C from a C++ background, I was thinking that this would be where I would use templates, so that I can store any type of object in my container. But Objective-C doesn't use templates, it does however have id.

Objective-C has an id type; this can represent any type of object. The actual type of the object is then determined at runtime, so we can use it to make a generic container. First we need an object that will be a node in the linked list:

#import <Cocoa/Cocoa.h>

@interface ListNode : NSObject {
    id data;
    ListNode *next;
    ListNode *prev;
}

- (id)initWithObject:(id)object;

- (id)data;
- (ListNode *)next;
- (ListNode *)prev;
- (void)setNext:(ListNode *)object;
- (void)setPrev:(ListNode *)object;
@end

So, this is pretty simple really, we just store whatever object that we want in the ListNode's data attribute. This even means that we can have a linked list of different types of objects. We also need an object that is going to organise the list, and allow us to iterate through it:

@interface LinkedList : NSObject {
    ListNode *head;
    ListNode *tail;
    ListNode *iterator;
    int size;
}

- (id)initWithObject:(id)object;

- (void)addToFront:(id)object;
- (void)addToBack:(id)object;
- (void)insertInFront:(id)object;
- (void)insertBehind:(id)object;
- (void)removeCurrent;

- (id)getFront;
- (id)getBack;
- (id)getCurrent;
- (id)getNext;
- (id)getPrevious;

- (int)size;
- (BOOL)atTail;
- (BOOL)atHead;

@end

The implementation is fairly obvious:

#import "LinkedList.h"

@implementation ListNode

- (id)initWithObject:(id)object {
    self = [super init];
    if(self != nil) {   
        [object retain];
        data = object;
        next = nil;
        prev = nil;
    }   
    return self;        
}

- (void)dealloc {
    [data release];
    [next release];
    [prev release];
    [super dealloc];
}

- (id)data          { return data; }
- (ListNode *)next  { return next; }
- (ListNode *)prev  { return prev; }

- (void)setNext:(ListNode *)object {
    [object retain];
    if(next != nil) { [next release]; }
    next = object;
}

- (void)setPrev:(ListNode *)object {
    [object retain];
    if(prev != nil) { [prev release]; }
    prev = object;  
}

@end


@implementation LinkedList

- (id)initWithObject:(id)object {
    self = [super init];
    if(self != nil) {   
        head = [[ListNode alloc] initWithObject:object];
        tail = head;
        [self getFront];
        size = 1;
    }   
    return self;        
}

- (void)dealloc {
    while([self getNext] != nil) {
        [self removeCurrent];
    }   
    [head release];
    [tail release];
    [iterator release];
    [super dealloc];
}


- (void)addToFront:(id)object {
    ListNode *node = [[ListNode alloc] initWithObject:object];
    [node setNext:head];
    [head setPrev:node];
    size += 1;
    head = node;    
}
- (void)addToBack:(id)object {
    ListNode *node = [[ListNode alloc] initWithObject:object];
    [node setPrev:tail];
    [tail setNext:node];
    size += 1;
    tail = node;    
}

- (void)insertInFront:(id)object {
    if([iterator next] == nil) {
        // we're at the front?
        [self addToFront:object];
    } else {
        ListNode *node = [[ListNode alloc] initWithObject:object];
        [node setPrev:iterator];
        [node setNext:[iterator next]];
        [[iterator next] setPrev:node];
        [iterator setNext:node];
        size += 1;
        iterator = node;    
    }
}
- (void)insertBehind:(id)object {
    if([iterator prev] == nil) {
        // this means we're at the end
        [self addToBack:object];
    } else {
        ListNode *node = [[ListNode alloc] initWithObject:object];
        [node setPrev:[iterator prev]];
        [node setNext:iterator];
        [[iterator prev] setNext:node];
        [iterator setPrev:node];
        size += 1;
        iterator = node;        
    }
}


- (id)getFront {
    iterator = head;
    return [head data];
}
- (id)getBack {
    iterator = tail;
    return [tail data];
}
- (id)getCurrent {
    return [iterator data];
}
- (id)getNext {
    if([iterator next] != nil) {
        iterator = [iterator next];
        return [iterator data];
    } else {
        return nil; 
    }

}
- (id)getPrevious {
    if([iterator prev] != nil) {
        iterator = [iterator prev];
        return [iterator data];
    } else {
        return nil;
    }
}

- (int)size {
    return size;
}

- (BOOL)atTail {
    if(iterator == tail) {
        return YES;
    } else if([iterator next] == nil) {
        return YES;
    } else {
        return NO;
    }
}
- (BOOL)atHead {
    if(iterator == head) {
        return YES;
    } else if([iterator prev] == nil) {
        return YES;
    } else {
        return NO;
    }
    
}


- (void)removeCurrent {
    /* When we remove a node, then we set the next 
       pointer of this previous, to this next, and visa versa */
    
    if( ([iterator next] == nil) && ([iterator prev] == nil) ) {
        // this is the last node
        [iterator release];
        head = tail = nil;      
        iterator = nil;
    }
    
    ListNode *l;
    l = iterator;
    if([iterator prev] != nil) {
        [[iterator next] setPrev:[iterator prev]];      
    }   
    if([iterator next] != nil) {
        [[iterator prev] setNext:[iterator next]];
    }
    iterator = ([iterator next] != nil) ? [iterator next] : [iterator prev];
    [l release];
    size -= 1;
}


@end

That should all be more or less self explanatory. When you want to create your linked list then the code is very simple. In the following (single) line of code, we creating a LinkedList with a single node in it, which will contain an InfluenzaSample object:

// Set the Influenza Sample
fluBrowser = [[LinkedList alloc] initWithObject:[[InfluenzaSample alloc] 
        initWithDate:[NSCalendarDate dateWithString:[queryDate description]]]];

comment

Recent posts / Archive

Categories

Using Objective-C's dynamic runtime behaviour