Tiny Stack Implementation

[KristopherWindsor]

If you don't know what a stack is, you do now. :P

Code: Select all

' Tiny Stack Implementation
' By Kristopher Windsor

Type stackFrame
  Declare Constructor(Data As Integer, n As stackFrame Ptr)
  As Integer Data
  As stackFrame Ptr n
End Type

Constructor stackFrame(Data As Integer, n As stackFrame Ptr)
  this.data = Data
  this.n = n
End Constructor

Dim As stackFrame Ptr stack, temp

'add to stack
stack = new stackFrame(5, stack)
stack = new stackFrame(10, stack)
stack = new stackFrame(15, stack)

'remove from stack
While stack <> 0
  Print stack->Data
  temp = stack->n
  delete(stack)
  stack = temp
Wend

Sleep()

[kiyotewolf]

How could you access each piece of the stack individually?
Keep track of the pointers, in a separate array?



~Kiyote!

[edit]

I made use of this already, your tiny stack implementation.

[edit2]

I'm using the tiny stack to draw objects on the screen non-destructively.
Each time I put a pixel, I push the underlying pixel to the stack.

It's for a custom cursor with odd proportions, very narrow, but long in both X & Y.

Much faster and more efficient than saving the entire background, or even saving the bounding box of pixels, which the object occupies.

[Aave]

No offence, but I don't really like this implementation. Traditionally stacks have simple push() and pop() (perhaps also peek()) methods that hide all that memory management complexity. Your implementation forces user to deal with pointers and e.g. that popping code is horribly clunky to do each time you wish to remove an item (will result in code duplication). A proper implementation wouldn't be much longer in code, but far more practical and intuitive to use.

EDIT: kiyotewolf, stacks are not really designed for accessing anything but the topmost item. You should look for another data structure for that (such as a "vector", an automatically expanding array).

[kiyotewolf]

kiyotewolf, stacks are not really designed for accessing anything but the topmost item.

Yeah, that kinda occurred to me after the fact.

I guess, I could save the position of the first, as a sort of RESTORE command, then pass through the other members, until I find the one I want again.



~Kiyote!

[KristopherWindsor]

Nice, kiyotewolf, although I think you could use some other data structures just as well for that case. :)

A proper implementation wouldn't be much longer in code.

I disagree because my implementation was 12 lines of code (plus the actual stack usage), hence the name of the thread.

[kiyotewolf]

Nice, kiyotewolf, although I think you could use some other data structures just as well for that case. :)

A proper implementation wouldn't be much longer in code.

I disagree because my implementation was 12 lines of code (plus the actual stack usage), hence the name of the thread.

* from the stands of ABOGG Stadium, a roar a standing ovation erupts from the 5 row packed perfect square of the ... TRANSMISSION too weak .. SIGNAL FADE ... RETRY? *

[Aave]

A proper implementation wouldn't be much longer in code.

I disagree because my implementation was 12 lines of code (plus the actual stack usage), hence the name of the thread.

So I quickly hacked together my own stack:

Code: Select all

' Tiny Yet Intuitive Stack Implementation
' By Tapio

Type StackFrame
	data As Integer = 0
	prev As StackFrame Ptr = 0
End Type

Type Stack
	Declare Sub push(data As Integer)
	Declare Function pop() As Integer
	top As StackFrame Ptr = 0
End Type

Sub Stack.push(value As Integer)
	Dim newFrame As StackFrame Ptr = New StackFrame()
	newFrame->data = value
	newFrame->prev = this.top
	this.top = newFrame
End Sub

Function Stack.pop() As Integer
	If top = 0 Then Return 0
	Dim oldFrame As StackFrame Ptr = this.top
	Function = oldFrame->data
	this.top = oldFrame->prev
	Delete oldFrame
End Function

Dim myStack As Stack

myStack.push(5)
myStack.push(10)
myStack.push(15)

While myStack.top <> 0
	Print myStack.pop()
Wend

It's slightly longer, but still tiny. The usage code must be count because the thing you are calling 12 lines is only a stack frame implementation, useless without the actual stack framework.

Now I'm sure you can see how much easier my version is to use: pushing is simpler and more intuitive, but the biggest advantage comes with popping, which is just one line compared to your 3-4. There is also no need for the user to manage memory/pointers.

If you still disagree, try creating a more complicated usage example and see how tiresome and ugly popping becomes with your code, not to mention that the code line count will rise very quickly.

[counting_pine]

The original code in this thread looks quite Lispy I think, apart from the additional complication required for memory management.

Well just to throw in my own lot, here's a simple, string-based Integer stack:

Code: Select all

#define stacksize(s) (len(s) \ sizeof(cvi(s)))
#define push(s, n) s &= mki(n)
#define top(s) cvi(right(s, sizeof(cvi(s))))
#define pop(s) s = left(s, len(s) - sizeof(cvi(s)))
#define fastpop(s) cptr(integer ptr, varptr(s))[1] -= sizeof(cvi(s))

dim as string s
for i as integer = 1 to 10
    push(s, i)
next

while stacksize(s) > 0
    print top(s)
    pop(s)
wend

[KristopherWindsor]

@Aave - I know that can be done, but it's 22 lines vs. my 12. My solution can be re-implemented quickly for whatever data type you're working with (even multiple times in the same program), which is why the size matters.

Counting_pine has an interesting solution, but it won't work well for other data types.

[Aave]

Counting_pine really takes the lead in shortness and amount of magic :)

I know that can be done, but it's 22 lines vs. my 12.

I hate to repeat myself, but your implementation scales really badly: do a couple of more pops and you have longer code than mine and what's worse, code is duplicated. Also, my push is much shorter to write although the line count in that is the same. In addition, I find it a really bad design decision to try to shave off a couple of lines in the user-invisible type code with the cost of usability - especially when a nice interface can be implemented with even less lines as counting_pine has proved (I don't say my implementation is near perfect, I'm trying to make a point of the clunkyness of your interface).

If you were programming for some embedded microcontroller where you need to be the most space efficient, you would be using an array instead of a pointer list, not too differently from what counting_pine is doing.

My solution can be re-implemented quickly for whatever data type you're working with

The stack should be wrapped inside a macro that regenerates the Type for appropriate data types (i.e. replace Integer with a macro parameter and append the typename to the stack's typename). Then if you change the stack implementation, you don't have to keep several different implementations in sync as the compiler takes care of that.

[TJF]

Counting_pine has an interesting solution, but it won't work well for other data types.

This solution works well on each numeric data type. Just replace MKI / CVI by your requested data conversation statement (ie MKD / CVD or MKSHORT / CVSHORT).

And here's a similar STRING solution

Code: Select all

#DEFINE PUSH(_S_, _T_) _S_ &= !"\1" & _T_
#DEFINE TOP(_S_) MID(_S_, INSTRREV(_S_, !"\1") + 1)
#DEFINE POP(_S_) _S_ = LEFT(_S_, INSTRREV(_S_, !"\1") - 1)

VAR s = ""
FOR i AS INTEGER = 1 TO 10
  PUSH(s, "This is no " & STR(i))
NEXT

WHILE LEN(s)
  PRINT TOP(s)
  POP(s)
WEND

The strings must not contain CHR(1) or CHR(0).
It's not easy to count the entries on a STRING stack -- usually you don't need the number, it's sufficiant to know if there is any.

[counting_pine]

It can work for pointers too, assuming CVI/MKI can properly store pointers.

Here's a version that uses pointers with New/Delete:

Code: Select all

#define stacksize(s) (len(s) \ sizeof(cvi(s)))

#define push(s, n) s &= mki(n)
#define top(s) cvi(right(s, sizeof(cvi(s))))
#define pop(s) s = left(s, len(s) - sizeof(cvi(s)))
#define fastpop(s) cptr(integer ptr, varptr(s))[1] -= sizeof(cvi(s))

#define push_T(s, n, T) push(s, cint(new T(n)))
#define push_aT(s, n) push_T(s, n, typeof((n)))
#define top_T(s, T) *cptr(T ptr, top(s))
#define pop_T(s, T) delete @top_T(s, T): pop(s)
#define fastpop_T(s, T) delete @top_T(s, T): fastpop(s)


type MyUDT
    declare constructor ()
    declare constructor (byref as MyUDT)
    as integer elt
end type
constructor MyUDT(): elt = 0: end constructor
constructor MyUDT(byref rhs as MyUDT): elt = rhs.elt: end constructor


assert( sizeof(MyUDT ptr) = sizeof(cvi("")) )


dim as string s
dim as MyUDT u

for i as integer = 1 to 10
    u.elt = i
    push_aT(s, u)
next

while stacksize(s)
    print top_T(s, MyUDT).elt
    pop_T(s, MyUDT)
wend

(Note: new UDT(u) doesn't seem to copy-construct properly on simple structs, so you may want to give it an explicit copy-constructor.)

And here's a special String version (apparently we don't support New/Delete with Strings.)

Code: Select all

#define stacksize(s) (len(s) \ sizeof(cvi(s)))

#define push(s, n) s &= mki(n)
#define top(s) cvi(right(s, sizeof(cvi(s))))
#define pop(s) s = left(s, len(s) - sizeof(cvi(s)))
#define fastpop(s) cptr(integer ptr, varptr(s))[1] -= sizeof(cvi(s))

#define push_S(s, x) push(s, cint(callocate(sizeof(string)))): top_S(s) = x
#define top_S(s) *cptr(string ptr, top(s))
#define pop_S(s) Top_S(s) = "": pop(s)
#define fastpop_S(s) Top_S(s) = "": fastpop(s)


assert( sizeof(any ptr) = sizeof(cvi("")) )


dim as string s
for i as integer = 1 to 10
    push_S(s, i & " :)")
next

while stacksize(s) > 0
    print top_S(s)
    pop_S(s)
wend