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

use std::cmp::{Ord, Ordering};

mod sort;
mod select;

use crate::sort::make_tree;

#[derive(Debug)]
struct Pair<K, V> {
    key: K,
    value: V,
}

impl<K: Ord, V> Eq for Pair<K, V> {
}

impl<K: Ord, V> PartialEq for Pair<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.key.eq(&other.key)
    }
}

impl<K: Ord, V> Ord for Pair<K, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.key.cmp(&other.key)
    }
}

impl<K: Ord, V> PartialOrd for Pair<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.key.partial_cmp(&other.key)
    }
}

pub struct MultiMap<K, V> {
    entries: Vec<Pair<K, V>>,
}

impl<K, V> MultiMap<K, V> {
    pub fn new() -> MultiMap<K, V> {
        MultiMap {
            entries: Vec::new(),
        }
    }
    pub fn with_capacity(capacity: usize) -> MultiMap<K, V> {
        MultiMap {
            entries: Vec::with_capacity(capacity),
        }
    }
    pub fn len(&self) -> usize {
        self.entries.len()
    }
    pub fn capacity(&self) -> usize {
        self.entries.capacity()
    }
    pub fn truncate(&mut self) {
        self.entries.truncate(0)
    }
}

impl<K: Ord, V> MultiMap<K, V> {
    fn find(&self, key: &K) -> Option<usize> {
        let mut i = 0;
        while i < self.entries.len() {
            match key.cmp(&self.entries[i].key) {
                Ordering::Less => i = 2 * i + 1,
                Ordering::Greater => i = 2 * i + 2,
                Ordering::Equal => return Some(i),
            }
        }
        None
    }
    pub fn remove(&mut self, key: &K) -> Option<V> {
        if let Some(pos) = self.find(key) {
            let value = self.entries.swap_remove(pos).value;
            make_tree(&mut self.entries);
            Some(value)
        } else {
            None
        }
    }
    pub fn get(&mut self, key: &K) -> Option<&V> {
        if let Some(pos) = self.find(key) {
            Some(&self.entries[pos].value)
        } else {
            None
        }
    }
    pub fn insert(&mut self, key: K, value: V) {
        self.entries.push(Pair { key, value });
        make_tree(&mut self.entries);
    }
}


#[cfg(test)]
mod tests {
    use super::MultiMap;
    #[test]
    fn it_works() {
        let mut mm = MultiMap::new();
        mm.insert(1, 2);
        assert_eq!(mm.get(&1), Some(&2));
        mm.insert(2, 3);
        println!("{:?}", mm.entries);
        assert_eq!(mm.get(&2), Some(&3));
        assert_eq!(mm.get(&1), Some(&2));
    }
}