001/* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2008-2012 SonarSource 004 * mailto:contact AT sonarsource DOT com 005 * 006 * Sonar is free software; you can redistribute it and/or 007 * modify it under the terms of the GNU Lesser General Public 008 * License as published by the Free Software Foundation; either 009 * version 3 of the License, or (at your option) any later version. 010 * 011 * Sonar is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 * Lesser General Public License for more details. 015 * 016 * You should have received a copy of the GNU Lesser General Public 017 * License along with Sonar; if not, write to the Free Software 018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 019 */ 020package org.sonar.graph; 021 022import java.util.Collection; 023import java.util.Collections; 024import java.util.Set; 025 026public class Dsm<V> { 027 028 private V[] vertices; 029 private DsmCell[][] cells; 030 private int dimension; 031 private DirectedGraphAccessor<V, ? extends Edge<V>> graph; 032 033 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> graph, Collection<V> vertices, Set<Edge> feedbackEdges) { 034 this.graph = graph; 035 this.dimension = vertices.size(); 036 this.cells = new DsmCell[dimension][dimension]; 037 initVertices(vertices); 038 initCells(feedbackEdges); 039 } 040 041 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph, Set<Edge> feedbackEdges) { 042 this(acyclicGraph, acyclicGraph.getVertices(), feedbackEdges); 043 } 044 045 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph) { 046 this(acyclicGraph, acyclicGraph.getVertices(), Collections.<Edge>emptySet()); 047 } 048 049 private void initCells(Set<Edge> feedbackEdges) { 050 for (int x = 0; x < dimension; x++) { 051 for (int y = 0; y < dimension; y++) { 052 V from = vertices[x]; 053 V to = vertices[y]; 054 055 Edge<V> edge = graph.getEdge(from, to); 056 boolean isFeedbackEdge = (edge != null && feedbackEdges.contains(edge)); 057 DsmCell cell = new DsmCell(edge, isFeedbackEdge); 058 cells[x][y] = cell; 059 } 060 } 061 } 062 063 private void initVertices(Collection<V> verticesCol) { 064 this.vertices = (V[]) new Object[dimension]; 065 int i = 0; 066 for (V vertex : verticesCol) { 067 vertices[i] = vertex; 068 i++; 069 } 070 } 071 072 public V getVertex(int rowIndex) { 073 return vertices[rowIndex]; 074 } 075 076 public int getDimension() { 077 return dimension; 078 } 079 080 public void permute(int fromIndex, int toIndex) { 081 if (fromIndex != toIndex) { 082 checkIndicesBoudaries(fromIndex, toIndex); 083 permuteVertice(fromIndex, toIndex); 084 permuteColumns(fromIndex, toIndex); 085 permuteRows(fromIndex, toIndex); 086 } 087 } 088 089 private void checkIndicesBoudaries(int... indices) { 090 for (int index : indices) { 091 if (index < 0 || index >= dimension) { 092 StringBuilder builder = new StringBuilder("DSM contains the following vertices : "); 093 for (V vertex : vertices) { 094 builder.append(vertex.toString()).append(" | "); 095 } 096 builder.append(". Trying to reach index ").append(index); 097 throw new ArrayIndexOutOfBoundsException(builder.toString()); 098 } 099 } 100 } 101 102 private void permuteVertice(int fromIndex, int toIndex) { 103 V fromVertex = vertices[fromIndex]; 104 V toVertex = vertices[toIndex]; 105 vertices[fromIndex] = toVertex; 106 vertices[toIndex] = fromVertex; 107 } 108 109 private void permuteRows(int fromYIndex, int toYIndex) { 110 for (int x = 0; x < dimension; x++) { 111 permuteCells(x, fromYIndex, x, toYIndex); 112 } 113 } 114 115 private void permuteColumns(int fromXIndex, int toXIndex) { 116 for (int y = 0; y < dimension; y++) { 117 permuteCells(fromXIndex, y, toXIndex, y); 118 } 119 } 120 121 private void permuteCells(int fromXIndex, int fromYIndex, int toXIndex, int toYIndex) { 122 DsmCell fromCell = cells[fromXIndex][fromYIndex]; 123 DsmCell toCell = cells[toXIndex][toYIndex]; 124 cells[toXIndex][toYIndex] = fromCell; 125 cells[fromXIndex][fromYIndex] = toCell; 126 } 127 128 public int getNumberOfIncomingEdges(int y, int from, int to) { 129 int incomingEdges = 0; 130 for (int x = from; x <= to; x++) { 131 DsmCell cell = cells[x][y]; 132 if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) { 133 incomingEdges++; 134 } 135 } 136 return incomingEdges; 137 } 138 139 public int getNumberOfOutgoingEdges(int x, int from, int to) { 140 int outgoingEdges = 0; 141 for (int y = from; y <= to; y++) { 142 DsmCell cell = cells[x][y]; 143 if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) { 144 outgoingEdges++; 145 } 146 } 147 return outgoingEdges; 148 } 149 150 public DsmCell getCell(int x, int y) { 151 return cells[x][y]; 152 } 153 154 public V[] getVertices() { 155 V[] verticesCopy = (V[]) new Object[vertices.length]; 156 System.arraycopy(vertices, 0, verticesCopy, 0, vertices.length); 157 return verticesCopy; 158 } 159}