* Re: Queue implementation in Ada
2014-10-28 2:01 Queue implementation in Ada compguy45
@ 2014-10-28 3:30 ` Jeffrey Carter
2014-10-28 10:00 ` Simon Wright
2014-10-28 8:29 ` Dmitry A. Kazakov
` (2 subsequent siblings)
3 siblings, 1 reply; 10+ messages in thread
From: Jeffrey Carter @ 2014-10-28 3:30 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 3:30 ` Jeffrey Carter
@ 2014-10-28 10:00 ` Simon Wright
2014-10-28 18:29 ` Jeffrey Carter
0 siblings, 1 reply; 10+ messages in thread
From: Simon Wright @ 2014-10-28 10:00 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 10:00 ` Simon Wright
@ 2014-10-28 18:29 ` Jeffrey Carter
2014-10-28 19:25 ` Simon Wright
0 siblings, 1 reply; 10+ messages in thread
From: Jeffrey Carter @ 2014-10-28 18:29 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 18:29 ` Jeffrey Carter
@ 2014-10-28 19:25 ` Simon Wright
2014-10-28 20:27 ` Dmitry A. Kazakov
0 siblings, 1 reply; 10+ messages in thread
From: Simon Wright @ 2014-10-28 19:25 UTC (permalink / raw)
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!
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 19:25 ` Simon Wright
@ 2014-10-28 20:27 ` Dmitry A. Kazakov
2014-10-28 21:27 ` Simon Wright
0 siblings, 1 reply; 10+ messages in thread
From: Dmitry A. Kazakov @ 2014-10-28 20:27 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 2:01 Queue implementation in Ada compguy45
2014-10-28 3:30 ` Jeffrey Carter
@ 2014-10-28 8:29 ` Dmitry A. Kazakov
2014-10-28 9:56 ` Simon Wright
2014-10-28 13:16 ` Brad Moore
3 siblings, 0 replies; 10+ messages in thread
From: Dmitry A. Kazakov @ 2014-10-28 8:29 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 2:01 Queue implementation in Ada compguy45
2014-10-28 3:30 ` Jeffrey Carter
2014-10-28 8:29 ` Dmitry A. Kazakov
@ 2014-10-28 9:56 ` Simon Wright
2014-10-28 13:16 ` Brad Moore
3 siblings, 0 replies; 10+ messages in thread
From: Simon Wright @ 2014-10-28 9:56 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Queue implementation in Ada
2014-10-28 2:01 Queue implementation in Ada compguy45
` (2 preceding siblings ...)
2014-10-28 9:56 ` Simon Wright
@ 2014-10-28 13:16 ` Brad Moore
3 siblings, 0 replies; 10+ messages in thread
From: Brad Moore @ 2014-10-28 13:16 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread