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

#![allow(clippy::type_repetition_in_bounds)]

use std::collections::HashMap;
use std::hash::Hash;

use ironsea_index::IndexedDestructured;
use ironsea_index::Record;
use ironsea_index::RecordFields;
use serde::Deserialize;
use serde::Serialize;

/// Implementation of [`ironsea_index`]::[`IndexedDestructured`].
///
/// The index is backed by a [`std`]`::`[`collections`]`::`[`HashMap`].
///
/// An ordered [`std`]`::`[`vec`]`::`[`Vec`] of keys is maintained, in
/// order to satisfy range queries.
///
/// [`ironsea_index`]: https://epfl-dias.github.io/ironsea_index/ironsea_index/index.html
/// [`IndexedDestructured`]: https://epfl-dias.github.io/ironsea_index/ironsea_index/trait.IndexedDestructured.html
///
/// [`std`]: https://doc.rust-lang.org/std/index.html
/// [`collections`]: https://doc.rust-lang.org/std/collections/index.html
/// [`HashMap`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
/// [`vec`]: https://doc.rust-lang.org/std/vec/index.html
/// [`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html

#[derive(Clone, Debug, Deserialize, Serialize)]
pub struct Index<F, K>
where
    K: Clone + Eq + Hash + PartialEq + Ord,
{
    hashmap: HashMap<K, F>,
    keys: Vec<K>,
}

impl<F, K> Index<F, K>
where
    K: Clone + Eq + Hash + PartialEq + Ord,
{
    /// Creates a new Index from the provided iterator.
    pub fn new<I, R>(iter: I) -> Self
    where
        I: Iterator<Item = R>,
        R: Record<K> + RecordFields<F>,
    {
        let (size, _) = iter.size_hint();
        let mut hashmap = HashMap::with_capacity(size);

        for r in iter {
            hashmap.insert(r.key(), r.fields());
        }

        let mut keys = hashmap.keys().cloned().collect::<Vec<_>>();
        keys.sort_unstable();

        Index { hashmap, keys }
    }

    /// Return an ordered list of all keys contained in the index.
    pub fn keys(&self) -> &Vec<K> {
        &self.keys
    }

    /// Returns the position within the index of the key.
    ///
    /// If the key is not found, return the index where it should be
    /// inserted.
    fn index(&self, key: &K) -> usize {
        match self.keys.binary_search(&key) {
            Ok(i) => i,
            Err(i) => {
                if i >= self.keys.len() {
                    self.keys.len() - 1
                } else {
                    i
                }
            }
        }
    }
}

impl<F, K> IndexedDestructured<F, K> for Index<F, K>
where
    K: Clone + Eq + Hash + PartialEq + Ord,
{
    fn find(&self, key: &K) -> Vec<&F> {
        let mut values = vec![];

        if let Some(fields) = self.hashmap.get(key) {
            values.push(fields);
        }

        values
    }

    fn find_range(&self, start: &K, end: &K) -> Vec<(K, &F)> {
        let start = self.index(start);
        let end = self.index(end);

        (start..end)
            .filter_map(|i| {
                let key = &self.keys[i];
                if let Some(fields) = self.hashmap.get(key) {
                    Some((key.clone(), fields))
                } else {
                    None
                }
            })
            .collect()
    }
}