BatchedDeque

A batched Deque

 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: 
45: 
46:

namespace Algs4.Queue

open System.Collections
open System.Collections.Generic

exception Empty

type IDeque<'a> = 
   abstract IsEmpty   : bool
   abstract pushFront : 'a->IDeque<'a>
   abstract pushBack  : 'a->IDeque<'a>
   abstract popFront  :  unit-> 'a*IDeque<'a>
   abstract popBack   :  unit-> 'a*IDeque<'a>

type BatchDeque<'a> (front,rear) = 
   interface IDeque<'a> with
      member x.IsEmpty = 
         match front, rear with 
         | [], []  -> true
         | _       -> false

      member x.pushFront v = BatchDeque(v::front,    rear) :> _
      member x.pushBack  v = BatchDeque(   front, v::rear) :> _
      member x.popFront () = 
         match front, rear with
         | x::xs,   _ -> x, BatchDeque(xs, rear) :> _
         | []   ,  [] -> raise Empty
         | []   ,   _ -> //splits rear in two, favoring rearbot for odd length
                         let _, reartop, rearbot = List.fold(fun (i, reartop, rearbot) e -> 
                                                              if i < rear.Length / 2 
                                                              then (i+1, e::reartop, rearbot)
                                                              else (i+1, reartop, e::rearbot)) (0,[],[]) rear
                         printfn "reartop, rearbot  %A %A" reartop rearbot
                         let rear', (x::front')  = reartop |> List.rev , rearbot //|> List.rev
                         x, BatchDeque(front', rear') :> _
      member x.popBack () = 
         match front, rear with 
         | _ , x::xs -> x, BatchDeque(front, xs) :> _
         | []   ,  [] -> raise Empty
         | _   ,   [] -> //splits front in two, favoring frontbot for odd length
                         let _, fronttop, frontbot = List.fold(fun (i, reartop, rearbot) e -> 
                                                               if i < rear.Length /2
                                                               then (i+1, e::reartop, rearbot)
                                                               else (i+1, reartop, e::rearbot)) (0,[],[]) front
                         let front', (x::rear') = fronttop |> List.rev , frontbot
                         x, BatchDeque(front', rear') :> _

Multiple items
type Queue =
  new : unit -> Queue + 3 overloads
  member Clear : unit -> unit
  member Clone : unit -> obj
  member Contains : obj:obj -> bool
  member CopyTo : array:Array * index:int -> unit
  member Count : int
  member Dequeue : unit -> obj
  member Enqueue : obj:obj -> unit
  member GetEnumerator : unit -> IEnumerator
  member IsSynchronized : bool
  ...

Full name: System.Collections.Queue

--------------------
type Queue<'T> =
  new : unit -> Queue<'T> + 2 overloads
  member Clear : unit -> unit
  member Contains : item:'T -> bool
  member CopyTo : array:'T[] * arrayIndex:int -> unit
  member Count : int
  member Dequeue : unit -> 'T
  member Enqueue : item:'T -> unit
  member GetEnumerator : unit -> Enumerator<'T>
  member Peek : unit -> 'T
  member ToArray : unit -> 'T[]
  ...
  nested type Enumerator

Full name: System.Collections.Generic.Queue<_>

--------------------
Queue() : unit
Queue(capacity: int) : unit
Queue(col: ICollection) : unit
Queue(capacity: int, growFactor: float32) : unit

--------------------
Queue() : unit
Queue(capacity: int) : unit
Queue(collection: IEnumerable<'T>) : unit

namespace System

namespace System.Collections

namespace System.Collections.Generic

exception Empty

Full name: Algs4.Queue.Empty

type IDeque<'a> =
  interface
    abstract member IsEmpty : bool
    abstract member popBack : unit -> 'a * IDeque<'a>
    abstract member popFront : unit -> 'a * IDeque<'a>
    abstract member pushBack : 'a -> IDeque<'a>
    abstract member pushFront : 'a -> IDeque<'a>
  end

Full name: Algs4.Queue.IDeque<_>

abstract member IDeque.IsEmpty : bool

Full name: Algs4.Queue.IDeque`1.IsEmpty

type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool

abstract member IDeque.pushFront : 'a -> IDeque<'a>

Full name: Algs4.Queue.IDeque`1.pushFront

abstract member IDeque.pushBack : 'a -> IDeque<'a>

Full name: Algs4.Queue.IDeque`1.pushBack

abstract member IDeque.popFront : unit -> 'a * IDeque<'a>

Full name: Algs4.Queue.IDeque`1.popFront

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

abstract member IDeque.popBack : unit -> 'a * IDeque<'a>

Full name: Algs4.Queue.IDeque`1.popBack

Multiple items
type BatchDeque<'a> =
interface IDeque<'a>
new : front:'a list * rear:'a list -> BatchDeque<'a>

Full name: Algs4.Queue.BatchDeque<_>

--------------------
new : front:'a list * rear:'a list -> BatchDeque<'a>

val front : 'a list

val rear : 'a list

val x : BatchDeque<'a>

override BatchDeque.IsEmpty : bool

Full name: Algs4.Queue.BatchDeque`1.IsEmpty

override BatchDeque.pushFront : v:'a -> IDeque<'a>

Full name: Algs4.Queue.BatchDeque`1.pushFront

val v : 'a

override BatchDeque.pushBack : v:'a -> IDeque<'a>

Full name: Algs4.Queue.BatchDeque`1.pushBack

override BatchDeque.popFront : unit -> 'a * IDeque<'a>

Full name: Algs4.Queue.BatchDeque`1.popFront

val x : 'a

val xs : 'a list

val raise : exn:System.Exception -> 'T

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

val reartop : 'a list

val rearbot : 'a list

Multiple items
type List<'T> =
  new : unit -> List<'T> + 2 overloads
  member Add : item:'T -> unit
  member AddRange : collection:IEnumerable<'T> -> unit
  member AsReadOnly : unit -> ReadOnlyCollection<'T>
  member BinarySearch : item:'T -> int + 2 overloads
  member Capacity : int with get, set
  member Clear : unit -> unit
  member Contains : item:'T -> bool
  member ConvertAll<'TOutput> : converter:Converter<'T, 'TOutput> -> List<'TOutput>
  member CopyTo : array:'T[] -> unit + 2 overloads
  ...
  nested type Enumerator

Full name: System.Collections.Generic.List<_>

--------------------
List() : unit
List(capacity: int) : unit
List(collection: IEnumerable<'T>) : unit

val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold

val i : int

val e : 'a

property List.Length: int

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val rear' : 'a list

val front' : 'a list

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

override BatchDeque.popBack : unit -> 'a * IDeque<'a>

Full name: Algs4.Queue.BatchDeque`1.popBack

val fronttop : 'a list

val frontbot : 'a list

Raw view Test code New version

More information

Link:	http://fssnip.net/dJ
Posted:	12 years ago
Author:	Nicolas2
Tags:	deque , queue , stack