' FB 1.05.0 Win64

' queue_rosetta.bi
' simple generic Queue type

#Define Queue(T) Queue_##T

#Macro Declare_Queue(T)
Type Queue(T)
 Public:
    Declare Constructor()
    Declare Destructor()
    Declare Property capacity As Integer
    Declare Property count As Integer
    Declare Property empty As Boolean
    Declare Property front As T
    Declare Function pop() As T
    Declare Sub push(item As T)
  Private:
    a(any) As T
    count_ As Integer = 0
    Declare Function resize(size As Integer) As Integer
End Type

Constructor Queue(T)()
  Redim a(0 To 0) '' create a default T instance for various purposes
End Constructor

Destructor Queue(T)()
  Erase a
End Destructor

Property Queue(T).capacity As Integer
  Return UBound(a)
End Property

Property Queue(T).count As Integer
  Return count_
End Property

Property Queue(T).empty As Boolean
  Return count_ = 0
End Property

Property Queue(T).front As T
  If count_ > 0 Then
    Return a(1)
  End If
  Print "Error: Attempted to access 'front' element of an empty queue"
  Return a(0)  '' return default element
End Property

Function Queue(T).pop() As T
  If count_ > 0 Then
    Dim value As T = a(1)
    If count_ > 1 Then  '' move remaining elements to fill space vacated
      For i As Integer = 2 To count_
        a(i - 1) = a(i)
      Next
    End If
    a(count_) = a(0)  '' zero last element
    count_ -= 1
    Return value
  End If
  Print "Error: Attempted to remove 'front' element of an empty queue"
  Return a(0)  '' return default element
End Function

Sub Queue(T).push(item As T)
  Dim size As Integer = UBound(a)
  count_ += 1
  If count_ >  size Then
    size = resize(size)
    Redim Preserve a(0 to size)
  End If
  a(count_) = item
End Sub

Function Queue(T).resize(size As Integer) As Integer
  If size = 0 Then
    size = 4
  ElseIf size <= 32 Then
    size  = 2 * size
  Else
    size += 32
  End If
  Return size
End Function
#EndMacro