17 people like it.

Sorted Map

Sorted Map

  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: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 
184: 
185: 
186: 
187: 
188: 
189: 
190: 
191: 
192: 
193: 
194: 
195: 
196: 
197: 
198: 
199: 
200: 
201: 
202: 
203: 
204: 
205: 
206: 
207: 
208: 
209: 
210: 
211: 
212: 
213: 
214: 
215: 
216: 
217: 
218: 
  module SortedMap =

    (*
    //  let avl =
    //    ['a'..'z'] |> List.fold (fun avl char ->
    //      AvlTree.insert char char avl
    //    ) AvlTree.empty
    //  
    //  avl |> AvlTree.min // 'z'
    //  avl |> AvlTree.max // 'a'
    //  avl |> AvlTree.exists 'b' // true
    //  avl |> AvlTree.find 'd' // Some 'd'
    //  avl |> AvlTree.size // 26
    //  avl |> AvlTree.value // 'p' (root node)
    //  
    //  let avl2 = avl |> AvlTree.delete 'd' // 
    //  avl2 |> AvlTree.exists 'd' // false
    //  avl2 |> AvlTree.size // 25
    *)

    open System.Collections
    open System.Collections.Generic

    type Node<'k, 'v> when 'k : comparison
      = Empty
      | Node of 'k * 'v * int * int * Node<'k, 'v> * Node<'k, 'v>
      with
        interface IEnumerable<'v> with
          member x.GetEnumerator() =
            let rec inOrder (tree:Node<'k, 'v>) =
              seq {
                match tree with
                | Empty -> yield! Seq.empty
                | Node(_, v, _, _, l, r) -> 
                  yield! inOrder l; yield v; yield! inOrder r
              }

            (inOrder x).GetEnumerator()

          member x.GetEnumerator() =
            (x :> IEnumerable<'v>).GetEnumerator() :> IEnumerator

    let empty = Empty
    
    let rec min = function
      | Empty -> failwith "Empty tree"
      | Node(_, v, _, _, Empty, _) -> v
      | Node(_, _, _, _, l, _) -> min l 

    let rec max = function
      | Empty -> failwith "Empty tree"
      | Node(_, v, _, _, _, Empty) -> v
      | Node(_, _, _, _, _, r) -> max r
      
    let left = function
      | Node(_, _, _, _, l, _) -> l
      | Empty -> failwith "Can't get left child of empty node"

    let right = function
      | Node(_, _, _, _, _, r) -> r
      | Empty -> failwith "Can't get right child of empty node"

    let value = function
      | Node(_, v, _, _, _, _) -> v
      | Empty -> failwith "Can't get value of empty node"

    let size = function
      | Empty -> 0
      | Node(_, _, s, _, _, _) -> s

    let private sizeOf l r = 
      (size l) + (size r) + 1

    let height = function
      | Empty -> 0
      | Node(_, _, _, h, _, _) -> h
      
    let private heightOf l r =
      (Microsoft.FSharp.Core.Operators.max (height l) (height r)) + 1

    let private rotateLeft root =
      match root with
      | Node(rk, rv, _, rh, rl, Node(pk, pv, _, ph, pl, pr)) ->
        let root = Node(rk, rv, sizeOf rl pl, heightOf rl pl, rl, pl)
        Node(pk, pv, sizeOf root pr, heightOf root pr, root, pr)
      
      | _ -> failwith "Can't rotate tree left"

    let private rotateRight root =
      match root with
      | Node(rk, rv, _, rh, Node(pk, pv, _, ph, pl, pr), rr) ->
        let root = Node(rk, rv, sizeOf pr rr, heightOf pr rr, pr, rr)
        Node(pk, pv, sizeOf root pl, heightOf root pl, pl, root)

      | _ -> failwith "Can't rotate tree right"

    let private balanceOf l r = 
      (height l) - (height r)

    let balance = function
      | Empty -> 0
      | Node(_, _, _, _, l, r) -> balanceOf l r

    let private rebalance k v l r =
      let h = heightOf l r 
      let s = sizeOf l r

      match balanceOf l r with
      | -2 ->
        rotateLeft 
         (match balance r with
          | 1 -> Node(k, v, s, h, l, rotateRight r)
          | _ -> Node(k, v, s, h, l, r))

      | 2 ->
        rotateRight
         (match balance l with
          | -1 -> Node(k, v, s, h, rotateLeft l, r)
          | _ -> Node(k, v, s, h, l, r))

      | _ -> Node(k, v, s, h, l, r)

    let inOrderPrev (tree:Node<'k, 'v>) =
      let rec prev prevVal tree = 
        match tree with
        | Empty -> Empty
        | Node(k, v, _, _, l, Empty) -> prevVal := Some(k, v); l
        | Node(k, v, s, h, l, r) -> 
          let r = prev prevVal r
          Node(k, v, sizeOf l r, h, l, r)
        
      let prevVal = ref None

      match tree with
      | Empty -> Empty, !prevVal
      | Node(_, _, _, _, l, _) -> prev prevVal l, !prevVal

    let inOrderNext (tree:Node<'k, 'v>) =
      let rec next nextVal tree = 
        match tree with
        | Empty -> Empty
        | Node(k, v, _, _, Empty, r) -> nextVal := Some(k, v); r
        | Node(k, v, s, h, l, r) -> 
          let l = next nextVal l
          Node(k, v, sizeOf l r, h, l, r)

      let nextVal = ref None

      match tree with
      | Empty -> Empty, !nextVal
      | Node(_, _, _, _, _, r) -> next nextVal r, !nextVal

    let rec find key (tree:Node<'k, 'v>) =
      match tree with
      | Empty -> None
      | Node(k, v, _, _, l, r) ->
        if key < k
          then find key l
          elif key > k
            then find key r
            else Some v

    let rec exists key (tree:Node<'k, 'v>) =
      tree |> find key |> Option.isSome

    let rec insert key value (tree:Node<'k, 'v>) =
      match tree with
      | Empty -> Node(key, value, 1, 1, Empty, Empty)
      | Node(k, v, s, h, l, r) -> 
        if key < k 
          then rebalance k v (insert key value l) r
          elif key > k 
            then rebalance k v l (insert key value r)
            else Node(key, value, s, h, l, r)

    let rec delete key (tree:Node<'k, 'v>) =
      match tree with
      | Empty -> Empty
      | Node(k, v, _, _, l, r) ->
        if key < k
          then rebalance k v (delete key l) r
          elif key > k
            then rebalance k v l (delete key r)
            else 
              match inOrderPrev tree with
              | _, None -> 
                match inOrderNext tree with
                | _, None -> Empty
                | r, Some(k, v) -> rebalance k v l r
              | l, Some(k, v) -> rebalance k v l r

    let rec preOrder (tree:Node<'k, 'v>) =
      seq {
        match tree with
        | Empty -> yield! Seq.empty
        | Node(_, v, _, _, l, r) ->
          yield v; yield! preOrder l; yield! preOrder r
      }

    let rec postOrder (tree:Node<'k, 'v>) =
      seq {
        match tree with
        | Empty -> yield! Seq.empty
        | Node(_, v, _, _, l, r) ->
          yield! postOrder l; yield! postOrder r; yield v
      }

    let levelOrder (tree:Node<'k, 'v>) =
      let queue = new Queue<Node<'k, 'v>>()
      tree |> queue.Enqueue

      seq {
        while queue.Count > 0 do
          let node = queue.Dequeue()
          yield node |> value
          node |> left |> queue.Enqueue 
          node |> right |> queue.Enqueue
      }
namespace System
namespace System.Collections
namespace System.Collections.Generic
Multiple items
union case Node.Node: 'k * 'v * int * int * Node<'k,'v> * Node<'k,'v> -> Node<'k,'v>

--------------------
type Node<'k,'v (requires comparison)> =
  | Empty
  | Node of 'k * 'v * int * int * Node<'k,'v> * Node<'k,'v>
  interface IEnumerable<'v>

Full name: Script.SortedMap.Node<_,_>
union case Node.Empty: Node<'k,'v>
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<_>
Multiple items
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
  member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>
val x : Node<'k,'v> (requires comparison)
override Node.GetEnumerator : unit -> IEnumerator<'v>

Full name: Script.SortedMap.Node`2.GetEnumerator
val inOrder : (Node<'k,'v> -> seq<'v>) (requires comparison)
val tree : Node<'k,'v> (requires comparison)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
module Seq

from Microsoft.FSharp.Collections
val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty
val v : 'v
val l : Node<'k,'v> (requires comparison)
val r : Node<'k,'v> (requires comparison)
override Node.GetEnumerator : unit -> IEnumerator

Full name: Script.SortedMap.Node`2.GetEnumerator
Multiple items
type IEnumerator =
  member Current : obj
  member MoveNext : unit -> bool
  member Reset : unit -> unit

Full name: System.Collections.IEnumerator

--------------------
type IEnumerator<'T> =
  member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>
val empty : Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.empty
val min : _arg1:Node<'a,'b> -> 'b (requires comparison)

Full name: Script.SortedMap.min
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val v : 'b
val l : Node<'a,'b> (requires comparison)
val max : _arg1:Node<'a,'b> -> 'b (requires comparison)

Full name: Script.SortedMap.max
val r : Node<'a,'b> (requires comparison)
val left : _arg1:Node<'a,'b> -> Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.left
val right : _arg1:Node<'a,'b> -> Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.right
val value : _arg1:Node<'a,'b> -> 'b (requires comparison)

Full name: Script.SortedMap.value
val size : _arg1:Node<'a,'b> -> int (requires comparison)

Full name: Script.SortedMap.size
val s : int
val private sizeOf : l:Node<'a,'b> -> r:Node<'c,'d> -> int (requires comparison and comparison)

Full name: Script.SortedMap.sizeOf
val r : Node<'c,'d> (requires comparison)
val height : _arg1:Node<'a,'b> -> int (requires comparison)

Full name: Script.SortedMap.height
val h : int
val private heightOf : l:Node<'a,'b> -> r:Node<'c,'d> -> int (requires comparison and comparison)

Full name: Script.SortedMap.heightOf
namespace Microsoft
namespace Microsoft.FSharp
namespace Microsoft.FSharp.Core
module Operators

from Microsoft.FSharp.Core
val max : e1:'T -> e2:'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.max
val private rotateLeft : root:Node<'a,'b> -> Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.rotateLeft
val root : Node<'a,'b> (requires comparison)
val rk : 'a (requires comparison)
val rv : 'b
val rh : int
val rl : Node<'a,'b> (requires comparison)
val pk : 'a (requires comparison)
val pv : 'b
val ph : int
val pl : Node<'a,'b> (requires comparison)
val pr : Node<'a,'b> (requires comparison)
val private rotateRight : root:Node<'a,'b> -> Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.rotateRight
val rr : Node<'a,'b> (requires comparison)
val private balanceOf : l:Node<'a,'b> -> r:Node<'c,'d> -> int (requires comparison and comparison)

Full name: Script.SortedMap.balanceOf
val balance : _arg1:Node<'a,'b> -> int (requires comparison)

Full name: Script.SortedMap.balance
val private rebalance : k:'a -> v:'b -> l:Node<'a,'b> -> r:Node<'a,'b> -> Node<'a,'b> (requires comparison)

Full name: Script.SortedMap.rebalance
val k : 'a (requires comparison)
val inOrderPrev : tree:Node<'k,'v> -> Node<'k,'v> * ('k * 'v) option (requires comparison)

Full name: Script.SortedMap.inOrderPrev
val prev : (('a * 'b) option ref -> Node<'a,'b> -> Node<'a,'b>) (requires comparison)
val prevVal : ('a * 'b) option ref (requires comparison)
val tree : Node<'a,'b> (requires comparison)
union case Option.Some: Value: 'T -> Option<'T>
val prevVal : ('k * 'v) option ref (requires comparison)
Multiple items
val ref : value:'T -> 'T ref

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

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
union case Option.None: Option<'T>
val inOrderNext : tree:Node<'k,'v> -> Node<'k,'v> * ('k * 'v) option (requires comparison)

Full name: Script.SortedMap.inOrderNext
val next : (('a * 'b) option ref -> Node<'a,'b> -> Node<'a,'b>) (requires comparison)
val nextVal : ('a * 'b) option ref (requires comparison)
val nextVal : ('k * 'v) option ref (requires comparison)
val find : key:'k -> tree:Node<'k,'v> -> 'v option (requires comparison)

Full name: Script.SortedMap.find
val key : 'k (requires comparison)
val k : 'k (requires comparison)
val exists : key:'k -> tree:Node<'k,'v> -> bool (requires comparison)

Full name: Script.SortedMap.exists
module Option

from Microsoft.FSharp.Core
val isSome : option:'T option -> bool

Full name: Microsoft.FSharp.Core.Option.isSome
val insert : key:'k -> value:'v -> tree:Node<'k,'v> -> Node<'k,'v> (requires comparison)

Full name: Script.SortedMap.insert
val value : 'v
val delete : key:'k -> tree:Node<'k,'v> -> Node<'k,'v> (requires comparison)

Full name: Script.SortedMap.delete
val preOrder : tree:Node<'k,'v> -> seq<'v> (requires comparison)

Full name: Script.SortedMap.preOrder
val postOrder : tree:Node<'k,'v> -> seq<'v> (requires comparison)

Full name: Script.SortedMap.postOrder
val levelOrder : tree:Node<'k,'v> -> seq<'v> (requires comparison)

Full name: Script.SortedMap.levelOrder
val queue : Queue<Node<'k,'v>> (requires comparison)
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
Queue.Enqueue(item: Node<'k,'v>) : unit
property Queue.Count: int
val node : Node<'k,'v> (requires comparison)
Queue.Dequeue() : Node<'k,'v>
Raw view New version

More information

Link:http://fssnip.net/2i
Posted:5 years ago
Author:fholm
Tags: map , sorted