Invercargill/src/lib/DataStructures/HashSet.vala

namespace Invercargill.DataStructures {

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

        [Compact]
        private class HashSetItem<T> {
            public uint hash;
            public T item;
        }

        private HashSetItem<T>* tombstone;
        private HashSetItem<T>*[] buckets;
        private uint n_items = 0;
        private uint n_buckets = 16;
        private uint n_collissions = 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) {
            tombstone = new HashSetItem<T>();
            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 HashSetItem<T>[n_buckets];

        }

        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;
            var old_buckets = buckets;
            buckets = new HashSetItem<T>*[n_buckets];
            n_collissions = 0;

            for(uint i = 0; i < old_buckets.length; i++) {
                var bucket = old_buckets[i];
                if(bucket == null || bucket == tombstone) {
                    continue;
                }

                var bucket_index = bucket->hash % n_buckets;
                while(buckets[bucket_index] != null) {
                    bucket_index++;
                    n_collissions++;
                    ensure_room_for_bucket(bucket_index);
                }

                buckets[bucket_index] = bucket;
            }
        }

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

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

        public override uint length { get { return n_items; }}

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

        public override Tracker<T> get_tracker () {
            return Iterate.range(0, (int)n_buckets)
                .where(i => buckets[i] != null && buckets[i] != tombstone)
                .select<T>(i => buckets[i]->item)
                .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 (owned T item, bool overwrite) {
            if(n_collissions > n_buckets / 4) {
                double_buckets();
            }
            
            var bucket_hash = hash_func(item);
            var bucket_index = bucket_hash % n_buckets;
            var bucket = buckets[bucket_index];
            while(bucket != null && bucket != tombstone) {
                if(bucket->hash == bucket_hash && equal_func(bucket->item, item)) {
                    if(overwrite)
                        bucket->item = (owned)item;
                    return overwrite;
                }
                bucket_index++;
                n_collissions++;
                ensure_room_for_bucket(bucket_index);
                bucket = buckets[bucket_index];
            }
            
            HashSetItem<T>* new_bucket = new HashSetItem<T>();
            new_bucket->hash = bucket_hash;
            new_bucket->item = (owned)item;
            buckets[bucket_index] = new_bucket;
            n_items++;
            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] != null) {
                if(buckets[bucket_index] != tombstone) {
                    var ours = buckets[bucket_index]->item;
                    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 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;
        }

        public T? remove(T item) {
            var bucket_index = bucket_for(item);
            while(bucket_index < buckets.length && buckets[bucket_index] != null) {
                if(buckets[bucket_index] != tombstone) {
                    var ours = buckets[bucket_index]->item;
                    if(equal_func(ours, item)) {
                        delete buckets[bucket_index];
                        buckets[bucket_index] = tombstone;
                        n_items--;
                        return ours;
                    }
                }
                bucket_index++;
            }
            return null;
        }

        public void clear() {
            n_items = 0;
            n_buckets = 16;
            n_collissions = 0;
            delete_items();
            buckets = new HashSetItem<T>*[n_buckets];
        }

        private void delete_items() {
            for(uint i = 0; i < buckets.length; i++) {
                if(buckets[i] != null && buckets[i] != tombstone)
                delete buckets[i];
            }
        }

        ~HashSet() {
            delete_items();
            delete tombstone;
        }



    }
}