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

[Lev Walkin]

Matej Kosik wrote:
> -----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

no problem, just send a couple of messages not waiting for results.
messages will be queued there.

> - - add two elements at the begining of the queue

queue != dequeue.

> - - remove elements from the end of the queue

queue != dequeue, so this shouldn't necessarily be possible.

> Can you?