Invercargill/src/lib/Collections/Set.vala

using Invercargill.Convert;

namespace Invercargill {

    public class Set<T> : Collection<T> {

        private Vector<T> items;
        private Vector<Series<int>> buckets;
        private HashDelegate<T> hash_func;
        private EqualityDelegate<T> equal_func;

        construct {
            setup();
        }

        public Set(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>();
            items = new Vector<T>();
            buckets = new Vector<Series<int>>();
            buckets.add_all(range(0, 4096).select<Series<int>>(i => new Series<int>()));
        }


        public override Tracker<T> get_tracker () {
            return items.get_tracker();
        }

        public override void add (T item) {
            var index = (int)bucket_for(item);
            var bucket = buckets.get_or_default(index);
            if(bucket != null && bucket.any(i => equal_func(i, item)))
                return;

            if(bucket == null) {
                bucket = new Series<int>();
                buckets[index] = bucket;
            }

            var item_index = items.count();
            items.add(item);
            bucket.add(item_index);
        }

        public override void add_all (Enumerable<T> items) {
            items.iterate(add);
        }

        public Set<T> union(Enumerable<T> items) {
            var new_set = to_set (hash_func, equal_func);
            new_set.add_all (items);
            return new_set;
        }

        public Set<T> difference(Enumerable<T> items) {
            var new_set = to_set (hash_func, equal_func);
            new_set.remove_all(items);
            return new_set;
        }

        public Set<T> intersection(Enumerable<T> items) {
            var new_set = to_set (hash_func, equal_func);
            new_set.remove_except(items);
            return new_set;
        }

        public new T? find(T item) {
            var bucket = buckets.get_or_default((int)bucket_for(item));
            if(bucket == null) 
                return null;

            foreach (var index in bucket) {
                var result = items[index];
                if(equal_func(result, item)) {
                    return result;
                }
            }
            return null;
        }

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

        public override void remove_where (Invercargill.PredicateDelegate<T> predicate) {
            items.where(predicate).iterate(remove);
        }

        public void remove(T item) {
            var bucket = buckets.get_or_default((int)bucket_for(item));
            if(bucket == null) 
                return;

            foreach (var index in bucket) {
                var result = items[index];
                if(equal_func(result, item)) {
                    bucket.remove_first_where(i => i == index);
                    items.remove(index);
                }
            }
        }

        public void remove_all(Enumerable<T> items) {
            items.iterate(remove);
        }

        public void remove_except(Enumerable<T> items) {
            var other = items.to_set(hash_func, equal_func);
            remove_where(i => !other.has(i));
        }

        public bool has(T item) {
            var bucket = buckets.get_or_default((int)bucket_for(item));
            return bucket != null && bucket.any(i => equal_func(i, item));
        }

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

    }
}