Circular queue

A circular queue implemented over an array.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44:

type CircularQueue<'T> =
    {  mutable first : int
       mutable len : int
       mutable capacity : int
       mutable content : 'T[]  }

let newQueue capacity : CircularQueue<'T> =
    {  first = 0
       len = 0
       capacity = capacity
       content = Array.zeroCreate capacity  }
       
let grow (q : CircularQueue<'T>) =
    let content : 'T[] = Array.zeroCreate (q.capacity * 2)
    let l0 =
        if q.first + q.len > q.capacity
        then
            q.capacity - q.first
        else
            q.len
    let l1 = q.len - l0
            
    System.Array.Copy(q.content, q.first, content, 0, l0)
    System.Array.Copy(q.content, 0, content, l0, l1)
    
    q.first <- 0
    q.capacity <- content.Length
    q.content <- content

let add (q : CircularQueue<'T>) (item : 'T) =
    if q.len >= q.capacity then grow q
    let pos = (q.first + q.len) % q.capacity
    q.content.[pos] <- item
    q.len <- q.len + 1

let pick (q : CircularQueue<'T>) : 'T =
    if q.len <= 0 then failwith "Cannot pick from an empty queue"
    q.len <- q.len - 1
    let old_first = q.first
    q.first <- (q.first + 1) % q.capacity
    q.content.[old_first]

let isEmpty (q : CircularQueue<'T>) : bool =
    q.len = 0

CircularQueue.first: int

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

CircularQueue.len: int

CircularQueue.capacity: int

CircularQueue.content: 'T []

val newQueue : capacity:int -> CircularQueue<'T>

Full name: Script.newQueue

val capacity : int

type CircularQueue<'T> =
  {mutable first: int;
   mutable len: int;
   mutable capacity: int;
   mutable content: 'T [];}

Full name: Script.CircularQueue<_>

module Array

from Microsoft.FSharp.Collections

val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate

val grow : q:CircularQueue<'T> -> unit

Full name: Script.grow

val q : CircularQueue<'T>

val content : 'T []

val l0 : int

val l1 : int

namespace System

type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array

System.Array.Copy(sourceArray: System.Array, destinationArray: System.Array, length: int64) : unit
System.Array.Copy(sourceArray: System.Array, destinationArray: System.Array, length: int) : unit
System.Array.Copy(sourceArray: System.Array, sourceIndex: int64, destinationArray: System.Array, destinationIndex: int64, length: int64) : unit
System.Array.Copy(sourceArray: System.Array, sourceIndex: int, destinationArray: System.Array, destinationIndex: int, length: int) : unit

property System.Array.Length: int

val add : q:CircularQueue<'T> -> item:'T -> unit

Full name: Script.add

val item : 'T

val pos : int

val pick : q:CircularQueue<'T> -> 'T

Full name: Script.pick

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

val old_first : int

val isEmpty : q:CircularQueue<'T> -> bool

Full name: Script.isEmpty

type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool

Raw view Test code New version

More information

Link:	http://fssnip.net/7O
Posted:	13 years ago
Author:	Johann Deneux
Tags:	collections , array , queue