LRUCache with constant access time for reading and writing

gistfile1.m

//
//  LRUCache.m
//  ObjCAlg
//
//  Created by Tomasz Kuzma on 20/02/2015.
//



#import <Foundation/Foundation.h>
#import <Cocoa/Cocoa.h>

@interface LRUCache : NSObject
-(instancetype)initWithCapacity:(NSUInteger)capacity;
-(id)getObjectForKey:(id<NSCopying>)key;
-(void)setObject:(id)object forKey:(id<NSCopying>)key;
@end



@interface _LRUNode : NSObject
@property (nonatomic, strong) id object;
@property (nonatomic, strong) id<NSCopying> key;
@property (nonatomic, strong) _LRUNode *prev;
@property (nonatomic, strong) _LRUNode *next;

@end

@implementation _LRUNode : NSObject
- (NSString *)description{
    return [NSString stringWithFormat:@"(key:%@ object:%@)",self.key,self.object];
}
@end

@implementation LRUCache{
    NSMutableDictionary *_dict;
    NSInteger _capacity;
    _LRUNode *_head;
    _LRUNode *_tail;
}

-(instancetype)initWithCapacity:(NSUInteger)capacity{
    self = [super init];
    
    if(!self){
        return nil;
    }
    
    _capacity = capacity;
    _dict = [NSMutableDictionary new];
    
    return self;
}

-(id)getObjectForKey:(id<NSCopying>)key{
    if(!key){
        return nil;
    }
    
    _LRUNode *node = _dict[key];
    
    if (!node) {
        return nil;
    }
    
    if (node != _tail) {
        _LRUNode *prev = node.prev;
        _LRUNode *next = node.next;
        if (prev) {
            prev.next = next;
            next.prev = prev;
        }
        else{
            next.prev = nil;
            _head = next;
        }
        
        _tail.next = node;
        node.prev = _tail;
        _tail = node;
        node.next = nil;
    }
    
    
    return node.object;
}

-(void)setObject:(id)object forKey:(id<NSCopying>)key{
    if (!object || !key){
        return ;
    }
    
    _LRUNode *node = [_LRUNode new];
    node.object = object;
    node.key = key;
    
    if(_dict.count < _capacity){

        if (!_tail && !_head) {
            _head = node;
        }
        else if (!_tail){
            _tail = node;
            _tail.prev = _head;
            _head.next = node;
        }
        else{
            _tail.next = node;
            node.prev = _tail;
            _tail = node;
        }
        _dict[key] = node;
        
    }
    else{
        _LRUNode *second = _head.next;
        second.prev = nil;
        [_dict removeObjectForKey:_head.key];
        _head = second;

        _tail.next = node;
        node.prev = _tail;
        _tail = node;
        
        _dict[key] = node;
    }
    
}

- (NSString *)description{
    NSMutableArray *list = [NSMutableArray new];
    _LRUNode *node = _head;
    
    while (YES) {
        [list addObject:node.description];
        
        
        if (!node.next) {
            break;
        }
        
        node = node.next;

    }
    
    return [NSString stringWithFormat:@"%@, dict:%@, list:%@",super.description,
            _dict,[list componentsJoinedByString:@" - "]];
}
@end

int main(int argc, char *argv[]) {
    @autoreleasepool {
        
        LRUCache *cache = [[LRUCache alloc] initWithCapacity:5];
        
        [cache setObject:@"1" forKey:@"a"];
        [cache setObject:@"2" forKey:@"b"];
        [cache setObject:@"3" forKey:@"c"];
        [cache setObject:@"4" forKey:@"d"];
        [cache setObject:@"5" forKey:@"e"];
        NSLog(@"cache:\r%@ ",cache.description);
        
        
        assert([[cache getObjectForKey:@"a"] isEqualToString:@"1"]);
        NSLog(@"cache:\r%@ ",cache.description);
        [cache setObject:@"6" forKey:@"f"];
        NSLog(@"cache:\r%@ ",cache.description);
        assert([cache getObjectForKey:@"b"] == nil);
        
        [cache setObject:@"7" forKey:@"g"];
        NSLog(@"cache:\r%@ ",cache.description);
        assert([cache getObjectForKey:@"c"] == nil);
        
        assert([[cache getObjectForKey:@"a"] isEqualToString:@"1"]);
        NSLog(@"cache:\r%@ ",cache.description);
        
        [cache setObject:@"8" forKey:@"h"];
        NSLog(@"cache:\r%@ ",cache.description);
        assert([cache getObjectForKey:@"d"] == nil);
    }
    NSLog(@"test passed");
}