#[cfg(test)]
extern crate quickcheck;
#[cfg(test)]
#[macro_use(quickcheck)]
extern crate quickcheck_macros;
use std::collections::HashMap;
use std::fmt;
use std::hash::Hash;
use std::iter::DoubleEndedIterator;
use std::ops::Index;
use std::vec::Vec;
type ExtractComparable<V, C> = fn(&V) -> C;
pub struct OrderedMap<K, V, C> {
map: HashMap<K, V>,
descending_pairs: Vec<(K, C)>,
extract_comparable: ExtractComparable<V, C>,
}
impl<K: fmt::Debug, V: fmt::Debug, C: fmt::Debug> fmt::Debug for OrderedMap<K, V, C> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OrderedMap")
.field("map", &self.map)
.field("descending_pairs", &self.descending_pairs)
.finish()
}
}
pub struct DescendingKeys<'a, K: 'a, C: 'a> {
inner: std::slice::Iter<'a, (K, C)>,
}
impl<'a, K: 'a, C: 'a> Iterator for DescendingKeys<'a, K, C> {
type Item = &'a K;
fn next(&mut self) -> Option<Self::Item> {
match self.inner.next() {
None => None,
Some((k, _)) => Some(k),
}
}
}
impl<'a, K: 'a, C: 'a> DoubleEndedIterator for DescendingKeys<'a, K, C> {
fn next_back(&mut self) -> Option<Self::Item> {
match self.inner.next_back() {
None => None,
Some((k, _)) => Some(k),
}
}
}
pub struct DescendingValues<'a, K, V, C> {
map: &'a HashMap<K, V>,
keys: DescendingKeys<'a, K, C>,
}
impl<'a, K, V, C> Iterator for DescendingValues<'a, K, V, C>
where
K: Eq + Hash,
{
type Item = &'a V;
fn next(&mut self) -> Option<Self::Item> {
match self.keys.next() {
None => None,
Some(k) => Some(self.map.index(k)),
}
}
}
impl<'a, K, V, C> DoubleEndedIterator for DescendingValues<'a, K, V, C>
where
K: Eq + Hash,
{
fn next_back(&mut self) -> Option<Self::Item> {
match self.keys.next_back() {
None => None,
Some(k) => Some(self.map.index(k)),
}
}
}
pub struct DescendingItems<'a, K, V, C> {
map: &'a HashMap<K, V>,
keys: DescendingKeys<'a, K, C>,
}
impl<'a, K, V, C> Iterator for DescendingItems<'a, K, V, C>
where
K: Eq + Hash,
{
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
match self.keys.next() {
None => None,
Some(k) => Some((k, self.map.index(k))),
}
}
}
impl<'a, K, V, C> DoubleEndedIterator for DescendingItems<'a, K, V, C>
where
K: Eq + Hash,
{
fn next_back(&mut self) -> Option<Self::Item> {
match self.keys.next_back() {
None => None,
Some(k) => Some((k, self.map.index(k))),
}
}
}
impl<'a, K: 'a, V: 'a, C: 'a> OrderedMap<K, V, C>
where
K: Eq + Hash + Copy,
C: PartialOrd,
{
pub fn new(extract_comparable: ExtractComparable<V, C>) -> Self {
OrderedMap {
map: HashMap::new(),
descending_pairs: vec![],
extract_comparable,
}
}
pub fn len(&self) -> usize {
self.map.len()
}
pub fn descending_keys(&'a self) -> DescendingKeys<'a, K, C> {
DescendingKeys {
inner: self.descending_pairs.iter(),
}
}
pub fn descending_values(&'a self) -> DescendingValues<'a, K, V, C> {
DescendingValues {
map: &self.map,
keys: self.descending_keys(),
}
}
pub fn descending_items(&'a self) -> DescendingItems<'a, K, V, C> {
DescendingItems {
map: &self.map,
keys: self.descending_keys(),
}
}
fn insert_into_pairs(&mut self, k: K, c: C) {
let mut insert_index = None;
for (i, (_ek, ec)) in self.descending_pairs.iter().enumerate() {
if &c >= ec {
insert_index = Some(i);
break;
}
}
let idx = match insert_index {
None => self.descending_pairs.len(),
Some(i) => i,
};
self.descending_pairs.insert(idx, (k, c));
}
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
let new_c = (self.extract_comparable)(&v);
match self.map.insert(k, v) {
None => {
self.insert_into_pairs(k, new_c);
None
}
Some(v) => {
remove_from_pairs(&mut self.descending_pairs, &k);
self.insert_into_pairs(k, new_c);
Some(v)
}
}
}
pub fn remove(&mut self, k: &K) -> Option<V> {
match self.map.remove(k) {
None => None,
Some(v) => {
remove_from_pairs(&mut self.descending_pairs, k);
Some(v)
}
}
}
}
fn remove_from_pairs<K, C>(pairs: &mut Vec<(K, C)>, k: &K) -> bool
where
K: Eq,
{
let mut removed = false;
for i in 0..pairs.len() {
if pairs[i].0 == *k {
pairs.remove(i);
removed = true;
break;
}
}
removed
}
#[cfg(test)]
mod tests {
use std::collections::HashMap;
use super::OrderedMap;
fn to_comparable(t: &(f32, f64)) -> f32 {
t.0
}
#[quickcheck]
fn descending_order(kvs: Vec<(i32, (f32, f64))>) -> bool {
let empty = kvs.is_empty();
let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
let mut map = OrderedMap::new(to_comparable);
for (k, v) in ks.iter().zip(vs.iter()) {
map.insert(k.clone(), v.clone());
}
let mut tuples: Vec<(i32, f32)> = ks
.iter()
.zip(vs.iter())
.map(|(k, v)| (k.clone(), to_comparable(v)))
.collect();
let mut count = HashMap::new();
for k in ks.iter() {
count.insert(k, 0);
}
for k in ks.iter() {
count.insert(k, count.get(k).unwrap() + 1);
}
let mut i = 0;
for _ in 0..tuples.len() {
if i < tuples.len() {
let (k, _c) = tuples[i];
let cnt = count.get_mut(&k).unwrap();
if *cnt > 1 {
tuples.remove(i);
*cnt = *cnt - 1;
} else {
i = i + 1;
}
} else {
break;
}
}
tuples.sort_by(|(_, c1), (_, c2)| c1.partial_cmp(c2).unwrap());
tuples.reverse();
let truth_keys: Vec<i32> = tuples.iter().map(|(k, _)| k.clone()).collect();
let have_keys: Vec<i32> = map.descending_keys().map(|x| x.clone()).collect();
let property = truth_keys == have_keys;
let safe1 = empty || !truth_keys.is_empty();
property && safe1
}
#[quickcheck]
fn same_length(kvs: Vec<(i32, (f32, f64))>) -> bool {
let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
let mut map = OrderedMap::new(to_comparable);
for (k, v) in ks.iter().zip(vs.iter()) {
map.insert(k.clone(), v.clone());
}
map.map.len() == map.descending_keys().collect::<Vec<_>>().len()
}
#[quickcheck]
fn same_keys(kvs: Vec<(i32, (f32, f64))>) -> bool {
let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
let mut map = OrderedMap::new(to_comparable);
for (k, v) in ks.iter().zip(vs.iter()) {
map.insert(k.clone(), v.clone());
}
let mut a = map.descending_keys().map(|x| x.clone()).collect::<Vec<_>>();
a.sort();
let mut b = map.map.keys().map(|x| x.clone()).collect::<Vec<_>>();
b.sort();
let mut ks = ks;
ks.sort();
ks.dedup();
a == b && b == ks
}
#[quickcheck]
fn insert_then_remove_all_is_empty(kvs: Vec<(i32, (f32, f64))>, other_keys: Vec<i32>) -> bool {
let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
let mut map = OrderedMap::new(to_comparable);
for (k, v) in ks.iter().zip(vs.iter()) {
map.insert(k.clone(), v.clone());
}
for k in ks.iter() {
map.remove(k);
}
let a = 0 == map.map.len() && 0 == map.descending_keys().collect::<Vec<_>>().len();
for k in other_keys.iter() {
map.remove(k);
}
let b = 0 == map.map.len() && 0 == map.descending_keys().collect::<Vec<_>>().len();
a && b
}
#[quickcheck]
fn insert_then_remove_is_identity(kvs: Vec<(u32, (f32, f64))>, new_v: (f32, f64)) -> bool {
let ks: Vec<u32> = kvs.iter().map(|(k, _)| k.clone()).collect();
let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
let mut map = OrderedMap::new(to_comparable);
for (k, v) in ks.iter().zip(vs.iter()) {
map.insert(k.clone(), v.clone());
}
let old_map = map.map.clone();
let old_keys = map
.descending_keys()
.map(|k| k.clone())
.collect::<Vec<u32>>();
let k: u32 = ks.iter().sum();
let k: u32 = k + 1;
map.insert(k.clone(), new_v);
map.remove(&k);
let new_map = map.map.clone();
let new_keys = map.descending_keys().map(|k| k.clone()).collect::<Vec<_>>();
old_map == new_map && old_keys == new_keys
}
}