1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
/*
* Copyright (C) 2005 Stefan Kleine Stegemann
*
* The sources from MissigKit are not released under any particular
* license. Do with them what ever you want to do. Include them in
* your projects, use MissingKit standalone or simply ignore it.
* Whatever you do, keep in mind the this piece of software may
* have errors and that it is distributed WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE.
*/
#ifndef _H_MKLINKEDLIST
#define _H_MKLINKEDLIST
#import <Foundation/Foundation.h>
@class MKLinkedListElement;
/**
* A very simple but convenient implementation of a linked
* list ADT. Elements of the List are decorated with an
* MKLinkedListElement that maintains the additional informations
* for the list structure.
*/
@interface MKLinkedList : NSObject
{
MKLinkedListElement* first;
MKLinkedListElement* last;
unsigned size;
}
/** Create a new, empty list. */
- (id) init;
/** Append the object at the end of the list. The object becomes the
* last element of the list. Returns the new MKLinkedListElement that
* is created for the object. The object is retained by the list. */
- (MKLinkedListElement*) addObject: (id)anObject;
/** Insert an object before another object in the list. Returns the
* MKLinkedListElement that is created for anObject. The object is
* retained by the list. */
- (MKLinkedListElement*) insertObject: (id)anObject
before: (MKLinkedListElement*)anElement;
/** Shortcut for
* [list insertObject: anObject before: [list elementAtIndex: anIndex]] */
- (MKLinkedListElement*) insertObject: (id)anObject
beforeElementAtIndex: (unsigned)anIndex;
/** Remove an element from the list. The element and the element's object
* are released. */
- (void) remove: (MKLinkedListElement*)anElement;
/** Get the number of elements in the receiver. */
- (unsigned) count;
/** Get the first element in the list. */
- (MKLinkedListElement*) first;
/** Shortcut for [[list first] object]. */
- (id) firstObject;
/** Get the last element in the list. */
- (MKLinkedListElement*) last;
/** Shortcut for [[list last] object]. */
- (id) lastObject;
/** Get the a particular element from the list. Warning: this method
* method has a worse performance because the elements of the list
* are traversed in sequential order until the desired element has
* been found. The worst case performance for this method is O(n/2)
* where n is the size of the list. */
- (MKLinkedListElement*) elementAtIndex: (unsigned)anIndex;
/** Shortcut for [[list elementAtIndex: anIndex] object]. See elementAtIndex
* for more informations. */
- (id) objectAtIndex: (int)anIndex;
/** Make an element the last element of the list. The element that
* is currently at the last position will become the predecessor
* of the new last element. */
- (void) makeLast: (MKLinkedListElement*) anElement;
/** Make an element the first element of the list. The element that
* is currently at the first position will become the successor of
* the new first element. */
- (void) makeFirst: (MKLinkedListElement*) anElement;
@end
/**
* When an object is inserted into an MKLinkedList, a corresponding
* MKLinkedListElement is created that holds the element and some
* more informations which allows the list to maintain it's structure.
*
* Note that it is not possible to create an MKLinkedListElement
* explicitly. Creation (and also deletion) of MKLinkedListElements
* is always done by an MKLinkedList.
*/
@interface MKLinkedListElement : NSObject
{
id object;
MKLinkedList* list;
MKLinkedListElement* previous;
MKLinkedListElement* next;
}
/** Get the object that is decorated by the receiver. */
- (id) object;
/** Set the object that is decorated by the receiver. This will send
* a release message to the current object and a retain message to
* anObject. */
- (void) setObject: (id)anObject;
/** Get the previous element in the list the receiver belongs to. Returns
* nil if this element is at the beginning of the list. */
- (MKLinkedListElement*) previous;
/** Get the next element in the list the receiver belongs to. Returns nil
* if this element is at the end of the list. */
- (MKLinkedListElement*) next;
/** Get the list the receiver belongs to. */
- (MKLinkedList*) list;
@end
#endif
|
