/*

     This file is part of Combean.

     Combean is free software; you can redistribute it and/or modify

     it under the terms of the GNU General Public License as published by

     the Free Software Foundation; either version 2 of the License, or

     (at your option) any later version.

     Combean 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 for more details.

     You should have received a copy of the GNU General Public License

     along with Combean; if not, write to the Free Software

     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

 /*

  * Created on 06.01.2005

  *

  */

 package net.sourceforge.combean.samples.simplegraphs;

 import net.sourceforge.combean.graph.NodePairEdge;

 import net.sourceforge.combean.graph.NumberNode;

 import net.sourceforge.combean.interfaces.graph.Edge;

 import net.sourceforge.combean.interfaces.graph.EdgeIterator;

 import net.sourceforge.combean.interfaces.graph.Graph;

 import net.sourceforge.combean.interfaces.graph.Node;

 import net.sourceforge.combean.interfaces.graph.NodeIterator;

 import net.sourceforge.combean.interfaces.graph.prop.GlobalNumberedNodesGraphProp;

 import net.sourceforge.combean.interfaces.graph.prop.OutgoingEdgeNeighborhoodGraphProp;

 import net.sourceforge.combean.util.except.IllegalParameterException;

 /**

  * This class represents a graph where every node is identified by a long-value.

  * 

  * @author schickin

  *

  */

 public abstract class NumberGraph

   implements Graph,

              OutgoingEdgeNeighborhoodGraphProp,

              GlobalNumberedNodesGraphProp {

         /**

          * The number of the first node in the graph.

          */

         public static final int FIRSTNODE = 0;

         /**

          * The virtual node number if no such node exists.

          */

         public static final int NOSUCHNODE = -1;

         /**

          *

          */

         public NumberGraph() {

                 super();

         }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.Graph#getEdgeClass()

      */

     public Class getEdgeClass() {

         return NodePairEdge.class;

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.Graph#getNodeClass()

      */

     public Class getNodeClass() {

          return NumberNode.class;

     }

         /**

          * @see net.sourceforge.combean.interfaces.graph.prop.GlobalNodesGraphProp#getAllNodesIterator()

          */

         public NodeIterator getAllNodesIterator() {

                 return new NumberNodeIterator(FIRSTNODE, getNumNodes()-1);

         }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.GlobalIndexedNodesGraphProp#getNode(int)

      */

     public Node getNode(int index) {

         if (index < 0 || index >= getNumNodes()) {

             throw new IllegalParameterException(

                     "node index out of bounds. " +

                     "must be in interval [0..number of nodes-1]");

         }

          return new NumberNode(index);

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.prop.GlobalNumberedNodesGraphProp#getNodeNumber(net.sourceforge.combean.interfaces.graph.Node)

      */

     public int getNodeNumber(Node v) {

          return ((NumberNode) v).getNodeNum();

     }

     /**

          * Create a node in the graph.given its number

          * 

          * @param num the number of the node to be created

          * @return the node with the given number

          * or null if the node does not exist in the graph or num is NOSUCHNODE.

          */

         public final NumberNode convertNumToNode(int num) {

                 NumberNode result = new NumberNode(num);

                 if (!contains(result)) {

                         result = null;

                 }

                 return result;

         }

         public final EdgeIterator getIncidentEdges(Node v) {

                 return new NumberNeighborIterator(this, (NumberNode)v);

         }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.OutgoingEdgeNeighborhoodGraphProp#getOutgoingEdges()

      */

     public EdgeIterator getOutgoingEdges(Node v) {

          return getIncidentEdges(v);

     }

         public final Node getFirstNode(Edge e) {

                 NodePairEdge ep = (NodePairEdge) e;

                 return ep.getFirstNode();

         }

         public final Node getSecondNode(Edge e) {

                 NodePairEdge ep = (NodePairEdge) e;

                 return ep.getSecondNode();

         }

         public final Node getOtherNode(Edge e, Node v) {

                 NodePairEdge ep = (NodePairEdge) e;

                 if (ep.getFirstNode().equals(v)) {

                         return ep.getSecondNode();

                 }

                 return ep.getFirstNode();

         }

         /**

          * Helps NumberNodeIterators to calculate the next node when iterating

          * through neighbors.

          * 

          * @param startNode the start node of the NumberNeighborIterator

          * @param currNode the current node of the NumberNeighborIterator or null is this

          * is the first iteration

          * @return the next node of the NumberNeighborIterator or

          * NOSUCHNODE if no next node exists

          */

         protected int nextNode(NumberNode startNode, NumberNode currNode) {

                 if (empty() || !contains(startNode)) {

                         return NOSUCHNODE;

                 }

                 int currNodeNum = 0;

                 if (currNode != null) {

                         currNodeNum = currNode.getNodeNum()+1;

                 }

                 return calcNextNode(startNode.getNodeNum(), currNodeNum);

         }

         /**

          * Template method for calculating neighbors.

          * 

          * Calculates the smallest number >= minNodeNum of a node in the neighborhood of

          * the node with the number sourceNumNode or NOSUCHNODE if no next node exists.

          * It is guaranteed that the graph in non-empty and that the node number startNodeNum

          * is contained in the graph.

          * Note that minNodeNum may also be negative.

          * 

          * @param sourceNodeNum

          * @param minNodeNum

          * @return the next node in the neighborhood of the given node

          * @see net.sourceforge.combean.samples.simplegraphs.NumberGraph#nextNode(NumberNode, NumberNode)

          */

         protected abstract int calcNextNode(int sourceNodeNum, int minNodeNum);

         /**

          * Check whether a given node is contained in the graph.

          * 

          * @param v the node to be checked

          * @return true if v is contained in the graph

          */

         public final boolean contains(NumberNode v) {

                 return FIRSTNODE <= v.getNodeNum() &&

                   v.getNodeNum() < getNumNodes();

         }

         /**

          * Check if the graph is empty.

          * 

          * @return true if the graph does not contain any node.

          */

         public final boolean empty() {

                 return getNumNodes() == 0;

         }

 }