DoubleAdjacencyStringMatrix.java

/*
 * Created on 2004/02/04 Copyright (C)
 * 2004 Koga Laboratory. All rights
 * reserved.
 */
package org.mklab.tool.control.system;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import org.mklab.tool.control.system.graph.SparceStringMatrix;
import org.mklab.tool.control.system.sink.DoubleContinuousSink;
import org.mklab.tool.control.system.sink.DoubleOutputPort;
import org.mklab.tool.control.system.sink.Exporter;
import org.mklab.tool.control.system.source.DoubleContinuousSource;
import org.mklab.tool.control.system.source.DoubleGround;
import org.mklab.tool.control.system.source.DoubleInputPort;
import org.mklab.tool.control.system.source.Importer;


/**
 * ブロック線図(グラフ)の隣接関係を保持する文字列行列を表すクラスです。
 * 
 * @author Yusuke Tsutsui
 * @version $Revision: 1.52 $.
 */
public class DoubleAdjacencyStringMatrix {

  /** システムのタグ文字列(G1,G2,…)と実際のシステム(ControlSystem)を関連付けるマップ */
  private Map<String, DoubleSystemBuilder> csMap = new HashMap<>();

  /** sourceシステムの番号とそれが接続するノードの番号のマップ */
  private Map<Integer, Integer> sourceMap = new HashMap<>();

  /** inputポートの番号とそれが接続するノードの番号のマップ */
  private Map<Integer, Integer> inputMap = new HashMap<>();

  /** sinkシステムの番号とそれが接続するノードの番号のマップ */
  private Map<Integer, Integer> sinkMap = new HashMap<>();

  /** outputポートの番号とそれが接続するノードの番号のマップ */
  private Map<Integer, Integer> outputMap = new HashMap<>();

  /** 多重器のマップ(出力ノード番号、入力ノード番号のリスト) */
  private Map<Integer, List<Integer>> muxMap = new HashMap<>();

  /** 分離器のマップ(入力ノード番号、出力ノード番号のリスト) */
  private Map<Integer, List<Integer>> demuxMap = new HashMap<>();

  /** 出力器のマップ(出力番号、出力器) */
  private Map<Integer, Exporter> exporterMap = new TreeMap<>();

  /** 入力器のマップ(入力番号、入力器) */
  private Map<Integer, Importer> importerMap = new TreeMap<>();

  // /** 乗除算器のマップ(出力ノード番号、入力ノード番号のリスト) */
  // private Map<Integer, List<Integer>> productMap = new HashMap<Integer, List<Integer>>();

  /** システムのID番号 */
  private int systemId = 1;

  /** 行列の成分を保持する文字列行列 */
  private SparceStringMatrix elements;

  /** ノードの次数 */
  private int[] nodeDegrees;

  /**
   * 大きさ<code>size</code>の隣接行列を生成します。
   * 
   * @param size 隣接行列のサイズ
   */
  public DoubleAdjacencyStringMatrix(final int size) {
    this.elements = new SparceStringMatrix(size, size);
    this.nodeDegrees = new int[size];
    for (int i = 0; i < size; i++) {
      this.nodeDegrees[i] = -1;
    }
  }

  /**
   * <code>inputNode</code>ノードと<code>outputNode</code>ノードの間にエッジ(重み({@link DoubleSystemBuilder}))を追加します。
   * 
   * <p>既に同じ位置にエッジが存在する場合は、重みが置き換えられます。
   * 
   * @param inputNode 入力ノード
   * @param outputNode 出力ノード
   * @param system 入力ノードと出力ノードの間のエッジの重み({@link DoubleSystemBuilder})
   */
  public void addEdge(final int inputNode, final int outputNode, final DoubleSystemBuilder system) {
    system.resetAutoSize();

    addEdge(inputNode, outputNode, "G" + this.systemId); //$NON-NLS-1$
    setControlSystem("G" + this.systemId, system); //$NON-NLS-1$
    this.systemId++;

    if (system.isAutoSize() == false && system.getInputSize() != -1 && inputNode != 1) {
      this.nodeDegrees[inputNode - 1] = system.getInputSize();
    }
    if (system.isAutoSize() == false && system.getOutputSize() != -1 && outputNode != this.nodeDegrees.length) {
      this.nodeDegrees[outputNode - 1] = system.getOutputSize();
    }

    setupNodeDegree();
  }

  /**
   * MOMOシステムを追加します。
   * 
   * @param inputNodes 入力ノードのリスト
   * @param outputNodes 出力ノードのリスト
   * @param system MIMOシステム
   */
  @SuppressWarnings("boxing")
  public void addMIMO(final List<Integer> inputNodes, final List<Integer> outputNodes, final DoubleSystemBuilder system) {
    for (final Integer inputNode : inputNodes) {
      if (inputNode == null) {
        continue;
      }
      for (final Integer outputNode : outputNodes) {
        if (outputNode == null) {
          continue;
        }

        if (hasEdge(inputNode, outputNode)) {
          return;
        }

        system.resetAutoSize();
        addEdge(inputNode, outputNode, "S" + this.systemId); //$NON-NLS-1$
        setControlSystem("S" + this.systemId, system); //$NON-NLS-1$
      }
    }

    this.systemId++;
  }

  /**
   * 指定したノードとノードの間にエッジがあるか判定します。
   * 
   * @param inputNode 入力ノード
   * @param outputNode 出力ノード
   * @return 指定したノードとノードの間にエッジがあればtrue、そうでなければfalse
   */
  public boolean hasEdge(final int inputNode, final int outputNode) {
    return this.elements.hasElement(inputNode, outputNode);
  }

  /**
   * <code>inputNode</code>ノードから<code>outputNode</code>ノードに単位エッジ(重み=Iまたは-I)を追加します。
   * 
   * @param inputNode 入力ノード
   * @param outputNode 出力ノード
   * @param positive 正入力かどうか(trueであれば正入力)
   */
  public void addUnitEdge(final int inputNode, final int outputNode, final boolean positive) {
    if (positive) {
      addEdge(inputNode, outputNode, "P"); //$NON-NLS-1$
    } else {
      addEdge(inputNode, outputNode, "N"); //$NON-NLS-1$
    }

    if (this.nodeDegrees[inputNode - 1] == -1 && this.nodeDegrees[outputNode - 1] != -1) {
      this.nodeDegrees[inputNode - 1] = this.nodeDegrees[outputNode - 1];
    }

    if (this.nodeDegrees[outputNode - 1] == -1 && this.nodeDegrees[inputNode - 1] != -1) {
      this.nodeDegrees[outputNode - 1] = this.nodeDegrees[inputNode - 1];
    }

    setupNodeDegree();
  }

  /**
   * <code>inputNodes</code>の各ノードから<code>outputNode</code>ノードへの多重器を追加します。
   * 
   * @param inputNodes 入力ノードのリスト
   * @param outputNode 出力ノード
   */
  @SuppressWarnings("boxing")
  public void addMultiplexer(final List<Integer> inputNodes, final int outputNode) {
    this.muxMap.put(outputNode, inputNodes);

    for (int i = 1; i <= inputNodes.size(); i++) {
      final Integer node = inputNodes.get(i - 1);
      if (node == null) {
        continue;
      }
      addEdge(node, outputNode, "M" + i + "/" + inputNodes.size()); //$NON-NLS-1$ //$NON-NLS-2$
    }

    int outputSize = 0;
    for (final Integer node : inputNodes) {
      if (node == null) {
        continue;
      }

      final int inputNode = node;
      if (this.nodeDegrees[inputNode - 1] == -1) {
        return;
      }

      outputSize += this.nodeDegrees[inputNode - 1];
    }

    this.nodeDegrees[outputNode - 1] = outputSize;

    setupNodeDegree();
  }

  /**
   * <code>inputNodes</code>の各ノードから<code>outputNode</code>ノードへの加算器を追加します。
   * 
   * @param inputNodes 入力ノードのリスト
   * @param outputNode 出力ノード
   * @param positives 正入力かどうか(正入力ならばtrue)
   */
  @SuppressWarnings("boxing")
  public void addSum(final List<Integer> inputNodes, final int outputNode, final List<Boolean> positives) {
    if (inputNodes.size() != positives.size()) {
      throw new IllegalArgumentException(Messages.getString("AdjacencyStringMatrix.8")); //$NON-NLS-1$
    }

    for (int i = 0; i < inputNodes.size(); i++) {
      final Integer node = inputNodes.get(i);
      if (node == null) {
        continue;
      }

      addUnitEdge(node, outputNode, positives.get(i));
    }
  }

  /**
   * 多重器の出力ノードの次数を設定します。
   * 
   * @return 新たに多重器の出力ノードの次数を設定したならばtrue、そうでなければfalse
   */
  @SuppressWarnings("boxing")
  private boolean setupMultiplexerNodeDegree() {
    boolean changed = false;

    outer:for (Integer node : this.muxMap.keySet()) {
      int outputNode = node;
      if (this.nodeDegrees[outputNode - 1] != -1) {
        continue;
      }

      final List<Integer> inputNodes = this.muxMap.get(outputNode);

      int outputSize = 0;
      for (final Integer inputNode : inputNodes) {
        if (inputNode == null) {
          continue;
        }
        if (this.nodeDegrees[inputNode - 1] == -1) {
          continue outer;
        }

        outputSize += this.nodeDegrees[inputNode - 1];
      }

      this.nodeDegrees[outputNode - 1] = outputSize;
      changed = true;
    }

    return changed;
  }

  /**
   * <code>inputNode</code>ノードから<code>outputNodes</code>の各ノードへの分離器を追加します。
   * 
   * @param inputNode 入力ノード
   * @param outputNodes 出力ノードのリスト
   */
  @SuppressWarnings("boxing")
  public void addDeMultiplexer(final int inputNode, final List<Integer> outputNodes) {
    this.demuxMap.put(inputNode, outputNodes);

    for (int i = 1; i <= outputNodes.size(); i++) {
      final Integer node = outputNodes.get(i - 1);
      if (node == null) {
        continue;
      }

      addEdge(inputNode, node, "D" + i + "/" + outputNodes.size()); //$NON-NLS-1$ //$NON-NLS-2$
    }

    int inputSize = 0;
    for (final Integer node : outputNodes) {
      if (node == null) {
        continue;
      }

      final int outputNode = node;
      if (this.nodeDegrees[outputNode - 1] == -1) {
        return;
      }

      inputSize += this.nodeDegrees[outputNode - 1];
    }

    this.nodeDegrees[inputNode - 1] = inputSize;

    setupNodeDegree();
  }

  /**
   * 分離器の入力ノードの次数を設定します。
   * 
   * @return 新たに分離器の入力ノードの次数を設定したならばtrue、そうでなければfalse
   */
  @SuppressWarnings("boxing")
  private boolean setupDeMultiplexerNodeDegree() {
    boolean changed = false;

    outer:for (final Integer node : this.demuxMap.keySet()) {
      if (node == null) {
        continue;
      }

      int inputNode = node;

      if (this.nodeDegrees[inputNode - 1] != -1) {
        continue;
      }

      final List<Integer> outputNodes = this.demuxMap.get(inputNode);

      int inputSize = 0;
      for (final Integer outputNode : outputNodes) {
        if (outputNode == null) {
          continue;
        }
        if (this.nodeDegrees[outputNode - 1] == -1) {
          continue outer;
        }

        inputSize += this.nodeDegrees[outputNode - 1];
      }

      this.nodeDegrees[inputNode - 1] = inputSize;
      changed = true;
    }

    return changed;
  }

  /**
   * sourceシステムを追加します。
   * 
   * @param inputNode sourceシステムを接続するノードの番号
   * @param controlSystem sourceシステム
   * @param sourceNumber sourceシステムの番号
   */
  @SuppressWarnings("boxing")
  public void addSource(final int inputNode, final DoubleSystemBuilder controlSystem, final int sourceNumber) {
    controlSystem.resetAutoSize();

    final DoubleSystemOperator system = controlSystem.getSystemOperator();

    if (system instanceof Importer) {
      this.importerMap.put(sourceNumber, (Importer)system);
    }

    if (system instanceof DoubleInputPort) {
      if (this.inputMap.containsKey(sourceNumber)) {
        throw new IllegalArgumentException(Messages.getString("AdjacencyStringMatrix.11")); //$NON-NLS-1$
      }

      this.inputMap.put(sourceNumber, inputNode);
      final String tag = "I" + sourceNumber; //$NON-NLS-1$
      addEdge(1, inputNode, tag);
      setControlSystem(tag, controlSystem);
    } else {
      this.sourceMap.put(sourceNumber, inputNode);
      addEdge(1, inputNode, controlSystem);
    }

    if (system instanceof DoubleContinuousSource) {
      final int outputSize = controlSystem.getOutputSize();
      if (((DoubleContinuousSource)system).isAutoSize() == false || outputSize != -1) {
        this.nodeDegrees[inputNode - 1] = outputSize;
        setupNodeDegree();
      }

      final int size = this.nodeDegrees[inputNode - 1];
      if (size != -1) {
        system.setOutputSize(size);
      }
    }
  }

  /**
   * Sinkシステムを追加します
   * 
   * @param outputNode Sinkシステムを接続するノードの番号
   * @param controlSystem Sinkシステム
   * @param sinkNumber Sinkの番号
   */
  @SuppressWarnings("boxing")
  public void addSink(final int outputNode, final DoubleSystemBuilder controlSystem, final int sinkNumber) {
    controlSystem.resetAutoSize();

    final DoubleSystemOperator system = controlSystem.getSystemOperator();

    if (system instanceof Exporter) {
      this.exporterMap.put(sinkNumber, (Exporter)system);
    }

    if (system instanceof DoubleOutputPort) {
      if (this.outputMap.containsKey(sinkNumber)) {
        throw new IllegalArgumentException(Messages.getString("AdjacencyStringMatrix.13")); //$NON-NLS-1$
      }

      this.outputMap.put(sinkNumber, outputNode);
      final String tag = "O" + sinkNumber; //$NON-NLS-1$
      addEdge(outputNode, this.size(), tag);
      setControlSystem(tag, controlSystem);
    } else {
      this.sinkMap.put(sinkNumber, outputNode);
      addEdge(outputNode, this.size(), controlSystem);
    }

    if (system instanceof DoubleContinuousSink) {
      final int inputSize = controlSystem.getInputSize();
      if (((DoubleContinuousSink)system).isAutoSize() == false || inputSize != -1) {
        this.nodeDegrees[outputNode - 1] = inputSize;
        setupNodeDegree();
      }

      final int size = this.nodeDegrees[outputNode - 1];
      if (size != -1) {
        system.setInputSize(size);
      }
    }
  }

  /**
   * ポート番号順にソートしたinputポートとsourceシステムが接続されたノードのリストを返します。
   * 
   * @return 「ポート番号順にソートしたinputポート」＋「sourceシステム」とが接続されたノードのリスト
   */
  @SuppressWarnings("boxing")
  public List<Integer> getSortedInputSourceNodes() {
    final List<Integer> inputSourceNodes = new ArrayList<>();

    final SortedMap<Integer, Integer> sortedInputMap = new TreeMap<>();
    for (final Integer key : this.inputMap.keySet()) {
      sortedInputMap.put(key, this.inputMap.get(key));
    }

    /** inputポートが接続れているノードのリスト */
    for (final Integer node : sortedInputMap.values()) {
      if (getControlSystem(getWeightOfEdge(1, node)).getSystemOperator() instanceof DoubleInputPort) {
        inputSourceNodes.add(node);
      }
    }

    final SortedMap<Integer, Integer> sortedSourceMap = new TreeMap<>();
    for (final Integer key : this.sourceMap.keySet()) {
      sortedSourceMap.put(key, this.sourceMap.get(key));
    }

    /** sourceが接続れているノードのリスト */
    for (final Integer node : sortedSourceMap.values()) {
      if (getControlSystem(getWeightOfEdge(1, node)).getSystemOperator() instanceof DoubleInputPort == false) {
        inputSourceNodes.add(node);
      }
    }
    return inputSourceNodes;
  }

  /**
   * ポート番号順にソートしたoutputポートとsinkシステムが接続されたノードのリストを返します。
   * 
   * @return 「sinkシステム」＋「ポート番号順にソートしたoutputポート」とが接続されたノードのリスト
   */
  @SuppressWarnings("boxing")
  public List<Integer> getSortedOutputSinkNodes() {
    final List<Integer> outputSinkNodes = new ArrayList<>();
    final int size = this.elements.getRowSize();

    final SortedMap<Integer, Integer> sortedSinkMap = new TreeMap<>();
    for (final Integer key : this.sinkMap.keySet()) {
      sortedSinkMap.put(key, this.sinkMap.get(key));
    }

    /** sinkが接続されているノードのリスト */
    for (final Integer node : sortedSinkMap.values()) {
      if (getControlSystem(getWeightOfEdge(node, size)).getSystemOperator() instanceof DoubleOutputPort == false) {
        outputSinkNodes.add(node);
      }
    }

    final SortedMap<Integer, Integer> sortedOutputMap = new TreeMap<>();
    for (final Integer key : this.outputMap.keySet()) {
      sortedOutputMap.put(key, this.outputMap.get(key));
    }

    /** outputポートが接続されているノードのリスト */
    for (final Integer node : sortedOutputMap.values()) {
      if (getControlSystem(getWeightOfEdge(node, size)).getSystemOperator() instanceof DoubleOutputPort) {
        outputSinkNodes.add(node);
      }
    }
    return outputSinkNodes;
  }

  /**
   * タグに対応するシステムを返します。
   * 
   * @param tag システムのタグ(G1,G2,...)
   * @return その文字列に対応する {@link DoubleSystemBuilder}
   */
  public DoubleSystemBuilder getControlSystem(final String tag) {
    return this.csMap.get(tag);
  }

  /**
   * エッジを追加(隣接行列の成分を設定)します。
   * 
   * @param inputNode 入力ノード
   * @param outputNode 出力ノード
   * @param weight エッジの重み
   */
  private void addEdge(final int inputNode, final int outputNode, final String weight) {
    this.elements.setElement(inputNode, outputNode, weight);
  }

  /**
   * システムのタグとシステムの対を登録します。
   * 
   * @param tag システムのタグ(G1,G2,...)
   * @param system そのタグに対応するシステム
   */
  private void setControlSystem(final String tag, final DoubleSystemBuilder system) {
    this.csMap.put(tag, system);
  }

  /**
   * エッジの重み(隣接行列の成分)を返します。
   * 
   * @param inputNode 入力ノード
   * @param outputNode 出力ノード
   * @return システムを表す文字列
   */
  public String getWeightOfEdge(final int inputNode, final int outputNode) {
    return this.elements.getElement(inputNode, outputNode);
  }

  /**
   * 隣接行列のサイズを返します。
   * 
   * @return 隣接行列のサイズ
   */
  public int size() {
    return this.elements.getColumnSize();
  }

  /**
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString() {
    return this.elements.toString();
  }

  /**
   * 行列を標準出力に出力します。
   */
  public void print() {
    this.elements.print();
  }

  /**
   * ノードの次数を返します。
   * 
   * @param nodeNumber ノードの番号
   * @return ノードの次数
   */
  public int getNodeDegree(final int nodeNumber) {
    return this.nodeDegrees[nodeNumber - 1];
  }

  /**
   * ノードの次数を設定します。
   * 
   * @param nodeNumber ノードの番号
   * @param degree ノードの次数
   */
  public void setNodeDegree(int nodeNumber, int degree) {
    this.nodeDegrees[nodeNumber - 1] = degree;
    setupNodeDegree();
  }

  /**
   * ノードの次数を設定します。
   */
  void setupNodeDegree() {
    boolean changed = false;

    do {
      changed = false;

      for (int row = 1; row <= this.size(); row++) {
        for (int column = 1; column <= this.size(); column++) {
          final String weight = this.elements.getElement(row, column);

          if (weight.length() == 0) {
            continue;
          }

          final DoubleSystemBuilder controlSystem = getControlSystem(weight);
          final DoubleSystemOperator system = controlSystem == null ? null : controlSystem.getSystemOperator();

          if (system != null) {
            if (this.nodeDegrees[row - 1] == -1 && this.nodeDegrees[column - 1] != -1) {
              if (system instanceof DoubleBlockSystem == false || ((DoubleBlockSystem)system).getOutputNodeSize() == 1) {
                system.setOutputSize(this.nodeDegrees[column - 1]);
                if (row != 1 && this.nodeDegrees[row - 1] == -1) {
                  final int inputSize = system.getInputSize();
                  if (inputSize != -1) {
                    changed = true;
                    this.nodeDegrees[row - 1] = inputSize;
                  }
                }
              }
            }

            if (this.nodeDegrees[column - 1] == -1 && this.nodeDegrees[row - 1] != -1) {
              if (system instanceof DoubleBlockSystem == false || ((DoubleBlockSystem)system).getInputNodeSize() == 1) {
                system.setInputSize(this.nodeDegrees[row - 1]);
                if (column != this.nodeDegrees.length && this.nodeDegrees[column - 1] == -1) {
                  final int outputSize = system.getOutputSize();
                  if (outputSize != -1) {
                    changed = true;
                    this.nodeDegrees[column - 1] = outputSize;
                  }
                }
              }
            }

            if (system instanceof DoubleGround && isConnectedToMultiplexer(column - 1)) {
              final int outputSize = system.getOutputSize();
              if (outputSize == -1) {
                changed = true;
                this.nodeDegrees[column - 1] = 0;
                system.setOutputSize(0);
              }
            }

          } else if (weight.equals("P") || weight.equals("N")) { //$NON-NLS-1$ //$NON-NLS-2$
            if (this.nodeDegrees[row - 1] == -1 && this.nodeDegrees[column - 1] != -1) {
              changed = true;
              this.nodeDegrees[row - 1] = this.nodeDegrees[column - 1];
            }

            if (this.nodeDegrees[column - 1] == -1 && this.nodeDegrees[row - 1] != -1) {
              changed = true;
              this.nodeDegrees[column - 1] = this.nodeDegrees[row - 1];
            }
          }
        }
      }

      if (setupMultiplexerNodeDegree()) {
        changed = true;
      }
      if (setupDeMultiplexerNodeDegree()) {
        changed = true;
      }

    } while (changed);

    setInputSizeAndOutputSize();
  }

  /**
   * 接続先が多重器であるか判定します。
   * 
   * @param node 接続先をしらべるノード
   * @return 接続先が多重器ならばtrue、そうでなければfalse
   */
  private boolean isConnectedToMultiplexer(final int node) {
    for (int column = 1; column <= this.size(); column++) {
      final String weight = this.elements.getElement(node + 1, column);
      if (weight.length() == 0) {
        continue;
      }

      if (weight.startsWith("M")) { //$NON-NLS-1$
        return true;
      }
    }

    return false;
  }

  /**
   * 入力数と出力数が未定のシステムの入出力数を設定します。
   */
  private void setInputSizeAndOutputSize() {
    final int size = this.size();

    for (int row = 1; row <= size; row++) {
      for (int column = 1; column <= size; column++) {
        final String weight = this.elements.getElement(row, column);

        if (weight.length() == 0) {
          continue;
        }

        final DoubleSystemBuilder controlSystem = getControlSystem(weight);
        final DoubleSystemOperator system = controlSystem == null ? null : controlSystem.getSystemOperator();

        if (system == null) {
          continue;
        }

        final int inputNodeSize = this.nodeDegrees[row - 1];
        if (inputNodeSize != -1 && system.getInputSize() == -1) {
          system.setInputSize(inputNodeSize);
          final int outputSize = system.getOutputSize();
          if (outputSize != -1) {
            this.nodeDegrees[column - 1] = outputSize;
          }
        }

        final int outputNodeSize = this.nodeDegrees[column - 1];
        if (outputNodeSize != -1 && system.getOutputSize() == -1) {
          system.setOutputSize(outputNodeSize);
          final int inputSize = system.getInputSize();
          if (inputSize != -1) {
            this.nodeDegrees[row - 1] = inputSize;
          }
        }
      }
    }
  }
}