Advertisement
Guest User

Untitled

a guest
Dec 21st, 2014
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.72 KB | None | 0 0
  1. //
  2. // CKLinkedList.m
  3. // CKLinkedList
  4. //
  5. // Created by Igor Rastvorov on 11/27/14.
  6. // Copyright (c) 2014 Igor Rastvorov. All rights reserved.
  7.  
  8. #import "CKLinkedList.h"
  9.  
  10. /**
  11. Represents a single node in a doubly linked list.
  12. */
  13. @interface CKListNode : NSObject
  14.  
  15. @property(nonatomic, strong) CKListNode *next;
  16. @property(nonatomic, strong) CKListNode *previous;
  17. @property(nonatomic, strong) id data;
  18.  
  19. -(id) initWithData:(id) data;
  20. -(BOOL) isEqual:(id)object;
  21.  
  22. @end
  23.  
  24. @implementation CKListNode
  25.  
  26. @synthesize next = _next;
  27. @synthesize data = _data;
  28.  
  29. -(id) initWithData:(id)data {
  30. self = [super init];
  31. if (self) {
  32. [self setData:data];
  33. }
  34.  
  35. return self;
  36. }
  37. -(BOOL) isEqual:(id)object {
  38. if (object != nil && [object isKindOfClass:[CKListNode class]]) {
  39. return [[self data] isEqual:[object data]];
  40. }
  41.  
  42. return NO;
  43. }
  44. -(NSString *) description {
  45. return [[self data] description];
  46. }
  47.  
  48. @end
  49.  
  50. @interface CKLinkedList ()
  51.  
  52. @property(nonatomic, readwrite) NSUInteger size;
  53.  
  54. -(CKListNode *) listNodeAtIndex:(NSUInteger) index;
  55. -(void) removeNodeAtIndex:(NSUInteger) index;
  56. @end
  57.  
  58. @implementation CKLinkedList
  59.  
  60. @synthesize size = _size;
  61.  
  62. #pragma mark - Initializing
  63.  
  64. -(instancetype) init {
  65. return [self initWithArray: nil];
  66. }
  67.  
  68. -(id) initWithArray:(NSArray *)array {
  69. self = [super init];
  70. if (self) {
  71. if (array != nil) {
  72. for (id object in array) {
  73. [self addObjectToTail:object];
  74. }
  75. }
  76. }
  77.  
  78. return self;
  79. }
  80.  
  81. #pragma mark - Adding objects
  82.  
  83. -(void) addObjectToHead:(id)object {
  84. CKListNode *listNode = [[CKListNode alloc] initWithData:object];
  85.  
  86. listNode.data = object;
  87. listNode.previous = nil;
  88. listNode.next = _head;
  89. _head.previous = listNode;
  90.  
  91. _head = listNode;
  92.  
  93. if ([self isEmpty]) {
  94. _tail = _head;
  95. }
  96.  
  97. ++self.size;
  98. }
  99.  
  100. #pragma mark - CKQueue
  101.  
  102. -(void) addObjectToTail:(id)object {
  103. CKListNode *listNode = [[CKListNode alloc] initWithData:object];
  104.  
  105. if ([self isEmpty]) {
  106. _head = listNode;
  107. _tail = _head;
  108.  
  109. listNode.previous = nil;
  110. } else {
  111. listNode.previous = _tail;
  112. }
  113.  
  114. listNode.next = nil;
  115. listNode.data = object;
  116.  
  117. _tail.next = listNode;
  118. _tail = listNode;
  119.  
  120. ++self.size;
  121. }
  122.  
  123. #pragma mark - Retrieving objects
  124.  
  125. -(id) objectAtTail {
  126. return [_tail data];
  127. }
  128. -(id) objectAtIndex:(NSUInteger) index {
  129. return [[self listNodeAtIndex:index] data];
  130. }
  131.  
  132. -(id <CKList>) sublistWithRange:(NSRange) range {
  133. id <CKList> sublist = [[CKLinkedList alloc] init];
  134.  
  135. NSUInteger endIndex = range.location + range.length;
  136. for (NSUInteger startIndex = range.location; startIndex <= endIndex; ++startIndex) {
  137. CKListNode *currentNode = [self listNodeAtIndex:startIndex];
  138. [sublist addObjectToTail: currentNode];
  139. }
  140.  
  141. return sublist;
  142. }
  143.  
  144. -(NSUInteger) indexOfObject:(id) object {
  145. NSUInteger size = [self size];
  146. for (NSUInteger index = 0; index <= size; ++index) {
  147. if ([[self objectAtIndex:index] isEqual:object]) {
  148. return index;
  149. }
  150. }
  151.  
  152. return NSNotFound;
  153. }
  154.  
  155. -(NSUInteger) lastIndexOfObject:(id) object {
  156. for (NSUInteger index = [self size] - 1; index != 0; --index) {
  157. if ([[self objectAtIndex:index] isEqual:object]) {
  158. return index;
  159. }
  160. }
  161.  
  162. return NSNotFound;
  163. }
  164.  
  165. #pragma mark - CKQueue
  166. -(id) objectAtHead {
  167. return [_head data];
  168. }
  169.  
  170. #pragma mark - Removing objects
  171.  
  172. -(void) removeObjectFromTail {
  173. [self removeObjectAtIndex: [self size] - 1];
  174. }
  175. -(void) removeObjectAtIndex:(NSUInteger) index {
  176. [self removeNodeAtIndex:index];
  177. --self.size;
  178. }
  179.  
  180. #pragma mark - CKQueue
  181. -(void) removeObjectFromHead {
  182. [self removeObjectAtIndex:0];
  183. }
  184.  
  185. #pragma mark - CKCollection
  186.  
  187. -(void) clear {
  188. for (NSUInteger listNodeIndex = 0; listNodeIndex <= [self size]; ++listNodeIndex) {
  189. [self removeObjectFromHead];
  190. }
  191. }
  192.  
  193. #pragma mark - List state
  194.  
  195. #pragma mark - CKCollection
  196.  
  197. -(BOOL) containsObject:(id) object {
  198. NSUInteger size = [self size];
  199. for (NSUInteger i = 0; i < size; ++i) {
  200. if ([[self objectAtIndex:i] isEqual:object]) {
  201. return YES;
  202. }
  203. }
  204.  
  205. return NO;
  206. }
  207.  
  208. -(NSString *) description {
  209. if ([self isEmpty]) {
  210. return @"(empty)";
  211. }
  212.  
  213. NSString *contents = [NSMutableString stringWithString:@"(n"];
  214.  
  215. NSUInteger listNodeIndex;
  216. for (listNodeIndex = 0; listNodeIndex < [self size] - 1; ++listNodeIndex) {
  217.  
  218. contents = [contents stringByAppendingString:[NSString stringWithFormat:@"t%@,n", [self listNodeAtIndex:listNodeIndex]]];
  219. }
  220. contents = [contents stringByAppendingString:[NSString stringWithFormat:@"t%@n)", [self listNodeAtIndex:listNodeIndex]]];
  221.  
  222. return contents;
  223. }
  224.  
  225. -(BOOL) isEmpty {
  226. return ([self size] == 0);
  227. }
  228.  
  229. -(BOOL) isEqual:(id) object {
  230. if (object != nil && [object isKindOfClass:[CKLinkedList class]]) {
  231. if ([self size] != [object size]) {
  232. return NO;
  233. }
  234.  
  235. CKListNode *listNode = nil;
  236. CKListNode *comparedListNode = nil;
  237.  
  238. for (NSUInteger listNodeIndex = 0; listNodeIndex < [self size]; ++listNodeIndex) {
  239. listNode = [self listNodeAtIndex:listNodeIndex];
  240. comparedListNode = [object listNodeAtIndex:listNodeIndex];
  241.  
  242. if (![listNode isEqual:comparedListNode]) {
  243. return NO;
  244. }
  245. }
  246. }
  247.  
  248. return YES;
  249. }
  250.  
  251. -(NSUInteger) hash {
  252. if ([self isEmpty]) {
  253. return [super hash];
  254. }
  255.  
  256. NSUInteger hashCode = [[self objectAtIndex:0] hash];;
  257. for (NSUInteger i = 1; i < [self size]; ++i) {
  258. hashCode ^= [[self objectAtIndex:i] hash];
  259. }
  260.  
  261. return hashCode;
  262. }
  263.  
  264. -(NSArray *) toArray {
  265. NSMutableArray *array = [NSMutableArray arrayWithCapacity:[self size]];
  266.  
  267. for (NSUInteger index = 0; index < [self size]; ++index) {
  268. [array addObject:[self objectAtIndex:index]];
  269. }
  270.  
  271. return array;
  272. }
  273.  
  274. // ---------------------------------
  275. // Private interface
  276. // ---------------------------------
  277.  
  278. -(CKListNode *) listNodeAtIndex:(NSUInteger) index {
  279. if (index >= [self size] ) {
  280. return nil;
  281. }
  282.  
  283. CKListNode *listNode = _head;
  284. for (NSUInteger listNodeIndex = 0; listNodeIndex < index; ++listNodeIndex) {
  285. listNode = [listNode next];
  286. }
  287.  
  288. return listNode;
  289. }
  290.  
  291. -(void) removeNodeAtIndex:(NSUInteger) index {
  292. CKListNode *deallocationTarget = [self listNodeAtIndex:index];
  293.  
  294. if (deallocationTarget == nil) {
  295. return;
  296. }
  297.  
  298. if (deallocationTarget == _head) {
  299. _head = deallocationTarget.next;
  300. } else if (deallocationTarget == _tail) {
  301. _tail = deallocationTarget.previous;
  302. } else {
  303. deallocationTarget.previous.next = deallocationTarget.next;
  304. deallocationTarget.next.previous = deallocationTarget.previous;
  305. }
  306.  
  307. deallocationTarget = nil;
  308. }
  309.  
  310. @end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement