dijkstraqueue.java

来自「High performance DB query」· Java 代码 · 共 121 行

/*
 * @(#)$Id: DijkstraQueue.java,v 1.7 2004/07/02 23:59:22 huebsch Exp $
 *
 * Copyright (c) 2001-2004 Regents of the University of California.
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached BERKELEY-LICENSE
 * file. If you do not find these files, copies can be found by writing to:
 * Computer Science Division, Database Group, Universite of California,
 * 617 Soda Hall #1776, Berkeley, CA 94720-1776. Attention: Berkeley License
 *
 * Copyright (c) 2003-2004 Intel Corporation. All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE file.
 * If you do not find these files, copies can be found by writing to:
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300,
 * Berkeley, CA, 94704.  Attention:  Intel License Inquiry.
 */


package simulator.schedulers.network.topology.transitstub;

import java.util.ArrayList;
import java.util.TreeMap;
import org.apache.log4j.Logger;

/** Priority queue for Dijkstra */
public class DijkstraQueue {

    private static Logger logger = Logger.getLogger(DijkstraQueue.class);
    TreeMap queue;

    /**
     * Constructor DijkstraQueue
     */
    public DijkstraQueue() {
        queue = new TreeMap(new DijkstraComparator());
    }

    /**
     * Method isEmpty
     * @return
     */
    public boolean isEmpty() {
        return queue.size() == 0;
    }

    /**
     * Method getNext
     * @return
     */
    public DijkstraContainer getNext() {

        // return the smallest weight
        Integer integer = (Integer) queue.firstKey();
        ArrayList list = (ArrayList) queue.get(integer);
        DijkstraContainer dc = (DijkstraContainer) list.remove(0);

        if (list.size() == 0) {
            queue.remove(integer);
        }

        return dc;
    }

    /**
     * Method addElement
     *
     * @param dc
     */
    public void addElement(DijkstraContainer dc) {
        Integer integer = new Integer(dc.getCurrentWeight());

        if (queue.get(integer) != null) {
            ArrayList list = (ArrayList) queue.get(integer);

            list.add(dc);
        } else {
            ArrayList list = new ArrayList();

            list.add(dc);
            queue.put(integer, list);
        }
    }

    /**
     * Method changeElement
     *
     * @param dc
     * @param oldValue
     */
    public void changeElement(DijkstraContainer dc, int oldValue) {
        Integer oldValueInt = new Integer(oldValue);
        ArrayList removedList = (ArrayList) queue.get(oldValueInt);

        if (removedList == null) {
            logger.error("Error1. Cannot find " + dc + " Queue: " + queue);

            return;
        }

        boolean found = false;

        for (int k = 0; k < removedList.size(); k++) {
            DijkstraContainer curDC = (DijkstraContainer) removedList.get(k);

            if (curDC.vertex.equals(dc.getVertex())) {
                found = true;

                break;
            }
        }

        if (found == true) {
            addElement(dc);
        } else {
            logger.error("Error2. Cannot find " + dc + " " + queue);
        }
    }
}