eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'Queue':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: Queue


Inheritance:

   Object
   |
   +--Collection
      |
      +--Queue
         |
         +--SharedQueue

Package:
stx:libbasic2
Category:
Collections-Ordered
Version:
rev: 1.47 date: 2019/06/04 10:37:50
user: cg
file: Queue.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
Claus Gittinger

Description:


Queues provide a simple implementation of a collection,
where elements are added at one end and removed at the other.

Access protocol is somewhat like a stream's protocol, 
i.e. access is by #nextPut: and #next.

The queue is created with a size argument, defining how many elements
are to be stored. It will report an error if the queue ever becomes full
and another element is to be added. 
Likewise, it will report an error if it is empty and an element is to be removed.

It is NOT safe when two processes access the same queue-instance simultaneously,
since accesses to the internals are not protected against process-switches.
See SharedQueue for a class which IS safe w.r.t. processes and which blocks
on write when full or on read when empty.

[Implementation note:]
    All of queue's functionality is also provided by the OrderedCollection (OC)
    class; OC could easily simulate a queue (using #addLast: / #removeFirst).
    The reason for providing Queue is not any speed advantage
    (actually, OC seems to be even a tiny bit faster).
    The point is that an implementation of SharedQueue as a subclass of OC
    would require that many OC methods had to be blocked and/or redefined in
    such a subclass, to care for simultaneous access.
    Since queue implements a much more lightweight protocol,
    the sharedQueue implementation is much cleaner when based on this more
    lightweight Queue class.


Class protocol:

defaults
o  defaultSize

instance creation
o  new
return a new queue with space for some elements

o  new: size
return a new queue with space for size elements


Instance protocol:

accessing
o  at: index
return an element from the queue - indexing starts at 1 with the element
which would next be fetched

o  remove: anElement ifAbsent: exceptionalValue
remove and return a particular element from the queue;
Return the value from exceptionalValue if the element is not in the queue

o  removeAll
remove all elements in the queue; return the receiver

o  removeIdentical: anElement ifAbsent: exceptionalValue
remove and return a particular element from the queue;
Return the value from exceptionalValue if the element is not in the queue

o  removeLast
remove and return the last value in the queue;
Return nil, if the queue is empty

accessing-protocol compatibility
o  add: someObject
same as #nextPut: - for protocol compatibility with other collections

o  addFirst: someObject
same as #nextPutFirst: - for protocol compatibility with other collections

o  removeFirst
same as #next - for protocol compatibility with other collections

accessing-reading
o  next
return the next value in the queue;
Return nil, if the queue is empty.
WARNING: this is an old behavior, which should be changed
to raise an error if empty.
It is left in here until all queue-users have been changed to
call nextOrNil instead, to avoid breaking existing applications.

o  nextOrNil
return the next value in the queue;
Return nil, if the queue is empty

o  peek
return the next value in the queue without removing it.
If the queue is empty, return nil.

o  peekOrNil
return the next value in the queue without removing it.
If the queue is empty, return nil.

accessing-writing
o  nextPut: anObject
enter anObject into the queue - if the queue is full, report an error

o  nextPutAll: aCollection
enter all elements from aCollection into the queue.

o  nextPutFirst: anObject

enumerating
o  do: aBlock
evaluate the argument, aBlock for each element in the queue

o  reverseDo: aBlock
evaluate the argument, aBlock for each element in the queue

initialization
o  capacity: newSize
change the capacity of the queue.
That is the number of slots it can hold
before the writer gets an exception (here)
or is suspended (in SharedQueue).

o  init: size
initialize the receiver for size entries

not implemented
o  findFirst: anObject ifNone: aBlock
(comment from inherited method)
find the index of the first element, for which evaluation of the argument, aBlock returns true;
return its index or the value from exceptionValue if none detected.
This is much like #detect:ifNone:, however, here an INDEX is returned,
while #detect:ifNone: returns the element.

o  findLast: anObject ifNone: aBlock
(comment from inherited method)
find the index of the last element, for which evaluation of the argument, aBlock returns true.
Return its index or the value from exceptionValue if none detected.

o  grow: newSize
(comment from inherited method)
change the receiver's size

queries
o  capacity
return the number of elements the queue can hold.
Trying to add more will:
- raise an error in queue
- block the writer in sharedQueue
- lead to an automatic resize in UnlimitedSharedQueue

o  isEmpty
return true, if there are no elements in the queue

o  isFull
return true, if the queue is full i.e. if writing is not
possible

o  size
return the number of elements in the queue

o  species
return the type of collection to be returned by collect, select etc.

testing
o  isFixedSize
return true if the receiver cannot grow


Examples:


adding at one end, removing at the other ...
  |q element  |

  q := Queue new:10.
  1 to:5 do:[:i |
      Transcript showCR:('adding ' , i printString).
      q nextPut:i
  ].

  [q notEmpty] whileTrue:[
      element := q next.
      Transcript showCR:('removed ' , element printString).
  ].
timing; Queue vs. OrderedCollection
  |q oc tQueue tOC  |

  q := Queue new:100.
  tQueue := Time millisecondsToRun:[
      1000 timesRepeat:[
          1 to:100 do:[:i |
              q nextPut:i
          ].
          [q isEmpty] whileFalse:[
              q next
          ].
      ]
  ].

  oc := OrderedCollection new:100.
  tOC := Time millisecondsToRun:[
      1000 timesRepeat:[
          1 to:100 do:[:i |
              oc addLast:i
          ].
          [oc isEmpty] whileFalse:[
              oc removeFirst
          ].
      ]
  ].
  Transcript showCR:('queue time: ' , tQueue printString , ' ms').
  Transcript showCR:('oc time   : ' , tOC printString , ' ms').


ST/X 7.2.0.0; WebServer 1.670 at bd0aa1f87cdd.unknown:8081; Fri, 29 Mar 2024 08:36:38 GMT