CODEWITHSUNDEEP
erlang
some_id
some_id

Reputation: 29896

Setting a limit to a queue size

How does one set a queue to hold N values. When the N is reached, remove the last item and add a value to the front of the queue.

Should this be done with if statement?

I also want to calculate the values within the queue as a new item is added. e.g. add all of the values in the queue.

Upvotes: 1

Views: 1808

Answers (2)

nmichaels
nmichaels

Reputation: 50981

Given the comments, this will do it:

enqueue(Value, Queue) ->
    Pushed = queue:in(Value, Queue),
    Sum = fun (Q) -> lists:sum(queue:to_list(Q)) end,
    case queue:len(Pushed) of
        Len when Len > 10 ->
            Popped = queue:drop(Pushed),
            {Popped, Sum(Popped)};
        _ ->
            {Pushed, Sum(Pushed)}
    end.

If you don't actually want to sum the items, you can use lists:foldl instead, or just write a function to do the operation directly on a queue.

Upvotes: 4

rvirding
rvirding

Reputation: 20916

I assume from your query that you both want to maximize the length of the queue and get the sum of all the values.

To answer your easiest question first: Erlang queues, however you wish to represent them, are normal Erlang data structures so there are no problems in storing them in a dictionary.

The OTP queue module is actually very simple but the plethora of interfaces easily makes it confusing to use. @Nathon's enqueue function can be made much more efficient by not using the queue data structure directly but by defining your own data structure which includes the queue and its current length, {Length,Queue}. If the sum is important then you could even include it as well.

The queue representations are very simple so it is very easy to write your own specialised form of it.

The simplest way is to keep the queue in a list and take elements from the head and add new elements to the end. So :

new(Max) when is_integer(Max), Max > 0 -> {0,Max,[]}.   %Length, Max and Queue list

take({L,M,[H|T]}) -> {H,{L-1,M,T}}.

add(E, {L,M,Q}) when L < M ->
    {L+1,M,Q ++ [E]};                                   %Add element to end of list
add(E, {M,M,[H|T]}) -
    {M,M,T ++ [E]}.                                     %Add element to end of list

When the queue becomes full the oldest member, which is at the front of the queue, is dropped. An empty queue generates an error. This is a very simple structure but it is inefficient as the queue is copied every time a new element is added. Reversing the list does not help as then the list is copied every time an element is removed from it. But it is simple, and it does work.

A much more efficient structure is to split the queue into two lists, the front end of the queue and the rear end of the queue. The rear end is reversed and becomes the new front when the front is empty. So:

new(Max) when is_integer(Max), Max > 0 ->
    {0,Max,[],[]}.                                      %Length, Max, Rear and Front

take({L,M,R,[H|T]}) -> {H,{L-1,M,R,T}};
take{{L,M,R,[]}) when L > 0 ->
    take({L,M,[],lists:reverse(R)}).                    %Move the rear to the front

add(E, {L,M,R,F}) when L < M ->
    {L+1,M,[R|E],F};                                    %Add element to rear
add(E, {M,M,R,[H|T]}) ->
    {M,M,[R|E],T};                                      %Add element to rear
add(E, {M,M,R,[]}) ->
    add(E, {M,M,[],lists:reverse(R)}).                  %Move the rear to the front

Again when the queue becomes full the oldest member, which is at the front of the queue, is dropped and an empty queue generates an error. This is the data structure used in the queue module.

It would be very easy to add the current sum of the elements to the structure and manage it directly.

Often, when working on simple data structures like this, it is just as easy to roll your own module as it is to use a provided one.

Upvotes: 6

Related Questions