/// GEM3D.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.
 */
 
#ifndef Tulip_GEM3D_H
#define Tulip_GEM3D_H

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

#include "tulip/TulipPlugin.h"

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

private: 
 
    typedef struct Vector 
    {
        long int x, y, z;
        
        Vector(long int ix = 0, long int iy = 0, long int iz = 0)
        {
            x = ix;
            y = iy;
			z = iz;
        }
    };
        
    typedef struct GEM3Dparam
    {
        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

        GEM3Dparam()
        {}
        
        GEM3Dparam(int m) 
        {
            pos.x  = 0;
            pos.y  = 0;
			pos.z  = 0;
            dir  = 0.0;
            heat = 0;
            mass = m;
            mark = false;
        }
    };
    
    /*
     * Functions used to implement the GEM3D 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();
        
    
    GEM3Dparam   *GemProp;
    int        *Map;
    node       *Invmap;
    std::queue<int> *Q;
    std::vector<int> *Adjacent;
    
    /*
     * GEM3D variables
     */

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

    /*
     * GEM3D Constants
     */
    
    // static const int MAXATTRACT    = 1048576;
    static const long ELEN = 128L;
    static const long ELENSQR = ELEN * ELEN;
    static const long MAXATTRACT = 1048576L; 
    
    /*
     * GEM3D 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 GEM3D
     * 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