use std::mem::swap;

fn main() {
    let mut set = HashSet::new();

    for n in 0..=2000 {
        assert!(!set.has(n));
    }

    for n in 1..=1000 {
        set.insert(n);
    }

    for n in 5..=55 {
        set.insert(n);
    }

    for n in 1001..=2000 {
        assert!(!set.has(n));
    }

    for n in 1..=1000 {
        assert!(set.has(n));
    }
}

type Value = i64;
pub struct HashSet {
    len: usize,
    slots: Vec<HashSetSlot>,
}

impl HashSet {
    // the maximum number of slots per value before we shrink the vec.
    const MAX_LOAD_RATIO: usize = 4;
    // the number of slots per value we allocate when resizing the vec.
    const TARGET_LOAD_RATIO: usize = 3;
    // the minimum number of slots per value befoe we grow the vec.
    const MIN_LOAD_RATIO: usize = 2;

    // Creates a new, empty, hash set.
    pub fn new() -> Self {
        HashSet {
            len: 0,
            slots: Vec::new(),
        }
    }

    // The number of items in the set.
    pub fn len(&mut self) -> usize {
        self.len
    }

    // Inserts a value into this hash set.
    //
    // If an equal value already exists, it will be replaced by
    // the new value. This is a non-op, unless the type can have,
    // different values which are equal to each other, which is
    // a hack but might let us build HashMap on top of this.
    pub fn insert(&mut self, value: Value) {
        self.resize_if_neccessary(self.len + 1);
        self.do_insert(value);
    }

    // Actually inserts the value into the backing slot vec.
    fn do_insert(&mut self, value: Value) {
        let hash = self.hash(value);
        let mut index = hash % self.slots.len();

        loop {
            match &self.slots[index] {
                HashSetSlot::Empty => {
                    self.slots[index] = HashSetSlot::Value { value };
                },
                HashSetSlot::Value {
                    value: colliding_value,
                } => {
                    // copy value and drop the ref to slots
                    let colliding_value = *colliding_value;
                    // probe for next free index
                    let mut next = index;
                    while self.slots[next] != HashSetSlot::Empty {
                        next = (next + 1) % self.slots.len();
                    }
                    // put our value there
                    self.slots[next] = HashSetSlot::Value { value };
                    // and put a pointer to it here
                    self.slots[index] = HashSetSlot::CollidingValue {
                        value: colliding_value,
                        next,
                    };
                },
                HashSetSlot::CollidingValue {
                    value: _,
                    next,
                } => {
                    // follow the pointer
                    index = *next;
                    continue;
                },
                HashSetSlot::Tombstone { next } => {
                    self.slots[index] = HashSetSlot::CollidingValue { value, next: *next };
                },
            }
            break;
        }
    }

    // Checks whether a value is present in the HashSet.
    pub fn has(&self, value: Value) -> bool {
        false
    }

    // Resizes the underlying slot vec if neccessary.
    fn resize_if_neccessary(&mut self, target_len: usize) {
        let max_slots = target_len * Self::MAX_LOAD_RATIO;
        let min_slots = target_len * Self::MIN_LOAD_RATIO;
        let neccessary = self.slots.len() < min_slots || self.slots.len() > max_slots;
        if neccessary {
            let target_capacity = target_len * Self::TARGET_LOAD_RATIO;
            let mut new_slots = vec![HashSetSlot::Empty; target_capacity];
            swap(&mut new_slots, &mut self.slots);
            let old_slots = new_slots;
            for slot in old_slots {
                match slot {
                    HashSetSlot::Value { value } => self.do_insert(value),
                    HashSetSlot::CollidingValue { value, next } => self.do_insert(value),
                    HashSetSlot::Empty => {}
                    HashSetSlot::Tombstone { next } => {}
                }
            }
        }
    }

    // Hashes a value into an integer digest.
    pub fn hash(&self, value: Value) -> usize {
        // TODO: consider actually implementing a hash if you must
        value as usize
    }
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum HashSetSlot {
    // there is no value here
    Empty,
    // there is a value here, with no colliding values
    Value { value: Value },
    // there is a value here, but there is another value whose
    // hash collided with this one, which you may find at the
    // index specified by next.
    CollidingValue { value: Value, next: usize },
    // there is no value here, but there used to be, and a value
    // that was colliding with it may be found at the index
    // specified by next.
    Tombstone { next: usize },
}