Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 229 lines (193 sloc) 5.208 kb
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
1 /*
2 // CWLinkedList.m
3 // Zangetsu
4 //
5 // Created by Colin Wheeler on 4/26/12.
6 // Copyright (c) 2012. All rights reserved.
7 //
8
9
10 Copyright (c) 2012 Colin Wheeler
11
12 Permission is hereby granted, free of charge, to any person obtaining a copy
13 of this software and associated documentation files (the "Software"), to deal
14 in the Software without restriction, including without limitation the rights
15 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 copies of the Software, and to permit persons to whom the Software is
17 furnished to do so, subject to the following conditions:
18
19 The above copyright notice and this permission notice shall be included in
20 all copies or substantial portions of the Software.
21
22 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
28 THE SOFTWARE.
29 */
30
31 #import "CWLinkedList.h"
32
33 @interface CWLinkedListNode : NSObject
1d53c20 Colin Wheeler removing nonatomic from properties, will reapply in individual cases aga...
authored
34 @property(retain) CWLinkedListNode *next;
35 @property(retain) id data;
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
36 @end
37
38 @implementation CWLinkedListNode
39
40 - (id)init
41 {
42 self = [super init];
43 if (self) {
44 _next = nil;
45 _data = nil;
46 }
47 return self;
48 }
49
50 @end
51
52 @interface CWLinkedList ()
53 @property(readwrite,assign) NSUInteger count;
1d53c20 Colin Wheeler removing nonatomic from properties, will reapply in individual cases aga...
authored
54 @property(retain) CWLinkedListNode *head;
55 @property(weak) CWLinkedListNode *tail;
0335043 Colin Wheeler isolating error code into its own method for objectAtIndex
authored
56 -(BOOL)hasErrorForObjectAtIndex:(NSUInteger)index;
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
57 @end
58
59 @implementation CWLinkedList
60
61 - (id)init
62 {
63 self = [super init];
64 if (self) {
65 _head = nil;
66 _tail = nil;
67 _count = 0;
68 }
69 return self;
70 }
71
72 -(void)addObject:(id)anObject
73 {
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
74 if(!anObject) { return; }
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
75
76 CWLinkedListNode *node = [[CWLinkedListNode alloc] init];
77 node.data = anObject;
78
79 if (self.head) {
80 self.tail.next = node;
81 self.tail = node;
82 } else {
83 self.head = node;
84 self.tail = node;
85 }
86
87 self.count++;
88 }
89
4fdc20e Colin Wheeler new api -[CWLinkedList insertObject:atIndex]
authored
90 -(void)insertObject:(id)anObject atIndex:(NSUInteger)index
91 {
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
92 if(!anObject) { return; }
93
94 if (index > (self.count - 1)) {
95 NSError *error = CWCreateError(@"com.Zangetsu.CWLinkedList", 443,
96 @"Trying to retrieve an item beyond list bounds");
97 CWLogError(error);
4fdc20e Colin Wheeler new api -[CWLinkedList insertObject:atIndex]
authored
98 return;
99 }
100
101 if (index == 0) {
102 CWLinkedListNode *node = [[CWLinkedListNode alloc] init];
103 node.data = anObject;
104 node.next = self.head;
105 self.head = node;
eb11a43 Colin Wheeler Fixes an issue where linked list count did not increment when using inse...
authored
106 self.count++;
4fdc20e Colin Wheeler new api -[CWLinkedList insertObject:atIndex]
authored
107 } else {
108 NSUInteger current = 0;
109 CWLinkedListNode *node = self.head;
110 while (current != (index - 1)) {
111 node = node.next;
112 current++;
113 }
114 CWLinkedListNode *insertNode = [[CWLinkedListNode alloc] init];
115 insertNode.data = anObject;
116 insertNode.next = node.next;
117 node.next = insertNode;
eb11a43 Colin Wheeler Fixes an issue where linked list count did not increment when using inse...
authored
118 self.count++;
4fdc20e Colin Wheeler new api -[CWLinkedList insertObject:atIndex]
authored
119 }
120 }
121
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
122 -(void)removeObjectAtIndex:(NSUInteger)index
123 {
a8beb9c Colin Wheeler removing redundant if test
authored
124 if (index > (self.count - 1)) {
125 NSError *error = CWCreateError(@"com.Zangetsu.CWLinkedList", 443,
126 @"Trying to retrieve an item beyond list bounds");
127 CWLogError(error);
128 return;
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
129 }
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
130
131 if (index == 0) {
132 if (self.count > 1) {
133 self.head = self.head.next;
134 } else {
135 self.head = nil;
a2c0c70 Colin Wheeler misc improvements
authored
136 self.tail = nil;
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
137 }
138 self.count--;
139 return;
140 }
141
142 NSUInteger current = 0;
143 CWLinkedListNode *node = self.head;
144 while (current != ( index - 1 )) {
145 node = node.next;
146 current++;
147 }
148
149 node.next = node.next.next;
150 self.count--;
151 }
152
dc27b02 Colin Wheeler new api -[CWLinkedList removeObject:]
authored
153 -(void)removeObject:(id)object
154 {
0c73be5 Colin Wheeler if object is nil then return early
authored
155 if((!self.head) || (!object)) { return; }
dc27b02 Colin Wheeler new api -[CWLinkedList removeObject:]
authored
156 NSUInteger index = 0;
157 NSUInteger max = (self.count - 1);
158 CWLinkedListNode *currentNode = self.head;
159
160 if ([currentNode.data isEqual:object]) {
161 [self removeObjectAtIndex:0];
162 return;
163 }
164
165 do {
166 CWLinkedListNode *nextNode = currentNode.next;
167 if ([nextNode.data isEqual:object]) {
168 currentNode.next = currentNode.next.next;
169 nextNode.next = nil;
170 self.count--;
171 return;
172 }
173 currentNode = currentNode.next;
174 index++;
175 } while ((index < max) && currentNode);
176 }
177
0335043 Colin Wheeler isolating error code into its own method for objectAtIndex
authored
178 -(BOOL)hasErrorForObjectAtIndex:(NSUInteger)index
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
179 {
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
180 if (!self.head) {
181 NSError *error = CWCreateError(@"com.Zangetsu.CWLinkedList", 442,
182 @"Trying to retrieve a item with an index in an empty list");
183 CWLogError(error);
0335043 Colin Wheeler isolating error code into its own method for objectAtIndex
authored
184 return YES;
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
185 }
186 if (index > (self.count - 1)) {
187 NSError *error = CWCreateError(@"com.Zangetsu.CWLinkedList", 443,
188 @"Trying to retrieve an item beyond list bounds");
189 CWLogError(error);
0335043 Colin Wheeler isolating error code into its own method for objectAtIndex
authored
190 return YES;
191 }
192 return NO;
193 }
194
195 -(id)objectAtIndex:(NSUInteger)index
196 {
197 if ([self hasErrorForObjectAtIndex:index]) {
d7c0a3e Colin Wheeler instead of throwing exceptions CWLinkedList will now log error messages
authored
198 return nil;
199 }
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
200
201 NSUInteger current = 0;
202 CWLinkedListNode *currentNode = self.head;
203
204 while (current != index) {
205 currentNode = currentNode.next;
206 current++;
207 }
208
209 return currentNode.data;
210 }
211
40243ba Colin Wheeler new api -[CWLinkedList enumerateObjectsWithBlock:]
authored
212 -(void)enumerateObjectsWithBlock:(void(^)(id object, BOOL *stop))block
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
213 {
40243ba Colin Wheeler new api -[CWLinkedList enumerateObjectsWithBlock:]
authored
214 if(!self.head) { return; }
215 BOOL shouldStop = NO;
216 NSUInteger index = 0;
217 NSUInteger max = self.count;
218 CWLinkedListNode *currentNode = self.head;
219
220 while ((index < max) && currentNode) {
221 block(currentNode.data, &shouldStop);
222 if(shouldStop == YES) { return; }
223 currentNode = currentNode.next;
224 index++;
225 }
226 }
227
e66bd2a Colin Wheeler new data structure api CWLinkedList
authored
228 @end
Something went wrong with that request. Please try again.