duke@1: /*
ohair@554: * Copyright (c) 2002, 2003, Oracle and/or its affiliates. All rights reserved.
duke@1: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1: *
duke@1: * This code is free software; you can redistribute it and/or modify it
duke@1: * under the terms of the GNU General Public License version 2 only, as
duke@1: * published by the Free Software Foundation.
duke@1: *
duke@1: * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1: * version 2 for more details (a copy is included in the LICENSE file that
duke@1: * accompanied this code).
duke@1: *
duke@1: * You should have received a copy of the GNU General Public License version
duke@1: * 2 along with this work; if not, write to the Free Software Foundation,
duke@1: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1: *
ohair@554: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554: * or visit www.oracle.com if you need additional information or have any
ohair@554: * questions.
duke@1: */
duke@1:
duke@1: class List {
duke@1:
duke@1: /** The first element of the list, supposed to be immutable.
duke@1: */
duke@1: public A head;
duke@1:
duke@1: /** The remainder of the list except for its first element, supposed
duke@1: * to be immutable.
duke@1: */
duke@1: public List tail;
duke@1:
duke@1: /** Construct a list given its head and tail.
duke@1: */
duke@1: public List(A head, List tail) {
duke@1: this.tail = tail;
duke@1: this.head = head;
duke@1: }
duke@1:
duke@1: /** Construct an empty list.
duke@1: */
duke@1: public List() {
duke@1: this(null, null);
duke@1: }
duke@1:
duke@1: /** Construct a list consisting of given element.
duke@1: */
duke@1: public static List make(A x1) {
duke@1: return new List(x1, new List());
duke@1: }
duke@1:
duke@1: /** Construct a list consisting of given elements.
duke@1: */
duke@1: public static List make(A x1, A x2) {
duke@1: return new List(x1, new List(x2, new List()));
duke@1: }
duke@1:
duke@1: /** Construct a list consisting of given elements.
duke@1: */
duke@1: public static List make(A x1, A x2, A x3) {
duke@1: return new List(x1, new List(x2, new List(x3, new List())));
duke@1: }
duke@1:
duke@1: /** Construct a list consisting all elements of given array.
duke@1: */
duke@1: public static List make(A[] vec) {
duke@1: List xs = new List();
duke@1: for (int i = vec.length - 1; i >= 0; i--)
duke@1: xs = new List(vec[i], xs);
duke@1: return xs;
duke@1: }
duke@1:
duke@1: /** Construct a list consisting of a given number of identical elements.
duke@1: * @param len The number of elements in the list.
duke@1: * @param init The value of each element.
duke@1: */
duke@1: public static List make(int len, A init) {
duke@1: List l = new List();
duke@1: for (int i = 0; i < len; i++) l = new List(init, l);
duke@1: return l;
duke@1: }
duke@1:
duke@1: /** Does list have no elements?
duke@1: */
duke@1: public boolean isEmpty() {
duke@1: return tail == null;
duke@1: }
duke@1:
duke@1: /** Does list have elements?
duke@1: */
duke@1: public boolean nonEmpty() {
duke@1: return tail != null;
duke@1: }
duke@1:
duke@1: /** Return the number of elements in this list.
duke@1: */
duke@1: public int length() {
duke@1: List l = this;
duke@1: int len = 0;
duke@1: while (l.tail != null) {
duke@1: l = l.tail;
duke@1: len++;
duke@1: }
duke@1: return len;
duke@1: }
duke@1:
duke@1: /** Prepend given element to front of list, forming and returning
duke@1: * a new list.
duke@1: */
duke@1: public List prepend(A x) {
duke@1: return new List(x, this);
duke@1: }
duke@1:
duke@1: /** Prepend given list of elements to front of list, forming and returning
duke@1: * a new list.
duke@1: */
duke@1: public List prependList(List xs) {
duke@1: if (this.isEmpty()) return xs;
duke@1: else if (xs.isEmpty()) return this;
duke@1: else return this.prependList(xs.tail).prepend(xs.head);
duke@1: }
duke@1:
duke@1: /** Reverse list, forming and returning a new list.
duke@1: */
duke@1: public List reverse() {
duke@1: List rev = new List();
duke@1: for (List l = this; l.nonEmpty(); l = l.tail)
duke@1: rev = new List(l.head, rev);
duke@1: return rev;
duke@1: }
duke@1:
duke@1: /** Append given element at length, forming and returning
duke@1: * a new list.
duke@1: */
duke@1: public List append(A x) {
duke@1: return make(x).prependList(this);
duke@1: }
duke@1:
duke@1: /** Append given list at length, forming and returning
duke@1: * a new list.
duke@1: */
duke@1: public List appendList(List x) {
duke@1: return x.prependList(this);
duke@1: }
duke@1:
duke@1: /** Copy successive elements of this list into given vector until
duke@1: * list is exhausted or end of vector is reached.
duke@1: */
duke@1: public A[] toArray(A[] vec) {
duke@1: int i = 0;
duke@1: List l = this;
duke@1: while (l.nonEmpty() && i < vec.length) {
duke@1: vec[i] = l.head;
duke@1: l = l.tail;
duke@1: i++;
duke@1: }
duke@1: return vec;
duke@1: }
duke@1:
duke@1: /** Form a string listing all elements with given separator character.
duke@1: */
duke@1: public String toString(String sep) {
duke@1: if (isEmpty()) {
duke@1: return "";
duke@1: } else {
duke@1: StringBuffer buf = new StringBuffer();
duke@1: buf.append(((Object)head).toString());
duke@1: for (List l = tail; l.nonEmpty(); l = l.tail) {
duke@1: buf.append(sep);
duke@1: buf.append(((Object)l.head).toString());
duke@1: }
duke@1: return buf.toString();
duke@1: }
duke@1: }
duke@1:
duke@1: /** Form a string listing all elements with comma as the separator character.
duke@1: */
duke@1: public String toString() {
duke@1: return toString(",");
duke@1: }
duke@1:
duke@1: /** Compute a hash code, overrides Object
duke@1: */
duke@1: public int hashCode() {
duke@1: List l = this;
duke@1: int h = 0;
duke@1: while (l.tail != null) {
duke@1: h = h * 41 + (head != null ? head.hashCode() : 0);
duke@1: l = l.tail;
duke@1: }
duke@1: return h;
duke@1: }
duke@1:
duke@1: /** Is this list the same as other list?
duke@1: */
duke@1: public boolean equals(Object other) {
duke@1: return other instanceof List && equals(this, (List)other);
duke@1: }
duke@1:
duke@1: /** Are the two lists the same?
duke@1: */
duke@1: public static boolean equals(List xs, List ys) {
duke@1: while (xs.tail != null && ys.tail != null) {
duke@1: if (xs.head == null) {
duke@1: if (ys.head != null) return false;
duke@1: } else {
duke@1: if (!xs.head.equals(ys.head)) return false;
duke@1: }
duke@1: xs = xs.tail;
duke@1: ys = ys.tail;
duke@1: }
duke@1: return xs.tail == null && ys.tail == null;
duke@1: }
duke@1:
duke@1: /** Does the list contain the specified element?
duke@1: */
duke@1: public boolean contains(A x) {
duke@1: List l = this;
duke@1: while (l.tail != null) {
duke@1: if (x == null) {
duke@1: if (l.head == null) return true;
duke@1: } else {
duke@1: if (x.equals(l.head)) return true;
duke@1: }
duke@1: l = l.tail;
duke@1: }
duke@1: return false;
duke@1: }
duke@1:
duke@1: }