Nebula 1994 June/NEBULA_SE.ISO/SourceCode/MiscKit/Source/MiscLinkedList.m

Text File | 1994-01-31 | 13.6 KB | 640 lines

//
//    MiscLinkedList.m -- an implementation of a doubly linked list
//        Written by Sean Luke (c) 1993, 1994 by Sean Luke.
//        Additional methods and editing by Don Yacktman.
//                Version 0.9.  All rights reserved.
//
//        This notice may not be removed from this source code.
//
//    This object is included in the MiscKit by permission from the author
//    and its use is governed by the MiscKit license, found in the file
//    "LICENSE.rtf" in the MiscKit distribution.  Please refer to that file
//    for a list of all applicable permissions and restrictions.
//

// ***** make sure that the list insertion methods don't reverse the order
// of the inserted list!

// ***** finish writing the extra methods


#import <misckit/misckit.h>

@implementation MiscLinkedList

- init
    {
    return [self initForClass:[MiscLinkedListNode class]];
    }

- initForClass: this_class
    {
    id returnval=[super init];
    node_length=0;
    node_class=this_class;
    return returnval;
    }

- free
{
    [self freeNodes];
    return [super free];
}

- freeObjects
    {
    id temp;
    [self goFirst];
    while (node_length)
        {
        temp=[self deleteObject];
        if (temp!=nil) [[temp freeObject] free]; // deletes node AND object
        }
    return self;
    }

- freeNodes
    {
    id temp;
    [self goFirst];
    while (node_length)
        {
        temp=[self deleteObject];
        if (temp!=nil) [temp free]; // deletes node ONLY
        }
    return self;
    }

- goFirst
    {
    current_node=first_node;
    if (current_node==nil) return nil;
    return [current_node getObject];
    }

- goNext
     {
    id new_node;
    if (current_node==nil) return nil;
    new_node=[current_node getNext];
    if (new_node==nil) return nil;
    current_node=new_node;
    return [current_node getObject];
    }

- goLast
    {
    current_node=last_node;
    if (current_node==nil) return nil;
    return [current_node getObject];
    }

- goPrevious
     {
    id new_node;
    if (current_node==nil) return nil;
    new_node=[current_node getPrevious];
    if (new_node==nil) return nil;
    current_node=new_node;
    return [current_node getObject];
    }

- getNode
    {
    if (current_node==nil) return nil;
    return current_node;
    }


- getObject
    {
    if (current_node==nil) return nil;
    return [current_node getObject];
    }

- setObject:this_object
    {
    if (current_node==nil) return nil;
    return [current_node setObject:this_object];
    }

- insertObjectAfter: this_object
    {
    id new_node;
    if (this_object==nil) return nil;
    new_node=[[node_class alloc] initObject:this_object];
    if (node_length==0)                    // node is both ends
        {
        first_node=new_node;
        last_node=new_node;
        current_node=new_node;
        }
    else if (current_node==last_node)     // node is last end
        {
        [new_node setNext:nil];
        [new_node setPrevious:current_node];
        [current_node setNext:new_node];
        last_node=new_node;
        current_node=new_node;
        }
    else                                 // node is in the middle
        {
        [new_node setNext:[current_node getNext]];
        [new_node setPrevious:current_node];
        [current_node setNext:new_node];
        [[new_node getNext] setPrevious:new_node];
        current_node=new_node;
        }
    node_length++;
//    printf ("Last Node: %d\n",(int)last_node);
    return this_object;
    }

- insertObjectBefore: this_object
    {
    id new_node;
    if (this_object==nil) return nil;
    new_node=[[node_class alloc] initObject:this_object];

    if (node_length==0)                    // node is both ends
        {
        first_node=new_node;
        last_node=new_node;
        current_node=new_node;
        }
    else if (current_node==first_node)     // node is first end
        {
        [new_node setPrevious:nil];
        [new_node setNext:current_node];
        [current_node setPrevious:new_node];
        first_node=new_node;
        current_node=new_node;
        }
    else                                 // node is in the middle
        {
        [new_node setPrevious:[current_node getPrevious]];
        [new_node setNext:current_node];
        [current_node setPrevious:new_node];
        [[new_node getPrevious] setNext:new_node];
        current_node=new_node;
        }
    node_length++;
//    printf ("Last Node: %d\n",(int)last_node);
    return this_object;
    }

- deleteObject
    {
    id next_node, previous_node, the_object;
    if (current_node==nil) return nil;

    next_node=[current_node getNext];
    previous_node=[current_node getPrevious];
    the_object=[current_node getObject];
    [current_node free];
    node_length--;

    if (node_length==0)                    // that was the last node!
        {
        first_node=nil;
        last_node=nil;
        current_node=nil;
        }
    else if (next_node==nil)             // current node was last
        {
        last_node=previous_node;
        [previous_node setNext:nil];
        current_node=previous_node;
        }
    else if (previous_node==nil)        // current node was first
        {
        first_node=next_node;
        [next_node setPrevious:nil];
        current_node=next_node;
        }
    else                                // node is in the center
        {
        [next_node setPrevious:previous_node];
        [previous_node setNext:next_node];
        current_node=previous_node;            // (default)
        }
//    printf ("Deleting Last Node: %d\n",(int)last_node);

    return the_object;
    }

- (int) getLength
    {
    return node_length;
    }

- read: (NXTypedStream*) stream
    {
    int x;
    id temp=nil;
    id previous=nil;

    [super read:stream];
    NXReadTypes(stream, "i", &node_length);
    // others don't matter, since they'll be different anyhow.

    first_node=temp;
    current_node=temp;
    for (x=1;x<=node_length;x++)
        {
        temp=NXReadObject(stream);
        if (previous==nil)
            {
            first_node=temp;                // only read one!
            current_node=temp;
            [temp setPrevious: nil];        // just in case
            }
        else
            {
            [temp setPrevious:previous];
            [previous setNext:temp];
            }
        previous=temp;
        }
    last_node=temp;
    [temp setNext:nil];                    // just in case
    node_class=[temp class]; // assume that all nodes are same class.
    return self;
    }

- insertList: this_list
    { // ***** need a version that will insert objects from a NeXT List too
    // inserts this_list into the beginning of the list

    if ([this_list getLength])            // not empty
        {
        [this_list goFirst];
        do
            {
            [self insertObjectBefore: [this_list getObject]];
            }
        while ([this_list goNext]!=nil);
        }
    return self;
    }



- insertListAtFront: this_list
    { // ***** need a version that will insert objects from a NeXT List too
    // inserts this_list into the beginning of the list

    if ([this_list getLength])            // not empty
        {
        [this_list goFirst];
        [self goFirst];
        do
            {
            [self insertObjectBefore: [this_list getObject]];
            }
        while ([this_list goNext]!=nil);
        }
    return self;
    }



- appendList: this_list
    { // ***** need a version that will insert objects from a NeXT List too
    // appends this_list onto the end of the list

    if ([this_list getLength])            // not empty
        {
        [this_list goFirst];
        [self goLast];
        do
            {
            [self insertObjectAfter: [this_list getObject]];
            }
        while ([this_list goNext]!=nil);
        }
    return self;
    }



- write: (NXTypedStream*) stream
    {
    int x;
    id temp;

    [super write:stream];
    NXWriteTypes(stream, "i", (const int*) &node_length);
    temp=first_node;
    for (x=1;x<=node_length;x++)
        {
        NXWriteObject(stream,temp);
        temp=[temp getNext];
        }
    return self;
    }

- swapWithNext
    {
    id farnext;
    id farprevious;
    id swapnode;

    if (current_node==nil) return nil;                    // node doesn't exist
    if ([current_node getNext]==nil) return nil;        // no node with which to swap

    farnext=[[current_node getNext] getNext];
    farprevious=[current_node getPrevious];
    swapnode=[current_node getNext];

    [swapnode setPrevious: farprevious];
    [swapnode setNext: current_node];
    [current_node setPrevious: swapnode];
    [current_node setNext: farnext];

    if (farnext!=nil)                                        // swapping doesn't move node to back
        {
        [farnext setPrevious: current_node];
        }
    if (farprevious!=nil)                                    // swapping doesn't move node from front
        {
        [farprevious setNext: swapnode];
        }
    return self;
    }

- swapWithPrevious
    {
    id farnext;
    id farprevious;
    id swapnode;

    if (current_node==nil) return nil;                    // node doesn't exist
    if ([current_node getPrevious]==nil) return nil;    // no node with which to swap

    farnext=[current_node getNext];
    farprevious=[[current_node getPrevious] getPrevious];
    swapnode=[current_node getPrevious];

    [swapnode setNext: farnext];
    [swapnode setPrevious: current_node];
    [current_node setNext: swapnode];
    [current_node setPrevious: farprevious];

    if (farnext!=nil)                                        // swapping doesn't move node from back
        {
        [farnext setPrevious: swapnode];
        }
    if (farprevious!=nil)                                    // swapping doesn't move node to front
        {
        [farprevious setNext: current_node];
        }
    return self;
    }


- moveToFirst
    {
    id next_node;
    id previous_node;

    if (current_node==nil) return nil;

    next_node=[current_node getNext];
    previous_node=[current_node getPrevious];

    if (next_node!=nil) [next_node setPrevious: previous_node];
    if (previous_node!=nil) [previous_node setNext: next_node];
    [first_node setPrevious:current_node];
    [current_node setNext:first_node];
    [current_node setPrevious:nil];
    first_node=current_node;
    return self;
    }


- moveToLast
    {
    id next_node;
    id previous_node;

    if (current_node==nil) return nil;

    next_node=[current_node getNext];
    previous_node=[current_node getPrevious];

    if (next_node!=nil) [next_node setPrevious: previous_node];
    if (previous_node!=nil) [previous_node setNext: next_node];
    [last_node setNext:current_node];
    [current_node setPrevious:last_node];
    [current_node setNext:nil];
    last_node=current_node;
    return self;
    }

// We guess in the -read method and choose for the node class the
// node at the end of the list...likely to be more correct than
// simply setting the default class, and means that whomever un-archives
// the list doesn't have to worry as much about making sure the class
// is the right one.  Of course, the archiver has to make sure that
// the last node is representative of what we want, but that is
// not likely to be a problem, since typically all nodes will be of
// the same class.
/*- awake
    {
    [super awake];
    node_class=[MiscLinkedListNode class];
    return self;
    }*/

- empty
{
    return [self freeNodes];
}

- (BOOL)isEqual:anObject;
{
    id temp2, temp = first_node;

    // first, a few shortcuts to speed up common cases
    if (anObject == self) return YES;    // same object
    if ([anObject class] != [self class]) return NO; // different classes
    if ([anObject count] != [self count]) return NO; // different lengths

    [anObject goFirst];
    temp2 = [anObject getNode];
    while (temp && temp2) { // check each object against counterpart in other
        if (![[temp getObject] isEqual:[temp2 getObject]]) return NO; // diff!
        temp = [temp getNext];
        temp2 = [temp2 getNext];
    }
    if (temp || temp2) return NO; // different lengths (shouldn't happen)
    return YES;
}


- makeObjectsPerform:(SEL)aSelector;
{
    id temp = first_node;
    while (temp) {
        id tobj = [temp getObject];
        if ([tobj respondsTo:aSelector]) {
            [tobj perform:aSelector];
        }
        temp = [temp getNext];
    }
    return self;
}

- makeObjectsPerform:(SEL)aSelector with:anObject
{
    id temp = first_node;
    while (temp) {
        id tobj = [temp getObject];
        if ([tobj respondsTo:aSelector]) {
            [tobj perform:aSelector with:anObject];
        }
        temp = [temp getNext];
    }
    return self;
}

- replaceObject:anObject with:newObject; // return anObject
{
    id temp = first_node;
    while (temp) {
        if ([temp getObject] == anObject) {
            return [temp setObject:newObject];
        }
        temp = [temp getNext];
    }
    return nil;
}

- removeObject:anObject; // return anObject
{
    current_node = first_node;
    while (current_node) {
        if ([current_node getObject] == anObject) {
            return [self deleteObject];
        }
        current_node = [current_node getNext];
    }
    return nil;
}

- addObjectIfAbsent:anObject; // appends it
{
    id temp = first_node;
    while (temp) {
        if ([temp getObject] == anObject) return nil; // found it!
        temp = [temp getNext];
    }
    return [self addObject:anObject];
}

// these four are obvious:
- removeLastObject
{
    id the_object = [last_node getObject];
    id new_last = [last_node getPrevious];
    if (!last_node) return nil;
    node_length--;
    [last_node free];
    last_node = new_last;
    [last_node setNext:nil];
    return the_object;
}
- lastObject
{
    return [last_node getObject];
}

- removeFirstObject
{
    id the_object = [first_node getObject];
    id new_first = [first_node getNext];
    if (!first_node) return nil;
    node_length--;
    [first_node free];
    first_node = new_first;
    [first_node setPrevious:nil];
    return the_object;
}

- firstObject
{
    return [first_node getObject];
}

- (unsigned int)count // same as -getLength
{
    return (unsigned int)node_length;
}

- addObject:anObject // appends object to list
{
    id new_node = [[node_class alloc] initObject:anObject];

    [last_node setNext:new_node];
    [new_node setPrevious:last_node];
    [new_node setNext:nil];
    last_node = new_node;
    if (!first_node) first_node = new_node;
    node_length++;
    return self;
}

// NXTransport protocol implementation:
- encodeUsing:(id <NXEncoding>)portal
{
    int i; id temp;
    [portal encodeData:&node_length ofType:"i"];
    [portal encodeObjectBycopy:node_class];
    temp = first_node;
    for (i=1; i<=node_length; i++) {
        [portal encodeObjectBycopy:temp];
        temp=[temp getNext];
    }
    return self;
}

- decodeUsing:(id <NXDecoding>)portal
{
    int x; id temp = nil; id previous = nil;
    [portal decodeData:&node_length ofType:"i"];
    first_node = temp;
    current_node = temp;
    node_class = [portal decodeObject];
    for (x=1; x<=node_length; x++) {
        temp = [portal decodeObject];
        if (previous == nil) {
            first_node = temp;                // only read one!
            current_node = temp;
            [temp setPrevious: nil];        // just in case
        } else {
            [temp setPrevious:previous];
            [previous setNext:temp];
        }
        previous = temp;
    }
    last_node = temp;
    [temp setNext:nil];                    // just in case
    return self;
}

- encodeRemotelyFor:(NXConnection *)connection
    freeAfterEncoding:(BOOL *)flagp isBycopy:(BOOL)isByCopy
{
    if (isByCopy) {
        *flagp = NO; // object will copy.
        return self; //encode object (copy it)
    }
    *flagp = NO; // object will copy.
    // super will encode the proxy otherwise
    return [super encodeRemotelyFor:connection
                freeAfterEncoding:flagp isBycopy:isByCopy];
}

@end