uniques 0.2.1

#![doc = include_str!("../README.md")]

//--------------------------------------------------------------------------------------------------
// Crates

use std::collections::{HashMap, hash_map::Entry};

//--------------------------------------------------------------------------------------------------
// Structs

/**
Analyze items in a slice and calculate the unique, first, duplicate, and subsequent items and their
indices

| [`Uniques`] field  | Description                                | [`Itertools`] method      |
|--------------------|--------------------------------------------|---------------------------|
| [`unique`]         | Values appearing exactly once for indices  | *none*                    |
| [`first`]          | First occurring values for indices         | [`Itertools::unique`]     |
| [`duplicate`]      | Duplicate values for indices               | [`Itertools::duplicates`] |
| [`subsequent`]     | Subsequent duplicate values for indices    | [`Itertools::duplicates`] |
| [`unique_idx`]     | Indices of values that appear exactly once | *none*                    |
| [`first_idx`]      | Indices of first occurring values          | *none*                    |
| [`duplicate_idx`]  | Indices of values that are duplicated      | *none*                    |
| [`subsequent_idx`] | Indices of subsequent duplicate values     | *none*                    |

> Note that [`Itertools`] methods do not include indices.

[`unique_idx`]: [`Uniques::uniques_idx`]
[`first_idx`]: [`Uniques::first_idx`]
[`duplicate_idx`]: [`Uniques::duplicate_idx`]
[`subsequent_idx`]: [`Uniques::subsequent_idx`]

[`unique`]: [`Uniques::uniques`]
[`first`]: [`Uniques::first`]
[`duplicate`]: [`Uniques::duplicate`]
[`subsequent`]: [`Uniques::subsequent`]

[`Itertools`]: https://docs.rs/itertools/latest/itertools/trait.Itertools.html
[`Itertools::duplicates`]: https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.duplicates
[`Itertools::unique`]: https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.unique

# Examples

## Example with no duplicate values and only unique values

```rust
use std::collections::HashMap;
use uniques::*;

let result = Uniques::new(&["a", "b", "c"]);

assert_eq!(
    result.unique_idx,
    HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]),
);

assert_eq!(
    result.first_idx,
    HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]),
);

assert!(result.duplicate_idx.is_empty());

assert!(result.subsequent_idx.is_empty());

assert_eq!(
    result.unique,
    HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]),
);

assert_eq!(
    result.first,
    HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]),
);

assert!(result.duplicate.is_empty());

assert!(result.subsequent.is_empty());
```

## Example with duplicate values and unique values

```rust
use std::collections::HashMap;
use uniques::*;

let result = Uniques::new(&["a", "b", "c", "a", "b"]);

assert_eq!(
    result.unique_idx,
    HashMap::from([(&"c", 2)]),
);

assert_eq!(
    result.first_idx,
    HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]),
);

assert_eq!(
    result.duplicate_idx,
    HashMap::from([(&"a", vec![0, 3]), (&"b", vec![1, 4])]),
);

assert_eq!(
    result.subsequent_idx,
    HashMap::from([(&"a", vec![3]), (&"b", vec![4])]),
);

assert_eq!(
    result.unique,
    HashMap::from([(2, &"c")]),
);

assert_eq!(
    result.first,
    HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]),
);

assert_eq!(
    result.duplicate,
    HashMap::from([(0, &"a"), (1, &"b"), (3, &"a"), (4, &"b")]),
);

assert_eq!(
    result.subsequent,
    HashMap::from([(3, &"a"), (4, &"b")]),
);
```

## Example with only duplicate values and no unique values

```rust
use std::collections::HashMap;
use uniques::*;

let result = Uniques::new(&["a", "b", "c", "a", "b", "c"]);

assert!(result.unique_idx.is_empty());

assert_eq!(
    result.first_idx,
    HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]),
);

assert_eq!(
    result.duplicate_idx,
    HashMap::from([
        (&"a", vec![0, 3]),
        (&"b", vec![1, 4]),
        (&"c", vec![2, 5]),
    ]),
);

assert_eq!(
    result.subsequent_idx,
    HashMap::from([(&"a", vec![3]), (&"b", vec![4]), (&"c", vec![5])]),
);

assert!(result.unique.is_empty());

assert_eq!(
    result.first,
    HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]),
);

assert_eq!(
    result.duplicate,
    HashMap::from([
        (0, &"a"),
        (1, &"b"),
        (2, &"c"),
        (3, &"a"),
        (4, &"b"),
        (5, &"c"),
    ]),
);

assert_eq!(
    result.subsequent,
    HashMap::from([(3, &"a"), (4, &"b"), (5, &"c")]),
);
```
*/
pub struct Uniques<'a, T> {
    /// Indices of values that appear exactly once
    pub unique_idx: HashMap<&'a T, usize>,

    /// Indices of first occurring values
    pub first_idx: HashMap<&'a T, usize>,

    /// Indices of values that are duplicated
    pub duplicate_idx: HashMap<&'a T, Vec<usize>>,

    /// Indices of subsequent duplicate values
    pub subsequent_idx: HashMap<&'a T, Vec<usize>>,

    /// Values appearing exactly once for indices
    pub unique: HashMap<usize, &'a T>,

    /**
    First occurring values for indices

    Similar to
    [`Itertools::unique`](https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.unique)
    but includes indices
    */
    pub first: HashMap<usize, &'a T>,

    /**
    Duplicate values for indices

    Similar to
    [`Itertools::duplicates`](https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.duplicates)
    but includes indices
    */
    pub duplicate: HashMap<usize, &'a T>,

    /**
    Subsequent duplicate values for indices

    Similar to
    [`Itertools::duplicates`](https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.duplicates)
    but includes indices
    */
    pub subsequent: HashMap<usize, &'a T>,
}

impl<'a, T> Uniques<'a, T> {
    /**
    Analyze items in a slice and calculate the unique, first, and duplicate items and their indices
    */
    pub fn new(items: &'a [T]) -> Uniques<'a, T>
    where
        T: std::hash::Hash + Eq,
    {
        let mut unique_idx = HashMap::new();
        let mut first_idx = HashMap::new();
        let mut duplicate_idx = HashMap::new();
        let mut subsequent_idx = HashMap::new();

        let mut unique = HashMap::new();
        let mut first = HashMap::new();
        let mut duplicate = HashMap::new();
        let mut subsequent = HashMap::new();

        for (i, x) in items.iter().enumerate() {
            match first_idx.entry(x) {
                Entry::Vacant(first_idx_x) => {
                    first_idx_x.insert(i);
                    first.insert(i, x);

                    unique_idx.insert(x, i);
                    unique.insert(i, x);
                }
                Entry::Occupied(first_idx_x) => {
                    let first_i = *first_idx_x.get();
                    duplicate_idx
                        .entry(x)
                        .and_modify(|v: &mut Vec<_>| v.push(i))
                        .or_insert_with(|| {
                            duplicate.insert(first_i, first[&first_i]);
                            vec![first_i, i]
                        });
                    duplicate.insert(i, x);

                    subsequent_idx
                        .entry(x)
                        .and_modify(|v: &mut Vec<_>| v.push(i))
                        .or_insert_with(|| vec![i]);
                    subsequent.insert(i, x);

                    if let Some(j) = unique_idx.remove(x) {
                        unique.remove(&j);
                    }
                }
            }
        }

        Uniques {
            unique_idx,
            first_idx,
            duplicate_idx,
            subsequent_idx,
            unique,
            first,
            duplicate,
            subsequent,
        }
    }
}

//--------------------------------------------------------------------------------------------------
// Tests

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashMap;

    #[test]
    fn integers_empty() {
        let input: &[usize] = &[];

        let unique_idx = HashMap::new();
        let first_idx = HashMap::new();
        let duplicate_idx = HashMap::new();
        let subsequent_idx = HashMap::new();

        let unique = HashMap::new();
        let first = HashMap::new();
        let duplicate = HashMap::new();
        let subsequent = HashMap::new();

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }

    #[test]
    fn integers_no_duplicates() {
        let input = &[0, 1, 2];

        let unique_idx = HashMap::from([(&0, 0), (&1, 1), (&2, 2)]);
        let first_idx = HashMap::from([(&0, 0), (&1, 1), (&2, 2)]);
        let duplicate_idx = HashMap::new();
        let subsequent_idx = HashMap::new();

        let unique = HashMap::from([(0, &0), (1, &1), (2, &2)]);
        let first = HashMap::from([(0, &0), (1, &1), (2, &2)]);
        let duplicate = HashMap::new();
        let subsequent = HashMap::new();

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }

    #[test]
    fn integers_with_duplicates() {
        let input = &[0, 1, 2, 0, 1];

        let unique_idx = HashMap::from([(&2, 2)]);
        let first_idx = HashMap::from([(&0, 0), (&1, 1), (&2, 2)]);
        let duplicate_idx = HashMap::from([(&0, vec![0, 3]), (&1, vec![1, 4])]);
        let subsequent_idx = HashMap::from([(&0, vec![3]), (&1, vec![4])]);

        let unique = HashMap::from([(2, &2)]);
        let first = HashMap::from([(0, &0), (1, &1), (2, &2)]);
        let duplicate = HashMap::from([(0, &0), (1, &1), (3, &0), (4, &1)]);
        let subsequent = HashMap::from([(3, &0), (4, &1)]);

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }

    #[test]
    fn strs_empty() {
        let input: &[&str] = &[];

        let unique_idx = HashMap::new();
        let first_idx = HashMap::new();
        let duplicate_idx = HashMap::new();
        let subsequent_idx = HashMap::new();

        let unique = HashMap::new();
        let first = HashMap::new();
        let duplicate = HashMap::new();
        let subsequent = HashMap::new();

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }

    #[test]
    fn strs_no_duplicates() {
        let input = &["a", "b", "c"];

        let unique_idx = HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]);
        let first_idx = HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]);
        let duplicate_idx = HashMap::new();
        let subsequent_idx = HashMap::new();

        let unique = HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]);
        let first = HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]);
        let duplicate = HashMap::new();
        let subsequent = HashMap::new();

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }

    #[test]
    fn strs_with_duplicates() {
        let input = &["a", "b", "c", "a", "b"];

        let unique_idx = HashMap::from([(&"c", 2)]);
        let first_idx = HashMap::from([(&"a", 0), (&"b", 1), (&"c", 2)]);
        let duplicate_idx = HashMap::from([(&"a", vec![0, 3]), (&"b", vec![1, 4])]);
        let subsequent_idx = HashMap::from([(&"a", vec![3]), (&"b", vec![4])]);

        let unique = HashMap::from([(2, &"c")]);
        let first = HashMap::from([(0, &"a"), (1, &"b"), (2, &"c")]);
        let duplicate = HashMap::from([(0, &"a"), (1, &"b"), (3, &"a"), (4, &"b")]);
        let subsequent = HashMap::from([(3, &"a"), (4, &"b")]);

        let result = Uniques::new(input);

        assert_eq!(result.unique_idx, unique_idx);
        assert_eq!(result.first_idx, first_idx);
        assert_eq!(result.duplicate_idx, duplicate_idx);
        assert_eq!(result.subsequent_idx, subsequent_idx);

        assert_eq!(result.unique, unique);
        assert_eq!(result.first, first);
        assert_eq!(result.duplicate, duplicate);
        assert_eq!(result.subsequent, subsequent);
    }
}