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

'From Smalltalk/X, Version:3.2.1 on 18-oct-1997 at 4:24:40 pm'                  !

Collection subclass:#Queue
	instanceVariableNames:'contentsArray readPosition writePosition tally'
	classVariableNames:''
	poolDictionaries:''
	category:'Collections-Ordered'
!

!Queue class methodsFor:'documentation'!

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.
"
!

documentation
"
    Queues provides a simple implementation of a queue, where
    elements are enterred at one end and removed at the other.
    Access protocol is somewhat like a streams 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 its empty and an element is to be removed.

    It is not safe when two processes access Queues simultanously,
    since accesses to the internals are not protected against process-switches.

    See SharedQueue for a class which is safe with processes and blocks
    on write when full or on read when empty.

    [author:]
        Claus Gittinger
"
! !

!Queue class methodsFor:'instance creation'!

new
    "return a new queue with space for some elements"

    ^ self new:50
!

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

    ^ super new init:size

    "
     |q|

     q := Queue new.
     (1 to:5) do:[:i | q nextPut:i].
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     q nextPutAll:(6 to:10).
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript show:(q next); space.
     Transcript showCR:(q next).
    "
! !

!Queue methodsFor:'accessing'!

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

    |value pos "{ Class: SmallInteger }"|

    (tally == 0) ifTrue:[^ nil].

    pos := readPosition.

    value := contentsArray at:pos.
    pos := pos + 1.
    pos > contentsArray size ifTrue:[pos := 1].
    readPosition := pos.
    tally := tally - 1.
    ^ value
!

nextPut:anObject
    "enter anObject into the queue - if the queue is full, report an error"

    |sz pos "{ Class: SmallInteger }" |

    sz := contentsArray size.
    pos := writePosition.

    (tally == sz) ifTrue:[
	self error:'queue is full'.
	^ self
    ].

    contentsArray at:pos put:anObject.
    pos := pos + 1.
    pos > sz ifTrue:[pos := 1].
    writePosition := pos.
    tally := tally + 1
!

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

    aCollection do:[:element | self nextPut:element]
!

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

    (tally == 0) ifTrue:[^ nil].
    ^ contentsArray at:readPosition.
!

removeLast
    "return the last value in the queue; 
     Return nil, if the queue is empty"

    |value pos "{ Class: SmallInteger }"|

    (tally == 0) ifTrue:[^ nil].

    pos := writePosition.
    pos == 1 ifTrue:[
        pos := contentsArray size
    ] ifFalse:[
        pos := pos - 1.
    ].

    value := contentsArray at:pos.
    writePosition := pos.
    tally := tally - 1.
    ^ value

    "Created: 22.6.1996 / 18:49:41 / cg"
! !

!Queue methodsFor:'enumerating'!

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

    |n   "{ Class: SmallInteger }"
     pos "{ Class: SmallInteger }"|

    pos := readPosition.
    n := tally.
    1 to:n do:[:i |
        aBlock value:(contentsArray at:pos).
        pos := pos + 1.
        pos > contentsArray size ifTrue:[
            pos := 1
        ]
    ]

    "Modified: 18.10.1997 / 16:24:01 / cg"
! !

!Queue methodsFor:'initialization'!

init:size
    "initialize the receiver for size entries"

    contentsArray := Array new:size.
    readPosition := writePosition := 1.
    tally := 0.
! !

!Queue methodsFor:'queries'!

capacity 
    "return the number of elements the queue can hold"

    ^ contentsArray size
!

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

    ^ tally == 0
!

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

    ^ tally == contentsArray size
!

size
    "return the number of elements in the queue"

    ^ tally
! !

!Queue class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic2/Queue.st,v 1.19 1997-10-21 17:37:35 cg Exp $'
! !