4 people like it.

Type-a-head search tree for strings

This is a search tree for strings I've built for work to back fast type-a-head for AJAX forms, it could be made million times more space efficient but there was no real need for it so.

 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: 

module SearchTree = 

  open System

  let inline private ($) a b = b a

  type T<'a> = {
    Map : Map<char, T<'a>> 
    Values : 'a list
  }

  type TO<'a> = T<'a> option

  let empty<'a> : TO<'a> = None
  let insert (s:string) value (t:TO<_>) =
    
    let rec insert (i:int) (t:TO<_>) =
      if i < s.Length then
        
        let c = s.[i]

        match t with
        | None -> 
          let subNode = None $ insert (i+1)
          let map = Map.empty $ Map.add c subNode
          {Map=map; Values=[value]}

        | Some node ->
          match node.Map $ Map.tryFind c with
          | None ->
            let subNode = None $ insert (i+1)
            let map = node.Map $ Map.add c subNode
            {Map=map; Values=value::node.Values}

          | Some subNode ->
            let subNode = Some subNode $ insert (i+1)
            let map = node.Map $ Map.add c subNode
            {Map=map; Values=value::node.Values}

      else
        {Map=Map.empty; Values=[value]}

    t $ insert 0 $ Some

  let find (s:string) (t:TO<_>) =
    
    let rec find (i:int) (t:TO<_>) =
      
      if i < s.Length then
        let c = s.[i]

        match t with
        | None -> []
        | Some node ->
          node.Map $ Map.tryFind c $ find (i+1)
        
      else
        match t with
        | None -> []
        | Some node -> node.Values
        
    t $ find 0

    
//Example
open System

let rnd = Random()
let randomChar () =
  Math.Floor((rnd.NextDouble() * 26.0) + 65.0) |> char

let randomString () =
  let sb = new Text.StringBuilder()
  for i = 0 to 20 do
    sb.Append(randomChar()) |> ignore
  sb.ToString()

let mutable tree = 
  SearchTree.empty<int>

for i = 0 to 1000000 do
  tree <- tree |> SearchTree.insert (randomString()) i
namespace System
val a : 'a
val b : ('a -> 'b)
type T<'a> =
  {Map: Map<char,T<'a>>;
   Values: 'a list;}

Full name: Script.SearchTree.T<_>
Multiple items
T.Map: Map<char,T<'a>>

--------------------
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
Multiple items
val char : value:'T -> char (requires member op_Explicit)

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

--------------------
type char = Char

Full name: Microsoft.FSharp.Core.char
T.Values: 'a list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type TO<'a> = T<'a> option

Full name: Script.SearchTree.TO<_>
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
val empty<'a> : TO<'a>

Full name: Script.SearchTree.empty
union case Option.None: Option<'T>
val insert : s:string -> value:'a -> t:TO<'a> -> T<'a> option

Full name: Script.SearchTree.insert
val s : string
Multiple items
val string : value:'T -> string

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

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
val value : 'a
val t : TO<'a>
val insert : (int -> TO<'a> -> T<'a>)
val i : 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<_>
property String.Length: int
val c : char
val subNode : T<'a>
val map : Map<char,T<'a>>
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty
val add : key:'Key -> value:'T -> table:Map<'Key,'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.add
union case Option.Some: Value: 'T -> Option<'T>
val node : T<'a>
T.Map: Map<char,T<'a>>
val tryFind : key:'Key -> table:Map<'Key,'T> -> 'T option (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.tryFind
val find : s:string -> t:TO<'a> -> 'a list

Full name: Script.SearchTree.find
val find : (int -> TO<'b> -> 'b list)
val t : TO<'b>
val node : T<'b>
T.Map: Map<char,T<'b>>
T.Values: 'b list
val rnd : Random

Full name: Script.rnd
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
Random() : unit
Random(Seed: int) : unit
val randomChar : unit -> char

Full name: Script.randomChar
type Math =
  static val PI : float
  static val E : float
  static member Abs : value:sbyte -> sbyte + 6 overloads
  static member Acos : d:float -> float
  static member Asin : d:float -> float
  static member Atan : d:float -> float
  static member Atan2 : y:float * x:float -> float
  static member BigMul : a:int * b:int -> int64
  static member Ceiling : d:decimal -> decimal + 1 overload
  static member Cos : d:float -> float
  ...

Full name: System.Math
Math.Floor(d: float) : float
Math.Floor(d: decimal) : decimal
Random.NextDouble() : float
val randomString : unit -> string

Full name: Script.randomString
val sb : Text.StringBuilder
namespace System.Text
Multiple items
type StringBuilder =
  new : unit -> StringBuilder + 5 overloads
  member Append : value:string -> StringBuilder + 18 overloads
  member AppendFormat : format:string * arg0:obj -> StringBuilder + 4 overloads
  member AppendLine : unit -> StringBuilder + 1 overload
  member Capacity : int with get, set
  member Chars : int -> char with get, set
  member Clear : unit -> StringBuilder
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EnsureCapacity : capacity:int -> int
  member Equals : sb:StringBuilder -> bool
  ...

Full name: System.Text.StringBuilder

--------------------
Text.StringBuilder() : unit
Text.StringBuilder(capacity: int) : unit
Text.StringBuilder(value: string) : unit
Text.StringBuilder(value: string, capacity: int) : unit
Text.StringBuilder(capacity: int, maxCapacity: int) : unit
Text.StringBuilder(value: string, startIndex: int, length: int, capacity: int) : unit
Text.StringBuilder.Append(value: char []) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: obj) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: uint64) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: uint32) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: uint16) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: decimal) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: float) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: float32) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: int64) : Text.StringBuilder
   (+0 other overloads)
Text.StringBuilder.Append(value: int) : Text.StringBuilder
   (+0 other overloads)
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
Text.StringBuilder.ToString() : string
Text.StringBuilder.ToString(startIndex: int, length: int) : string
val mutable tree : SearchTree.TO<int>

Full name: Script.tree
module SearchTree

from Script
val empty<'a> : SearchTree.TO<'a>

Full name: Script.SearchTree.empty
val insert : s:string -> value:'a -> t:SearchTree.TO<'a> -> SearchTree.T<'a> option

Full name: Script.SearchTree.insert
Raw view Test code New version

More information

Link:http://fssnip.net/3M
Posted:13 years ago
Author:fholm
Tags: type-a-head , tree , searchtree , string

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.