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.

Introduced properties

abstract fun peek: E

core :: Queue :: peek

Look at the next element but does not remove it
abstract fun take: E

core :: Queue :: take

Take the next element (according to the specific queue)
fun take_all: Array[E]

core :: Queue :: take_all

Take and return all elements until the queue is empty.

Redefined properties

redef type SELF: Queue[E]

core $ Queue :: SELF

Type of this instance, automatically specialized in every class
redef fun first: E

core $ Queue :: first

first is made an alias of peek to avoid bad surprises

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?
fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?
type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
type CONCURRENT: ConcurrentCollection[E]

core :: Collection :: CONCURRENT

Type of the concurrent variant of this collection
type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter
protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack
abstract fun add(item: E)

core :: SimpleCollection :: add

Add item to this collection.
fun add_all(coll: Collection[E])

core :: SimpleCollection :: add_all

Add each item of coll.
protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according
fun as_random: Queue[E]

core :: SimpleCollection :: as_random

Return a random proxy queue where result.take is random.
protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.
fun class_name: String

core :: Object :: class_name

The class name of the object.
abstract fun clear

core :: RemovableCollection :: clear

Remove all items
fun combinations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations

All r-length combinations on self (in same order) without repeated elements.
fun combinations_with_replacement(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations_with_replacement

All r-length combination on self (in same order) with repeated elements.
fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer
fun count(item: nullable Object): Int

core :: Collection :: count

How many occurrences of item are in the collection?
fun first: E

core :: Collection :: first

Return the first item of the collection
init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer
fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.
fun has(item: nullable Object): Bool

core :: Collection :: has

Is item in the collection ?
fun has_all(other: Collection[nullable Object]): Bool

core :: Collection :: has_all

Does the collection contain at least each element of other?
fun has_any(other: Collection[nullable Object]): Bool

core :: Collection :: has_any

Does the collection contain at least one element of other?
fun has_exactly(other: Collection[nullable Object]): Bool

core :: Collection :: has_exactly

Does the collection contain exactly all the elements of other?
fun has_only(item: nullable Object): Bool

core :: Collection :: has_only

Is the collection contain only item?
fun hash: Int

core :: Object :: hash

The hash code of the object.
init init

core :: Object :: init

fun inspect: String

core :: Object :: inspect

Developer readable representation of self.
protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".
fun is_empty: Bool

core :: Collection :: is_empty

Is there no item in the collection?
intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).
fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?
intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.
abstract fun iterator: Iterator[E]

core :: Collection :: iterator

Get a new iterator on the collection.
fun join(separator: nullable Text, last_separator: nullable Text): String

core :: Collection :: join

Concatenate and separate each elements with separator.
fun length: Int

core :: Collection :: length

Number of items in the collection.
protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
fun not_empty: Bool

core :: Collection :: not_empty

Alias for not is_empty.
intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
fun output

core :: Object :: output

Display self on stdout (debug only).
intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
abstract fun peek: E

core :: Queue :: peek

Look at the next element but does not remove it
fun permutations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: permutations

All r-length permutations on self (all possible ordering) without repeated elements.
fun plain_to_s: String

core :: Collection :: plain_to_s

Concatenate elements without separators
fun product(r: Int): Collection[SequenceRead[E]]

core :: Collection :: product

Cartesian product, over r times self.
fun rand: E

core :: Collection :: rand

Return a random element form the collection
abstract fun remove(item: nullable Object)

core :: RemovableCollection :: remove

Remove an occurrence of item
fun remove_all(item: nullable Object)

core :: RemovableCollection :: remove_all

Remove all occurrences of item
fun sample(length: Int): Array[E]

core :: Collection :: sample

Return a new array made of (at most) length elements randomly chosen.
fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes
fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer
fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON
intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.
abstract fun take: E

core :: Queue :: take

Take the next element (according to the specific queue)
fun take_all: Array[E]

core :: Queue :: take_all

Take and return all elements until the queue is empty.
fun to_a: Array[E]

core :: Collection :: to_a

Build a new array from a collection
abstract fun to_concurrent: CONCURRENT

core :: Collection :: to_concurrent

Wraps self in a thread-safe collection
fun to_counter: Counter[E]

core :: Collection :: to_counter

Create and fill up a counter with the elements of `self.
fun to_curlslist: CURLSList

core :: Collection :: to_curlslist

Convert Collection[String] to CURLSList
fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON
abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON
fun to_s: String

core :: Object :: to_s

User readable representation of self.
fun to_shuffle: Array[E]

core :: Collection :: to_shuffle

Return a new array made of elements in a random order.
package_diagram core::Queue Queue core::SimpleCollection SimpleCollection core::Queue->core::SimpleCollection serialization::Serializable Serializable core::SimpleCollection->serialization::Serializable core::RemovableCollection RemovableCollection core::SimpleCollection->core::RemovableCollection ...serialization::Serializable ... ...serialization::Serializable->serialization::Serializable ...core::RemovableCollection ... ...core::RemovableCollection->core::RemovableCollection core::MinHeap MinHeap core::MinHeap->core::Queue

Ancestors

interface Collection[E: nullable Object]

core :: Collection

The root of the collection hierarchy.
interface Object

core :: Object

The root of the class hierarchy.
interface RemovableCollection[E: nullable Object]

core :: RemovableCollection

Items can be removed from this collection
interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize

Parents

interface SimpleCollection[E: nullable Object]

core :: SimpleCollection

Items can be added to these collections.

Children

class MinHeap[E: Object]

core :: MinHeap

A min-heap implemented over an array

Class definitions

core $ Queue
# 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