use std::fmt;

// Error type
struct SparseSetError;

#[derive(Debug, Copy, Clone)]
struct DenseItem<T> {
    index: usize,
    value: T
}

// 'sparse' is the sparse list tracking the indices of densely-stored items
// 'dense' is the dense list containing the actual items
// 'n' is the total number of densely-stored items
#[derive(Debug)]
struct SparseSet<'s, 'd, T> {
    sparse: &'s mut [Option<usize>],
    dense: &'d mut [Option<DenseItem<T>>],
    n: usize
}

impl<'s, 'd, T> SparseSet<'s, 'd, T> {
    // A new sparse set can be created with two mutable slices: one for the sparse and one for the dense slices
    pub fn new(sparse_slice: &'s mut [Option<usize>], dense_slice: &'d mut [Option<DenseItem<T>>], n: usize) -> SparseSet<'s, 'd, T> {
        SparseSet {
            sparse: sparse_slice,
            dense: dense_slice,
            n: n
        }
    }

    // Add an item to the set at a target sparse location
    fn insert(&mut self, target_sparse_index: usize, value: T) {
        // Create the item, first of all
        let item = DenseItem {
            index: target_sparse_index,
            value: value
        };

        // Insert the item into the dense slice at index N
        self.dense[self.n] = Some(item);
        
        // Write N to the sparse slice at the target index
        self.sparse[target_sparse_index] = Some(self.n);

        // Increase N by one, lastly
        self.n += 1;
    }

    // Remove an item at the supplied target index from the set
    // Replaces the selected target with the last item in the dense vector
    fn remove(&mut self, target_sparse_index: usize) -> Result<(), SparseSetError> {
        // Get the last dense item and clear its former dense entry
        let last_item = self.dense[self.n - 1].as_ref().unwrap();
        let last_item_sparse_index = last_item.index;
        self.dense[self.n - 1] = None;

        // Replace the target dense item with the last dense item
        let target_dense_index = self.sparse[target_sparse_index].unwrap();
        self.dense[target_dense_index] = Some(last_item);

        // Update the (former) last dense item's corresponding dense index key to point to its new location (where the target used to be)
        self.sparse[last_item_sparse_index] = Some(target_dense_index);

        // Clear the target's sparse entry
        self.sparse[target_sparse_index] = None;

        // Decrement N
        self.n -= 1;

        Ok(())
    }
}

fn main() {
    // Create the arrays for our sparse set
    let mut dense_array: [Option<DenseItem<f32>>; 8] = [None; 8];
    let mut sparse_array: [Option<usize>; 8] = [None; 8];

    let mut test_set: SparseSet<f32> = SparseSet::new(&mut sparse_array, &mut dense_array, 0);
    test_set.insert(0, 69.0);
    test_set.insert(4, 420.0);
    test_set.insert(7, 9001.0);
    println!("{:?}", test_set);
    test_set.remove(1);
    println!("{:?}", test_set);
}