This is MiscLinkedList.rtf in view mode; [Download] [Up]
Release 0.9 Copyright ©1994 by Don Yacktman. All Rights Reserved. MiscLinkedList Inherits From: Object Declared In: misckit/MiscLinkedList.h Protocols: NXTransport Class Description The MiscLinkedList is an implementation of a doubly-linked list. This type of data structure is useful for storing sparse data that will be traversed often. (Linked lists are very memory efficient when dealing with sparse data, unlike hashing and some array schemes.) If fast random access is desired, a linked list may not be suitable for the application. The MiscLinkedList is much faster than the NeXT List object for insertion and deletion, but it suffers in performance when searching for a specific node (random access). Traversing the List from one end to the other is about the same, but slightly faster for the NeXT List object. The MiscLinkedList can store any type of objectsÐor a mixture of different object types. A single object may be stored in the list in multiple places, as well. Using a MiscLinkedList is simple. First create a new list using the standard +alloc and ±init methods. Once created, the list has references to both the start and the end of the list as well as a pointer to the ªcurrentº node. The pointer to the current node is akin to a cursor: most operations on the MiscLinkedList will occur at this node or immediately before or after it. To add objects to a MiscLinkedList, use the ±insertObjectAfter: or ±insertObjectBefore methods. They will insert the object either before or after the current node in the list. You can also insert a complete MiscLinkedList or a List into a MiscLinkedList. To do this, use one of the ±insertList:, ±insertListAtFront:, and ±appendList: methods. To remove an object, use ±deleteObject. You can also change the ordering of nodes in the list. A node my be swapped with it's neighbor with either ±swapWithNext or ±swapWithPrevious. A node may be moved to the front or end of the list by using ±moveToFirst or ±moveToLast. The current object may be replaced with a new object by using the ±setObject: method. To traverse the list, use ±goFirst, ±goLast, ±goNext, or ±goPrevious. Note that many of the methods which traverse the list might alter the current node; this is documented below for every method in which it occurs. All objects in a MiscLinkedList may be broadcast a messgae with ±makeObjectsPerform: and ±makeObjectsPerform:with:. You can find out how many objects are in the MiscLinkedList via the ±count or ±getLength methods. (They are identical.) There are also several methods which are similiar to the List object. You can compare lists with the ±isEqual method. You can replace and remove objects, given their id, with ±replaceObject:with: and ±removeObject: respectively. You can add objects uniquely with ±addObjectIfAbsent:. For convenience, there are also methods to operate on the front and end of a MiscLinkedList: ±firstObject, ±removeFirstObject, ±lastObject, and ±removeLastObject. You can also use ±addObject: to append objects to a MiscLinkedList. A MiscLinkedList implements the NXTransport protocol, allowing it to be copied over a Distributed Objects connection. It also understands ±read: and ±write: which allows it to be archived to a stream. Internally, the MiscLinkedList uses a special class, the MiscLinkedListNode, to keep track of the actual list. Each node contains a pointer to the next and previous node and a pointer to the object it contains. Normally you won't need to worry about these nodes; their use allows any kind of object to be added to the list without it needing to know about linked lists and it allows an object to appear in the list multiple times. (This is better than requiring an object to have pointers to the next and previous object itself.) If you need to add special capabilities to a MiscLinkedList, however, you may wish to subclass the MiscLinkedListNode to facilitate this. See the documentation for that class if you need more information about this. The MiscLinkedList may be initialized to deal with a different node class by using the ±initForClass: method. You can access the current node object, rather than the object it contains, with the ±getNode method. Under normal circumstances, this shouldn't ever be necessary. When you are finished with the MiscLinkedList, you can free it with ±free, which frees the MiscLinkedList and it's nodes, but not the objects it contains. If you wish to free the objects, first send a ±freeObjects message Note that it is unwise to send -freeObjects if an object appears in the list more than once, since the MiscLinkedList will attempt to free the object more than once. The ±empty method will empty out a MiscLinkedList without freeing the objects it contains (but it will free the nodes). Instance Variables id current_node; id first_node; id last_node; id node_class; int node_length; current_node Pointer to the ªcurrentº node in the list. Most actions are performed in the vicinity of the node this points to. first_node Pointer to the last node of the list. last_node Pointer to the last node of the list. node_class The class object used to create new nodes; this should ideally be either a MiscLinkedListNode subclass or respond to all the same methods as the MiscLinkedListNode, since MiscLinkedList doesn't check ±respondsTo:. node_length The number of nodes (objects) in the MiscLinkedList Method Types Initializing and freeing ± empty ± freeNodes ± freeObjects ± init ± initForClass: Getting size ± count ± getLength Changing which is the current node ± firstObject ± goFirst ± goLast ± goNext ± goPrevious ± lastObject Manipulating the current node ± getNode ± getObject ± moveToFirst ± moveToLast ± setObject: ± swapWithNext ± swapWithPrevious Adding and deleting objects ± addObject: ± addObjectIfAbsent: ± deleteObject ± insertObjectAfter: ± insertObjectBefore: ± removeLastObject ± removeFirstObject ± removeObject: ± replaceObject: Adding an entire MiscLinkedList ± appendList: ± insertList: ± insertListAtFront: Comparing MiscLinkedLists ± isEqual: Sending messages to the objects ± makeObjectsPerform: ± makeObjectsPerform:with: Archiving a MiscLinkedList ± read: ± write: Instance Methods addObject: - addObject:anObject Adds anObject to the end of the list. Returns self. See also: -addObjectIfAbsent: and ±removeObject: addObjectIfAbsent: - addObjectIfAbsent:anObject Adds anObject to the end of the list if anObject is not already anywhere in the list. Returns self. See also: -addObject: and ±removeObject: appendList: - appendList:this_list Insert the list this_list after the last node of the receiving list. The objects that were in this_list are left in the same order when inserted into the receiver. The list this_list is left unchanged. The list this_list may be either a MiscLinkedList, a List, or subclasses thereof. Returns self. See also: -insertList: and ±insertListAtFront: count - (unsigned int)count Returns the number of objects (nodes) in the list. See also: -getLength deleteObject - deleteObject Deletes the current node and object. The node previous to the deleted node becomes the current node unless the deleted node was the first node. In that case, the first node in the list will be the current node. Returns self. See also: ±removeFirstObject, ±removeLastObject, and ±removeObject: empty - empty Empties the list of all objects and frees all the nodes that made up the list. The objects in the list are not freed. See also: ±free, ±freeObjects, and -freeNodes firstObject - firstObject Returns the first object in the list. See also: ±getObject and -lastObject free - free Frees all the nodes in the list and the list itself. See also: ±empty, ±free, and -freeNodes freeObjects - freeObjects Frees all the objects in the list and the nodes associated with them. Returns self. See also: ±empty, ±free, and -freeNodes freeNodes - freeNodes Frees all the nodes in the receiver but does not free the objects that were in the nodes. Returns self. See also: ±empty, ±free, and -freeObjects getLength - (int)getLength Returns the number of objects (nodes) in the list. See also: -count getNode - getNode Returns the current node. Under most circumstances you shouldn't need to use this method. See also: -getObject getObject - getObject Returns the object stored in the current node. See also: ±firstObject, -getNode, and ±lastObject goFirst - goFirst Make the first node of the list the current node. Returns nil if there are no objects in the list, otherwise returns self. See also: ±goLast, ±goNext, and ±goPrevious goLast - goLast Make the last node of the list the current node. Returns nil if there are no objects in the list, otherwise returns self. See also: -goFirst, ±goNext, and ±goPrevious goNext - goNext Make the node after the current node become the current node. If already at the end of the list, nil is returned. Otherwise, returns self. See also: -goFirst, ±goLast, and ±goPrevious goPrevious - goPrevious Make the node before the current node become the current node. If already at the start of the list, nil is returned. Otherwise, returns self. See also: -goFirst, ±goLast, and ±goNext init - init Initialize the receiving instance of MiscLinkedList with the MiscLinkedListNode class as the class used to create new nodes in the list. Returns self. See also: -initForClass: initForClass: - initForClass:this_class Initialize the receiving instance of MiscLinkedList with the class this_class as the class used to create new nodes in the list. Returns self. See also: -init insertList: - insertList:this_list Insert the list this_list before the current node of the receiving list. The objects that were in this_list are left in the same order when inserted into the receiver. The list this_list is left unchanged. The list this_list may be either a MiscLinkedList, a List, or subclasses thereof. Returns self. See also: -appendList: and ±insertListAtFront: insertListAtFront: - insertListAtFront:this_list Insert the list this_list at the front of the receiving list. The objects that were in this_list are left in the same order when inserted into the receiver. The list this_list is left unchanged. The list this_list may be either a MiscLinkedList, a List, or subclasses thereof. Returns self. See also: -appendList: and ±insertList: insertObjectAfter: - insertObjectAfter:this_object Insert this_object into the list after the current object/node. Returns this_object. See also: -insertObjectBefore: insertObjectBefore: - insertObjectBefore:this_object Insert this_object into the list before the current object/node. Returns this_object. See also: -insertObjectAfter: isEqual: - (BOOL)isEqual:anObject Returns YES if anObject is the same class as the receiver and contains the exact same set of objects as determined by sending ±isEqual: to each of the objects in the list. Returns NO otherwise. lastObject - lastObject Returns the last object in the list. See also: -firstObject and -getObject makeObjectsPerform: - makeObjectsPerform:(SEL)aSelector Traverses the list from the first to the last node, sending the aSelector message to each object in the list. Returns self. See also: -makeObjectsPerform:with: makeObjectsPerform:with: - makeObjectsPerform:(SEL)aSelector with:anObject Traverses the list from the first to the last node, sending the aSelector message with the argument anObject to each object in the list. Returns self. See also: -makeObjectsPerform: moveToFirst - moveToFirst Moves the current node to the front of the MiscLinkedList. Returns self. If there is no current node, then nil is returned. See also: -moveToLast, -swapWithPrevious, and -swapWithNext moveToLast - moveToLast Moves the current node to the end of the MiscLinkedList. Returns self. If there is no current node, then nil is returned. See also: -moveToFirst, -swapWithPrevious, and -swapWithNext read: - read:(NXTypedStream *)stream Unarchives the receiving MiscLinkedList and all the objects it contains from stream. Returns self. See also: -write: removeFirstObject - removeFirstObject Removes the first object from the list. The removed object is returned. See also: ±deleteObject, ±removeLastObject, and ±removeObject: removeLastObject - removeLastObject Removes the last object from the list. The removed object is returned. See also: ±deleteObject, ±removeFirstObject, and ±removeObject: removeObject: - removeObject:anObject Searches through the list for the first occurrence of anObject and removes it from the list. Returns anObject. See also: -addObject:, -addObjectIfAbsent:, ±deleteObject, ±removeFirstObject, and ±removeLastObject replaceObject:with: - replaceObject:anObject with:newObject Searches from the start of the list for the first occurrence of anObject and replaces it with newObject. Returns anObject. This method will change the current node; the replaced object's node becomes the new current node. See also: -setObject: setObject: - setObject:this_object Sets the object in the current node to this_object. Returns the object which was replaced. See also: -replaceObject:with: swapWithNext - swapWithNext Swaps the current node with the node just after of it the MiscLinkedList. Returns self. If there is no current node or no next node, then nil is returned. See also: -moveToFirst, -moveToLast, and -swapWithPrevious swapWithPrevious - swapWithPrevious Swaps the current node with the node in front of it the MiscLinkedList. Returns self. If there is no current node or no previous node, then nil is returned. See also: -moveToFirst, -moveToLast, and -swapWithNext write: - write:(NXTypedStream *)stream Archives the receiving MiscLinkedList and all the objects it contains to stream. Returns self. See also: -read:
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.