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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
use std::hash::Hasher;
use std::ops::Deref;
use abomonation::Abomonation;
use timely_sort::Unsigned;
pub trait Hashable {
type Output: Unsigned+Copy;
fn hashed(&self) -> Self::Output;
}
impl<T: ::std::hash::Hash> Hashable for T {
type Output = u64;
fn hashed(&self) -> u64 {
let mut h: ::fnv::FnvHasher = Default::default();
self.hash(&mut h);
h.finish()
}
}
pub trait HashOrdered : Ord+Hashable { }
impl<T: Ord+Hashable> HashOrdered for OrdWrapper<T> { }
impl<T: Ord+Hashable> HashOrdered for HashableWrapper<T> { }
impl<T: Unsigned+Copy> HashOrdered for UnsignedWrapper<T> { }
impl<T: Ord+Hashable+Abomonation> Abomonation for OrdWrapper<T> {
#[inline] unsafe fn entomb<W: ::std::io::Write>(&self, write: &mut W) -> ::std::io::Result<()> {
self.item.entomb(write)
}
#[inline] unsafe fn exhume<'a,'b>(&'a mut self, mut bytes: &'b mut [u8]) -> Option<&'b mut [u8]> {
let temp = bytes;
bytes = self.item.exhume(temp)?;
Some(bytes)
}
}
impl<T: Hashable+Abomonation> Abomonation for HashableWrapper<T> {
#[inline] unsafe fn entomb<W: ::std::io::Write>(&self, write: &mut W) -> ::std::io::Result<()> {
self.item.entomb(write)
}
#[inline] unsafe fn exhume<'a,'b>(&'a mut self, mut bytes: &'b mut [u8]) -> Option<&'b mut [u8]> {
let temp = bytes;
bytes = self.item.exhume(temp)?;
Some(bytes)
}
}
impl<T: Unsigned+Copy+Hashable+Abomonation> Abomonation for UnsignedWrapper<T> {
#[inline] unsafe fn entomb<W: ::std::io::Write>(&self, write: &mut W) -> ::std::io::Result<()> {
self.item.entomb(write)
}
#[inline] unsafe fn exhume<'a,'b>(&'a mut self, mut bytes: &'b mut [u8]) -> Option<&'b mut [u8]> {
let temp = bytes;
bytes = self.item.exhume(temp)?;
Some(bytes)
}
}
#[derive(Clone, Eq, PartialEq, Debug, Default)]
pub struct OrdWrapper<T: Ord+Hashable> {
pub item: T
}
impl<T: Ord+Hashable> PartialOrd for OrdWrapper<T> {
#[inline]
fn partial_cmp(&self, other: &Self) -> Option<::std::cmp::Ordering> {
(self.item.hashed(), &self.item).partial_cmp(&(other.item.hashed(), &other.item))
}
}
impl<T: Ord+Hashable> Ord for OrdWrapper<T> {
#[inline]
fn cmp(&self, other: &Self) -> ::std::cmp::Ordering {
(self.item.hashed(), &self.item).cmp(&(other.item.hashed(), &other.item))
}
}
impl<T: Ord+Hashable> Hashable for OrdWrapper<T> {
type Output = T::Output;
fn hashed(&self) -> T::Output { self.item.hashed() }
}
impl<T: Ord+Hashable> Deref for OrdWrapper<T> {
type Target = T;
fn deref(&self) -> &T { &self.item }
}
#[derive(Clone, Default, Ord, PartialOrd, Eq, PartialEq, Debug, Copy)]
pub struct HashableWrapper<T: Hashable> {
hash: T::Output,
pub item: T,
}
impl<T: Hashable> Hashable for HashableWrapper<T> {
type Output = T::Output;
#[inline]
fn hashed(&self) -> T::Output { self.hash }
}
impl<T: Hashable> Deref for HashableWrapper<T> {
type Target = T;
#[inline]
fn deref(&self) -> &T { &self.item }
}
impl<T: Hashable> From<T> for HashableWrapper<T> {
#[inline]
fn from(item: T) -> HashableWrapper<T> {
HashableWrapper {
hash: item.hashed(),
item,
}
}
}
#[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Default, Debug, Copy)]
pub struct UnsignedWrapper<T: Unsigned+Copy> {
pub item: T,
}
impl<T: Unsigned+Copy> Hashable for UnsignedWrapper<T> {
type Output = T;
#[inline]
fn hashed(&self) -> Self::Output { self.item }
}
impl<T: Unsigned+Copy> Deref for UnsignedWrapper<T> {
type Target = T;
#[inline]
fn deref(&self) -> &T { &self.item }
}
impl<T: Unsigned+Copy> From<T> for UnsignedWrapper<T> {
#[inline]
fn from(item: T) -> Self { UnsignedWrapper { item } }
}