Tiny Stack Implementation

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
KristopherWindsor
Posts: 2428
Joined: Jul 19, 2006 19:17
Location: Sunnyvale, CA
Contact:

Tiny Stack Implementation

Postby KristopherWindsor » Mar 28, 2011 12:54

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
Posts: 1009
Joined: Oct 11, 2008 7:42
Location: ABQ, NM
Contact:

Postby kiyotewolf » Jul 14, 2011 6:06

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
Posts: 128
Joined: Jun 13, 2008 19:55
Location: Helsinki, Finland
Contact:

Postby Aave » Jul 14, 2011 12:59

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
Posts: 1009
Joined: Oct 11, 2008 7:42
Location: ABQ, NM
Contact:

Postby kiyotewolf » Jul 14, 2011 13:40

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
Posts: 2428
Joined: Jul 19, 2006 19:17
Location: Sunnyvale, CA
Contact:

Postby KristopherWindsor » Jul 19, 2011 5:23

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

Aave wrote: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
Posts: 1009
Joined: Oct 11, 2008 7:42
Location: ABQ, NM
Contact:

Postby kiyotewolf » Jul 19, 2011 9:34

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

Aave wrote: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
Posts: 128
Joined: Jun 13, 2008 19:55
Location: Helsinki, Finland
Contact:

Postby Aave » Jul 19, 2011 12:40

KristopherWindsor wrote:
Aave wrote: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
Site Admin
Posts: 6225
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Jul 19, 2011 16:02

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
Last edited by counting_pine on Jul 20, 2011 12:30, edited 2 times in total.
KristopherWindsor
Posts: 2428
Joined: Jul 19, 2006 19:17
Location: Sunnyvale, CA
Contact:

Postby KristopherWindsor » Jul 20, 2011 11:30

@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
Posts: 128
Joined: Jun 13, 2008 19:55
Location: Helsinki, Finland
Contact:

Postby Aave » Jul 20, 2011 12:03

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

KristopherWindsor wrote: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.

KristopherWindsor wrote: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
Posts: 3600
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Postby TJF » Jul 20, 2011 13:53

KristopherWindsor wrote: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
Site Admin
Posts: 6225
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Jul 20, 2011 15:37

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

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 4 guests