Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/benchmarks/programs/tsp/build.sml
ViewVC logotype

Annotation of /sml/trunk/benchmarks/programs/tsp/build.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 193 - (view) (download)

1 : monnier 193 (* build.sml
2 :     *
3 :     * COPYRIGHT (c) 1994 AT&T Bell Laboratories.
4 :     *
5 :     * Build a two-dimensional tree for TSP.
6 :     *)
7 :    
8 :     structure BuildTree : sig
9 :    
10 :     datatype axis = X_AXIS | Y_AXIS
11 :    
12 :     val buildTree : {
13 :     n : int, dir : axis,
14 :     min_x : real, min_y : real, max_x : real, max_y : real
15 :     } -> Tree.tree
16 :    
17 :     end = struct
18 :    
19 :     structure T = Tree
20 :    
21 :     val m_e = 2.7182818284590452354
22 :     val m_e2 = 7.3890560989306502274
23 :     val m_e3 = 20.08553692318766774179
24 :     val m_e6 = 403.42879349273512264299
25 :     val m_e12 = 162754.79141900392083592475
26 :    
27 :     datatype axis = X_AXIS | Y_AXIS
28 :    
29 :     (* builds a 2D tree of n nodes in specified range with dir as primary axis *)
30 :     fun buildTree arg = let
31 :     val rand = Rand.mkRandom 0w314
32 :     fun drand48 () = Rand.norm (rand ())
33 :     fun median {min, max, n} = let
34 :     val t = drand48(); (* in [0.0..1.0) *)
35 :     val retval = if (t > 0.5)
36 :     then Math.ln(1.0-(2.0*(m_e12-1.0)*(t-0.5)/m_e12))/12.0
37 :     else ~(Math.ln(1.0-(2.0*(m_e12-1.0)*t/m_e12))/12.0)
38 :     in
39 :     min + ((retval + 1.0) * (max - min)/2.0)
40 :     end
41 :     fun uniform {min, max} = min + (drand48() * (max - min))
42 :     fun build {n = 0, ...} = T.NULL
43 :     | build {n, dir=X_AXIS, min_x, min_y, max_x, max_y} = let
44 :     val med = median{min=min_y, max=max_y, n=n}
45 :     fun mkTree (min, max) = build{
46 :     n=n div 2, dir=Y_AXIS, min_x=min_x, max_x=max_x,
47 :     min_y=min, max_y=max
48 :     }
49 :     in
50 :     T.mkNode(
51 :     mkTree(min_y, med), mkTree(med, max_y),
52 :     uniform{min=min_x, max=max_x}, med, n)
53 :     end
54 :     | build {n, dir=Y_AXIS, min_x, min_y, max_x, max_y} = let
55 :     val med = median{min=min_x, max=max_x, n=n}
56 :     fun mkTree (min, max) = build{
57 :     n=n div 2, dir=X_AXIS, min_x=min, max_x=max,
58 :     min_y=min_y, max_y=max_y
59 :     }
60 :     in
61 :     T.mkNode(
62 :     mkTree(min_x, med), mkTree(med, max_x),
63 :     med, uniform{min=min_y, max=max_y}, n)
64 :     end
65 :     in
66 :     build arg
67 :     end
68 :    
69 :     end; (* Build *)
70 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0