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 }