Created
May 14, 2018 13:32
-
-
Save rust-play/4ecdbb7d74ecd312629158b0a13be1e8 to your computer and use it in GitHub Desktop.
Code shared from the Rust Playground
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// rustc -C opt-level=3 -C lto | |
#![feature(box_syntax)] | |
struct Xorshift128 { state: [u32; 4] } | |
impl Xorshift128 { | |
fn new(mut x0: u32) -> Self { | |
let mut state = [0; 4]; | |
for i in 0 .. state.len() { | |
x0 = 1_812_433_253u32.wrapping_mul(x0 ^ (x0 >> 30)) + (i as u32) + 1; | |
state[i] = x0; | |
} | |
// All state must not be 0. | |
for i in 0 .. state.len() { | |
if state[i] == 0 { | |
state[i] = i as u32 + 1; | |
} | |
} | |
let mut x = Self { state }; | |
x.next(); | |
x | |
} | |
fn next(&mut self) -> i32 { | |
const A: u32 = 11; | |
const B: u32 = 8; | |
const C: u32 = 19; | |
let temp = self.state[0] ^ (self.state[0] << A); | |
self.state[0] = self.state[1]; | |
self.state[1] = self.state[2]; | |
self.state[2] = self.state[3]; | |
self.state[3] = self.state[3] ^ (self.state[3] >> C) | |
^ temp ^ (temp >> B); | |
self.state[self.state.len() - 1] as i32 | |
} | |
} | |
type NodeCell = Option<Box<Node>>; | |
struct Node { | |
x: i32, | |
y: i32, | |
left: NodeCell, | |
right: NodeCell, | |
} | |
impl Node { | |
fn new(x: i32, rng: &mut Xorshift128) -> Self { | |
Self { | |
x, | |
y: rng.next(), | |
left: None, | |
right: None, | |
} | |
} | |
} | |
fn merge(lower: NodeCell, greater: NodeCell) -> NodeCell { | |
match (lower, greater) { | |
(None, greater) => greater, | |
(lower, None) => lower, | |
(Some(mut lower_node), Some(mut greater_node)) => { | |
if lower_node.y < greater_node.y { | |
lower_node.right = merge(lower_node.right.take(), Some(greater_node)); | |
Some(lower_node) | |
} else { | |
greater_node.left = merge(Some(lower_node), greater_node.left.take()); | |
Some(greater_node) | |
} | |
} | |
} | |
} | |
fn split_binary(orig: NodeCell, value: i32) -> (NodeCell, NodeCell) { | |
if let Some(mut orig_node) = orig { | |
if orig_node.x < value { | |
let split_pair = split_binary(orig_node.right.take(), value); | |
orig_node.right = split_pair.0; | |
(Some(orig_node), split_pair.1) | |
} else { | |
let split_pair = split_binary(orig_node.left.take(), value); | |
orig_node.left = split_pair.1; | |
(split_pair.0, Some(orig_node)) | |
} | |
} else { | |
(None, None) | |
} | |
} | |
fn merge3(lower: NodeCell, equal: NodeCell, greater: NodeCell) -> NodeCell { | |
merge(merge(lower, equal), greater) | |
} | |
struct SplitResult { | |
lower: NodeCell, | |
equal: NodeCell, | |
greater: NodeCell, | |
} | |
fn split(orig: NodeCell, value: i32) -> SplitResult { | |
let (lower, equal_greater) = split_binary(orig, value); | |
let (equal, greater) = split_binary(equal_greater, value + 1); | |
SplitResult { | |
lower, | |
equal, | |
greater, | |
} | |
} | |
struct Tree { | |
root: NodeCell, | |
} | |
impl Tree { | |
fn new() -> Self { | |
Self { root: None } | |
} | |
fn has_value(&mut self, x: i32) -> bool { | |
let splited = split(self.root.take(), x); | |
let res = splited.equal.is_some(); | |
self.root = merge3(splited.lower, splited.equal, splited.greater); | |
res | |
} | |
fn insert(&mut self, x: i32, rng: &mut Xorshift128) { | |
let mut splited = split(self.root.take(), x); | |
if splited.equal.is_none() { | |
splited.equal = Some(box Node::new(x, rng)); | |
} | |
self.root = merge3(splited.lower, splited.equal, splited.greater); | |
} | |
fn erase(&mut self, x: i32) { | |
let splited = split(self.root.take(), x); | |
self.root = merge(splited.lower, splited.greater); | |
} | |
} | |
fn main() { | |
let mut rng = Xorshift128::new(0); | |
let mut tree = Tree::new(); | |
let mut cur = 5; | |
let mut res = 0; | |
for i in 1 .. 1_000_000 { | |
let a = i % 3; | |
cur = (cur * 57 + 43) % 10_007; | |
match a { | |
0 => tree.insert(cur, &mut rng), | |
1 => tree.erase(cur), | |
2 => res += if tree.has_value(cur) { 1 } else { 0 }, | |
_ => {} | |
} | |
} | |
println!("{}", res); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment