/*
 * Copyright (C) 2007 Bill Cox
 *
 * This program 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.
 *
 * This program 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 this program; if not, write to the Free Software 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
 */

/*--------------------------------------------------------------------------------------------------
  This module places classes into rows in the schema.  The algorithm is basically:

  - Assign classes to rows, starting with classes without parents, and assigning their children
    to the next row, and so on
  - Assign relative positions within rows to reduce crossings as much as possible
  - Assign exact position to minimize total length of horizontal routing
--------------------------------------------------------------------------------------------------*/

#include "dw.h"

/*--------------------------------------------------------------------------------------------------
  Place this class in the given row number (starting from 0), and assign it's unassigned children
  to the next row recursively.
--------------------------------------------------------------------------------------------------*/
static void placeClassAndChildrenInRow(
    dvClass class,
    uint32 rowIndex)
{
    dvSchema schema = dvClassGetSchema(class);
    dwRow row;
    dvClass child;
    dvRelationship relationship;

    if(rowIndex >= dwSchemaGetUsedRow(schema)) {
	row = dwRowAlloc();
	dwSchemaAppendRow(schema, row);
    }
    row = dwSchemaGetiRow(schema, rowIndex);
    dwRowAppendClass(row, class);
    dvForeachClassChildRelationship(class, relationship) {
	child = dvRelationshipGetChildClass(relationship);
	if(dwClassGetRow(child) == dwRowNull) {
            placeClassAndChildrenInRow(class, rowIndex + 1);
	}
    } dvEndClassChildRelationship;
}

/*--------------------------------------------------------------------------------------------------
  Place classes on the schema.
--------------------------------------------------------------------------------------------------*/
static void placeSchemaIntoRows(
    dvSchema schema)
{
    dvClass class;

    dvForeachSchemaClass(schema, class) {
	if(dvClassGetFirstParentRelationship(class) == dvRelationshipNull) {
	    placeClassAndChildrenInRow(class, 0);
	}
    } dvEndSchemaClass;
}

/*--------------------------------------------------------------------------------------------------
  Count the number of relationships in the other row that cross relationships of this class.
--------------------------------------------------------------------------------------------------*/
uint32 countClassCrossings(
    dvClass class,
    dwRow otherRow)
{
    
}

/*--------------------------------------------------------------------------------------------------
  Count the number of crossings from this row to the one above, unless we're the top, in which
  case compare against the next down.
--------------------------------------------------------------------------------------------------*/
static uint32  countCrossings(
    dwRow row1)
{
    dwSchema schema = dwRowGetSchema(row1);
    dwRow row2;
    dvClass class1, class2;
    uint32 index = dwRowGetSchemaIndex(row1);
    uint32 numCrossings = 0;

    if(index == 0) {
	row2 = dwSchemaGetiRow(schema, 1);
    } else {
	row2 = dwSchemaGetiRow(schema, index - 1);
    }
    dwForeachRowClass(row1, class1) {
	numCrossings += countClassCrossings(class1, row2);
    } dwEndForeachRowClass;
    return numCrossings;
}

/*--------------------------------------------------------------------------------------------------
  Compare two classes in a row to see whether or not they should be switched.  Assume all
  upper rows are fixed already, but that classes in lower rows may still move around.  Try both
  positions, and count the number of crossings to determine the better position.  This could be
  improved by also estimating the impact on total length.
--------------------------------------------------------------------------------------------------*/
static int compareClasses(
    const void *class1Ptr,
    const void *class2Ptr)
{
    dvClass class1 = *(dvClass *)class1Ptr;
    dvClass class2 = *(dvClass *)clas2 Ptr;
    dvRow row = dwClassGetRow(class1);
    uint32 crossings1 = countCrossings(row);
    uint32 crossings2;

    *class1Ptr = class2;
    *class2Ptr = class1;
    crossings2 = countCrossings(row);
    *class1Ptr = class1;
    *class2Ptr = class2;
    return crossings1 - crossings2;
}

/*--------------------------------------------------------------------------------------------------
  Reduce crossings between rows by sorting them from left to right to reduce crossings with their
  parent row.  This can be improved, but it's quick and easy.
--------------------------------------------------------------------------------------------------*/
static void sortRowsToReduceCrossings(
    dwSchema schema)
{
    dwRow row;
    dwClass class;
    uint32 rowIndex;

    if(dwSchemaGetNumRows(schema) < 2) {
	return; /* No other rows to compare against */
    }
    dwForeachSchemaRow(schema, row) {
	qsort(dwRowGetClasss(row), dwRowGetUsedClass(row), sizeof(dvClass), compareClasses);
	rowIndex = 0;
	dwForeachRowClass(row, class) {
	    dwClassSetRowIndex(class, rowIndex);
	    rowIndex++;
	} dwEndForeachRowClass;
    } dwEndForeachSchemaRow;
}

/*--------------------------------------------------------------------------------------------------
  Place classes on the schema.
--------------------------------------------------------------------------------------------------*/
void dwPlaceSchema(
    dvSchema schema)
{
    placeSchemaIntoRows(schema);
    sortRowsToReduceCrossings(schema);
}