(empty message)

[qanava.git] / src / la / laTimeTree.cpp

/*
Qanava - Graph drawing library for QT
Copyright (C) 2005 Benoit AUTHEMAN

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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

//-----------------------------------------------------------------------------
// This file is a part of the Qanava software.
//
// \file        laLayout.cpp
// \author      Benoit Autheman (benoit@faktiss.net)
// \date        2004 December 05
//-----------------------------------------------------------------------------


// Qanava haders
#include "laTimeTree.h"


// Std headers
#include <iterator>


// Boost headers
#ifndef DOXYSKIP
#include "boost/date_time/posix_time/posix_time.hpp"

using namespace boost::posix_time;
using namespace boost::gregorian;
#endif


namespace qan { // ::qan
namespace la { // ::qan::la


bool TimeTree::NodeDateComp::operator()( const Node* n1, const Node* n2 ) const
{
        const boost::posix_time::ptime* d1 = n1->getDate( );
        const boost::posix_time::ptime* d2 = n2->getDate( );
        if ( d1 == 0 || d2 == 0 )
                return false;
        return  ( *d1 < *d2 );
}

/* TimeTree Grid Management *///-----------------------------------------------
/*!
        \param  cy      Y coordinate of the cluster top left corner
        \param  w       Width of the cluster.
        \param  h       Height of the cluster.
 */
void    TimeTree::GridBuilder::buildClusterGrid( int cy, int w, int h, int r, int g, int b )
{
        _grid.addLine( 0, cy + h, w, cy + h, 1, false, false );
        _grid.addRectangle( 0, cy, w, h + 1, r, g, b );
}

/*!
        \param  sortedNodes     Set of time sorted nodes already placed on the canvas.
        \param  maxX, maxY      Maximum coordinate for the nodes in the current layout.
*/
void    TimeTree::GridBuilder::buildTimeGrid( NodeSet& nodes, int, int height )
{
        // Draw vertical time grid lines
        float x = 10.f;
        const boost::posix_time::ptime* lastNodeDate = 0;
        for ( NodeSet::iterator nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++ )
        {
                // Set default separation line settings
                bool dash = false;
                bool dot = true;

                const ptime* nodeDate = ( *nodeIter )->getDate( );
                if ( nodeDate != 0 && lastNodeDate != 0 && ( *nodeDate == *lastNodeDate ) )
                        x -= incX;

                // Different days are separated with a strong line
                if ( ( nodeDate != 0 && lastNodeDate == 0 ) ||  // First day
                         ( nodeDate != 0 && lastNodeDate != 0 && ( nodeDate->date( ) > lastNodeDate->date( ) ) ) ) // New Day
                {
                        dash = true;
                        dot = false;

                        // Add the date text
                        std::string dateText( "" );
                        try
                        {
                                dateText = to_simple_string( nodeDate->date( ) );
                        } catch( std::exception& e ) { }
                        _grid.addText( dateText, ( int )x, 3, true );
                        _grid.addText( dateText, ( int )x, height - 15, true );
                }

                // Add separation line to grid
                _grid.addLine( ( int )x - 5, 0, ( int )x - 5, height, 1, dash, dot );

                lastNodeDate = nodeDate;
                x += incX;
        }
}

void    TimeTree::GridBuilder::buildTimeLabel( Node& node, int x, int y )
{
        const ptime* nodeDate = node.getDate( );
        if ( nodeDate != 0 )
        {
                // Add date label to grid
                std::string timeText( "" );
                try
                {
                        timeText = boost::posix_time::to_simple_string( nodeDate->time_of_day( ) );
                } catch( std::exception& e ) { timeText = "00:01:00"; }
                _grid.addText( timeText, x, y );
        }
}
//-----------------------------------------------------------------------------

bool TimeTree::Group::GroupMedDateComp::operator()( const Group* g1, const Group* g2 ) const
{
        ptime tg1 = g1->getMedianDate( );
        ptime tg2 = g2->getMedianDate( );
        return ( tg1 < tg2 );
}

/*!
        \return A pointer to the line node list, 0 if line index is negative or superior to the group lines count.
 */
la::Node::Nodes*        TimeTree::Group::getLine( unsigned int line )
{
        if ( line >= _lines.size( ) )
                return 0;
        return _lines[ line ];
}

void                            TimeTree::Group::collectNodes( la::Node::Nodes& nodes ) const
{
        for ( Lines::const_iterator lineIter = _lines.begin( ); lineIter != _lines.end( ); lineIter++ )
        {
                const la::Node::Nodes* lineNodes = *lineIter;
                std::copy( lineNodes->begin( ), lineNodes->end( ),
                                                                                        std::back_insert_iterator< la::Node::Nodes >( nodes ) );
        }
}

void                            TimeTree::Group::setNodesType( int type )
{
        la::Node::Nodes nodes;
        collectNodes( nodes );
        for ( la::Node::Nodes::iterator nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++ )
                ( *nodeIter )->setType( type );
}

/*!
        To avoid aggressive merge during layout, the method return true when a node with no date
        occurs.
 */
bool    TimeTree::Group::intersect( const Group& group ) const
{
        for ( Lines::const_iterator lineIter = _lines.begin( ); lineIter != _lines.end( ); lineIter++ )
        {
                const la::Node::Nodes* lineNodes = *lineIter;
                if ( lineNodes->size( ) < 1 )
                        continue;
                const la::Node* nodeFirst = lineNodes->front( );
                const la::Node* nodeLast =  lineNodes->back( );

                const ptime* nodeFirstDate = nodeFirst->getDate( );
                const ptime* nodeLastDate = nodeLast->getDate( );
                if ( nodeFirstDate == 0 || nodeLastDate == 0 )
                        continue;

                // Test the current line time interval with the given group ones
                for ( Lines::const_iterator lineDstIter = group._lines.begin( ); lineDstIter != group._lines.end( ); lineDstIter++ )
                {
                        const la::Node::Nodes* lineDstNodes = *lineDstIter;
                        if ( lineDstNodes->size( ) < 1 )
                                continue;
                        const la::Node* nodeDstFirst = lineDstNodes->front( );
                        const la::Node* nodeDstLast =  lineDstNodes->back( );

                        const ptime* nodeDstFirstDate = nodeDstFirst->getDate( );
                        const ptime* nodeDstLastDate = nodeDstLast->getDate( );
                        if ( nodeDstFirstDate == 0 || nodeDstLastDate == 0 )
                                continue;

                        // Test mutual intersection

                        // Dst node area has an extremity in the node area
                        if ( ( ( *nodeDstFirstDate >= *nodeFirstDate  ) && ( *nodeDstFirstDate <= *nodeLastDate ) ) ||
                                 ( ( *nodeDstLastDate >= *nodeFirstDate ) && ( *nodeDstLastDate <= *nodeLastDate ) ) )
                                return true;

                        // Dst node area is larger than the node are
                        if ( ( *nodeDstFirstDate <= *nodeFirstDate ) && ( *nodeDstLastDate >= *nodeLastDate ) )
                                return true;
                }
        }
        return false;
}

boost::posix_time::ptime        TimeTree::Group::getMedianDate( ) const
{
        la::Node::Nodes groupNodes;
        collectNodes( groupNodes );

        // Get the min and max date in the cluster articles
        ptime dateMin = ptime( date( boost::date_time::pos_infin ) );
        ptime dateMax = ptime( date( boost::date_time::neg_infin ) );
        for ( la::Node::Nodes::const_iterator nodeIter = groupNodes.begin( ); nodeIter != groupNodes.end( ); nodeIter++ )
        {
                const ptime* nodeDate = ( *nodeIter )->getDate( );
                if ( nodeDate != 0 )
                {
                        if ( *nodeDate < dateMin )
                                dateMin = *nodeDate;
                        if ( *nodeDate > dateMax )
                                dateMax = *nodeDate;
                }
        }

        // Get the median time
        time_duration groupDuration = dateMax - dateMin;
        return dateMin + ( groupDuration / 2 );
}


/*!
        This method assumer that the groups inside the two track are disjoint within their own track groups.
 */
bool    TimeTree::Track::isDisjointOf( Track& track )
{
        // Check that given track groups are disjoint from thie track groups
        Group::Groups::iterator groupIter = track.getGroups( ).begin( );
        for ( ; groupIter != track.getGroups( ).end( ); groupIter++ )
        {
                Group::Groups::iterator groupDstIter = getGroups( ).begin( );
                for ( ; groupDstIter != getGroups( ).end( ); groupDstIter++ )
                {
                        if ( ( *groupIter )->intersect( **groupDstIter ) )
                                return false;
                }
        }
        return true;
}

/*! This method will merge tracks even if they have intersecting groups, so please verfiy track intersection if
    such behaviour is not desired.
 */
void    TimeTree::Track::mergeTrack( Track& track )
{
        Group::Groups& trackGroups = track.getGroups( );
        for ( Group::Groups::iterator groupIter = trackGroups.begin( ); groupIter != trackGroups.end( ); groupIter++ )
                _groups.push_front( *groupIter );
        trackGroups.clear( );
}

/*!
        \return Maximum number of lines in all track node groups, 0 if there is no lines.
 */
int             TimeTree::Track::getLineCount( ) const
{
        int lineCount = 0;
        for ( Group::Groups::const_iterator groupIter = _groups.begin( ); groupIter != _groups.end( ); groupIter++ )
        {
                if ( ( *groupIter )->getLineCount( ) > lineCount )
                        lineCount = ( *groupIter )->getLineCount( );
        }
        return lineCount;
}

/*!
        \return Height of the track after the layout.
 */
float   TimeTree::Track::layout( float trackY, float width, GridBuilder& gridBuilder )
{
        float trackYStart = trackY;
        trackY += trackIntervalY;
        int lineCount = getLineCount( );
        for ( int line = 0; line < lineCount; line++ )
        {
                la::Node::Nodes lineNodes;

                // Regroup track group current line as one line
                for ( Group::Groups::iterator groupIter = getGroups( ).begin( ); groupIter != getGroups( ).end( ); groupIter++ )
                {
                        la::Node::Nodes* groupLineNodes = ( *groupIter )->getLine( line );
                        if ( groupLineNodes == 0 )
                                continue;
                        std::copy( groupLineNodes->begin( ), groupLineNodes->end( ),
                                                                                std::back_insert_iterator< la::Node::Nodes >( lineNodes ) );
                }

                // Get current line maximum height
                float lineHeight = 0.f;
                for ( la::Node::Nodes::iterator lineNodeIter = lineNodes.begin( ); lineNodeIter != lineNodes.end( ); lineNodeIter++ )
                {
                        la::Node* lineNode = ( *lineNodeIter );
                        if ( lineNode->getDimension( )( 1 ) > lineHeight )
                                lineHeight = lineNode->getDimension( )( 1 );
                }

                // Center line nodes vertically
                for ( la::Node::Nodes::iterator lineNodeIter = lineNodes.begin( ); lineNodeIter != lineNodes.end( ); lineNodeIter++ )
                {
                        la::Node* lineNode = ( *lineNodeIter );
                        gridBuilder.buildTimeLabel( *lineNode, ( int )lineNode->getPosition( )( 0 ), ( int )trackY - 13 );
                        float deltaY = ( ( lineHeight - lineNode->getDimension( )( 1 ) ) / 2.f );
                        lineNode->getPosition( )( 1 ) = trackY + deltaY;
                }

                // Switch to next line
                trackY += lineHeight;
                if ( line < lineCount - 1 )
                {
                        trackY += 2;

                        // Add line grid separation line
                        gridBuilder.getGrid( ).addLine( 0, ( int )trackY, ( int )width, ( int )trackY, 1, false, true );

                        trackY += lineIntervalY;
                }
        }
        trackY += 2;
        return ( trackY - trackYStart );
}

void    TimeTree::Track::collectGroups( Group::Groups& groups )
{
        // Sort this track groups according to their average date thanks to a sorted multiset
        Group::GroupSet groupSet;
        std::copy( _groups.begin( ), _groups.end( ), std::inserter( groupSet, groupSet.begin( ) ) );

        // Copy the sorted groups to the groups collection list
        std::copy( groupSet.begin( ), groupSet.end( ), std::back_insert_iterator< Group::Groups >( groups ) );
}

int             TimeTree::Track::getNodeCount( ) const
{
        int nodeCount = 0;
        Group::Groups::const_iterator groupIter = _groups.begin( );
        for ( ; groupIter != _groups.end( ); groupIter++ )
        {
                la::Node::Nodes nodes;
                ( *groupIter )->collectNodes( nodes );
                nodeCount += nodes.size( );
                nodes.clear( );
        }
        return nodeCount;
}

void    TimeTree::Tracks::addTrack( Track* track )
{
        _tracks.push_back( track );
}

void    TimeTree::Tracks::mergeTracks( )
{
        std::set< Track* > tracksMerged;

        // Try to insert each tracks in the other ones
        for ( Track::Tracks::iterator trackIter = _tracks.begin( ); trackIter != _tracks.end( ); trackIter++ )
        {
                Track* track = *trackIter;

                Track::Tracks::iterator trackDstIter = _tracks.begin( );
                for ( ; trackDstIter != _tracks.end( ); trackDstIter++ )
                {
                        Track* trackDst = *trackDstIter;
                        if ( track == trackDst )
                                continue;

                        // Don't merge to a track that is merged and no longer exists
                        if ( tracksMerged.find( trackDst ) != tracksMerged.end( ) )
                                continue;

                        // Test if track content can be merged in dst track
                        if ( trackDst->isDisjointOf( *track ) )
                        {
                                trackDst->mergeTrack( *track );
                                tracksMerged.insert( track );
                        }
                }
        }

        // Supress merged tracks
        {
                std::set< Track* >::iterator trackIter = tracksMerged.begin( );
                for ( ; trackIter != tracksMerged.end( ); trackIter++ )
                        _tracks.remove( *trackIter );
        }
}

/*!
        \return Height of the resulting layout.
 */
float   TimeTree::Tracks::layout( float width, GridBuilder& gridBuilder )
{
        // Try to insert each tracs in the other ones
        float trackY = 0.f;
        unsigned int trackId = 0;
        for ( Track::Tracks::iterator trackIter = _tracks.begin( ); trackIter != _tracks.end( ); trackId++, trackIter++ )
        {
                Track* track = *trackIter;

                // For the first cluster increase space for the top days labels
                float trackStart = trackY;
                if ( trackId == 0 )
                        trackY += trackIntervalY + 2;

                // Layout track groups
                float height = track->layout( trackY, width, gridBuilder );
                trackY += height;

/*              int r = ( trackId % 2 == 0 ) ? 88 : 170;
                int g = ( trackId % 2 == 0 ) ? 90 : 171;
                int b = ( trackId % 2 == 0 ) ? 154 : 205;*/
                int r = ( trackId % 2 == 0 ) ? 105 : 170;
                int g = ( trackId % 2 == 0 ) ? 105 : 171;
                int b = ( trackId % 2 == 0 ) ? 175 : 205;

                // For the last cluster increase space for the top days labels
                if ( trackId >= _tracks.size( ) - 1 )
                        trackY += trackIntervalY;
                float trackEnd = trackY;

                gridBuilder.buildClusterGrid( ( int )trackStart, ( int )width, ( int )( trackEnd - trackStart ), r, g, b );
        }
        return trackY;
}

void    TimeTree::Tracks::collectGroups( Group::Groups& groups )
{
        // Collect tracks in their natural order (in fact they are garanteed to be sorted as they have been
        // added (and they have been added according to their group average date)
        for ( Track::Tracks::iterator trackIter = _tracks.begin( ); trackIter != _tracks.end( ); trackIter++ )
                ( *trackIter )->collectGroups( groups );
}


bool TimeTree::TrackDensityComp::operator()( const TimeTree::Track* t1, const TimeTree::Track* t2 ) const
{

        return ( t1->getNodeCount( ) / t1->getLineCount( ) ) > ( t2->getNodeCount( ) / t2->getLineCount( ) );
}


void    TimeTree::Tracks::sortByNodeDensity( )
{
        std::set< TimeTree::Track*, TrackDensityComp > tracksSetDensity;
        std::copy( _tracks.begin( ), _tracks.end( ), std::inserter( tracksSetDensity, tracksSetDensity.begin( ) ) );
        _tracks.clear( );
        std::copy( tracksSetDensity.begin( ), tracksSetDensity.end( ),
                                                                std::back_insert_iterator< Track::Tracks >( _tracks ) );
}

// Layout settings
float TimeTree::incX = 83.f;

float TimeTree::lineIntervalY = 16.f;

float TimeTree::trackIntervalY = 16.f;


/* TimeTree Layout Generation Management *///----------------------------------
/*!
        \note If cluster track merge option is enabled, then a valid style manager must
        have been provided in the TimeTree object constructor, otherwise, consecutive groups (clusters)
        will eventually be affected the same graphic style, creating undiscernable groups.
 */
void    TimeTree::layout( la::Graph& graph, Grid& grid, int /*width*/, int /*height*/, utl::Progress& /*progress*/ )
{
        // Layout the nodes horizontally
        NodeSet nodes;
        std::copy( graph.getNodes( ).begin( ), graph.getNodes( ).end( ),
                                                                                                std::inserter( nodes, nodes.begin( ) ) );
        float layoutWidth = layoutNodesX( nodes );

        // Generate groups for all nodes set to layout
        Group::GroupSet groups;
        NodeSetManager::iterator nodeSetIter = _nodeSetManager.begin( );
        for ( ; nodeSetIter != _nodeSetManager.end( ); nodeSetIter++ )
        {
                Group* clusterGroup = buildGroup( **nodeSetIter );
                groups.insert( clusterGroup );
        }

        // Create a track per group (tracks are sorted by time, since groups already are)
        Tracks* tracks = new Tracks( );
        for ( Group::GroupSet::iterator groupIter = groups.begin( ); groupIter != groups.end( ); groupIter++ )
        {
                Track* track = new Track( );
                track->addGroup( *groupIter );
                tracks->addTrack( track );
        }

        // Optimize tracks placement
        tracks->mergeTracks( );

        // Sort tracks per average node density (to maximize node count on first page)
//      tracks->sortByNodeDensity( );

        // Affect styles such that two consecutive groups on a track do not have the same style
        {
                int groupId = 0;
                Group::Groups groups;
                tracks->collectGroups( groups );
                for ( Group::Groups::iterator groupIter = groups.begin( ); groupIter != groups.end( ); groupId++, groupIter++ )
                        ( *groupIter )->setNodesType( 1 + ( groupId % 3 ) );
        }

        // Fix the tracks layout, ie assign concrete coordinate to graph nodes
        GridBuilder gridBuilder( grid );
        float layoutHeight = tracks->layout( layoutWidth, gridBuilder );

        // Draw the time grid
        gridBuilder.buildTimeGrid( nodes, ( int )layoutWidth, ( int )layoutHeight );
}

float                           TimeTree::layoutNodesX( NodeSet& nodes )
{
        // Set nodes horizontal (x) position according to their date
        float x = 10.f;
        Node* lastNode = 0;
        for ( NodeSet::iterator sortedNodeIter = nodes.begin( ); sortedNodeIter != nodes.end( ); sortedNodeIter++ )
        {
                Node* node = *sortedNodeIter;
                if ( lastNode != 0 )
                {
                        const ptime* nodeDate = node->getDate( );
                        const ptime* lastNodeDate = lastNode->getDate( );
                        if ( nodeDate != 0 && lastNodeDate != 0 && ( *nodeDate == *lastNodeDate ) )
                                x -= incX;
                }

                node->setPosition( x, -1.0f ); // y=-1 used later to indicate the node as still not been placed
                x += incX;

                lastNode = node;
        }
        return x;
}

TimeTree::Group*        TimeTree::buildGroup( NodeSet& clusterNodes )
{
        Group* clusterGroup = new Group( );

        la::Node::Nodes nodes;
        std::copy( clusterNodes.begin( ), clusterNodes.end( ),
                                                                        std::back_insert_iterator< la::Node::Nodes >( nodes ) );

        // Consume all nodes, ie affect all nodes to a line
        unsigned int runCount = 0;
        while ( ( nodes.size( ) > 0 ) && ( runCount < clusterNodes.size( ) ) )
        {
                // Consume as many nodes as possible for a line (ie all non simultaneous nodes or a node with a subnode in this cluster)
                la::Node::Nodes* lineNodes = new la::Node::Nodes( );
                la::Node* prevNode = 0;
                for ( la::Node::Nodes::iterator nodeIter = nodes.begin( ); nodeIter != nodes.end( ); nodeIter++ )
                {
                        la::Node* node = *nodeIter;

                        // Detect if the node hasn't already been positionned (ex: it is a sub node of an existing node in this cluster)
                        if ( node->getPosition( )( 1 ) >= 0.f )
                                continue;

                        if ( ( prevNode == 0 ) ||
                                 ( prevNode != 0 && ( node->getPosition( )( 0 ) > prevNode->getPosition( )( 0 ) ) ) )
                        {
                                // Consume the node
                                lineNodes->push_back( node );
                                node->getPosition( )( 1 ) = 1.0f;
                                prevNode = node;

                                // Consume the node subnodes (and sort subnodes by date)
                                NodeSet sortedOutNodes;
                                la::Node::NodesSet* outNodes = node->getOutNodesSet( );
                                std::copy( outNodes->begin( ), outNodes->end( ), std::inserter( sortedOutNodes, sortedOutNodes.begin( ) ) );
                                delete outNodes;

                                for ( NodeSet::iterator outNodeIter = sortedOutNodes.begin( ); outNodeIter != sortedOutNodes.end( ); outNodeIter++ )
                                {
                                        la::Node* outNode = *outNodeIter;
                                        if ( clusterNodes.find( outNode ) == clusterNodes.end( ) )
                                                continue; // Dismiss nodes not in this cluster (is not in the cluster sorted nodes set)

                                        if ( outNode->getPosition( )( 1 ) >= 0.f )
                                                continue;

                                        // Test that a node with a previous same date is not already in this line. Ex: Two sub
                                        // articles have the same date, so the same x position, they must be on different lines.
                                        bool skipNode = false;
                                        la::Node::Nodes::iterator lineNodeIter = lineNodes->begin( );
                                        for ( ; lineNodeIter != lineNodes->end( ); lineNodeIter++ )
                                        {
                                                if ( outNode->getPosition( )( 0 ) == ( *lineNodeIter )->getPosition( )( 0 ) )
                                                        skipNode = true;
                                        }
                                        if ( skipNode )
                                                continue;

                                        lineNodes->push_back( outNode );
                                        outNode->getPosition( )( 1 ) = 1.0f;
                                        prevNode = outNode;
                                }
                        }
                }

                // Supress all line nodes
                for ( la::Node::Nodes::iterator lineNodeIter = lineNodes->begin( ); lineNodeIter != lineNodes->end( ); lineNodeIter++ )
                        nodes.remove( *lineNodeIter );

                clusterGroup->addLine( lineNodes );

                // Avoid infinite recursion, allow no more runs than there is nodes
                runCount++;
        }

        return clusterGroup;
}
//-----------------------------------------------------------------------------


} // ::qan::la
} // ::qan