/* -- ported to 3.0 by Truilkan@TMI - 92/01/30 */ /******************************************************************* Description: Simple doubly linked list ADT written as an LPC object: This object may be used as is or as the basis for other abstract data types such as a stack, a set, or an orderd list. If you plan to use this object as is, then cloning this file [clone_object(THISFILE)] is the preferred means of getting a copy. If you plan to use this object as the basis for another ADT, then inheritance is the preferred means of obtaining a copy [inherit THISFILE;]. Implementation: Each node of the list is implemented as a two-tuple obtained via the allocate(2) call. The first element of each tuple is an object. The second element of each tuple is in turn another two-tuple (representing the next element in the list). C programmers will find that LPC arrays (returned by the allocate() call) provide the equivalent functionality of the C structure (or Pascal record) since LPC arrays do not require each element of an array to be of the same type. author: Truilkan@Babylon - May 26, 1991 ********************************************************************/ // Leto changed that weird 'string query("short") { foo }' thingy // 94-11-11 #include "adt_defs.h" private mixed *theHead, *theTail; static mixed *set_head(mixed *arg) { return (theHead = arg); } static mixed *set_tail(mixed *arg) { return (theTail = arg); } static void set_prev(mixed *arg, mixed *before) { if (arg != NULL) arg[2] = before; } static void set_next(mixed *arg, mixed *after) { if (arg != NULL) arg[1] = after; } mixed *query_head() { return theHead; } mixed *query_tail() { return theTail; } static mixed *new_elt(mixed thisObj, mixed *nextObj, mixed *prevObj) { return ({ thisObj, nextObj, prevObj }); } mixed value(mixed *arg) { if (arg) return arg[0]; else return 0; } mixed *next(mixed *arg) { if (arg != NULL) return arg[1]; else return NULL; } mixed *prev(mixed *arg) { if (arg) return arg[2]; else return NULL; } /* insert: Here I insert at the head of the list so that this object might form the basis of a stack ADT. Note that this object might also form the basis of an ordered list if insert() is redefined appropriately in an object inheriting this one. */ mixed *insert(mixed obj) { mixed *ohead, *nhead; ohead = query_head(); set_prev(ohead,nhead = set_head(new_elt(obj,query_head(),NULL))); return nhead; } /* note that delete does not (and can not) explicitly free any space because LPC does its own garbage collection */ mixed delete(mixed obj) { mixed *cur, *before, *after; if (obj == value(query_head())) { set_head(next(query_head())); set_prev(query_head(),NULL); return obj; } cur = next(before = query_head()); while (cur != NULL) { after = next(cur); if (obj == value(cur)) { set_next(before,after); set_prev(after,before); return obj; } before = cur; cur = after; } return NULL; } int empty() { return query_head() == NULL; } // string query("short") // I'm asuming it should be query_short(), but don't hold it // against me ;) Leto string query_short() { return "a list_adt object"; } string query_long(string arg) { return "This is a " + arg + ". There really isn't much that you can\n" + "do with it from an interactive environment. It is meant\n" + "to be accessed via the clone_object() or inherit LPC calls.\n"; } void print() { mixed cur; mixed val; cur = query_head(); while (cur != NULL) { val = value(cur); if (objectp(val) && val->query("short")) write("object: " + val->query("short") + "\n"); else write(val + "\n"); cur = next(cur); } } int id(string arg) { return arg == "list"; } void create() { set_head(NULL); set_tail(NULL); }