use std::cmp::Ordering;
use access::DataIndex;
use cons::Nil;
use field::Value;
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct Permutation<I> {
perm: Option<I>,
}
impl<I> Default for Permutation<I> {
fn default() -> Permutation<I> {
Permutation { perm: None }
}
}
impl<'a> From<&'a [usize]> for Permutation<&'a [usize]> {
fn from(orig: &'a [usize]) -> Permutation<&'a [usize]> {
Permutation { perm: Some(orig) }
}
}
impl From<Vec<usize>> for Permutation<Vec<usize>> {
fn from(orig: Vec<usize>) -> Permutation<Vec<usize>> {
Permutation { perm: Some(orig) }
}
}
impl Permutation<Vec<usize>> {
pub fn update_indices(mut self, new_permutation: &[usize]) -> Permutation<Vec<usize>> {
self.perm = match self.perm {
Some(ref prev_perm) => {
Some(
new_permutation
.iter()
.map(|&new_idx| prev_perm[new_idx])
.collect(),
)
}
None => Some(new_permutation.iter().map(|&idx| idx).collect()),
};
self
}
}
macro_rules! impl_permutation_len {
($($t:ty)*) => {$(
impl Permutation<$t>
{
pub fn map_index(&self, requested: usize) -> usize
{
self.perm.as_ref().map_or(requested, |perm| perm[requested])
}
pub fn len(&self) -> Option<usize>
{
self.perm.as_ref().map(|perm| perm.len())
}
pub fn is_permuted(&self) -> bool { self.perm.is_some() }
}
)*}
}
impl_permutation_len![&[usize] Vec<usize>];
pub trait UpdatePermutation {
fn update_permutation(self, order: &[usize]) -> Self;
}
impl UpdatePermutation for Nil {
fn update_permutation(self, _order: &[usize]) -> Nil {
Nil
}
}
pub trait SortOrder {
fn sort_order(&self) -> Vec<usize>;
}
impl<DI> SortOrder for DI
where
DI: DataIndex,
<DI as DataIndex>::DType: Ord,
{
fn sort_order(&self) -> Vec<usize> {
let mut order = (0..self.len()).collect::<Vec<_>>();
order.sort_by(|&left, &right| {
self.get_datum(left)
.unwrap()
.cmp(&self.get_datum(right).unwrap())
});
order
}
}
pub trait SortOrderUnstable {
fn sort_order_unstable(&self) -> Vec<usize>;
}
impl<DI> SortOrderUnstable for DI
where
DI: DataIndex,
<DI as DataIndex>::DType: Ord,
{
fn sort_order_unstable(&self) -> Vec<usize> {
let mut order = (0..self.len()).collect::<Vec<_>>();
order.sort_unstable_by(|&left, &right| {
self.get_datum(left)
.unwrap()
.cmp(&self.get_datum(right).unwrap())
});
order
}
}
pub trait SortOrderComparator<F> {
fn sort_order_by(&self, compare: F) -> Vec<usize>;
}
impl<DI, F> SortOrderComparator<F> for DI
where
DI: DataIndex,
F: FnMut(Value<&DI::DType>, Value<&DI::DType>) -> Ordering,
{
fn sort_order_by(&self, mut compare: F) -> Vec<usize> {
let mut order = (0..self.len()).collect::<Vec<_>>();
order.sort_by(|&left, &right| {
compare(
self.get_datum(left).unwrap(),
self.get_datum(right).unwrap(),
)
});
order
}
}
pub trait SortOrderUnstableComparator<F> {
fn sort_order_unstable_by(&self, compare: F) -> Vec<usize>;
}
impl<DI, F> SortOrderUnstableComparator<F> for DI
where
DI: DataIndex,
F: FnMut(Value<&DI::DType>, Value<&DI::DType>) -> Ordering,
{
fn sort_order_unstable_by(&self, mut compare: F) -> Vec<usize> {
let mut order = (0..self.len()).collect::<Vec<_>>();
order.sort_unstable_by(|&left, &right| {
compare(
self.get_datum(left).unwrap(),
self.get_datum(right).unwrap(),
)
});
order
}
}
pub fn sort_f32(left: &f32, right: &f32) -> Ordering {
left.partial_cmp(&right).unwrap_or_else(|| {
if left.is_nan() && !right.is_nan() {
Ordering::Less
} else {
Ordering::Greater
}
})
}
pub fn sort_f32_values(left: Value<&f32>, right: Value<&f32>) -> Ordering {
match (left, right) {
(Value::Na, Value::Na) => Ordering::Equal,
(Value::Na, Value::Exists(_)) => Ordering::Less,
(Value::Exists(_), Value::Na) => Ordering::Greater,
(Value::Exists(ref left), Value::Exists(ref right)) => sort_f32(left, right),
}
}
pub fn sort_f64(left: &f64, right: &f64) -> Ordering {
left.partial_cmp(&right).unwrap_or_else(|| {
if left.is_nan() && !right.is_nan() {
Ordering::Less
} else {
Ordering::Greater
}
})
}
pub fn sort_f64_values(left: Value<&f64>, right: Value<&f64>) -> Ordering {
match (left, right) {
(Value::Na, Value::Na) => Ordering::Equal,
(Value::Na, Value::Exists(_)) => Ordering::Less,
(Value::Exists(_), Value::Na) => Ordering::Greater,
(Value::Exists(ref left), Value::Exists(ref right)) => sort_f64(left, right),
}
}
pub trait FilterPerm<P> {
fn filter_perm(&self, predicate: P) -> Vec<usize>;
}
impl<DI, P> FilterPerm<P> for DI
where
DI: DataIndex,
P: FnMut(Value<&DI::DType>) -> bool,
{
fn filter_perm(&self, mut predicate: P) -> Vec<usize> {
let order = (0..self.len()).collect::<Vec<_>>();
order
.iter()
.filter(|&&idx| predicate(self.get_datum(idx).unwrap()))
.map(|&idx| idx)
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
use field::FieldData;
#[test]
fn sort_order_no_na() {
let field_data: FieldData<u64> = FieldData::from_vec(vec![2u64, 5, 3, 1, 8]);
let sorted_order = field_data.sort_order();
assert_eq!(sorted_order, vec![3, 0, 2, 1, 4]);
let field_data: FieldData<f64> = FieldData::from_vec(vec![2.0, 5.4, 3.1, 1.1, 8.2]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![3, 0, 2, 1, 4]);
let field_data: FieldData<f64> =
FieldData::from_vec(vec![2.0, ::std::f64::NAN, 3.1, 1.1, 8.2]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![1, 3, 0, 2, 4]);
let field_data: FieldData<f64> =
FieldData::from_vec(vec![2.0, ::std::f64::NAN, 3.1, ::std::f64::INFINITY, 8.2]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![1, 0, 2, 4, 3]);
}
#[test]
fn sort_order_na() {
let field_data = FieldData::from_field_vec(vec![
Value::Exists(2u64),
Value::Exists(5),
Value::Na,
Value::Exists(1),
Value::Exists(8),
]);
let sorted_order = field_data.sort_order();
assert_eq!(sorted_order, vec![2, 3, 0, 1, 4]);
let field_data = FieldData::from_field_vec(vec![
Value::Exists(2.1),
Value::Exists(5.5),
Value::Na,
Value::Exists(1.1),
Value::Exists(8.2930),
]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![2, 3, 0, 1, 4]);
let field_data = FieldData::from_field_vec(vec![
Value::Exists(2.1),
Value::Exists(::std::f64::NAN),
Value::Na,
Value::Exists(1.1),
Value::Exists(8.2930),
]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![2, 1, 3, 0, 4]);
let field_data = FieldData::from_field_vec(vec![
Value::Exists(2.1),
Value::Exists(::std::f64::NAN),
Value::Na,
Value::Exists(::std::f64::INFINITY),
Value::Exists(8.2930),
]);
let sorted_order = field_data.sort_order_by(sort_f64_values);
assert_eq!(sorted_order, vec![2, 1, 0, 4, 3]);
}
}