View Javadoc

1   package org.apache.commons.graph.model;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *   http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import static java.lang.String.format;
23  import static java.util.Collections.unmodifiableList;
24  
25  import java.util.LinkedList;
26  import java.util.List;
27  
28  import org.apache.commons.graph.Vertex;
29  import org.apache.commons.graph.WeightedEdge;
30  import org.apache.commons.graph.WeightedPath;
31  
32  /**
33   * Support {@link WeightedPath} implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path
34   * traversing the predecessor list bottom-up.
35   *
36   * @param <V> the Graph vertices type
37   * @param <WE> the Graph weighted edges type
38   */
39  public final class InMemoryPath<V extends Vertex, WE extends WeightedEdge<V>>
40      implements WeightedPath<V, WE>
41  {
42  
43      private final V source;
44  
45      private final V target;
46  
47      private final Double weigth;
48  
49      private final LinkedList<V> vertices = new LinkedList<V>();
50  
51      private final LinkedList<WE> edges = new LinkedList<WE>();
52  
53      public InMemoryPath( V start, V end, Double weigth )
54      {
55          this.source = start;
56          this.target = end;
57          this.weigth = weigth;
58      }
59  
60      /**
61       * {@inheritDoc}
62       */
63      public V getSource()
64      {
65          return source;
66      }
67  
68      /**
69       * {@inheritDoc}
70       */
71      public V getTarget()
72      {
73          return target;
74      }
75  
76      public void addVertexInHead( V vertex )
77      {
78          vertices.addFirst( vertex );
79      }
80  
81      public void addVertexInTail( V vertex )
82      {
83          vertices.addLast( vertex );
84      }
85  
86      /**
87       * {@inheritDoc}
88       */
89      public List<V> getVertices()
90      {
91          return unmodifiableList( vertices );
92      }
93  
94      public void addEdgeInHead( WE edge )
95      {
96          edges.addFirst( edge );
97      }
98  
99      public void addEdgeInTail( WE edge )
100     {
101         edges.addLast( edge );
102     }
103 
104     /**
105      * {@inheritDoc}
106      */
107     public List<WE> getEdges()
108     {
109         return unmodifiableList( edges );
110     }
111 
112     /**
113      * {@inheritDoc}
114      */
115     public int size()
116     {
117         return vertices.size();
118     }
119 
120     /**
121      * {@inheritDoc}
122      */
123     public Double getWeight()
124     {
125         return weigth;
126     }
127 
128     /**
129      * {@inheritDoc}
130      */
131     @Override
132     public int hashCode()
133     {
134         final int prime = 31;
135         int result = 1;
136         result = prime * result + ( ( edges == null ) ? 0 : edges.hashCode() );
137         result = prime * result + ( ( source == null ) ? 0 : source.hashCode() );
138         result = prime * result + ( ( target == null ) ? 0 : target.hashCode() );
139         result = prime * result + ( ( vertices == null ) ? 0 : vertices.hashCode() );
140         result = prime * result + ( ( weigth == null ) ? 0 : weigth.hashCode() );
141         return result;
142     }
143 
144     /**
145      * {@inheritDoc}
146      */
147     @Override
148     public boolean equals( Object obj )
149     {
150         if ( this == obj )
151         {
152             return true;
153         }
154 
155         if ( obj == null )
156         {
157             return false;
158         }
159 
160         if ( getClass() != obj.getClass() )
161         {
162             return false;
163         }
164 
165         InMemoryPath other = (InMemoryPath) obj;
166         if ( !source.equals( other.getSource() ) )
167         {
168             return false;
169         }
170 
171         if ( !target.equals( other.target ) )
172         {
173             return false;
174         }
175 
176         if ( !vertices.equals( other.vertices ) )
177         {
178             return false;
179         }
180 
181         if ( !edges.equals( other.getEdges() ) )
182         {
183             return false;
184         }
185 
186         if ( !weigth.equals( other.weigth ) )
187         {
188             return false;
189         }
190 
191         return true;
192     }
193 
194     /**
195      * {@inheritDoc}
196      */
197     @Override
198     public String toString()
199     {
200         return format( "InMemoryPath [weigth=%s, vertices=%s, edges=%s]", weigth, vertices, edges );
201     }
202 
203 }