path: root/sources/scalac/symtab/SymSet.java

/*     ____ ____  ____ ____  ______                                     *\
**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002-2005, LAMP/EPFL         **
** /_____/\____/\___/\____/____/                                        **
\*                                                                      */

// $Id$

package scalac.symtab;

/** Sets of symbols, implemented as binary trees.
 */
public class SymSet {
    private SymSet l, r;
    private Symbol sym;

    public SymSet() {}

    private SymSet(Symbol sym, SymSet l, SymSet r) {
        this.sym = sym; this.l = l; this.r = r;
    }

    /** Union of this set and `{sym}'.
     */
    public SymSet incl(Symbol sym) {
        if (this == EMPTY) {
            return new SymSet(sym, EMPTY, EMPTY);
        } else if (sym == this.sym) {
            return this;
        } else if (less(sym, this.sym)) {
            return new SymSet(this.sym, l.incl(sym), r);
        } else {
            assert less(this.sym, sym);
            return new SymSet(this.sym, l, r.incl(sym));
        }
    }

    /** Remove the element <code>sym</code> from the symbol set
     */
    public SymSet excl(Symbol sym) {
        if (sym == this.sym) {
            if (l == EMPTY) return r;
            if (r == EMPTY) return l;
            SymSet m = r;
            if (m.l != EMPTY) {
                SymSet p;
                do {
                    p = m;
                    m = m.l;
                } while (m.l != EMPTY);
                p.l = m.r;
                m.r = r;
            }
            m.l = l;
            return m;
        } else if (less(sym, this.sym)) {
            return new SymSet(this.sym, l.excl(sym), r);
        } else {
            assert less(this.sym, sym);
            return new SymSet(this.sym, l, r.excl(sym));
        }
    }

    /** Is `sym' an element of this set?
     */
    public boolean contains(Symbol sym) {
        if (this == EMPTY) {
            return false;
        } else if (sym == this.sym) {
            return true;
        } else if (less(sym, this.sym)) {
            return l.contains(sym);
        } else {
            assert less(this.sym, sym);
            return r.contains(sym);
        }
    }

    /** The number of elements in ths set.
     */
    public int size() {
        if (this == EMPTY) {
            return 0;
        } else {
            return 1 + l.size() + r.size();
        }
    }

    /** Copy elements of this set into `ss', starting at index `from'.
     *  Return index one past last element copied.
     */
    public int copyToArray(Symbol[] ss, int from) {
        if (this == EMPTY) {
            return from;
        } else {
            from = l.copyToArray(ss, from);
            ss[from] = sym;
            return r.copyToArray(ss, from + 1);
        }
    }

    /** Return all elements of this set as an array.
     */
    public Symbol[] toArray() {
        int s = size();
        if (s == 0) return Symbol.EMPTY_ARRAY;
        Symbol[] ss = new Symbol[s];
        copyToArray(ss, 0);
        return ss;
    }

    /** The empty set.
     */
    public final static SymSet EMPTY = new SymSet();

    private boolean less(Symbol s1, Symbol s2) {
        return s1.isLess(s2);
    }
}