001 package org.apache.commons.graph.model;
002
003 /*
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements. See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership. The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License. You may obtain a copy of the License at
011 *
012 * http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing,
015 * software distributed under the License is distributed on an
016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017 * KIND, either express or implied. See the License for the
018 * specific language governing permissions and limitations
019 * under the License.
020 */
021
022 import static java.lang.String.format;
023 import static java.util.Collections.unmodifiableList;
024
025 import java.util.LinkedList;
026 import java.util.List;
027
028 import org.apache.commons.graph.Vertex;
029 import org.apache.commons.graph.WeightedEdge;
030 import org.apache.commons.graph.WeightedPath;
031
032 /**
033 * Support {@link WeightedPath} implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path
034 * traversing the predecessor list bottom-up.
035 *
036 * @param <V> the Graph vertices type
037 * @param <WE> the Graph weighted edges type
038 */
039 public final class InMemoryPath<V extends Vertex, WE extends WeightedEdge<V>>
040 implements WeightedPath<V, WE>
041 {
042
043 private final V source;
044
045 private final V target;
046
047 private final Double weigth;
048
049 private final LinkedList<V> vertices = new LinkedList<V>();
050
051 private final LinkedList<WE> edges = new LinkedList<WE>();
052
053 public InMemoryPath( V start, V end, Double weigth )
054 {
055 this.source = start;
056 this.target = end;
057 this.weigth = weigth;
058 }
059
060 /**
061 * {@inheritDoc}
062 */
063 public V getSource()
064 {
065 return source;
066 }
067
068 /**
069 * {@inheritDoc}
070 */
071 public V getTarget()
072 {
073 return target;
074 }
075
076 public void addVertexInHead( V vertex )
077 {
078 vertices.addFirst( vertex );
079 }
080
081 public void addVertexInTail( V vertex )
082 {
083 vertices.addLast( vertex );
084 }
085
086 /**
087 * {@inheritDoc}
088 */
089 public List<V> getVertices()
090 {
091 return unmodifiableList( vertices );
092 }
093
094 public void addEdgeInHead( WE edge )
095 {
096 edges.addFirst( edge );
097 }
098
099 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 }