Skip to content

Instantly share code, notes, and snippets.

@rust-play
Created May 14, 2018 13:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rust-play/4ecdbb7d74ecd312629158b0a13be1e8 to your computer and use it in GitHub Desktop.
Save rust-play/4ecdbb7d74ecd312629158b0a13be1e8 to your computer and use it in GitHub Desktop.
Code shared from the Rust Playground
// 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