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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146


#[cfg(test)]
mod tests {
    use super::Hotel;

    #[test]
    fn inserting() {
        let collection = 0..10000;
        let mut hotel = Hotel::new();
        collection.for_each(|v| {
            let key = hotel.put(v);
            assert_eq!(key, v as usize);
        });
    }

    /// Guarantees that order of insertion is determinisitc even after retrieval
    #[test]
    fn order() {
        let collection = 0..10000;
        let mut hotel = Hotel::new();
        collection.for_each(|v| {
            let key = hotel.put(v);
            assert_eq!(key, v as usize);
        });

        hotel.take(0);
        hotel.take(15);
        hotel.take(32);
        hotel.take(3189);
        hotel.take(7777);

        assert_eq!(hotel.put(0), 7777);
        assert_eq!(hotel.put(0), 3189);
        assert_eq!(hotel.put(0), 32);
        assert_eq!(hotel.put(0), 15);
        assert_eq!(hotel.put(0), 0);
    }
}

/// collection to associate data with unique keys.
#[derive(Default)]
pub struct Hotel<T> {
    floor: Vec<Option<T>>,
    /// List of available slots on the floor
    holes: Vec<usize>,
}

impl<T> IntoIterator for Hotel<T> {
    type Item = (usize, T);

    type IntoIter = HotelIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        HotelIter {
            floor: self.floor,
            cursor: 0,
        }
    }

}

impl<T> Hotel<T> {
    pub fn with_capacity(capacity: usize) -> Self {
        Hotel {
            floor: Vec::with_capacity(capacity),
            holes: Vec::new(),
        }
    }

    pub fn new() -> Self {
        Hotel {
            floor: Vec::new(),
            holes: Vec::new(),
        }
    }

    pub fn values(&self) -> impl Iterator<Item = &T> {
        self.floor.iter().filter_map(|v| v.as_ref())
    }

    pub fn put(&mut self, value: T) -> usize {
        match self.holes.pop() {
            Some(index) => {
                self.floor[index] = Some(value);
                index
            }
            None => {
                let index = self.floor.len();
                self.floor.push(Some(value));
                index
            }
        }
    }

    pub fn get(&mut self, key: usize) -> Option<&T> {
        if let Some(v) = self.floor.get(key).and_then(|v| v.as_ref()) {
            Some(v)
        } else {
            None
        }
    }

    /// Remove element with `key` from Hotel and returns it.
    /// Returns None if key is not assigned.
    pub fn take(&mut self, key: usize) -> Option<T> {
        if self.floor.len() > key && self.floor[key].is_some() {
            // Declare this position as free to be occupied
            self.holes.push(key);
            return self.floor.remove(key);
        }

        None
    }

    /// Removes an element from the Hotel, returns Err of no Element is present
    pub fn remove(&mut self, key: usize) -> Result<T, ()> {
        self.take(key).ok_or(())
    }
}

pub struct HotelIter<T> {
    floor: Vec<Option<T>>,
    cursor: usize,
}

impl<T> Iterator for HotelIter<T> {
    type Item = (usize, T);

    fn next(&mut self) -> Option<Self::Item> {
        let cursor = self.cursor;
        if cursor >= self.floor.len() {
            return None;
        }
        
        self.cursor += 1;

        if self.floor[cursor].is_none() {
            return self.next();
        }


        let value = self.floor[cursor].take().unwrap();

        Some((cursor, value))
    }
}