Invercargill/src/lib/DataStructures/HashSet.vala

namespace Invercargill.DataStructures {

    public class HashSet<T> : Enumerable<T>, Lot<T>, ReadOnlyCollection<T>, ReadOnlySet<T>, Set<T> {

        private const uint BUCKET_TOMBSTONE = uint.MAX;
        private const uint BUCKET_EMPTY = 0;
        private uint[] buckets;
        private T[] items;
        private int n_items = 0;
        private int n_buckets = 16;
        private int n_collissions = 0;
        private int next_item_index = 0;
        private SafeReadFunc<T>? safe_read;
        private SafeWriteFunc<T>? safe_write;
        private HashDelegate<T> hash_func;
        private EqualityDelegate<T> equal_func;

        construct {
            setup();
        }

        public HashSet(HashDelegate<T>? value_hash_func = null, EqualityDelegate<T>? value_equal_func = null) {
            setup(value_hash_func, value_equal_func);
        }

        private void setup(HashDelegate<T>? value_hash_func = null, EqualityDelegate<T>? value_equal_func = null) {
            hash_func = value_hash_func ?? Operators.hash<T>();
            equal_func = value_equal_func ?? Operators.equality<T>();
            safe_read = get_safe_read_function_for<T>();
            safe_write = get_safe_write_function_for<T>();
            buckets = new uint[n_buckets];
            items = new T[n_buckets];

        }

        private T read_item(uint index) {
            if(safe_read != null){
                return safe_read(items, index);
            }
            return items[index];
        }

        private void write_item(uint index, T item) {
            if(safe_write != null) {
                safe_write(items, index, item);
                return;
            }
            items[index] = item;
        }

        private void ensure_room_for_items(int count) {
            if(items.length <= n_items + count) {
                items.resize(items.length * 2);
            }
        }

        private void ensure_room_for_bucket(uint index) {
            var target = buckets.length;
            while(target <= index) {
                target = buckets.length * 2;
            }
            if(target != buckets.length) {
                buckets.resize(target);
            }
        }

        private void double_buckets() {
            n_buckets *= 2;
            buckets = new uint[n_buckets];
            n_collissions = 0;

            for(var i = 0; i < n_items; i++) {
                var item = read_item(i);
                var bucket_index = bucket_for(item);
                while(buckets[bucket_index] != BUCKET_EMPTY) {
                    bucket_index++;
                    n_collissions++;
                    ensure_room_for_bucket(bucket_index);
                }
                buckets[bucket_index] = i+1;
            }
            
        }

        private T get_item(uint index) {
            if(index == BUCKET_EMPTY || index == BUCKET_TOMBSTONE) {
                assert_not_reached();
            }
            return read_item(index-1);
        }

        private uint add_item(T item) {
            ensure_room_for_items(1);
            write_item(next_item_index, item);
            n_items++;
            next_item_index++;
            return n_items;
        }

        private uint bucket_for(T item) {
            var hash = hash_func(item);
            return hash % n_buckets;
        }

        public override int? peek_count() {
            return n_items;
        }

        public override EnumerableInfo get_info() {
            return new EnumerableInfo.infer_ultimate (this, EnumerableCategory.IN_MEMORY);
        }

        public override Tracker<T> get_tracker () {
            return range(0, buckets.length)
                .where(i => buckets[i] != BUCKET_EMPTY && buckets[i] != BUCKET_TOMBSTONE)
                .select<T>(i => get_item(buckets[i]))
                .get_tracker();
        }

        public bool add (T item) {
            return add_internal(item, false);
        }

        public new void @set(T item) {
            add_internal(item, true);
        }

        private bool add_internal (T item, bool overwrite) {
            if(n_collissions > n_buckets / 4) {
                double_buckets();
            }
            
            var bucket_index = bucket_for(item);
            while(buckets[bucket_index] != BUCKET_EMPTY && buckets[bucket_index] != BUCKET_TOMBSTONE) {
                if(equal_func(get_item(buckets[bucket_index]), item)) {
                    if(overwrite)
                        write_item(buckets[bucket_index] - 1, item);
                    return overwrite;
                }
                bucket_index++;
                n_collissions++;
                ensure_room_for_bucket(bucket_index);
            }
            
            buckets[bucket_index] = add_item(item);
            return true;
        }

        public bool try_find(T search, out T item) {
            var bucket_index = bucket_for(search);
            while(bucket_index < buckets.length && buckets[bucket_index] != BUCKET_EMPTY) {
                if(buckets[bucket_index] != BUCKET_TOMBSTONE) {
                    var ours = get_item(buckets[bucket_index]);
                    if(equal_func(ours, search)) {
                        item = ours;
                        return true;
                    }
                }
                bucket_index++;
            }
            item = null;
            return false;
        }

        public void remove_first_where (Invercargill.PredicateDelegate<T> predicate) {
            remove(first_or_default(predicate));
        }

        public void remove_all_where (Invercargill.PredicateDelegate<T> predicate) {
            except_with(where(predicate));
        }

        public bool has(T item) {
            T? _;
            return try_find(item, out _);
        }

        public void clear() {
            n_items = 0;
            n_buckets = 16;
            n_collissions = 0;
            buckets = new uint[n_buckets];
            items = new T[n_buckets];
        }

        public T? remove(T item) {
            var bucket_index = bucket_for(item);
            while(bucket_index < buckets.length && buckets[bucket_index] != BUCKET_EMPTY) {
                if(buckets[bucket_index] != BUCKET_TOMBSTONE) {
                    var ours = get_item(buckets[bucket_index]);
                    if(equal_func(ours, item)) {
                        write_item(buckets[bucket_index] - 1, null);
                        buckets[bucket_index] = BUCKET_TOMBSTONE;
                        n_items--;
                        return ours;
                    }
                    else {
                    }
                }
                bucket_index++;
            }
            return null;
        }

        public bool equals(Enumerable<T> other) {
            if(other == this) {
                return true;
            }
            return other.non_common(this, hash_func, equal_func).count() == 0;
        }
        public bool is_subset_of(Enumerable<T> other) {
            return this.exclude(other, hash_func, equal_func).count() == 0;
        }

    }
}