//============================================================================
// aaset.d - a set class based on D's associative arrays
//
// Description: 
//   This is a set class implemented using associative arrays.
//   The value is ignored and only the key is used.
//
// Author:  William V. Baxter III
// Created: 14 Aug 2007
// Written in the D Programming Language (http://www.digitalmars.com/d)
//============================================================================
// $Id:$
//============================================================================

module aa_set;

import strlib = std.string;

class Set(T)
{
private:
    bool[T] elems_; // not a real set, just uses AA to map T->bool the value of the bool
                    // doesn't matter
public:
    this() {}
    this(Set init) { 
        //elems_ = init.elems_.dup;  ack!  doesn't work
        this.update(init);
    }
    this(T[] init) { 
        this.update(init);
    }
    Set dup() {
        return new Set(this);
    }

    void add(T el) {
        elems_[el] = true;
    }

    /// Remove element if it exsits, ignore if it doesn't
    void remove(T el) {
        elems_.remove(el);
    }

    ///  Remove element if it exists, throw ArrayBoundsError if it doesn't
    void drop(T el) {
        bool maybethrow = elems_[el]; // throws exception for non-existing elements.
        elems_.remove(el);
    }

    /// Update set with the union of itself and another 
    void update(OtherType)(OtherType other) {
        foreach(el; other) { elems_[el]=true; }
    }

    /// Update set with the difference of itself and another 
    /// (Remove all elements in other from itself
    void difference_update(OtherType)(OtherType other) {
        foreach(el; other) { 
            elems_.remove(el);
        }
    }

    /// Update set with the intersection of itself and another 
    /// Remove elements from set that are not in other
    void intersection_update(OtherType)(OtherType other) {
        bool[T] newelems;
        foreach(el; elems_) {
            // dont' think it's ok to remove elements in the middle
            // of iterating, so do adds to a freshy instead.
            if (el in other) {
                newelems[el] = true;
            }
        }
        elems_ = newelems;
    }

    // Return the symmetric difference of two sets as a new set.
    // (i.e. all elements that are in exactly one of the sets.)
    void symmetric_difference_update(OtherType)(OtherType other) {
        auto tmp = new Set(other);
        auto clone = this.dup;
        // remove your values from me
        this.difference_update(tmp);
        // remove my values from you
        tmp.difference_update(clone);
        // union what's left
        this.update(tmp);
    }
    void clear() {
        elems_ = elems_.init;
    }
    size_t length() {
        return elems_.length;
    }
    T[] tolist() {
        return elems_.keys;
    }
    bool opIn_r(T el) {
        return (el in elems_) != null;
    }
    int opEquals(Set!(T) other) {
        // This operation is slow because we don't have a good way to
        // iterate in sorted order over the keys in an AA.
        foreach(el; this) {
            if (!(el in other)) {
                return false;
            }
        }
        foreach(el; other) {
            if (!(el in this)) {
                return false;
            }
        }
        return true;
    }
    int opApply(int delegate(inout T) dg) {
        foreach(el, ref _v; elems_) {
            int ret = dg(el);
            if (ret) return ret;
        }
        return 0;
    }
    int opApplyReverse(int delegate(inout T) dg) {
        foreach(el, ref _v; elems_) {
            int ret = dg(el);
            if (ret) return ret;
        }
        return 0;
    }
    void opCatAssign(T el) {
        add(el);
    }
    char[] toString() {
        return strlib.format(elems_);
    }
    alias toString toUtf8;
}



//--- Emacs setup ---
// Local Variables:
// c-basic-offset: 4
// indent-tabs-mode: nil
// End: