[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Lua source
- From: Fred Bertsch <fb@...>
- Date: Sat, 18 Mar 2000 10:57:45 -0500 (EST)
On Sat, 18 Mar 2000, Erik Hougaard wrote:
> I do belive that I'm very complient to your copyright notice. I'm not
> hiding the fact that its "based on" Lua so my users could go hunting for
> Lua code to use in uCore - But there is not forum for Lua source - only
> C source libraries etc. can be found ? Is this anything you have
> considered ?
If there is such a forum, I'll donate a linked list implementation. (It's
included as an attachment.) It's implemented entirely in Lua, and the
documentation is contained in comments at the beginning of the file.
I'm afraid that the source looks a bit strange. I have to be a bit
paranoid about putting things in the global namespace in my
application. I let users run scripts on my server, so I have to be fairly
picky about what they can access.
The chief advantage of this over standard Lua list-tables is that
insertion and deletion takes constant time with this. Lists also behave
like objects and carry their operations with them.
F
$debug
--
-- LinkedList.lua
--
-- Written by Fred Bertsch, 1999.
-- Feel free to use it however you want.
--
-- This is a simple linked list package for Lua.
--
-- No global variable other than CreateList is created.
--
-- It is implemented entirely in Lua. No external C code is required.
--
-- It is always assumed that the lists and nodes given are correct.
-- Only minimal error checking is done. If the global variable _debug
-- is set to 1 before loading this file, then additional error checking
-- is performed. After loading the file, it is okay to unset _debug.
-- Do not directly manipulate the nodes or lists
--
-- The following standard Lua functions are used. It is assumed that
-- they exist when this code is loaded, but they may be removed from
-- the global space later:
-- newtag
-- settag
-- tag
-- settagmethod
-- rawsettable
-- error
--
--
-- CreateList(): This creates a linked list. It takes one optional
-- argument--a standard table-type Lua list. (eg: { 'a', 'b', 'c' })
-- This argument makes it easier to create constant lists.
--
--
-- list:
-- This is a table containing the info on the entire linked list.
-- Here are the contents:
-- First = first node
-- Last = last node
-- Note that while you can safely read the contents of the list,
-- you cannot and should not modify them except through the
-- list functions.
-- It contains the following functions:
-- list:Prepend( object ): Puts a lua object at the beginning of
-- the list.
-- list:Append( object ): Appends a lua object to the end of the
-- list.
-- list:AppendList( list ): Concatinates the two lists. The objects
-- in the list are not copied, but the nodes are. (ie: modifying
-- the order of the appended list will not affect this list, but
-- modifying the objects in the list will.)
-- list:Insert( node, object ): This puts a new object in the list.
-- The object is inserted before the given node. If the given node
-- is equal to nil, the object is inserted at the end of the list.
-- The node that the object was placed in is returned.
-- list:RemoveRange( nodeStart, nodeEnd ): This removes a range of
-- nodes from a given list. All nodes starting with the starting
-- node and ending immediately before the ending node are removed.
-- list:Remove( nodeToRemove ): This removes a single node from the
-- given list.
-- list:Length(): This returns the length of the list. Note that
-- this takes O( n ) time, where n is the length of the list.
--
--
-- node:
-- This is a table containing info on one node of a linked list.
-- Here are the contents:
-- Previous = previous node (nil iff none)
-- Next = next node (nil iff none)
-- Contents = contents (a lua object)
-- Note that while you can safely read the contents of the node,
-- you cannot and should not modify them except through the
-- list functions.
-- nil is a valid node representing the null node. (ie: end of the list,
-- before the beginning of the list, etc.)
--
--
-- Example code:
--
-- Here's a simple program that uses some of the features. (Including
-- iterating over the lists.)
--
-- list = CreateList( { 'is', 'the', 'C' } )
--
-- list:Append( 'code?' )
-- list:Prepend( 'Where' )
--
-- loopNode = list.First
-- while( loopNode ~= nil ) do
-- print( tostring( loopNode.Contents ) )
-- loopNode = loopNode.Next
-- end
--
do
-- This generates an error along with a stack dump when in debug mode.
local lerror = function( text )
$if _debug
print( tostring( text ) )
local nontable = nil
nontable[ 1 ] = nil -- Designed to produce a stack output if in debug mode.
$else
error( tostring( text ) )
$end
end
local TagInvalidSetTable = function( table, index, value )
%lerror( "Illegal attempt to set table values." )
end
-- These are the tags used by lists and nodes. No tag methods are attached to
-- them in order to improve speed slightly.
local tagList = newtag()
settagmethod( tagList, "settable", TagInvalidSetTable )
local tagNode = newtag()
settagmethod( tagNode, "settable", TagInvalidSetTable )
local SetTag = settag
local Tag = tag
local RawSetTable = rawsettable
-- This is the proper way to create a new linked list structure. It
-- returns an empty list.
function CreateList( ltable )
local list = {}
local tagList = %tagList
local tagNode = %tagNode
local SetTag = %SetTag
local Tag = %Tag
local RawSetTable = %RawSetTable
local LError = %lerror
-- This puts a new object at the beginning of the list. The node the object
-- was placed in is returned.
local Prepend = function( self, obj )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
$end
-- Create the node...
local nodeNew = { Next = self.First, Contents = obj }
%SetTag( nodeNew, %tagNode )
-- Update the list endpoints...
if( self.First ~= nil ) then
%RawSetTable( self.First, "Previous", nodeNew )
else
%RawSetTable( self, "Last", nodeNew )
end
%RawSetTable( self, "First", nodeNew )
return nodeNew
end
list.Prepend = Prepend
-- This puts a new object at the end of the list. The node the object was
-- placed in is returned.
list.Append = function( self, obj )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
$end
-- Create the node...
local nodeNew = { Previous = self.Last, Contents = obj }
%SetTag( nodeNew, %tagNode )
-- Update the list...
if( self.Last ~= nil ) then
%RawSetTable( self.Last, "Next", nodeNew )
else
%RawSetTable( self, "First", nodeNew )
end
%RawSetTable( self, "Last", nodeNew )
return nodeNew
end
-- This appends the contents of a list to another list. The contents
-- of the second list are copied.
list.AppendList = function( self, listToAppend )
$if _debug
if( %Tag( self ) ~= %tagList or %Tag( listToAppend ) ~= %tagList ) then
%LError( "Invalid list." )
end
$end
local node = listToAppend.First
while( node ~= nil ) do
self:Append( node.Contents )
node = node.Next
end
end
-- This puts a new object in the list. The object is inserted before the given
-- node. If the given node is equal to nil, the object is inserted at the end
-- of the list. The node that the object was placed in is returned.
list.Insert = function( self, node, obj )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
if( %Tag( node ) ~= %tagNode ) then
%LError( "Invalid node." )
end
$end
if( node ~= nil ) then
local nodePrevious = node.Previous
-- Create the node to insert...
local nodeToInsert = { Previous = nodePrevious, Next = node, Contents = obj }
%SetTag( nodeToInsert, %tagNode )
-- Update the previous node...
if( nodePrevious ~= nil ) then
%RawSetTable( nodePrevious, "Next", nodeToInsert )
else
%RawSetTable( self, "First", nodeToInsert )
end
-- Update the next node...
%RawSetTable( node, "Previous", nodeToInsert )
else
self:Append( obj )
end
end
-- This removes a range of nodes from a given list. All nodes starting with the
-- starting node and ending immediately before the ending node are removed.
list.RemoveRange = function( self, nodeStart, nodeEnd )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
if( %Tag( nodeStart ) ~= %tagNode or %Tag( nodeEnd ) ~= %tagNode ) then
%LError( "Invalid node." )
end
-- Confirm that the ending node is after the starting node...
local node = nodeStart
while( node ~= nil and node ~= nodeEnd ) do
node = node.Next
end
if( node ~= nodeEnd ) then
%LError( "Ending node did not come after starting node." )
end
$end
if( nodeStart ~= nil ) then
local nodePrevious = nodeStart.Previous
-- Update list endpoints...
if( self.First == nodeStart ) then
%RawSetTable( self, "First", nodeEnd )
end
if( nodeEnd == nil ) then
%RawSetTable( self, "Last", nodePrevious )
end
-- Update edges of removed section...
if( nodePrevious ~= nil ) then
%RawSetTable( nodePrevious, "Next", nodeEnd )
end
if( nodeEnd ~= nil ) then
%RawSetTable( nodeEnd, "Previous", nodePrevious )
end
end
end
-- This removes a single node from the given list.
list.Remove = function( self, nodeToRemove )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
if( %Tag( nodeToRemove ) ~= %tagNode ) then
%LError( "Invalid node." )
end
$end
if( nodeToRemove ~= nil ) then
local nodePrevious = nodeToRemove.Previous
local nodeNext = nodeToRemove.Next
-- Update endpoints in list...
if( self.First == nodeToRemove ) then
%RawSetTable( self, "First", nodeNext )
end
if( self.Last == nodeToRemove ) then
%RawSetTable( self, "Last", nodePrevious )
end
-- Update nodes that aren't being removed...
if( nodePrevious ~= nil ) then
%RawSetTable( nodePrevious, "Next", nodeNext )
end
if( nodeNext ~= nil ) then
%RawSetTable( nodeNext, "Previous", nodePrevious )
end
end
end
-- This returns the length of the list. Note that this takes O( n ) time, where
-- n is the length of the list.
list.Length = function( self )
$if _debug
if( %Tag( self ) ~= %tagList ) then
%LError( "Invalid list." )
end
$end
local n = 0
local node = self.First
while( node ~= nil ) do
n = n + 1
node = node.Next
end
return n
end
SetTag( list, tagList )
-- Insert elements from standard lua-type table if needed...
if( ltable ~= nil ) then
local index = 1
while( ltable[ index ] ~= nil ) do
list:Append( ltable[ index ] )
index = index + 1
end
end
return list
end
end
