[erlang-questions] queues (previously: documentation of data structures)

[Matej Kosik]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Andras Georgy Bekes wrote:
>> The first step would be implementing a new data type: `cell' with operations such as
>> - - cell:empty/0 (create an empty cell)
>> - - cell:make/1 (create a cell with a given contents)
>> - - cell:get/1 (non-destructively get the contents of a cell. Block (or throw an error or some
>> predefined value if it is empty)
>> - - cell:put/2 (destructively overwrite a cell with a given value)
>> Basically, cell can be represented as a process that responds to proper messages. There can be
>> wrapper procedures
>> - - cell:/isEmpty/1 returns true if a given cell is empty
>>
>> If you have cells, you can implement `queue item' as a triple composed from:
>> - - a cell containing a reference to the previous `queue item'
>> - - a cell containing a reference to the value of the current `queue item'
>> - - a cell containing a reference to the next `queue item'.
>>
>> If you have that, you can represent the whole queue as a couple composed from:
>> - - a cell containing a reference to the head
>> - - a cell containing a reference to the tail
> 
> Why having a process for each queue entry???
> Ok, you can change a specific element once you've put on the
> queue, but you probably don't want that.
> 
> Why not just use the message queue of Erlang?
> (see attached module --- very simple)
> 
> Pros:
> - one process for each queue
> - same efficiency as the message queues of the VM
>   (hope you're satisfied with that)
> - works when several processes use a common queue
> 
> Cons:
> - copies each queued element twice (just like your solution)
> - ???
> 
> 	Georgy

I am looking at your code. I partially see what you tried to say but in your implementation, you
cannot perform operations for adding and removing elements from head and from tail in whatever
order. In your program, because of nested `receive' operations you first have to remove something
from the queue and then you must add something to the queue. You cannot
- - add two elements at the end of the queue
- - add two elements at the begining of the queue
- - remove elements from the end of the queue
Can you?

> 
> 
> ------------------------------------------------------------------------
> 
> -module(myqueue).
> 
> -export([start/0,init/0,put/2,get/1,delete/1]).
> 
> start()->
>     spawn(?MODULE,init,[]).
> 
> init()->
>     loop().
> 
> loop()->
>     receive
> 	{getnext,PID} ->
> 	    receive
> 		{element, Data} ->
> 		    PID ! {element,Data};
> 		stop ->
> 		    ok
> 	    end;
> 	stop->
> 	    ok
>     end,
>     loop().
> 
> 
> put(Queue,Data)->
>     Queue ! {element,Data},
>     ok.
> 
> get(Queue)->
>     Queue ! {getnext,self()},
>     receive
> 	{element,Data}->
> 	    Data
>     end.
> 
> delete(Queue)->
>     Queue ! stop,
>     ok.
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions


- --
Matej Kosik
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHXpCvL+CaXfJI/hgRAlpIAKC6PeZlbqu4s4QPpZkKBIsjVecT0gCgo/c7
W53QNOy4YqyYOuc+NIwdlDI=
=J70x
-----END PGP SIGNATURE-----