/
cycles.rs
91 lines (71 loc) · 2.17 KB
/
cycles.rs
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
use std;
import std::rand;
import uint::range;
// random uint less than n
fn under(r : rand::rng, n : uint) -> uint { assert n != 0u; r.next() as uint % n }
// random choice from a vec
fn choice<T: copy>(r : rand::rng, v : [const T]) -> T { assert vec::len(v) != 0u; v[under(r, vec::len(v))] }
// k in n chance of being true
fn likelihood(r : rand::rng, k : uint, n : uint) -> bool { under(r, n) < k }
const iters : uint = 1000u;
const vlen : uint = 100u;
enum maybe_pointy {
none,
p(@pointy)
}
type pointy = {
mut a : maybe_pointy,
mut b : ~maybe_pointy,
mut c : @maybe_pointy,
mut f : fn@()->(),
mut g : fn~()->(),
mut m : [maybe_pointy],
mut n : [mut maybe_pointy],
mut o : {x : int, y : maybe_pointy}
};
// To add: objects; ifaces; anything type-parameterized?
fn empty_pointy() -> @pointy {
ret @{
mut a : none,
mut b : ~none,
mut c : @none,
mut f : fn@()->(){},
mut g : fn~()->(){},
mut m : [],
mut n : [mut],
mut o : {x : 0, y : none}
}
}
fn nopP(_x : @pointy) { }
fn nop<T>(_x: T) { }
fn test_cycles(r : rand::rng, k: uint, n: uint)
{
let v : [mut @pointy] = [mut];
// Create a graph with no edges
range(0u, vlen) {|_i|
v += [mut empty_pointy()];
}
// Fill in the graph with random edges, with density k/n
range(0u, vlen) {|i|
if (likelihood(r, k, n)) { v[i].a = p(choice(r, v)); }
if (likelihood(r, k, n)) { v[i].b = ~p(choice(r, v)); }
if (likelihood(r, k, n)) { v[i].c = @p(choice(r, v)); }
if (likelihood(r, k, n)) { v[i].f = bind nopP(choice(r, v)); }
//if (false) { v[i].g = bind (fn~(_x: @pointy) { })(choice(r, v)); }
// https://github.com/mozilla/rust/issues/1899
if (likelihood(r, k, n)) { v[i].m = [p(choice(r, v))]; }
if (likelihood(r, k, n)) { v[i].n += [mut p(choice(r, v))]; }
if (likelihood(r, k, n)) { v[i].o = {x: 0, y: p(choice(r, v))}; }
}
// Drop refs one at a time
range(0u, vlen) {|i|
v[i] = empty_pointy()
}
}
fn main()
{
let r = rand::rng();
range(0u, iters) {|i|
test_cycles(r, i, iters);
}
}