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.62 date: 2024/02/23 08:59:35
user: cg
file: Queue.st directory: libbasic2
module: stx stc-classLibrary: libbasic2

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.

 [Instance variables:]
     readPosition      <SmallInteger>  index of element to be read       { InstanceVariable: readPosition Class: SmallInteger }
     writePosition     <SmallInteger>  index of element to be written    { InstanceVariable: writePosition Class: SmallInteger }
     tally             <SmallInteger>  number of elements in the queue   { InstanceVariable: tally Class: SmallInteger }


copyright
COPYRIGHT (c) 1993 by Claus Gittinger
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

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

Usage example(s): 

     |q|

     q := Queue new:10.
     (1 to:5) do:[:i | q add:i].
     (6 to:100) do:[:i | q removeFirst. q add:i ].
     self assert:(q at:1) = 96.
     self assert:(q at:2) = 97.
     self assert:(q at:3) = 98.
     self assert:(q at:4) = 99.
     self assert:(q at:5) = 100.
     self should:[ q at:6 ] raise:Error.

o  first
return the first element in the queue - that is the element
which would next be fetched next

Usage example(s): 

     |q|

     q := Queue new:10.
     (1 to:5) do:[:i | q add:i].
     self assert:(q first == 1).
     self assert:(q at:1) == 1.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     self should:[ q first ] raise:Error.

o  last
return the last element in the queue - that is the element
which has been added last

Usage example(s): 

     |q|

     q := Queue new:10.
     (1 to:5) do:[:i | q add:i].
     self assert:(q first == 1).
     self assert:(q at:1) == 1.
     self assert:(q last == 5).
     self assert:(q at:q size) == 5.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     q removeFirst.
     self should:[ q first ] raise:Error.
     self should:[ q last ] raise:Error.

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

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

o  removeAllElementsForWhich: checkBlock ifAbsent: exceptionalValue
remove all elements from the queue for which checkBlock returns true;
Return the value from exceptionalValue if no such element is in the queue;
otherwise, return the last removed element (typically only one)

o  removeIdentical: anElement ifAbsent: exceptionalValue
remove and return a particular element from the queue (comparing identity);
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.
Answer anObject

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

o  nextPutFirst: anObject
insert anObject at the beginning of the queue;
If the queue is full, report an error.
Insertion at the beginning may be useful to add hi-prio elements (for example, in a job-scheduler)

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

Usage example(s): 

     |q coll|

     coll := OrderedCollection new.
     q := Queue new:10.
     q nextPut:1; nextPut:2; nextPutAll:(3 to:8).
     q removeFirst; removeLast.
     q reverseDo:[:el| coll add:el].
     coll.

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).

Usage example(s): 

     |q|
     1 to:10 do:[:fill |
         1 to:10 do:[:read |
             Transcript show:'fill: '; show:fill; show:' read: '; showCR:read.
             q := Queue new:10.
             fill timesRepeat:[ q nextPut: #foo ].
             read timesRepeat:[ q next ].
             q capacity:12.
             self assert:(q size == (fill-read)).
             self assert:((Array streamContents:[:s | q do:[:e |s nextPut:e]]) = (Array new:(fill-read) withAll:#foo)).
        ].    
     ].

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  notEmpty
return true, if there are elements in the queue

o  notEmptyOrNil
return true, if there are elements in the queue

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.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Sun, 24 Nov 2024 10:06:33 GMT