stack.bi
Code: Select all
'' stack.bi
namespace sty
''' A simple generic LIFO container.
'''
''' Elements are removed from the stack in last-in-first-out order;
''' they are removed in the opposite order they were added.
'''
''' The elements of the container are pointers to some memory, so it is
''' up to the user to free this memory if necessary. For example,
''' s.Push(new integer(420))
''' ..use s.Top()..
''' delete cast(integer ptr, t.Top()) : t.Pop()
'''
''' Copying Stack objects copies the element addresses, not the elements
''' themselves, so care must be taken when they are copied (passed by
''' value, copy constructed or assigned to).
'''
''' Implementation notes:
''' The stack is represented by three pointers into an array:
''' m_start - the first element
''' m_finish - one-past the last element
''' m_eos - one past the end of the array
'''
''' The size of the stack is equal to (m_finish - m_start) and it's
''' total capacity (m_eos - m_start). If an element is added when the
''' stack size is equal to its capacity, the array grows exponentially
''' (capacity * 2 + 1). This has the effect of allowing elements to
''' be removed easily simply decreasing the m_finish pointer, and
''' minimizing reallocations as stack size grows large.
'''
type Stack
public:
'' Construct/Copy/Destroy/Assign
' Constructs an empty stack.
declare constructor ()
' Constructs an empty stack with an initial capacity.
declare constructor (capacity as uinteger)
' Constructs a stack with elements from another.
declare constructor (byref x as Stack)
' Destroys the stack (pops all elements)
declare destructor ()
' Copy assigns from another stack.
declare operator let (byref x as Stack)
'' Size/Empty
' Gets the number of elements in the stack.
declare function Size () as uinteger
' Returns true (-1) if the stack is empty, false (0) otherwise.
declare function Empty () as integer
'' Accessors/Modifiers
' Gets the top element in the stack. If stack is empty, results
' are undefined.
declare function Top () as any ptr
' Adds an element onto the top of the stack.
declare sub Push (x as any ptr)
' Removes the top element, if any, from the stack.
declare sub Pop ()
private:
m_start as any ptr ptr = any
m_finish as any ptr ptr = any
m_eos as any ptr ptr = any
end type
end namespace
Code: Select all
'' stack.bas
# include once "crt/string.bi" ' for memcpy
# include once "stack.bi"
namespace sty
'' :::::
constructor Stack ()
m_start = 0
m_finish = 0
m_eos = 0
end constructor
'' :::::
constructor Stack (capacity as uinteger)
m_start = new byte[capacity * sizeof(any ptr)]
m_finish = m_start
m_eos = m_start + capacity
end constructor
'' :::::
constructor Stack (byref x as Stack)
' x is empty ?
if (x.m_start = x.m_finish) then
m_start = 0
m_finish = m_start
m_eos = m_finish
' copy elements..
else
dim sz as uinteger = x.m_finish - x.m_start
dim capacity as uinteger = x.m_eos - x.m_start
m_start = new byte[capacity * sizeof(any ptr)]
..memcpy(m_start, x.m_start, sz * sizeof(any ptr))
m_finish = m_start + sz
m_eos = m_start + capacity
end if
end constructor
'' :::::
destructor Stack ()
delete[] cast(byte ptr, m_start)
end destructor
'' :::::
operator Stack.let (byref x as Stack)
' not empty ?
if (m_start <> m_finish) then
delete[] cast(byte ptr, m_start)
end if
' copy elements..
dim sz as uinteger = x.m_finish - x.m_start
dim capacity as uinteger = x.m_eos - x.m_start
m_start = new byte[capacity * sizeof(any ptr)]
..memcpy(m_start, x.m_start, sz * sizeof(any ptr))
m_finish = m_start + sz
m_eos = m_start + capacity
end operator
'' :::::
function Stack.Size () as uinteger
return m_finish - m_start
end function
'' :::::
function Stack.Empty () as integer
return m_start = m_finish
end function
'' :::::
function Stack.Top () as any ptr
return *(m_finish - 1)
end function
'' :::::
sub Stack.Push (x as any ptr)
' need to grow ?
if (m_finish = m_eos) then
dim sz as uinteger = m_finish - m_start
dim newcapacity as uinteger = (m_eos - m_start) * 2 + 1
dim newstart as any ptr ptr = _
new byte[newcapacity * sizeof(any ptr)]
..memcpy(newstart, m_start, sz * sizeof(any ptr))
delete[] cast(byte ptr, m_start)
m_start = newstart
m_finish = m_start + sz
m_eos = m_start + newcapacity
end if
*m_finish = x
m_finish += 1
end sub
'' :::::
sub Stack.Pop ()
if (m_start <> m_finish) then m_finish -= 1
end sub
end namespace
Code: Select all
'' stack-demo.bas
# include once "stack.bi"
'' ::::: (main)
dim stack as sty.Stack
for i as integer = 1 to 5
stack.Push(new integer(i * 10))
next
while (not stack.Empty())
dim ref as integer ptr = stack.Top()
stack.Pop()
print *ref & " " ;
delete ref
wend : print
'' outputs:
'' 50 40 30 20 10