Stack

[Trond]

This code allows you to create stacks on the fly. The stacks stores longs, which means you can create stacks of pointers to structures if you need to store more complicated things than longs on it.

Overflow and underflow is checked for if the debugger is enabled.

Code: Select all

Procedure NewStack(Size.l)
  Protected *Long.Long = AllocateMemory((Size+2)*SizeOf(Long))
  *Long\l = Size*SizeOf(Long)
  ProcedureReturn *Long
EndProcedure

Procedure Push(Stack.l, Value.l)
  Protected *Length.Long = Stack+SizeOf(Long)
  *Length\l + SizeOf(Long)
  CompilerIf #PB_Compiler_Debugger
    Protected *Size.Long = Stack
    If *Length\l = *Size\l
        CallDebugger ; Stack overflow
    EndIf
  CompilerEndIf
  *Length + *Length\l
  *Length\l = Value
EndProcedure

Procedure.l Pop(Stack)
  Protected *Length.Long = Stack+SizeOf(Long)
  Protected *Value.Long
  CompilerIf #PB_Compiler_Debugger
    If *Length\l < 1
        CallDebugger ; Stack underflow
    EndIf
  CompilerEndIf
  *Value = *Length + *Length\l
  *Length\l - SizeOf(Long)
  ProcedureReturn *Value\l
EndProcedure

Procedure.l Top(Stack)
  Protected *Length.Long = Stack+SizeOf(Long)
  CompilerIf #PB_Compiler_Debugger
    If *Length\l < 1
        CallDebugger ; Stack underflow
    EndIf
  CompilerEndIf
  *Length + *Length\l
  ProcedureReturn *Length\l
EndProcedure

Procedure DeleteStack(Stack.l)
  FreeMemory(Stack)
EndProcedure

Procedure.l IsEmpty(Stack)
  Protected *Length.Long = Stack+SizeOf(Long)
  If *Length\l
    ProcedureReturn 0
  EndIf
  ProcedureReturn 1
EndProcedure

A = NewStack(160)
Push(A, 5)
Push(A, 10)
Debug IsEmpty(A)
Debug Top(A)
Debug Pop(A)
Debug Pop(A)
Debug IsEmpty(A)

[srod]

Huh, I was just about to write some stack routines for one of my projects!

You've saved me the bother!

I like the way you've used the first two longs to store internal data. I was going to use globals!

Thanks.

[Trond]

Good, I just added a function to test if the stack is empty.

[Flype]

stack data can also be stored in a structure.

just for play - it might be slower than trond's :

Code: Select all

Structure STACK
  Size.l
  Index.l
  Value.l[0]
EndStructure

Procedure.l NewStack(Size.l)
  Protected *Stack.STACK = AllocateMemory( SizeOf(STACK) + (Size * SizeOf(Long)) )
  *Stack\Size = Size 
  ProcedureReturn *Stack
EndProcedure

Procedure DelStack(*Stack.STACK)
  FreeMemory(*Stack)
EndProcedure

Procedure Push(*Stack.STACK, Value.l)
  CompilerIf #PB_Compiler_Debugger
  If *Stack\Index >= *Stack\Size
    CallDebugger ; Stack overflow
  EndIf
  CompilerEndIf
  *Stack\Value[*Stack\Index] = Value
  *Stack\Index + 1
EndProcedure

Procedure.l Pop(*Stack.STACK)
  CompilerIf #PB_Compiler_Debugger
  If *Stack\Index < 1
    CallDebugger ; Stack underflow
  EndIf
  CompilerEndIf
  *Stack\Index - 1
  ProcedureReturn *Stack\Value[*Stack\Index]
EndProcedure

Procedure.l Top(*Stack.STACK)
  CompilerIf #PB_Compiler_Debugger
  If *Stack\Index < 1
    CallDebugger ; Stack underflow
  EndIf
  CompilerEndIf
  ProcedureReturn *Stack\Value[*Stack\Index - 1]
EndProcedure

Procedure.l IsEmpty(*Stack.STACK)
  If Not *Stack\Index
    ProcedureReturn #True
  EndIf
EndProcedure

a = NewStack(160)
Push(a, 5)
Push(a, 10)
Debug IsEmpty(a)
Debug Top(a)
Debug Pop(a)
Debug Pop(a)
Debug IsEmpty(a)

[Psychophanta]

Yeah! Flype, your trick uses this http://www.purebasic.fr/english/viewtopic.php?t=17120
I think it is an elegant way