//-*-c++-*-

/// GEM.h - An implementation of a spring-embedder layout.
/** This plugin is an implementation of the GEM-2d layout
 *  algorithm first published as:
 *
 *  A. Frick, A. Ludwig, and H. Mehldau, "A fast, adaptive 
 *  layout algorithm for undirected graphs", In R. Tamassia
 *  and I. Tollis (Eds), Graph Drawing'94, Volume 894 of 
 *  Lecture Notes in Computer Science, Springer Verlag, 1995.
 *
 *  HISTORY:
 *
 *  The implementation started life as the public-domain 
 *  code produced by Arne Frick and released at
 *
 *  www.frick-consulting.de/publications.html
 *
 *  The core "embedder" part of the algorithm was used in the
 *  implementation of a Java plugin for the CWI "Royere"  tool,
 *  and then this code was ported to C++ to make the 
 *  implementation given here.
 *
 *  NOTES:
 *
 *  The embedder algorithm described by Frick involves three
 *  phases: insertion, arrangement, and optimization.  Only
 *  the first two of these phases are included here. 
 *  Experiments with the Java implementation showed that the
 *  optimization phase consumed significantly more time than
 *  the first two and produced apparently marginal improvements
 *  in the final layout.
 *
 *  As GEM, like other spring-embedder algorithms, is 
 *  computationally expensive, I have tried to optimize the
 *  loops somewhat by storing all necessary node information
 *  into two arrays: "GemProp" carries the (scalar) values 
 *  associated with each node by the layout algorithm, while
 *  "Adjacent" is an array of vectors, one vector per node,
 *  giving the index (integer) of each node.
 *
 *  AUTHOR:
 *
 *  David Duke, University of Bath, UK: Email: D.Duke@bath.ac.uk
 *  Version 0.1: 23 July 2001: Initial version
 *
 *  David Auber University France: Email:auber@tulip-software.com
 *  Version 0.2: 10 january 2002: Add progress bar managment
 *
 *  David Auber University France: Email:auber@tulip-software.com
 *  Version 0.3: 07 march 2002: Fix some memory leack due to operators
 *
 *  LICENCE:
 *
 *  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.
 *
 */
 
#ifndef Tulip_GEM_H
#define Tulip_GEM_H

#include <queue>
#include <vector>

#if (__GNUC__ < 3)
#include <hash_map>
#else
#include <ext/hash_map>
#endif


#include <tulip/TulipPlugin.h>

class GEM : public Layout { 
public:
    GEM(PropertyContext *);
    ~GEM();
  
    bool run();
    bool check(std::string &);
    void reset();

private: 
 
    typedef struct Vector {
      long int x, y;
      Vector(long int ix = 0, long int iy = 0):x(ix),y(iy){}
    };
    
    typedef struct GEMparam
    {
        Vector pos;        // position
        int in;
        
        Vector imp;        // impulse
        float dir;        // direction
        float heat;        // heat
        float mass;        // weight = nr incident edges
        bool  mark;        // used for BFS traversal

        GEMparam()
        {}
        
      GEMparam(int m):pos(0,0),dir(0.0),heat(0),mass(0),mark(false)
      {}
    };
    
    /*
     * Functions used to implement the GEM layout.
     */
     
    int select();
    int bfs(int root);
    int graph_center();
    void vertexdata_init(const float starttemp);
    Vector i_impulse(int v);
    void insert();
    void displace(int v, Vector imp);
    void a_round();
    void arrange();
        
    
    GEMparam   *GemProp;
    int        *Map;
    node       *Invmap;
    std::queue<int> *Q;
    std::vector<int> *Adjacent;
    
    /*
     * GEM variables
     */

    int             NodeCount;
    unsigned long    Iteration;
    long int        Temperature;
    Vector            Center;
    long int        Maxtemp;
    float            Oscillation, Rotation;

    /*
     * GEM Constants
     */
    
    // static const int MAXATTRACT    = 1048576;
    static const long ELEN = 24L;
    static const long ELENSQR = ELEN * ELEN;
    static const long MAXATTRACT = 1048576L; 
    
    /*
     * GEM Defualt Parameter Values
     */
     
    static const float IMAXTEMPDEF     = 1.0;
    static const float ISTARTTEMPDEF   = 0.3;
    static const float IFINALTEMPDEF   = 0.05;
    static const int   IMAXITERDEF     = 10;
    static const float IGRAVITYDEF     = 0.05;
    static const float IOSCILLATIONDEF = 0.4;
    static const float IROTATIONDEF    = 0.5;
    static const float ISHAKEDEF       = 0.2;
    static const float AMAXTEMPDEF     = 1.5;
    static const float ASTARTTEMPDEF   = 1.0;
    static const float AFINALTEMPDEF   = 0.02;
    static const int   AMAXITERDEF     = 3;
    static const float AGRAVITYDEF     = 0.1;
    static const float AOSCILLATIONDEF = 0.4;
    static const float AROTATIONDEF    = 0.9;
    static const float ASHAKEDEF       = 0.3;
    static const float OMAXTEMPDEF     = 0.25;
    static const float OSTARTTEMPDEF   = 1.0;
    static const float OFINALTEMPDEF   = 1.0;
    static const int   OMAXITERDEF     = 3;
    static const float OGRAVITYDEF     = 0.1;
    static const float OOSCILLATIONDEF = 0.4;
    static const float OROTATIONDEF    = 0.9;
    static const float OSHAKEDEF       = 0.3;
    
    /*
     * Following parameters can be initialised in the original GEM
     * from a configuration file.  Here they are hard-wired, but
     * this could be replaced by configuration from a file.
     */
     
    float    i_maxtemp;
    float    a_maxtemp;
    float    o_maxtemp;
    float    i_starttemp;
    float    a_starttemp;
    float    o_starttemp;
    float    i_finaltemp;
    float    a_finaltemp;
    float    o_finaltemp;
    int      i_maxiter;
    int      a_maxiter;
    int      o_maxiter;
    float    i_gravity;
    float    i_oscillation;
    float    i_rotation;
    float    i_shake;
    float    a_gravity;
    float    a_oscillation;
    float    a_rotation;
    float    a_shake;
    float    o_gravity;
    float    o_oscillation;
    float    o_rotation;
    float    o_shake;

};

#endif