Stable priority queue

[Aaron W. LaFramboise]

Hello,

I understand that an easy way to make the standard std::priority_q ueue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements. For my application, which queues elements very quickly and
runs for an indefinite amount of time, this scenario is a real concern,
and will eventually cause incorrect results.

Is there any easy and painless way of correcting this order-stamp
wraparound problem?


Aaron W. LaFramboise

[Howard]

Re: Stable priority queue


"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote in message
news:1073ei45ak 96d5e@corp.supe rnews.com...[color=blue]
> Hello,
>
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?
>
>
> Aaron W. LaFramboise
>[/color]

I don't know if this will help you but...

In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:

YYYYMMDDHHNNSST TT

where

YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=millisecond s

(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :-))

That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :-)), but the queue is
restored on startup, so the ordering is still preserved properly.

-Howard

[Howard]

Re: Stable priority queue


"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote in message
news:1073ei45ak 96d5e@corp.supe rnews.com...[color=blue]
> Hello,
>
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?
>
>
> Aaron W. LaFramboise
>[/color]

I don't know if this will help you but...

In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:

YYYYMMDDHHNNSST TT

where

YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=millisecond s

(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :-))

That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :-)), but the queue is
restored on startup, so the ordering is still preserved properly.

-Howard

[Siemel Naran]

Re: Stable priority queue

"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote in message
[color=blue]
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?[/color]

What is a stable priority queue?

[Siemel Naran]

Re: Stable priority queue

"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote in message
[color=blue]
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?[/color]

What is a stable priority queue?

[Kevin Goodsell]

Re: Stable priority queue

Siemel Naran wrote:
[color=blue]
>
> What is a stable priority queue?
>
>[/color]

I'm guessing items of the same priority come out in the order they were
inserted.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Kevin Goodsell]

Re: Stable priority queue

Siemel Naran wrote:
[color=blue]
>
> What is a stable priority queue?
>
>[/color]

I'm guessing items of the same priority come out in the order they were
inserted.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Jack Klein]

Re: Stable priority queue

On Mon, 05 Apr 2004 14:57:53 -0500, "Aaron W. LaFramboise"
<aaronblue6@c ox-internet.com> wrote in comp.lang.c++:
[color=blue]
> Hello,
>
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?
>
>
> Aaron W. LaFramboise[/color]

Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:

if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;

Don't forget to include <limits.h> or <climits>.

If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[Jack Klein]

Re: Stable priority queue

On Mon, 05 Apr 2004 14:57:53 -0500, "Aaron W. LaFramboise"
<aaronblue6@c ox-internet.com> wrote in comp.lang.c++:
[color=blue]
> Hello,
>
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements. For my application, which queues elements very quickly and
> runs for an indefinite amount of time, this scenario is a real concern,
> and will eventually cause incorrect results.
>
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?
>
>
> Aaron W. LaFramboise[/color]

Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:

if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;

Don't forget to include <limits.h> or <climits>.

If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[Siemel Naran]

Re: Stable priority queue

"Kevin Goodsell" <usenet2.spamfr ee.fusion@never box.com> wrote in message[color=blue]
> Siemel Naran wrote:[/color]
[color=blue][color=green]
> > What is a stable priority queue?[/color]
>
> I'm guessing items of the same priority come out in the order they were
> inserted.[/color]

Then maybe we can use the protected member 'c'. The standard says

template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};

So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
non-polymorphic class bothers us, we can use private inheritance with using
declarations.

We could get stable queue's and stacks too.

Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).

[Siemel Naran]

Re: Stable priority queue

"Kevin Goodsell" <usenet2.spamfr ee.fusion@never box.com> wrote in message[color=blue]
> Siemel Naran wrote:[/color]
[color=blue][color=green]
> > What is a stable priority queue?[/color]
>
> I'm guessing items of the same priority come out in the order they were
> inserted.[/color]

Then maybe we can use the protected member 'c'. The standard says

template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};

So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
non-polymorphic class bothers us, we can use private inheritance with using
declarations.

We could get stable queue's and stacks too.

Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).

[Dietmar Kuehl]

Re: Stable priority queue

"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote:[color=blue]
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements.[/color]

Use a 128-bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
[color=blue]
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?[/color]

It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:

- empty() -> 'm.empty()'
- top() -> 'm.begin()->second.front() '
- pop() -> 'm.begin()->second.pop() ;
if (m.begin()->second.empty() ) m.erase(m.begin ())'
- push(e) -> 'm[e.priority].push(e)'

I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (d-heap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.
--
<mailto:dietmar _kuehl@yahoo.co m> <http://www.dietmar-kuehl.de/>
<www.contendix. com> - Software Development & Consulting

[Dietmar Kuehl]

Re: Stable priority queue

"Aaron W. LaFramboise" <aaronblue6@c ox-internet.com> wrote:[color=blue]
> I understand that an easy way to make the standard std::priority_q ueue
> stable is by including an integer stamp with each node that is
> incremented each time a new node is pushed into the queue. However, no
> matter what reasonably-sized type I use for the stamp, eventually the
> stamp will 'wrap around' and possibly cause incorrect ordering of
> elements.[/color]

Use a 128-bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
[color=blue]
> Is there any easy and painless way of correcting this order-stamp
> wraparound problem?[/color]

It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:

- empty() -> 'm.empty()'
- top() -> 'm.begin()->second.front() '
- pop() -> 'm.begin()->second.pop() ;
if (m.begin()->second.empty() ) m.erase(m.begin ())'
- push(e) -> 'm[e.priority].push(e)'

I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (d-heap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.
--
<mailto:dietmar _kuehl@yahoo.co m> <http://www.dietmar-kuehl.de/>
<www.contendix. com> - Software Development & Consulting

[Claudio Puviani]

Re: Stable priority queue

"Dietmar Kuehl" <dietmar_kuehl@ yahoo.com> wrote[color=blue]
> Use a 128-bit integer (eg. made out of four longs): I
> doubt that this one will overflow on any currently available
> machine before the sun (note, not the SUN) cheases to exist.
> Even if you account for faster processors you should be
> on the safe side.[/color]

Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani

[Claudio Puviani]

Re: Stable priority queue

"Dietmar Kuehl" <dietmar_kuehl@ yahoo.com> wrote[color=blue]
> Use a 128-bit integer (eg. made out of four longs): I
> doubt that this one will overflow on any currently available
> machine before the sun (note, not the SUN) cheases to exist.
> Even if you account for faster processors you should be
> on the safe side.[/color]

Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani