SortedList.rtf

This is SortedList.rtf in view mode; [Download] [Up]

SortedList

INHERITS FROM List
DECLARED IN SortedList.h

CLASS DESCRIPTION

A SortedList is like a List, but its contents are always kept in sorted order. Objects can be added to the SortedList only through an addObject: method; direct insertion of objects into a specific slot is not allowed, since this would not assure that the list would always remain in the correct order.

The SortedList can use a variety of criteria by which it is to be kept in order. Several have been predefined, and you can define other, more complex methods for comparing the relative values of objects.

The SortedList is told of an accessor method. The SortedList will use that accessor method's return value to compare the relative values of objects and keep the data structure sorted. All objects placed in the list should respond to the accessor method.

If the objects placed in the SortedList have only a simple key, such as a single integer, floating point, or double precision numeric value, or an NXAtom string value, and the objects have a defined method for returning the value of the key, no redefinition or subclassing of the objects placed in the SortedList is necessary. More complex key values that include several several scalar quantities may require that the objects included in the list be subclassed so that a method capable of comparing the relative values of two objects is present.

For example, assume that we want to store objects in the SortedList by the value of a double precision instance variable in the object, arrivalTime. The method -(double)getArrivalTime returns the value of the instance variable. We could allocate and initialize a new list to hold the objects in sorted order through the following:

objectList = [[SortedList alloc] initCount:2];
[objectList setSortOrder:ASCENDING];
[objectList setKeyDataType:DOUBLE];
[objectList setKeyMethod:@selector(getArrivalTime)];

[objectList addObject:foo];

All objects added to the SortedList will be kept in ascending order by the value of the double precision variable returned by -getArrivalTime.

If a more complex key is required to compare the object's relative values the objects should be able to compare themselves. For example, it might be desirable to sort the objects in the list by a structure with several fields. If this is the case, the objects placed in the SortedList should define a method that takes a single argument of id, incorporates all the necessary logic involved in the comparison, and that returns an integer greater than, equal to, or less than zero, if the receiver is greater than, less than, or equal to the argument, respectively.

Suppose we need to sort an object of class Household by address, a complex structure that includes ZIP code, street name, and house address. The Household object might implement a method called -addressComparedTo:anotherHousehold. This would compare the address of the receiving object to that of the object passed as the argument, and return an integer greater than zero if the receiving object has an address "greater" than anotherHousehold, an integer less than zero if the address is "less" than anotherHousehold, or zero if the two are equal. The SortedList would be used in much the same way as it would be if the comparison operator were a simple scalar:

objectList = [[SortedList alloc] initCount:2];
[objectList setSortOrder:ASCENDING];
[objectList setKeyDataType:OTHER];
[objectList setKeyMethod:@selector(addressComparedTo:)];

[objectList addObject:foo];

The only difference is that the objects in the list must be able to compare themselves, while objects sorted by simple scalar types need only specifiy a method to access the instance variable.

INSTANCE VARIABLES

inherited from Object Class isa;

Inherited from List id *dataPtr;
unsigned int numElements;
unsigned int maxElements;

Declared in SortedList int sortOrder;
BOOL caseSensitive;
SEL keyMethod;
int keyDataType;

sortOrder Ascending or descending sort order.

caseSensitive Whether capitialization matters when comparing strings.

keyMethod The key value accessor method.

keyDataType Type of data returned by the accessor method.

METHOD TYPES

Initializing the class +initialize

Initializing a new SortedList object -initCount:

copying and freeing a SortedList -copy
-copyFromZone

Comparing SortedLists -(BOOL)isEqual

Manipulating objects -addObject:
-addObjectIfAbsent:

Sorting criteria -setSortOrder:
-(int)sortOrder
-setCaseSensitive:
-(BOOL)caseSensitive
-setKeyMethod:
-(SEL)keyMethod
-setKeyDataType:
-(int)keyDataType

Comparing objects -(int)compare:to:

Sorting a list -insertionSort;

Debugging -printKeyValues;

Cause run-time error -insertObject:at:
-replaceObjectAt:with:
-replaceObject:with:

Archiving methods -read:
-write:

CLASS METHODS

initialize
+initialize

Sets the class version number. Updated classes with more or different instance variables should change this version number so that the read: method can correctly handle new older data structures.

INSTANCE METHODS

addObject:
-addObject:anObject

Inserts anObject in the SortedList in sorted order. Returns self. If the object does not respond to the selector keyMethod the object will not be inserted and a run-time error will be reported.