Mon, 26 Oct 2015 13:23:30 -0700
Added tag jdk8u76-b00 for changeset 10ffafaf5340
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 */
24 class List<A> {
26 /** The first element of the list, supposed to be immutable.
27 */
28 public A head;
30 /** The remainder of the list except for its first element, supposed
31 * to be immutable.
32 */
33 public List<A> tail;
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 }
42 /** Construct an empty list.
43 */
44 public List() {
45 this(null, null);
46 }
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 }
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 }
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 }
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 }
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 }
85 /** Does list have no elements?
86 */
87 public boolean isEmpty() {
88 return tail == null;
89 }
91 /** Does list have elements?
92 */
93 public boolean nonEmpty() {
94 return tail != null;
95 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
178 /** Form a string listing all elements with comma as the separator character.
179 */
180 public String toString() {
181 return toString(",");
182 }
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 }
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 }
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 }
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 }
232 }