Queue implementation in Ada

Queue implementation in Ada

[compguy45]

Is there queue fifo implemented in ada? I saw this example but not sure where he is fetting fifo package
http://rosettacode.org/wiki/Queue/Usage

Re: Queue implementation in Ada

[Jeffrey Carter]

On 10/27/2014 07:01 PM, compguy45@gmail.com wrote:
> Is there queue fifo implemented in ada? I saw this example but not sure where he is fetting fifo package
> http://rosettacode.org/wiki/Queue/Usage

Ada has synchronized queues; see ARM A.18.27-31

http://www.adaic.org/resources/add_content/standards/12rm/html/RM-A-18-27.html

If you want unsynchronized queues, you could build your own, possibly using
Ada.Containers.Doubly_Linked_Lists (ARM A.18.3). Or you could download an
existing library that implements them, such as the PragmAda Reusable Components

http://pragmada.x10hosting.com/pragmarc.htm

-- 
Jeff Carter
"You me on the head hitted."
Never Give a Sucker an Even Break
108

Re: Queue implementation in Ada

[Simon Wright]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> If you want unsynchronized queues, you could build your own, possibly
> using Ada.Containers.Doubly_Linked_Lists (ARM A.18.3).

I used Vectors, ARM A.18.2. Not sure why one would choose one over the
other?

Re: Queue implementation in Ada

[Jeffrey Carter]

On 10/28/2014 03:00 AM, Simon Wright wrote:
> Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:
> 
>> If you want unsynchronized queues, you could build your own, possibly
>> using Ada.Containers.Doubly_Linked_Lists (ARM A.18.3).
> 
> I used Vectors, ARM A.18.2. Not sure why one would choose one over the
> other?

In the sense that both are random-access sequences, with essentially the same
interface, there is none. One could build either as a wrapper around the other.

Clearly any difference must be in the implementation. Given that one is named
Doubly_Linked_Lists and the other adds index-based access, it's reasonable to
think that the former is expected to be implemented as a linked list and the
latter as an array. Since a queue experiences frequent additions to the tail and
frequent deletions from the head, the linked list seems appropriate.

-- 
Jeff Carter
"My mind is a raging torrent, flooded with rivulets of
thought, cascading into a waterfall of creative alternatives."
Blazing Saddles
89

Re: Queue implementation in Ada

[Simon Wright]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> On 10/28/2014 03:00 AM, Simon Wright wrote:
>> Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:
>> 
>>> If you want unsynchronized queues, you could build your own, possibly
>>> using Ada.Containers.Doubly_Linked_Lists (ARM A.18.3).
>> 
>> I used Vectors, ARM A.18.2. Not sure why one would choose one over the
>> other?
>
> In the sense that both are random-access sequences, with essentially
> the same interface, there is none. One could build either as a wrapper
> around the other.
>
> Clearly any difference must be in the implementation. Given that one
> is named Doubly_Linked_Lists and the other adds index-based access,
> it's reasonable to think that the former is expected to be implemented
> as a linked list and the latter as an array. Since a queue experiences
> frequent additions to the tail and frequent deletions from the head,
> the linked list seems appropriate.

Good point.

I've been put off Doubly_Linked_Lists because I would usually have been
quite happy with singly linked lists. But really, what difference does
it make if all you're doing is implementing a Queue!

Re: Queue implementation in Ada

[Dmitry A. Kazakov]

On Tue, 28 Oct 2014 19:25:20 +0000, Simon Wright wrote:

> I've been put off Doubly_Linked_Lists because I would usually have been
> quite happy with singly linked lists. But really, what difference does
> it make if all you're doing is implementing a Queue!

Much. Singly-linked list is LIFO because only one end has O(1)
insertion/deletion. For a FIFO it is O(1) at one end and O(n) at another.
Thus the overall complexity is O(n), which is catastrophic. Doubly-linked
list has O(1) at any of its ends (and at any element in between).

However, using doubly-linked lists is an overkill for queues. Furthermore,
it requires dynamic memory allocation and maintenance of the list of free
elements (to reduce allocate/deallocate penalty). It is also not a very
good idea to let the queue grow infinitely. Usually a fixed size ring
buffer array is a better choice for a queue.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Queue implementation in Ada

[Simon Wright]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> Doubly-linked list has O(1) at any of its ends (and at any element in
> between).

The Booch Components are a counter-example to this assertion (I'm not in
any way saying that that's a good thing!); Append is indeed O(n).

Re: Queue implementation in Ada

[Dmitry A. Kazakov]

On Mon, 27 Oct 2014 19:01:58 -0700 (PDT), compguy45@gmail.com wrote:

> Is there queue fifo implemented in ada? I saw this example but not sure where he is fetting fifo package
> http://rosettacode.org/wiki/Queue/Usage

A lock-free queue:

http://www.dmitry-kazakov.de/ada/components.htm#Generic_FIFO

P.S. There is no universal queue implementation because requirements and
use scenario usually dictate this or that implementation.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Queue implementation in Ada

[Simon Wright]

compguy45@gmail.com writes:

> Is there queue fifo implemented in ada? I saw this example but not
> sure where he is fetting fifo package
> http://rosettacode.org/wiki/Queue/Usage

From here:
http://rosettacode.org/wiki/Queue/Definition#Ada

Re: Queue implementation in Ada

[Brad Moore]

On 2014-10-27 8:01 PM, compguy45@gmail.com wrote:
> Is there queue fifo implemented in ada? I saw this example but not sure where he is fetting fifo package
> http://rosettacode.org/wiki/Queue/Usage
>

Yet another option:

http://sourceforge.net/projects/dequesterity/

This is a suite of composable queues/deques where you can pick and 
choose features using a generic hierarchy.
eg. Bounded, Unbounded, Streaming, Synchronized (protected or task), 
Ravenscar, multiple readers/writers, Priority Queue, Remote, Streaming, etc.

Depending on your needs though, you might find that the standard library 
containers are sufficient. (Vectors, Doubly_Linked_Lists, or 
Synchronized_Queues) I'd look at those first, then if these are not 
sufficient, have a look at other solutions, such as the ones mentioned 
in this thread.

Brad