std/set.zc

Rama main · réplica de lectura del repositorio original.

import "./option.zc"
import "./hash.zc"

import "./mem.zc"

struct Set<T> {
    data: T*;
    occupied: bool*;
    deleted: bool*;
    len: usize;
    cap: usize;
}

impl Set<T> {
    /// Creates a new, empty Set.
    fn new() -> Set<T> {
        return Set<T> { data: 0, occupied: 0, deleted: 0, len: 0, cap: 0 };
    }

    fn _resize(self, new_cap: usize) {
        let old_data = self.data;
        let old_occupied = self.occupied;
        let old_deleted = self.deleted;
        let old_cap = self.cap;

        self.cap = new_cap;
        self.data = alloc_n<T>(new_cap);
        self.occupied = alloc_n<bool>(new_cap);
        self.deleted = alloc_n<bool>(new_cap);
        memset(self.data, 0, new_cap * sizeof(T));
        memset(self.occupied, 0, new_cap * sizeof(bool));
        memset(self.deleted, 0, new_cap * sizeof(bool));
        self.len = 0;

        for (let i: usize = 0; i < old_cap; i = i + 1) {
            if (old_occupied[i] && !old_deleted[i]) {
                self.add(old_data[i]);
            }
        }

        if (old_data != NULL) { dealloc<T>(old_data); }
        if (old_occupied != NULL) { dealloc<bool>(old_occupied); }
        if (old_deleted != NULL) { dealloc<bool>(old_deleted); }
    }

    /// Inserts a value; returns whether it was new.
    fn add(self, val: T) -> bool {
        if (self.contains(val)) {
            return false;
        }

        if (self.len >= self.cap * 0.75) {
            let new_cap = self.cap * 2;
            if (new_cap < 8) new_cap = 8;
            self._resize(new_cap);
        }

        let hash = hash_compute(&val, sizeof(T));
        let idx = hash % self.cap;

        while (self.occupied[idx] && !self.deleted[idx]) {
            idx = (idx + 1) % self.cap;
        }

        self.data[idx] = val;
        self.occupied[idx] = true;
        self.deleted[idx] = false;
        self.len = self.len + 1;
        return true;
    }

    /// Returns whether the value is present.
    fn contains(self, val: T) -> bool {
        if (self.cap == 0) {
            return false;
        }

        let hash = hash_compute(&val, sizeof(T));
        let idx = hash % self.cap;
        let start_idx = idx;

        while (self.occupied[idx]) {
            if (!self.deleted[idx] && self.data[idx] == val) {
                return true;
            }

            idx = (idx + 1) % self.cap;
            if (idx == start_idx) {
                return false;
            }
        }
        return false;
    }

    /// Removes a value; returns whether it was present.
    fn remove(self, val: T) -> bool {
        if (self.cap == 0) return false;

        let hash = hash_compute(&val, sizeof(T));
        let idx = hash % self.cap;
        let start_idx = idx;

        while (self.occupied[idx]) {
            if (!self.deleted[idx] && self.data[idx] == val) {
                self.deleted[idx] = true;
                self.len = self.len - 1;
                return true;
            }

            idx = (idx + 1) % self.cap;
            if (idx == start_idx) return false;
        }
        return false;
    }

    /// Returns the number of items.
    fn length(self) -> usize {
        return self.len;
    }

    /// Returns whether the set is empty.
    fn is_empty(self) -> bool {
        return self.len == 0;
    }

    /// Frees the backing storage.
    fn free(self) {
        if (self.data) {
            dealloc<T>(self.data);
            dealloc<bool>(self.occupied);
            dealloc<bool>(self.deleted);
        }
        self.data = 0;
        self.occupied = 0;
        self.deleted = 0;
        self.len = 0;
        self.cap = 0;
    }

    fn capacity(self) -> usize {
        return self.cap;
    }

    fn is_slot_occupied(self, idx: usize) -> bool {
        if (idx >= self.cap) return false;
        return self.occupied[idx] && !self.deleted[idx];
    }

    fn val_at(self, idx: usize) -> Option<T> {
        if (idx >= self.cap || !self.occupied[idx] || self.deleted[idx]) {
            return Option<T>::None();
        }
        return Option<T>::Some(self.data[idx]);
    }
    /// Removes all items.
    fn clear(self) {
        for (let i: usize = 0; i < self.cap; i = i + 1) {
            self.occupied[i] = false;
            self.deleted[i] = false;
        }
        self.len = 0;
    }
}

impl Drop for Set<T> {
    fn drop(self) {
        self.free();
    }
}