[erlang-questions] Managing priority heaps.

[Anders Nygren]

On Nov 3, 2007 9:05 PM, Jérémie Lumbroso <jeremie@REDACTED> wrote:
> Hello,
>
> I am trying to write a loop:
>
>     myloop(Lists, PriorityList)
>
> where:
>
>   * Lists is a tuplet of a number X of lists;
>   * PriorityList is a list of numbers N, such that 1 <= N <= X.
>
>   [Y|PrioRest] = PriorityList
>
> On every call, myloop needs to look at the first element of PriorityList,
> let that element be Y, and select list Y from the tuplet Lists (i.e.:
> SelectedList = element(Lists, Y) is called).
>
>   [Fst|Rest] = SelectedList
>
> Then myloop must take the first element Fst of SelectedList, process it,
> get a new priority number Z, and reinsert the element at the *end* of the
> list Z.
>
>   A = setElement(Lists, Y, Rest);
>   B = setElement(A, Z, element(A, Z) ++ [Fst]).
>
> Once this operation is done, myloop calls itself:
>
>   myloop(B, PrioRest ++ [Y]).
>
> The whole purpose of this operation is to have several priorities.
> PriorityList, will, for instance, be equal to [1, 2, 1, 2, 1, 3].
>
>
> My myloop function is long and convoluted, and has lots of bindings, which
> is quite hellish to manage.
>
> The thing is, I assume this sort of functionality must be quite common in
> Erlang's field of predilection ... and so I'm wondering if there isn't
> already some module to do this.
>
> Is there? And if not, could you help me?
>

I dont think there is anything ready made for this, but You can look at two
modules in stdlib that can be useful.
- queue, obviously queue functions, instead of element(A, Z) ++ [Fst] which
gets expensive if the lists are long.
- ets, with table type ordered set. to make a priority queue in ets
store your entries as {{Prio,now()}, Data}, when You read you get the first
inserted, using suitable matching/selection functions.
-search the archive, priority queue have been discussed several times before.

/Anders