rust

gistfile1.txt

// static mut isprime: [bool; 1000000] = [true; 1000000];

// dest node id, cost
struct Edge(usize, i64);
// current node, total cost
// struct State(usize, i64);
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    node: usize,
    cost: i64
}

impl Ord for State {
    fn cmp(&self, other: &State) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn sieve() -> Vec<i64> {
    let mut isprime = [true; 1000000];
    let mut p: i64 = 2;
    let mut primes: Vec<i64> = Vec::new();
    primes.push(2);
    while p * p < 1000000 {
        for m in p..1000000 {
            let idx = m * p;
            if idx >= 1000000 {
                break;
            }
            isprime[idx as usize] = false;
        }
        for i in (p + 1)..1000000 {
            if isprime[i as usize] {
                primes.push(i);
                p = i;
                break;
            }
        }
    }
    for v in (p + 1)..1000000 {
        if isprime[v as usize] {
            primes.push(v)
        }
    }

    primes
}

// borrowing (弱参照)じゃないと終わった後グラフが読めなくなる
fn dijkstra(G: &Vec<Vec<Edge>>, S: usize, D: usize) -> i64 {
    let mut q = BinaryHeap::new();
    let mut ans: Vec<i64> = vec![100000; G.len()];
    ans[S] = 0;
    //q.push(State(S, 0));
    q.push(State { node: S, cost: 0 } );
    while ! q.is_empty() {
        let (n, c) = match q.pop() {
            Some(State{ node: n, cost: c }) => (n, c),
            _ => (10000, 10000)
        };
        if ans[n] <= c {
            continue;
        }
        // G[n] -> Vec<Edge>, borrowing が必要
        for e in &G[n] {
            let &Edge(next, ecost) = e;
            if ans[next] <= c + ecost {
                continue;
            }
            q.push(State { node: next, cost: ecost + c });
        }
    }

    ans[D]
}

fn pow(x: i64, n: i64) -> i64 {
    match n {
        0 => 1,
        1 => x,
        _ => { let t = pow(x, n / 2); t * t * (if n % 2 == 1 { x } else { 1 }) }
    }
}

trait ConvertTo<T> {
    fn convert(&self) -> T;
}

impl ConvertTo<i64> for i32 {
    fn convert(&self) -> i64 {
        *self as i64
    }
}

fn normal<T: ConvertTo<i64>>(x: &T) -> i64 {
    x.convert()
}

fn inverse<T>() -> T
    where i32: ConvertTo<T> {
    42.convert()
}

fn main() {

    let f = |x: i32| x + 1;
    let y = &f;

    let res: Vec<i64> = sieve();
    for p in res {
        println!("{}", p);
    }
    println!("=---", );
    println!("{}", pow(2, 3));
    println!("{}", pow(2, 10));
    println!("{}", pow(2, 0));
}