[erlang-questions] Behaviour of queue

[Joe Armstrong]

Queue as robert said, are really easy. The simplest possible queue is
just a pair of lists {In, Out}. As new elements are added they are
appended to In

So we can write:

    new_queue() -> {[], []}.

   add(X, {In,Out}) -> {[X|In}, Out}.

What about extracting elements from the queue - these come from Out, so ...

   remove({In, [X|Out]} -> {X, {In, Out}};
...

But hang on, what happens in Out is empty - well if In is also empty
we have nothing to
remove so:

   remove({[], []}) -> empty;

Otherwise In is non empty and Out is empty so we revers In and move it
to Out and try again

   remove({In, []}) -> remove({[], reverse(In)}).

The nice thing about this is that amortized cost of using the queue is constant.
We create a single cons cell when adding to the In list, and a single
cons cell when
moving an element from the In to Out list - each element is only
touched once as it
moves from input to output.

This is by far the best method for short queue non persistent queues.

This pattern - a pair of two lists, one reversed one in normal order
is used over and
over again in many guises - it's the "natural" representation for a text editor.
Files are queues of lines. The current line being edited is a queue of
characters, etc.

Well worth remembering the pattern ...

/Joe



On Fri, Sep 10, 2010 at 11:13 AM, Chandru
<chandrashekhar.mullaparthi@REDACTED> wrote:
> On 9 September 2010 14:03, Fredrik Andersson <sedrik@REDACTED> wrote:
>
>> Hi all
>>
>> I have a question concerning the behaviour of the erlang queue module.
>> Does it store everything in memory or will it fallback to storing
>> things on disk if memory is running short? If it does not I need to
>> implement a layer on top of queue that will fallback to store things
>> on disk if needed.
>>
>>
> You can simulate a queue using an ordered_set mnesia table with the value of
> now() as the primary key. That might save you writing an extra layer on top.
>
> cheers
> Chandru
>