/* Copyright (c) 2000 by Kevin Forchione. All Rights Reserved. */
/*
* TADS LIBRARY EXTENSION
* STACK.T
* version 1.0
*
* stack.t implements a dynamically created FIFO or LIFO stack and a
* Vector class that can be used for list manipulation.
*
*----------------------------------------------------------------------
* REQUIREMENTS
*
* + HTML TADS 2.2.6 or later
*
*----------------------------------------------------------------------
* IMPORTANT LIBRARY INTERFACE AND MODIFICATION
*
* None.
*
*----------------------------------------------------------------------
* COPYRIGHT NOTICE
*
* You may modify and use this file in any way you want, provided that
* if you redistribute modified copies of this file in source form, the
* copies must include the original copyright notice (including this
* paragraph), and must be clearly marked as modified from the original
* version.
*
*------------------------------------------------------------------------------
* REVISION HISTORY
*
* 08-Mar-00: Creation.
*/
#define __STACK_MODULE_
#pragma C+
/*
* Stack: object
*
* This implements a FIFO (First-In-First-Out) or LIFO
* (Last-In-First-Out) stack that can be used for pushing and popping.
* The Stack will automatically create a Vector class object, which it
* uses for keeping track of pushed objects.
*
* To use a stack simply create it dynamically. The Stack default is
* LIFO. If you wish it to behave as a FIFO stack simply set its isLIFO
* attribute to nil.
*
* local stack = new Stack;
* stack.isLIFO = nil;
*
* You can push items onto the stack with the stack's push method:
*
* stack.push(item);
*
* and pop items off the stack using its pop method:
*
* item = stack.pop;
*
* When the stack is no longer needed you can delete it with the delete
* statement. The stack will automatically clean-up the Vector class
* object that it dynamically created.
*/
class Stack: object
isLIFO = true
vector = nil // pointer to dynamically-created Vector class obj
/*
* Push an item onto the stack. All items are pushed to the top of
* the stack.
*/
push(item) = {
self.vector.addElement(item);
}
/*
* Push an item to the bottom of the stack.
*/
pushB(item) = {
self.vector.addElementToHead(item);
}
/*
* Pop an item off the stack. If stack.isLIFO then it pops the
* item from the top of the stack; otherwise it pops the item from
* the bottom of the stack.
*/
pop = {
local item;
if (self.isLIFO)
{
item = self.vector.elementAt(self.vector.getSize);
self.vector.removeElementAt(self.vector.getSize);
}
else
{
item = self.vector.elementAt(1);
self.vector.removeElementAt(1);
}
return item;
}
/*
* Returns a boolean indicating whether the stack is empty or not.
*/
isEmpty = {
return self.vector.isEmpty;
}
/*
* Returns the size of the stack.
*/
getSize = {
return self.vector.getSize;
}
construct = {self.vector = new Vector;}
destruct = {delete self.vector;}
;
/*
* Vector: object
*
* The Vector class can be used to manipulate lists.
*/
class Vector: object
list = []
/*
* Add an element to the tail of the list.
*/
addElement(item) = {
self.list += item;
}
/*
* Add an element to the head of the list.
*/
addElementToHead(item) = {
local newlist = [];
newlist += item;
newlist += self.list;
self.list = newlist;
}
/*
* Add item to the list at pos n. If n > list.getSize the list
* is padded with nil values to a length of n-1 before adding item.
*/
addElementAt(item, n) = {
local newlist = [], l1 = [], l2 = [];
if (n > self.getSize) self.padVector(n-1);
newlist += self.sublist(1, n-1);
newlist += item;
newlist += self.sublist(n, self.getSize);
self.list = newlist;
}
/*
* Pad the list with nil elements to the length of n.
*/
padVector(n) = {
local i, len;
len = self.getSize + 1;
for (i = len; i <= n; ++i)
self.list += nil;
}
/*
* Left pad the list with nil elements to the length of n.
*/
lpadVector(n) = {
local i, len, newlist = [];
len = n - self.getSize;
for (i = 1; i <= len; ++i)
newlist += nil;
newlist += self.list;
self.list = newlist;
}
/*
* Remove the element at pos n in the list.
*/
removeElementAt(n) = {
local i, len, newlist = [];
len = self.getSize;
for (i = 1; i <= len; ++i)
{
if (i != n)
newlist += self.list[i];
}
self.list = newlist;
}
/*
* Remove the first occurrence (from left to right) of item from
* the list.
*/
removeFirstOccurrence(item) = {
local n = self.posFirstOccurrence(item);
if (0 < n && n <= self.getSize)
self.removeElementAt(n);
}
/*
* Remove the last occurrence (from left to right) of item from
* the list.
*/
removeLastOccurrence(item) = {
local n = self.posLastOccurrence(item);
if (0 < n && n <= self.getSize)
self.removeElementAt(n);
}
/*
* Remove all occurrences of item from the list.
*/
removeAllOccurrence(item) = {
self.list -= [item];
}
elementAt(n) = {
if (0 < n && n <= self.getSize)
return self.list[n];
else return nil;
}
/*
* Return the pos n for the first occurrence (from left to right) of
* item in the list.
*/
posFirstOccurrence(item) = {
local f = find(self.list, item);
if (f) return f;
return 0;
}
/*
* Return the pos n for the last occurrence (from left to right) of
* item in the list.
*/
posLastOccurrence(item) = {
local i, len;
for (i = length(self.list); i > 0; --i)
{
if (self.list[i] == item)
return i;
}
return 0;
}
/*
* Return a list of elements that are positions in the list for
* all occurrences of item.
*/
posAllOccurrence(item) = {
local i, len, newlist = [];
len = length(self.list);
for (i = 1; i <= len; ++i)
{
if (self.list[i] == item)
newlist += [i];
}
return newlist;
}
/*
* Return a count of all occurrences of item in the list.
*/
countOccurrence(item) = {
local n = self.posAllOccurrence(item);
return length(n);
}
/*
* Return a sublist of list, starting from pos for a length len
* (if provided). if len is not provided then it is the length of
* the remainder of the list. If len is greater than the length
* of the list then the sublist contains the remainder of the list.
* If pos is greater than the length of the list then an empty list
* is returned.
*/
sublist(pos, ...) = {
local i, len, newlist = [];
if (argcount > 1) len = getarg(2);
if (len == nil) len = self.getSize - pos + 1;
for (i = pos; i <= pos + len - 1; ++i)
{
if (self.getSize >= i)
newlist += self.list[i];
else break;
}
return newlist;
}
/*
* Returns the length of the list.
*/
getSize = {return length(self.list);}
/*
* Returns a boolean indicating whether the list is empty or not.
*/
isEmpty = {
if (self.getSize)
return nil;
else return true;
}
construct = {}
destruct = {}
;
