Java example source code file (AdjacencyList.java)

This example Java source code file (AdjacencyList.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

adjacencylist, arraylist, buildstep, iterator, linkedlist, list, override, stringbuilder, util, vertex

The AdjacencyList.java Java example source code

/*
 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
package sun.security.provider.certpath;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * An AdjacencyList is used to store the history of certification paths
 * attempted in constructing a path from an initiator to a target. The
 * AdjacencyList is initialized with a <code>List of
 * <code>Lists, where each sub-List contains objects of
 * type <code>Vertex. A Vertex describes one possible or
 * actual step in the chain building process, and the associated
 * <code>Certificate. Specifically, a Vertex object
 * contains a <code>Certificate and an index value referencing the
 * next sub-list in the process. If the index value is -1 then this
 * <code>Vertex doesn't continue the attempted build path.
 * <p>
 * Example:
 * <p>
 * Attempted Paths:<ul>
 * <li>C1->C2->C3
 * <li>C1->C4->C5
 * <li>C1->C4->C6
 * <li>C1->C4->C7
 * <li>C1->C8->C9
 * <li>C1->C10->C11
 * </ul>
 * <p>
 * AdjacencyList structure:<ul>
 * <li>AL[0] = C1,1
 * <li>AL[1] = C2,2   =>C4,3   =>C8,4     =>C10,5
 * <li>AL[2] = C3,-1
 * <li>AL[3] = C5,-1  =>C6,-1  =>C7,-1
 * <li>AL[4] = C9,-1
 * <li>AL[5] = C11,-1
 * </ul>
 * <p>
 * The iterator method returns objects of type <code>BuildStep, not
 * objects of type <code>Vertex.
 * A <code>BuildStep contains a Vertex and a result code,
 * accessible via getResult method. There are five result values.
 * <code>POSSIBLE denotes that the current step represents a
 * <code>Certificate that the builder is considering at this point in
 * the build. <code>FOLLOW denotes a Certificate (one of
 * those noted as <code>POSSIBLE) that the builder is using to try
 * extending the chain. <code>BACK represents that a
 * <code>FOLLOW was incorrect, and is being removed from the chain.
 * There is exactly one <code>FOLLOW for each BACK. The
 * values <code>SUCCEED and FAIL mean that we've come to
 * the end of the build process, and there will not be any more entries in
 * the list.
 * <p>
 * @see sun.security.provider.certpath.BuildStep
 * @see sun.security.provider.certpath.Vertex
 * <p>
 * @author  seth proctor
 * @since   1.4
 */
public class AdjacencyList {

    // the actual set of steps the AdjacencyList represents
    private ArrayList<BuildStep> mStepList;

    // the original list, just for the toString method
    private List<List mOrigList;

    /**
     * Constructs a new <code>AdjacencyList based on the specified
     * <code>List. See the example above.
     *
     * @param list a <code>List of Lists of
     *             <code>Vertex objects
     */
    public AdjacencyList(List<List list) {
        mStepList = new ArrayList<BuildStep>();
        mOrigList = list;
        buildList(list, 0, null);
    }

    /**
     * Gets an <code>Iterator to iterate over the set of
     * <code>BuildSteps in build-order. Any attempts to change
     * the list through the remove method will fail.
     *
     * @return an <code>Iterator over the BuildSteps
     */
    public Iterator<BuildStep> iterator() {
        return Collections.unmodifiableList(mStepList).iterator();
    }

    /**
     * Recursive, private method which actually builds the step list from
     * the given adjacency list. <code>Follow is the parent BuildStep
     * that we followed to get here, and if it's null, it means that we're
     * at the start.
     */
    private boolean buildList(List<List theList, int index,
                              BuildStep follow) {

        // Each time this method is called, we're examining a new list
        // from the global list. So, we have to start by getting the list
        // that contains the set of Vertexes we're considering.
        List<Vertex> l = theList.get(index);

        // we're interested in the case where all indexes are -1...
        boolean allNegOne = true;
        // ...and in the case where every entry has a Throwable
        boolean allXcps = true;

        for (Vertex v : l) {
            if (v.getIndex() != -1) {
                // count an empty list the same as an index of -1...this
                // is to patch a bug somewhere in the builder
                if (theList.get(v.getIndex()).size() != 0)
                    allNegOne = false;
            } else {
                if (v.getThrowable() == null)
                    allXcps = false;
            }
            // every entry, regardless of the final use for it, is always
            // entered as a possible step before we take any actions
            mStepList.add(new BuildStep(v, BuildStep.POSSIBLE));
        }

        if (allNegOne) {
            // There are two cases that we could be looking at here. We
            // may need to back up, or the build may have succeeded at
            // this point. This is based on whether or not any
            // exceptions were found in the list.
            if (allXcps) {
                // we need to go back...see if this is the last one
                if (follow == null)
                    mStepList.add(new BuildStep(null, BuildStep.FAIL));
                else
                    mStepList.add(new BuildStep(follow.getVertex(),
                                                BuildStep.BACK));

                return false;
            } else {
                // we succeeded...now the only question is which is the
                // successful step? If there's only one entry without
                // a throwable, then that's the successful step. Otherwise,
                // we'll have to make some guesses...
                List<Vertex> possibles = new ArrayList<>();
                for (Vertex v : l) {
                    if (v.getThrowable() == null)
                        possibles.add(v);
                }

                if (possibles.size() == 1) {
                    // real easy...we've found the final Vertex
                    mStepList.add(new BuildStep(possibles.get(0),
                                                BuildStep.SUCCEED));
                } else {
                    // ok...at this point, there is more than one Cert
                    // which might be the succeed step...how do we know
                    // which it is? I'm going to assume that our builder
                    // algorithm is good enough to know which is the
                    // correct one, and put it first...but a FIXME goes
                    // here anyway, and we should be comparing to the
                    // target/initiator Cert...
                    mStepList.add(new BuildStep(possibles.get(0),
                                                BuildStep.SUCCEED));
                }

                return true;
            }
        } else {
            // There's at least one thing that we can try before we give
            // up and go back. Run through the list now, and enter a new
            // BuildStep for each path that we try to follow. If none of
            // the paths we try produce a successful end, we're going to
            // have to back out ourselves.
            boolean success = false;

            for (Vertex v : l) {

                // Note that we'll only find a SUCCEED case when we're
                // looking at the last possible path, so we don't need to
                // consider success in the while loop

                if (v.getIndex() != -1) {
                    if (theList.get(v.getIndex()).size() != 0) {
                        // If the entry we're looking at doesn't have an
                        // index of -1, and doesn't lead to an empty list,
                        // then it's something we follow!
                        BuildStep bs = new BuildStep(v, BuildStep.FOLLOW);
                        mStepList.add(bs);
                        success = buildList(theList, v.getIndex(), bs);
                    }
                }
            }

            if (success) {
                // We're already finished!
                return true;
            } else {
                // We failed, and we've exhausted all the paths that we
                // could take. The only choice is to back ourselves out.
                if (follow == null)
                    mStepList.add(new BuildStep(null, BuildStep.FAIL));
                else
                    mStepList.add(new BuildStep(follow.getVertex(),
                                                BuildStep.BACK));

                return false;
            }
        }
    }

    /**
     * Prints out a string representation of this AdjacencyList.
     *
     * @return String representation
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[\n");

        int i = 0;
        for (List<Vertex> l : mOrigList) {
            sb.append("LinkedList[").append(i++).append("]:\n");

            for (Vertex step : l) {
                sb.append(step.toString()).append("\n");
            }
        }
        sb.append("]\n");

        return sb.toString();
    }
}