use std::default::Default;
use timely_sort::Unsigned;
use ::hashable::{Hashable, HashOrdered};
use super::{Trie, Cursor, Builder, MergeBuilder, TupleBuilder};
const MINIMUM_SHIFT : usize = 4;
const BLOAT_FACTOR : f64 = 1.1;
#[derive(Debug)]
pub struct HashedLayer<K: HashOrdered, L> {
pub keys: Vec<Entry<K>>,
pub vals: L,
}
impl<K: HashOrdered, L> HashedLayer<K, L> {
fn _entry_valid(&self, index: usize) -> bool { self.keys[index].is_some() }
fn lower(&self, index: usize) -> usize { self.keys[index].get_lower() }
fn upper(&self, index: usize) -> usize { self.keys[index].get_upper() }
}
impl<K: Clone+HashOrdered+Default, L: Trie> Trie for HashedLayer<K, L> {
type Item = (K, L::Item);
type Cursor = HashedCursor<L>;
type MergeBuilder = HashedBuilder<K, L::MergeBuilder>;
type TupleBuilder = HashedBuilder<K, L::TupleBuilder>;
fn keys(&self) -> usize { self.keys.len() }
fn tuples(&self) -> usize { self.vals.tuples() }
fn cursor_from(&self, lower: usize, upper: usize) -> Self::Cursor {
if lower < upper {
let mut shift = 0;
while upper - lower >= (1 << shift) {
shift += 1;
}
shift -= 1;
let mut pos = lower;
while pos < upper && !self.keys[pos].is_some() {
pos += 1;
}
HashedCursor {
shift: shift,
bounds: (lower, upper),
pos: pos,
child: self.vals.cursor_from(self.keys[pos].get_lower(), self.keys[pos].get_upper())
}
}
else {
HashedCursor {
shift: 0,
bounds: (0, 0),
pos: 0,
child: self.vals.cursor_from(0, 0),
}
}
}
}
#[derive(Debug, Clone)]
pub struct Entry<K: HashOrdered> {
key: K,
lower1: u32,
upper1: u32,
}
impl<K: HashOrdered> Entry<K> {
fn new(key: K, lower: usize, upper: usize) -> Self {
Entry {
key: key,
lower1: lower as u32,
upper1: upper as u32,
}
}
fn is_some(&self) -> bool { self.upper1 != 0 }
fn empty() -> Self where K: Default { Self::new(Default::default(), 0, 0) }
fn get_lower(&self) -> usize { self.lower1 as usize}
fn get_upper(&self) -> usize { self.upper1 as usize}
fn _set_lower(&mut self, x: usize) { self.lower1 = x as u32; }
fn set_upper(&mut self, x: usize) { self.upper1 = x as u32; }
}
pub struct HashedBuilder<K: HashOrdered, L> {
temp: Vec<Entry<K>>,
pub keys: Vec<Entry<K>>,
pub vals: L,
}
impl<K: HashOrdered+Clone+Default, L> HashedBuilder<K, L> {
#[inline(always)]
fn _lower(&self, index: usize) -> usize {
self.keys[index].get_lower()
}
#[inline(always)]
fn _upper(&self, index: usize) -> usize {
self.keys[index].get_upper()
}
}
impl<K: HashOrdered+Clone+Default, L: Builder> Builder for HashedBuilder<K, L> {
type Trie = HashedLayer<K, L::Trie>;
fn boundary(&mut self) -> usize {
debug_assert!((1 .. self.temp.len()).all(|i| self.temp[i-1].key < self.temp[i].key));
let boundary = self.vals.boundary();
if self.temp.len() > 0 {
if !self.temp[self.temp.len()-1].is_some() {
let pos = self.temp.len()-1;
self.temp[pos].set_upper(boundary);
}
let lower = self.keys.len();
if self.temp.len() < (1 << MINIMUM_SHIFT) {
self.keys.extend(self.temp.drain(..));
}
else {
let target = (BLOAT_FACTOR * (self.temp.len() as f64)) as u64;
let mut shift = MINIMUM_SHIFT;
while (1 << shift) < target {
shift += 1;
}
self.keys.reserve(1 << shift);
let mut cursor: usize = 0;
for entry in self.temp.drain(..) {
let target = (entry.key.hashed().as_u64() >> ((<K as Hashable>::Output::bytes() * 8) - shift)) as usize;
debug_assert!(target < (1 << shift));
while cursor < target {
self.keys.push(Entry::empty());
cursor += 1;
}
self.keys.push(entry);
cursor += 1;
}
while cursor < (1 << shift) {
self.keys.push(Entry::empty());
cursor += 1;
}
assert!((self.keys.len() - lower) < (2 << shift));
}
}
self.keys.len()
}
#[inline(never)]
fn done(mut self) -> Self::Trie {
self.boundary();
self.keys.shrink_to_fit();
let vals = self.vals.done();
if vals.tuples() > 0 {
assert!(self.keys.len() > 0);
}
HashedLayer {
keys: self.keys,
vals: vals,
}
}
}
impl<K: HashOrdered+Clone+Default, L: MergeBuilder> MergeBuilder for HashedBuilder<K, L> {
fn with_capacity(other1: &Self::Trie, other2: &Self::Trie) -> Self {
HashedBuilder {
temp: Vec::new(),
keys: Vec::with_capacity(other1.keys() + other2.keys()),
vals: L::with_capacity(&other1.vals, &other2.vals),
}
}
fn copy_range(&mut self, other: &Self::Trie, lower: usize, upper: usize) {
if lower < upper {
let other_basis = other.lower(lower);
let self_basis = self.vals.boundary();
for index in lower .. upper {
let other_entry = &other.keys[index];
let new_entry = if other_entry.is_some() {
Entry::new(
other_entry.key.clone(),
(other_entry.get_lower() + self_basis) - other_basis,
(other_entry.get_upper() + self_basis) - other_basis,
)
}
else { Entry::empty() };
self.keys.push(new_entry);
}
self.vals.copy_range(&other.vals, other.lower(lower), other.upper(upper-1));
self.boundary();
}
}
fn push_merge(&mut self, other1: (&Self::Trie, usize, usize), other2: (&Self::Trie, usize, usize)) -> usize {
let (trie1, mut lower1, upper1) = other1;
let (trie2, mut lower2, upper2) = other2;
debug_assert!(upper1 <= trie1.keys.len());
debug_assert!(upper2 <= trie2.keys.len());
self.temp.reserve((upper1 - lower1) + (upper2 - lower2));
while lower1 < trie1.keys.len() && !trie1.keys[lower1].is_some() { lower1 += 1; }
while lower2 < trie2.keys.len() && !trie2.keys[lower2].is_some() { lower2 += 1; }
while lower1 < upper1 && lower2 < upper2 {
debug_assert!(trie1.keys[lower1].is_some());
debug_assert!(trie2.keys[lower2].is_some());
match trie1.keys[lower1].key.cmp(&trie2.keys[lower2].key) {
::std::cmp::Ordering::Less => {
lower1 += self.push_while_less(trie1, lower1, upper1, &trie2.keys[lower2].key);
}
::std::cmp::Ordering::Equal => {
let lower = self.vals.boundary();
let upper = self.vals.push_merge(
(&trie1.vals, trie1.lower(lower1), trie1.upper(lower1)),
(&trie2.vals, trie2.lower(lower2), trie2.upper(lower2))
);
if upper > lower {
self.temp.push(Entry::new(trie1.keys[lower1].key.clone(), lower, upper));
}
lower1 += 1;
lower2 += 1;
while lower1 < trie1.keys.len() && !trie1.keys[lower1].is_some() { lower1 += 1; }
while lower2 < trie2.keys.len() && !trie2.keys[lower2].is_some() { lower2 += 1; }
}
::std::cmp::Ordering::Greater => {
lower2 += self.push_while_less(trie2, lower2, upper2, &trie1.keys[lower1].key);
}
}
}
if lower1 < upper1 { self.push_all(trie1, lower1, upper1); }
if lower2 < upper2 { self.push_all(trie2, lower2, upper2); }
self.boundary()
}
}
impl<K: HashOrdered+Clone+Default, L: TupleBuilder> TupleBuilder for HashedBuilder<K, L> {
type Item = (K, L::Item);
fn new() -> Self { HashedBuilder { temp: Vec::new(), keys: Vec::new(), vals: L::new() } }
fn with_capacity(cap: usize) -> Self {
HashedBuilder {
temp: Vec::with_capacity(cap),
keys: Vec::with_capacity(cap),
vals: L::with_capacity(cap),
}
}
#[inline(always)]
fn push_tuple(&mut self, (key, val): (K, L::Item)) {
let temp_len = self.temp.len();
if temp_len == 0 || self.temp[temp_len-1].key != key {
if temp_len > 0 { debug_assert!(self.temp[temp_len-1].key < key); }
let boundary = self.vals.boundary();
if temp_len > 0 {
self.temp[temp_len-1].set_upper(boundary);
}
self.temp.push(Entry::new(key, boundary, 0));
}
self.vals.push_tuple(val);
}
}
impl<K: HashOrdered+Clone+Default, L: MergeBuilder> HashedBuilder<K, L> {
fn push_while_less(&mut self, other: &HashedLayer<K, L::Trie>, lower: usize, upper: usize, vs: &K) -> usize {
let other_basis = other.lower(lower);
let self_basis = self.vals.boundary();
let mut bound = 0;
let mut index = lower;
while index < upper && !(other.keys[index].is_some() && &other.keys[index].key >= vs) {
if other.upper(index) != 0 {
if bound < other.upper(index) { bound = other.upper(index); }
debug_assert!(other.lower(index) < other.upper(index));
let lower = (other.lower(index) + self_basis) - other_basis;
let upper = (other.upper(index) + self_basis) - other_basis;
self.temp.push(Entry::new(other.keys[index].key.clone(), lower, upper));
}
index += 1;
}
debug_assert!(bound > 0);
self.vals.copy_range(&other.vals, other.lower(lower), bound);
index - lower
}
fn push_all(&mut self, other: &HashedLayer<K, L::Trie>, lower: usize, upper: usize) {
debug_assert!(lower < upper);
debug_assert!(upper <= other.keys.len());
let other_basis = other.lower(lower);
let self_basis = self.vals.boundary();
let mut bound = 0;
for index in lower .. upper {
if other.upper(index) != 0 {
if bound < other.upper(index) { bound = other.upper(index); }
let lower = (other.lower(index) + self_basis) - other_basis;
let upper = (other.upper(index) + self_basis) - other_basis;
self.temp.push(Entry::new(other.keys[index].key.clone(), lower, upper));
}
}
debug_assert!(bound > 0);
self.vals.copy_range(&other.vals, other.lower(lower), bound);
}
}
#[derive(Debug)]
pub struct HashedCursor<L: Trie> {
shift: usize,
bounds: (usize, usize),
pos: usize,
pub child: L::Cursor,
}
impl<K: HashOrdered, L: Trie> Cursor<HashedLayer<K, L>> for HashedCursor<L> {
type Key = K;
fn key<'a>(&self, storage: &'a HashedLayer<K, L>) -> &'a Self::Key { &storage.keys[self.pos].key }
fn step(&mut self, storage: &HashedLayer<K, L>) {
self.pos += 1;
while self.pos < self.bounds.1 && !storage.keys[self.pos].is_some() {
self.pos += 1;
}
if self.valid(storage) {
let child_lower = storage.keys[self.pos].get_lower();
let child_upper = storage.keys[self.pos].get_upper();
self.child.reposition(&storage.vals, child_lower, child_upper);
}
else {
self.pos = self.bounds.1;
}
}
#[inline(never)]
fn seek(&mut self, storage: &HashedLayer<K, L>, key: &Self::Key) {
if self.shift >= MINIMUM_SHIFT {
let target = (key.hashed().as_u64() >> ((K::Output::bytes() * 8) - self.shift)) as usize;
self.pos = target;
}
while self.pos < self.bounds.1 && (!storage.keys[self.pos].is_some() || &storage.keys[self.pos].key < key) {
self.pos += 1;
}
if self.valid(storage) {
self.child.reposition(&storage.vals, storage.keys[self.pos].get_lower(), storage.keys[self.pos].get_upper());
}
}
fn valid(&self, _storage: &HashedLayer<K, L>) -> bool { self.pos < self.bounds.1 }
fn rewind(&mut self, storage: &HashedLayer<K, L>) {
self.pos = self.bounds.0;
if self.valid(storage) {
self.child.reposition(&storage.vals, storage.keys[self.pos].get_lower(), storage.keys[self.pos].get_upper());
}
}
fn reposition(&mut self, storage: &HashedLayer<K, L>, lower: usize, upper: usize) {
self.shift = 0;
while upper - lower >= (1 << self.shift) {
self.shift += 1;
}
self.shift -= 1;
self.bounds = (lower, upper);
self.pos = lower;
while self.pos < self.bounds.1 && !storage.keys[self.pos].is_some() {
self.pos += 1;
}
if self.valid(storage) {
self.child.reposition(&storage.vals, storage.keys[self.pos].get_lower(), storage.keys[self.pos].get_upper());
}
}
}