001: package jsint;
002:
003: /** A Pair has two fields, first and rest (sometimes called car and cdr).
004: * The empty list is represented as a Pair, with both fields empty.
005: * (In Scheme it is an error to ask access those fields, but we don't complain.)
006: * @author Peter Norvig, Copyright 1998, peter@norvig.com, <a href="license.txt">license</a>
007: * subsequently modified by Jscheme project members
008: * licensed under zlib licence (see license.txt)
009: **/
010:
011: public class Pair implements java.io.Serializable, jscheme.SchemePair {
012:
013: /** The first element of the pair. **/
014: public Object first;
015:
016: /** The other element of the pair. **/
017: public Object rest;
018:
019: /** The empty list. It's first and rest fields are also EMPTY. **/
020: public static final Pair EMPTY = new Pair(null, null);
021:
022: static {
023: EMPTY.first = EMPTY.rest = EMPTY;
024: }
025:
026: /** Build a pair from two components. **/
027: public Pair(Object first, Object rest) {
028: this .first = first;
029: this .rest = rest;
030: }
031:
032: /** Return the first element of a list. **/
033: public Object getFirst() {
034: return first;
035: }
036:
037: /** Return the second element of a list. **/
038: public Object getRest() {
039: return rest;
040: }
041:
042: /** Set the first element of a list. **/
043: public Object setFirst(Object x) {
044: Object y = first;
045: this .first = x;
046: return y;
047: }
048:
049: /** Return the second element of a list. **/
050: public Object setRest(Object x) {
051: Object y = rest;
052: this .rest = x;
053: return y;
054: }
055:
056: /** Return the second element of a list. **/
057: public Object first() {
058: return first;
059: }
060:
061: /** Return the second element of a list. **/
062: public Object rest() {
063: return rest;
064: }
065:
066: /** Return the second element of a list. **/
067: public Object second() {
068: return U.toPair(rest).first;
069: }
070:
071: /** Return the third element of a list. **/
072: public Object third() {
073: return U.second(rest);
074: }
075:
076: /** Reverse the elements of a list. **/
077: public Object reverse() {
078: Object result = Pair.EMPTY;
079: Pair list = this ;
080: while (list != EMPTY) {
081: if (Scheme.isInterruptable())
082: Scheme.interruptCheck();
083: result = new Pair(list.first, result);
084: list = U.toList(list.rest);
085: }
086: return result;
087: }
088:
089: /** Lists that are .equals have the same .hashCode(). **/
090: public int hashCode() {
091: if (this == EMPTY)
092: return super .hashCode();
093: else {
094: int head = hashCode0(this .first);
095: int tail = hashCode0(this .rest);
096: return head + tail * 37;
097: }
098: }
099:
100: private static int hashCode0(Object it) {
101: if (it == null)
102: return 17;
103: else if (it instanceof Object[])
104: return arrayHashCode((Object[]) it);
105: else
106: return it.hashCode();
107: }
108:
109: private static int arrayHashCode(Object[] xs) {
110: int code = 0;
111: for (int i = 0; i < xs.length; i++)
112: code = code + xs[i].hashCode() * 37;
113: return code;
114: }
115:
116: /** Two pairs are equal if their first and rest fields are (equal?). **/
117: public boolean equals(Object that) {
118: if (this == that)
119: return true;
120: else
121: return (that instanceof Pair) && (that != EMPTY)
122: && (this != EMPTY) && this .equalsFirst((Pair) that)
123: && U.equal(this .rest, ((Pair) that).rest);
124: }
125:
126: private boolean equalsFirst(Pair that) {
127: return (this .first == null) ? that.first == null : U.equal(
128: this .first, ((Pair) that).first);
129: }
130:
131: /** Return a String representation of the pair. **/
132: public String toString() {
133: if (this == EMPTY)
134: return "()";
135: else
136: return this .stringifyPair(true, new StringBuffer())
137: .toString();
138: }
139:
140: /** Build up a String representation of the Pair in a StringBuffer. **/
141: public StringBuffer stringifyPair(boolean quoted, StringBuffer buf) {
142: String special = null;
143: if ((U.isPair(rest)) && U.rest(rest) == EMPTY)
144: special = (first == Symbol.QUOTE) ? "'"
145: : (first == Symbol.QUASIQUOTE) ? "`"
146: : (first == Symbol.UNQUOTE) ? ","
147: : (first == Symbol.UNQUOTE_SPLICING) ? ",@"
148: : null;
149:
150: if (special != null) {
151: buf.append(special);
152: U.stringify(U.second(this ), quoted, buf);
153: } else {
154: buf.append('(');
155: U.stringify(first, quoted, buf);
156: Object tail = rest;
157: while (U.isPair(tail)) {
158: if (Scheme.isInterruptable())
159: Scheme.interruptCheck();
160: buf.append(' ');
161: U.stringify(((Pair) tail).first, quoted, buf);
162: tail = ((Pair) tail).rest;
163: }
164: if (tail != EMPTY) {
165: buf.append(" . ");
166: U.stringify(tail, quoted, buf);
167: }
168: buf.append(')');
169: }
170: return buf;
171: }
172:
173: /** The length of a proper list. **/
174: public int length() {
175: int len = 0;
176: Object list = this ;
177: while (U.isPair(list)) {
178: if (Scheme.isInterruptable())
179: Scheme.interruptCheck();
180: len++;
181: list = U.rest(list);
182: }
183: return len;
184: }
185:
186: /** Find the nth element of a list, zero-based **/
187: public Object nth(int n) {
188: return U.toPair(listTail(n)).first;
189: }
190:
191: /** Find the nth tail of a list, zero-based. **/
192: public Object listTail(int n) {
193: int orig = n;
194: Pair list = this ;
195: while (n > 0) {
196: n--;
197: if (list.isEmpty())
198: E
199: .error(
200: "attempting to compute listTail "
201: + orig
202: + " which is greater than the length of the list",
203: this );
204: else
205: list = U.toList(list.rest);
206: }
207: return list;
208: }
209:
210: public boolean isEmpty() {
211: return this == Pair.EMPTY;
212: }
213:
214: // COMPILER SUPPORT METHODS
215:
216: // // get an element or a tail of a list using "n/2" notation:
217: // public Object getEltNover2(int n) {
218: // if ((n % 2)== 0)
219: // return (this.listTail(n/2));
220: // return (this.nth(n/2));
221: // }
222: //
223: // // set an element of a list (using "n/2" notation)
224: // public Object setEltNover2(int n,Object v) {
225: // Object oldv;
226: // if ((n % 2)== 0) return E.error("Error in Compiler: setEltOver2 "+n);
227: // oldv = this.nth(n/2);
228: // ((Pair) this.listTail(n/2)).first = v;
229: // return (oldv);
230: // }
231:
232: public Object getEltNover2(int n) {
233: Pair t = this ;
234: while ((n > 1) && (t.rest != null)) {
235: t = ((Pair) t.rest);
236: n -= 2;
237: }
238: if (n == 0)
239: return t;
240: if (n == 1)
241: return (t.first);
242: else
243: return null;
244: }
245:
246: public Object setEltNover2(int n, Object v) {
247: Pair t = this ;
248: while ((n > 1) && (t.rest != null)) {
249: t = ((Pair) t.rest);
250: n -= 2;
251: }
252: if (n == 1)
253: return (t.first = v);
254: else {
255: E.warn("ERROR in setEltNover2");
256: return null;
257: }
258: }
259:
260: private Object readResolve() throws java.io.ObjectStreamException {
261: return this.first == this && this.rest == this ? EMPTY : this;
262: }
263: }
|