A Simple Queue Module

Monkey Forums/User Modules/A Simple Queue Module

ImmutableOctet(SKNG)

(Posted 2013) [#1]

I figured since I'm pretty much done working on it, I'd post my queue module.

This module is based on dmaz's example in this thread.

I reworked and rewrote it for my own personal needs. The biggest differences are the conversion commands and the basic comparison system. For those who are interested, I made a few demos/examples that come along with it.

Some parts of this I definitely could have done better, but I really can't be bothered at the moment.

You can find the module itself here: https://bitbucket.org/ImmutableOctet/queue

(To actually download the module, go to downloads, then branches, and download 'master' in any format you see fit. Or you could always clone it off of the git server itself.)

Mark, if you end up viewing this post; would you mind adding something like this to Monkey by default?

marksibly

(Posted 2013) [#2]

Hi,

To date, whenever I've needed a queue I just use a List and AddLast/RemoveFirst.

But an array based one is probably more efficient, although yours doesn't look quite right to me - if you Put a bunch of values, then Get a few less, the ToArray, ToList etc. methods look like they'll fail as they iterate from 0 to IN. Also, when the array grows sometimes you need to insert space...?

Here's my quick attempt at a 'Deque' (a doubly ended queue - a tad more flexible and the name hopefully wont clash with anything) . Not throughly tested, and it can probably be optimized a bit...does it look OK?

Class Deque<T>

	Method Clear:Void()
		_first=0
		_last=0
	End
	
	Method Length:Int() Property
		If _last>=_first Return _last-_first
		Return _capacity-_first+_last
	End
	
	Method IsEmpty:Bool() Property
		Return _first=_last
	End
	
	Method Get:T( index:Int )
#If CONFIG="debug"
		If index<0 Or index>=Length Error "Illegal deque index"
#Endif
		Return _data[(index+_first)Mod _capacity]
	End
	
	Method Set:Void( index:Int,value:T )
#If CONFIG="debug"
		If index<0 Or index>=Length Error "Illegal deque index"
#Endif
		_data[(index+_first)Mod _capacity]=value
	End
	
	Method PushFirst:Void( value:T )
		If Length+1>=_capacity Grow
		_first-=1
		If _first<0 _first=_capacity-1
		_data[_first]=value
	End
	
	Method PushLast:Void( value:T )
		If Length+1>=_capacity Grow
		_data[_last]=value
		_last+=1
		If _last=_capacity _last=0
	End
	
	Method PopFirst:T()
#If CONFIG="debug"
		If IsEmpty() Error "Illegal operation on empty deque"
#Endif
		Local v:=_data[_first]
		_data[_first]=NIL
		_first+=1
		If _first=_capacity _first=0
		Return v
	End
	
	Method PopLast:T()
#If CONFIG="debug"
		If IsEmpty() Error "Illegal operation on empty deque"
#Endif
		If _last=0 _last=_capacity
		_last-=1
		Local v:=_data[_last]
		_data[_last]=NIL
		Return v
	End
	
	Method First:T()
#If CONFIG="debug"
		If IsEmpty() Error "Illegal operation on empty deque"
#Endif
		Return _data[_first]
	End
	
	Method Last:T()
#If CONFIG="debug"
		If IsEmpty() Error "Illegal operation on empty deque"
#Endif
		Return _data[_last]
	End
	
	Private
	
	Global NIL:T
	
	Field _data:T[]
	Field _capacity
	Field _first:Int
	Field _last:Int
	
	Method Grow:Void()
		Local data:=New T[_capacity*2+10]
		If _first<=_last
			For Local i:=_first Until _last
				data[i-_first]=_data[i]
			Next
			_last-=_first
			_first=0
		Else
			Local n:=_capacity-_first
			For Local i:=0 Until n
				data[i]=_data[_first+i]
			Next
			For Local i:=0 Until _last
				data[i+n]=_data[i]
			Next
			_last+=n
			_first=0
		Endif
		_capacity=data.Length
		_data=data
	End

End

AdamRedwoods

(Posted 2013) [#3]

+1 for Deque, fifo, filo, milo.

although the Grow() routine, do we really need to drop a new reference or can you just maintain things in 512 ("n") sized non-consecutive blocks? what's the performance hit vs a complete reference copy?
EDIT: i'm thinking too far ahead.

Skn3	(Posted 2013) [#4]

+1 as well :D

computercoder

(Posted 2013) [#5]

Very nice, +1 for Deque! :)

ImmutableOctet(SKNG)

(Posted 2013) [#6]

The dequeue looks like a good idea, but for the sake of optimization and control, I'm going to stick to my queue class. However, I do think 'Dequeue' should be a part of Monkey; if that happens, I can make conversion commands for my own queue.

The dequeue code you posted is a bit messy, but other than that, it looks good. Plus, I'd rather it be in that style if added to vanilla Monkey, because everything else is, and I'd rather have it be consistent. (Or the other code gets 'cleaned up')

The problems you were talking about with 'ToList' and ToArray (As well as 'ToStack', and 'Clone' by extension) were an oversight by myself, and are fixed now.

marksibly

(Posted 2013) [#7]

> The dequeue code you posted is a bit messy

Well, queues are a bit messy!

As far as I can tell, your code is still fundamentally broken, eg: try this:

Function Main:Int()

	Local q:=New Queue<Int>
	
	q.Put 1
	q.Put 2
	q.Put 3
	
	Print q.Get()	'pop 1
	Print q.Get()	'pop 2
	
	q.Put 4
	q.Put 5
	q.Put 6
	
	Print q.Get()	'pop 3?
	Print q.Get()	'pop 4?

	Return 0
End

...should print 1,2,3,4 but actually prints 1,2,0,0.

Then main problem is that you can end up with a situation where In<Out, which you don't seem to have taken into account anywhere.

This does indeed make things messy, esp. when the array needs to be resized as 'space' needs to be inserted between In and Out, not just tacked on to the end.

ImmutableOctet(SKNG)

(Posted 2013) [#8]

I really should have tested my queue more thoroughly, for what it's worth; thanks for the feedback.

I should hopefully be done with it, but if you find any more issues, let me know. I just committed a fix to the repository for what you were mentioning, and you were right, it was broken. From the look of it, I don't think I should make modules while I'm sick.

When I said your code was messy, I was talking about how sloppy the code looks. There's lowercase names, some indenting problems, spacing issues, and there's a lack of parentheses in some places. This looks closer to Blitz Basic's fast to write but slow to compile style, which I'm not against, but it doesn't encourage strict programming at all. It just doesn't look like there's a particular style or design philosophy to it, and to me that just screams "rough draft".

I take pride in writing my code as optimally as possible without losing style or reasonability. I always follow the proper design of a language as closely as possible, and when a language or API strays from its routes, I don't adapt with it without good reason. A good example of this would be Microsoft's naming schemes with their APIs. And then you have C#'s style of doing things, which is even worse about this, but at least it's actually separate from C and C++, so it's less insulting, but I'm getting off-topic.

Besides it fitting my needs in other respects, the biggest reason I stick with Monkey is because it looks clean and refined. Monkey has the history of Blitz Basic and Blitz Max on its side (Not to mention some Java and C# aspects, which isn't entirely bad), and I think it takes some of their best qualities into consideration. My biggest problems with it are a lack of lower-level access in the language itself, and some things aren't as optimal as they could be. This mainly has to do with a lack of other types of integers, and a few things I can live without in a non-native environment.

Anyway, now that I'm done ranting; your dequeue class does look like it functions properly, so it should work well for most users. I'm definitely all for you adding it to Monkey.

AdamRedwoods

(Posted 2013) [#9]

I was talking about how sloppy the code looks

i've seen worse.

ziggy

(Posted 2013) [#10]

i've seen worse.

Mine is usualy worse. I'm learning to help myself with the maintenance of code and I'm getting better, but Marks one is very simple compact and I like that.

marksibly

(Posted 2013) [#11]

'Eye of the beholder' thing I guess, but I do recommend the use of mixed case/munged symbols.

In particular, if I see: 'length' in my code, I know it's a local, if I see '_length' I know it's a field and if I see 'Length' I know it's a (possibly computed) property. In general anyway...

With your code, I found it quite hard to read since if I saw 'Length' I'd have to hunt around to find it's declaration.

It also allows you to 'overload' names a bit, eg: you can have a _data field and a Data property.

Incidentally, your Queue is still broken, eg:

'add this to queue.monkey to test!
Function Main:Int()

	Local q:=New Queue<Int>
	
	For Local i:=1 To 100
		q.Put i
		Print q.Get()
	Next
	
	Print "Capacity="+q.Data.Length  'size of internal buffer.

	Return 0
End

The problem is 'In' never wraps around, since you always grow the array immediately before it gets a chance to in Put().

ImmutableOctet(SKNG)

(Posted 2013) [#12]

I saw that exact issue before, it's not broken, just inefficient. In terms of getting the size, you should be using 'Size' (Or 'Length' for those who want it). Other than that, I've only used 'Length' once or twice as a local, and that has now been changed from the look of it. But really, if the comments point to it, and the local declaration is right there, confusion shouldn't be an issue.

However, I do agree with what you were saying about what is basically a memory leak, and I even made a small comment about this. I was thinking of eventually just checking unused space until it reached a multiple of 'InitSize', then shifting over (I'd probably do this in 'Put'). That doesn't exactly sound efficient, but it would be an effective approach. I may just end up having 'In' wrap back around properly, but it sounds like it could cause problems.

The reason for so many really basic wrappers for commands is choice, and keeping things consistent with other modules ('Push', 'Pop', 'Add', 'Remove', etc). Allowing users to use these same commands their used to is not only more convenient, but you could technically switch out what class is doing what, making it act almost as a wrapper itself.

Basically, if you make sure all unaltered wrapper methods call the same method, the implementation is not only easy to find, but consistent between the commands. In example; if you have 'Length' return 'Count', but 'Count' changes, you might get problems. However, if 'Length' returned 'Size', I never have to change or worry about it. This model of doing things has served me well in the past, I just need to get around to documenting it (For this module at the very least).

Honestly, I do agree that this is a bit cluttered, but at least it has a strict design philosophy behind it. However, the 'GetData' and 'SetData' methods were honestly only there to try and make things more future-proof and controllable, but I don't think it's really worth having them there at this point.

I've moved everything 'Data' related to two properties now. Assignment of '_Data' should be done using the 'Data' property if it's from an outside/unrelated source, otherwise use '_Data' itself.

ImmutableOctet(SKNG)

(Posted 2013) [#13]

It's not the best of methods, but I've added the whole 'reuse indexes' thing to the module. I've also added conversion commands to and from 'Deques'. Everything should be in working order now, and there shouldn't be any glaring flaws.

Those who want to use this module with a version older than v76 should define QUEUE_MONKEY_LEGACY as true in their own source code, or change the default in 'queue.monkey' itself.

AdamRedwoods

(Posted 2013) [#14]

I couldn't help it, but per my weird post above, I created a "bucket deque" (no Grow() routine). This darn thread made me do it!

http://monkeycoder.co.nz/Community/posts.php?topic=6037