list.java

GJC（Generic Java Compiler）编译器

/**
 * @(#)List.java	1.17 03/01/23
 *
 * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.sun.tools.javac.v8.util;

/**
 * A class for generic linked lists. Links are supposed to be
 *  immutable, the only exception being the incremental construction of
 *  lists via ListBuffers.  List is the main container class in
 *  GJC. Most data structures and algorthms in GJC use lists rather
 *  than arrays.
 *
 *  Lists are always trailed by a sentinel element, whose head and tail
 *  are both null.
 */
public final class List {

    /**
     * The first element of the list, supposed to be immutable.
     */
    public Object head;

    /**
     * The remainder of the list except for its first element, supposed
     *  to be immutable.
     */
    public List tail;

    /**
     * Construct a list given its head and tail.
     */
    public List(Object head, List tail) {
        super();
        this.tail = tail;
        this.head = head;
    }

    /**
      * Construct an empty list.
      */
    public List() {
        this(null, null);
    }

    /**
      * Construct an empty list.
      */
    public static List make() {
        return new List();
    }

    /**
      * Construct a list consisting of given element.
      */
    public static List make(Object x1) {
        return new List(x1, new List());
    }

    /**
      * Construct a list consisting of given elements.
      */
    public static List make(Object x1, Object x2) {
        return new List(x1, new List(x2, new List()));
    }

    /**
      * Construct a list consisting of given elements.
      */
    public static List make(Object x1, Object x2, Object x3) {
        return new List(x1, new List(x2, new List(x3, new List())));
    }

    /**
      * Construct a list consisting all elements of given array.
      */
    public static List make(Object[] vec) {
        List xs = new List();
        for (int i = vec.length - 1; i >= 0; i--)
            xs = new List(vec[i], xs);
        return xs;
    }

    /**
      * Construct a list consisting of a given number of identical elements.
      *  @param len    The number of elements in the list.
      *  @param init   The value of each element.
      */
    public static List make(int len, Object init) {
        List l = new List();
        for (int i = 0; i < len; i++)
            l = new List(init, l);
        return l;
    }

    /**
      * Does list have no elements?
      */
    public boolean isEmpty() {
        return tail == null;
    }

    /**
      * Does list have elements?
      */
    public boolean nonEmpty() {
        return tail != null;
    }

    /**
      * Return the number of elements in this list.
      */
    public int length() {
        List l = this;
        int len = 0;
        while (l.tail != null) {
            l = l.tail;
            len++;
        }
        return len;
    }

    /**
      * Prepend given element to front of list, forming and returning
      *  a new list.
      */
    public List prepend(Object x) {
        return new List(x, this);
    }

    /**
      * Prepend given list of elements to front of list, forming and returning
      *  a new list.
      */
    public List prependList(List xs) {
        if (this.isEmpty())
            return xs;
        if (xs.isEmpty())
            return this;
        List result = this;
        xs = xs.reverse();
        while (xs.nonEmpty()) {
            List h = xs;
            xs = xs.tail;
            h.tail = result;
            result = h;
        }
        return result;
    }

    /**
      * Reverse list, forming and returning a new list.
      */
    public List reverse() {
        List rev = new List();
        for (List l = this; l.nonEmpty(); l = l.tail)
            rev = new List(l.head, rev);
        return rev;
    }

    /**
      * Append given element at length, forming and returning
      *  a new list.
      */
    public List append(Object x) {
        return make(x).prependList(this);
    }

    /**
      * Append given list at length, forming and returning
      *  a new list.
      */
    public List appendList(List x) {
        return x.prependList(this);
    }

    /**
      * Copy successive elements of this list into given vector until
      *  list is exhausted or end of vector is reached.
      */
    public Object[] toArray(Object[] vec) {
        int i = 0;
        List l = this;
        while (l.nonEmpty() && i < vec.length) {
            vec[i] = l.head;
            l = l.tail;
            i++;
        }
        return vec;
    }

    /**
      * Form a string listing all elements with given separator character.
      */
    public String toString(String sep) {
        if (isEmpty()) {
            return "";
        } else {
            StringBuffer buf = new StringBuffer();
            buf.append(((Object) head).toString());
            for (List l = tail; l.nonEmpty(); l = l.tail) {
                buf.append(sep);
                buf.append(((Object) l.head).toString());
            }
            return buf.toString();
        }
    }

    /**
      * Form a string listing all elements with comma as the separator character.
      */
    public String toString() {
        return toString(",");
    }

    /**
      * Compute a hash code, overrides Object
      */
    public int hashCode() {
        List l = this;
        int h = 0;
        while (l.tail != null) {
            h = h * 41 + (head != null ? head.hashCode() : 0);
            l = l.tail;
        }
        return h;
    }

    /**
      * Is this list the same as other list?
      */
    public boolean equals(Object other) {
        return other instanceof List && equals(this, (List) other);
    }

    /**
      * Are the two lists the same?
      */
    public static boolean equals(List xs, List ys) {
        while (xs.tail != null && ys.tail != null) {
            if (xs.head == null) {
                if (ys.head != null)
                    return false;
            } else {
                if (!xs.head.equals(ys.head))
                    return false;
            }
            xs = xs.tail;
            ys = ys.tail;
        }
        return xs.tail == null && ys.tail == null;
    }

    /**
      * Does the list contain the specified element?
      */
    public boolean contains(Object x) {
        List l = this;
        while (l.tail != null) {
            if (x == null) {
                if (l.head == null)
                    return true;
            } else {
                if (x.equals(l.head))
                    return true;
            }
            l = l.tail;
        }
        return false;
    }

    /**
      * The last element in the list, if any, or null.
      */
    public Object last() {
        Object last = null;
        List t = this;
        while (t.tail != null) {
            last = t.head;
            t = t.tail;
        }
        return last;
    }
}