|
1 /* |
|
2 * Copyright (c) 2002, 2003, Oracle and/or its affiliates. All rights reserved. |
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
4 * |
|
5 * This code is free software; you can redistribute it and/or modify it |
|
6 * under the terms of the GNU General Public License version 2 only, as |
|
7 * published by the Free Software Foundation. |
|
8 * |
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT |
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
12 * version 2 for more details (a copy is included in the LICENSE file that |
|
13 * accompanied this code). |
|
14 * |
|
15 * You should have received a copy of the GNU General Public License version |
|
16 * 2 along with this work; if not, write to the Free Software Foundation, |
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
18 * |
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
20 * or visit www.oracle.com if you need additional information or have any |
|
21 * questions. |
|
22 */ |
|
23 |
|
24 class List<A> { |
|
25 |
|
26 /** The first element of the list, supposed to be immutable. |
|
27 */ |
|
28 public A head; |
|
29 |
|
30 /** The remainder of the list except for its first element, supposed |
|
31 * to be immutable. |
|
32 */ |
|
33 public List<A> tail; |
|
34 |
|
35 /** Construct a list given its head and tail. |
|
36 */ |
|
37 public List(A head, List<A> tail) { |
|
38 this.tail = tail; |
|
39 this.head = head; |
|
40 } |
|
41 |
|
42 /** Construct an empty list. |
|
43 */ |
|
44 public List() { |
|
45 this(null, null); |
|
46 } |
|
47 |
|
48 /** Construct a list consisting of given element. |
|
49 */ |
|
50 public static <A> List<A> make(A x1) { |
|
51 return new List<A>(x1, new List<A>()); |
|
52 } |
|
53 |
|
54 /** Construct a list consisting of given elements. |
|
55 */ |
|
56 public static <A> List<A> make(A x1, A x2) { |
|
57 return new List<A>(x1, new List<A>(x2, new List<A>())); |
|
58 } |
|
59 |
|
60 /** Construct a list consisting of given elements. |
|
61 */ |
|
62 public static <A> List<A> make(A x1, A x2, A x3) { |
|
63 return new List<A>(x1, new List<A>(x2, new List<A>(x3, new List<A>()))); |
|
64 } |
|
65 |
|
66 /** Construct a list consisting all elements of given array. |
|
67 */ |
|
68 public static <A> List<A> make(A[] vec) { |
|
69 List<A> xs = new List<A>(); |
|
70 for (int i = vec.length - 1; i >= 0; i--) |
|
71 xs = new List<A>(vec[i], xs); |
|
72 return xs; |
|
73 } |
|
74 |
|
75 /** Construct a list consisting of a given number of identical elements. |
|
76 * @param len The number of elements in the list. |
|
77 * @param init The value of each element. |
|
78 */ |
|
79 public static <A> List<A> make(int len, A init) { |
|
80 List<A> l = new List<A>(); |
|
81 for (int i = 0; i < len; i++) l = new List<A>(init, l); |
|
82 return l; |
|
83 } |
|
84 |
|
85 /** Does list have no elements? |
|
86 */ |
|
87 public boolean isEmpty() { |
|
88 return tail == null; |
|
89 } |
|
90 |
|
91 /** Does list have elements? |
|
92 */ |
|
93 public boolean nonEmpty() { |
|
94 return tail != null; |
|
95 } |
|
96 |
|
97 /** Return the number of elements in this list. |
|
98 */ |
|
99 public int length() { |
|
100 List<A> l = this; |
|
101 int len = 0; |
|
102 while (l.tail != null) { |
|
103 l = l.tail; |
|
104 len++; |
|
105 } |
|
106 return len; |
|
107 } |
|
108 |
|
109 /** Prepend given element to front of list, forming and returning |
|
110 * a new list. |
|
111 */ |
|
112 public List<A> prepend(A x) { |
|
113 return new List<A>(x, this); |
|
114 } |
|
115 |
|
116 /** Prepend given list of elements to front of list, forming and returning |
|
117 * a new list. |
|
118 */ |
|
119 public List<A> prependList(List<A> xs) { |
|
120 if (this.isEmpty()) return xs; |
|
121 else if (xs.isEmpty()) return this; |
|
122 else return this.prependList(xs.tail).prepend(xs.head); |
|
123 } |
|
124 |
|
125 /** Reverse list, forming and returning a new list. |
|
126 */ |
|
127 public List<A> reverse() { |
|
128 List<A> rev = new List<A>(); |
|
129 for (List<A> l = this; l.nonEmpty(); l = l.tail) |
|
130 rev = new List<A>(l.head, rev); |
|
131 return rev; |
|
132 } |
|
133 |
|
134 /** Append given element at length, forming and returning |
|
135 * a new list. |
|
136 */ |
|
137 public List<A> append(A x) { |
|
138 return make(x).prependList(this); |
|
139 } |
|
140 |
|
141 /** Append given list at length, forming and returning |
|
142 * a new list. |
|
143 */ |
|
144 public List<A> appendList(List<A> x) { |
|
145 return x.prependList(this); |
|
146 } |
|
147 |
|
148 /** Copy successive elements of this list into given vector until |
|
149 * list is exhausted or end of vector is reached. |
|
150 */ |
|
151 public A[] toArray(A[] vec) { |
|
152 int i = 0; |
|
153 List<A> l = this; |
|
154 while (l.nonEmpty() && i < vec.length) { |
|
155 vec[i] = l.head; |
|
156 l = l.tail; |
|
157 i++; |
|
158 } |
|
159 return vec; |
|
160 } |
|
161 |
|
162 /** Form a string listing all elements with given separator character. |
|
163 */ |
|
164 public String toString(String sep) { |
|
165 if (isEmpty()) { |
|
166 return ""; |
|
167 } else { |
|
168 StringBuffer buf = new StringBuffer(); |
|
169 buf.append(((Object)head).toString()); |
|
170 for (List<A> l = tail; l.nonEmpty(); l = l.tail) { |
|
171 buf.append(sep); |
|
172 buf.append(((Object)l.head).toString()); |
|
173 } |
|
174 return buf.toString(); |
|
175 } |
|
176 } |
|
177 |
|
178 /** Form a string listing all elements with comma as the separator character. |
|
179 */ |
|
180 public String toString() { |
|
181 return toString(","); |
|
182 } |
|
183 |
|
184 /** Compute a hash code, overrides Object |
|
185 */ |
|
186 public int hashCode() { |
|
187 List<A> l = this; |
|
188 int h = 0; |
|
189 while (l.tail != null) { |
|
190 h = h * 41 + (head != null ? head.hashCode() : 0); |
|
191 l = l.tail; |
|
192 } |
|
193 return h; |
|
194 } |
|
195 |
|
196 /** Is this list the same as other list? |
|
197 */ |
|
198 public boolean equals(Object other) { |
|
199 return other instanceof List && equals(this, (List)other); |
|
200 } |
|
201 |
|
202 /** Are the two lists the same? |
|
203 */ |
|
204 public static boolean equals(List xs, List ys) { |
|
205 while (xs.tail != null && ys.tail != null) { |
|
206 if (xs.head == null) { |
|
207 if (ys.head != null) return false; |
|
208 } else { |
|
209 if (!xs.head.equals(ys.head)) return false; |
|
210 } |
|
211 xs = xs.tail; |
|
212 ys = ys.tail; |
|
213 } |
|
214 return xs.tail == null && ys.tail == null; |
|
215 } |
|
216 |
|
217 /** Does the list contain the specified element? |
|
218 */ |
|
219 public boolean contains(A x) { |
|
220 List<A> l = this; |
|
221 while (l.tail != null) { |
|
222 if (x == null) { |
|
223 if (l.head == null) return true; |
|
224 } else { |
|
225 if (x.equals(l.head)) return true; |
|
226 } |
|
227 l = l.tail; |
|
228 } |
|
229 return false; |
|
230 } |
|
231 |
|
232 } |