This interface is used for data structures and algorithms that need some queuing but that let their users control how the queuing is done.
Most concrete queues have an efficient implementation of the basic methods
is_empty
, length
, add
, peek
, and take
.
However, the remove
method is possibly inefficient.
To workaround an inefficient implementation, one can instead mark the removed
elements (with a flag or in a set), and ignore then when take
returns one.
Unless stated otherwise, the iterator
method is unrelated with the queue
logic and may visit the elements in a order dependent on implementation.
core :: Queue :: defaultinit
core :: Collection :: CONCURRENT
Type of the concurrent variant of this collectionserialization :: Serializable :: accept_json_serializer
Refinable service to customize the serialization of this class to JSONserialization :: Serializable :: accept_msgpack_attribute_counter
Hook to customize the behavior of theAttributeCounter
serialization :: Serializable :: accept_msgpack_serializer
Hook to customize the serialization of this class to MessagePackserialization :: Serializable :: add_to_bundle
Called by[]=
to dynamically choose the appropriate method according
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Collection :: combinations
Allr
-length combinations on self (in same order) without repeated elements.
core :: Collection :: combinations_with_replacement
Allr
-length combination on self (in same order) with repeated elements.
serialization :: Serializable :: core_serialize_to
Actual serialization ofself
to serializer
core :: SimpleCollection :: defaultinit
core :: Queue :: defaultinit
core :: Collection :: defaultinit
core :: Object :: defaultinit
serialization :: Serializable :: from_deserializer
Create an instance of this class from thedeserializer
core :: Collection :: has_all
Does the collection contain at least each element ofother
?
core :: Collection :: has_any
Does the collection contain at least one element ofother
?
core :: Collection :: has_exactly
Does the collection contain exactly all the elements ofother
?
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
serialization :: Serializable :: msgpack_extra_array_items
Hook to request a larger than usual metadata arraycore :: Object :: output_class_name
Display class name on stdout (debug only).core :: Collection :: permutations
Allr
-length permutations on self (all possible ordering) without repeated elements.
core :: Collection :: product
Cartesian product, overr
times self
.
core :: RemovableCollection :: remove
Remove an occurrence ofitem
core :: RemovableCollection :: remove_all
Remove all occurrences ofitem
serialization :: Serializable :: serialize_msgpack
Serializeself
to MessagePack bytes
serialization :: Serializable :: serialize_to
Serializeself
to serializer
serialization :: Serializable :: serialize_to_json
Serializeself
to JSON
core :: Collection :: to_concurrent
Wrapsself
in a thread-safe collection
core :: Collection :: to_counter
Create and fill up a counter with the elements of `self.core :: Collection :: to_curlslist
Convert Collection[String] to CURLSListserialization :: Serializable :: to_pretty_json
Serializeself
to plain pretty JSON
core :: Collection :: to_shuffle
Return a new array made of elements in a random order.Serializer::serialize
# Queues are collection that controls how elements are retrieved.
#
# This interface is used for data structures and algorithms that need
# some queuing but that let their users control how the queuing is done.
#
# Most concrete queues have an efficient implementation of the basic methods
# `is_empty`, `length`, `add`, `peek`, and `take`.
# However, the `remove` method is possibly inefficient.
# To workaround an inefficient implementation, one can instead mark the removed
# elements (with a flag or in a set), and ignore then when `take` returns one.
#
# Unless stated otherwise, the `iterator` method is unrelated with the queue
# logic and may visit the elements in a order dependent on implementation.
interface Queue[E]
super SimpleCollection[E]
# Take the next element (according to the specific queue)
# ~~~
# var a = (new Array[Int]).as_lifo
# a.add 1
# a.add 2
# assert a.take == 2
# assert a.take == 1
#
# var h = new MinHeap[Int].default
# h.add 2
# h.add 1
# h.add 10
# assert h.take == 1
# assert h.take == 2
# assert h.take == 10
# ~~~
# ensure `result == peek`
fun take: E is abstract
# Look at the next element but does not remove it
#
# ~~~
# var a = (new Array[Int]).as_lifo
# a.add 1
# assert a.peek == 1
# a.add 2
# assert a.peek == 2
# assert a.take == 2
# assert a.peek == 1
# ~~~
fun peek: E is abstract
# `first` is made an alias of `peek` to avoid bad surprises
redef fun first do return peek
# Take and return all elements until the queue is empty.
#
# Ensure:
# * `is_empty`
# * `result.length == old(length)`
# * `not old(is_empty) implies result.first == old(peek)`
#
# ~~~
# var a = (new Array[Int]).as_lifo
# a.add 1
# a.add 2
# a.add 3
# assert a.take_all == [3, 2, 1]
# assert a.is_empty
# ~~~
fun take_all: Array[E]
do
var res = new Array[E]
while not is_empty do res.add take
return res
end
end
lib/core/queue.nit:26,1--98,3