1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
/* ____ ____ ____ ____ ______ *\
** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala **
** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, 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));
}
}
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);
}
}
|
