grid.h

C++蚂蚁实现/C++蚂蚁实现 C++蚂蚁实现

/*  Ant-based Clustering
    Copyright (C) 2004 Julia Handl
    Email: [e-mail]

    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-1307  USA

*/

/***************************************************

date: 7.4.2003

author: Julia Handl ([e-mail])

description: 
implementation of a the two-dimensional grid
used for ant-based clustering, SOMs and also for
the visualization of MDS solutions;

***************************************************/

#ifndef GRID_JH_2003
#define GRID_JH_2003


#include "conf.h"
#include "databin.h"

#define FREE -1


/* 
 class position

*/

template <class T>
class position {

 private:
    T coord[2];     // only two-d coordinates

  

 public:
    position();

    position(T i, T j);
    
    ~position();

  
    /* write-read access to coordinates */
    T &operator[](const int p);

    /* check limits to stay within torus */
    const int checkborder(const int p, const int lim);

    /* change coordinates to x = <di>, y = <dj> */
    void set(T di, T dj);

    /* add values in both dimensions to the coordinates 
       with/without boder check*/
    void add(T di, T dj, T imax, T jmax);
    void add(position<T> & P );
    void add(T di, T dj);

    /* divide both coordinates by <d> */
    void div(int d);


};


   


/* constructor: default initialisation */
template <class T>position<T>::position(void) {
    coord[0] = 0;
    coord[1] = 0;
}

/* constructor: initialisation to x = <i>, y = <j> */
template <class T>position<T>::position(T i, T j) {
    coord[0] = i;
    coord[1] = j;
    
}

/* destructor */
template <class T>position<T>::~position(void) {
}

/* write-read access to coordinates */
template <class T> T &position<T>::operator[](const int p) {
    return coord[p];
}

/* check violation of grid borders to stay "on the torus" */
template <class T>const int position<T>::checkborder(const int p, const int lim) {
    if (p >= lim) {
	return p % lim;
    }
    if (p < 0) {

	int temp = p%lim;
	if (temp != 0) return lim + (p%lim);
	else return 0;
    }
    return p;
}

/* set position to x = <di>, y = <dj> */	
template <class T>void position<T>::set(T di, T dj) {
    coord[0] = di;
    coord[1] = dj;
}


/* add values in both dimensions to the coordinates and check borders */
template <class T>void position<T>::add(T di, T dj, T imax, T jmax) {
    coord[0] += di; 
    coord[1] += dj;

    /* implement torus grid */
    coord[0] = checkborder(int(coord[0]), (int)imax);
    coord[1] = checkborder(int(coord[1]), (int)jmax);
	
}


/* add values in both dimensions to the coordinates, without border check */
template <class T>void position<T>::add(T di, T dj) {
    coord[0] += di; 
    coord[1] += dj;
	
}


/* add values in both dimensions to the coordinates, without boder check */
template <class T>void position<T>::add(position<T> & p) {
    coord[0] += p.coord[0]; 
    coord[1] += p.coord[1];
}


/* divide both coordinates by <d> */
template <class T>void position<T>::div(int d) {
    coord[0] /= double(d); 
    coord[1] /= double(d);
}




/* 
 class grid

 functions:
 - read-write access
 - neighbourhood function (for ACCL picking-dropping criteria)
 - addition with automated border check (for ACCL movements)
 
*/

class grid {
 public:

    /* pointer to current parameter settings */
    conf * par;

    /* pointer to current data */
    databin<USED_DATA_TYPE> * bin;

    /* the actual grid: a two-d array of grid cells */
    int ** cells;

    /* variables used for additional index structure */
    position<int> * index;  /* array of positions of free data items */
    int items;              /* number of items in index */
    int last;               /* current free position in index */

    
 public:
    /* Constructor */
    grid(conf * c, databin<USED_DATA_TYPE> * b);

    /* Destructor */
    ~grid();

    /* Intialisation: data elements are randomly scattered */
    void init();

    /* update x to lie within the interval [0, lim-1] */
    const int checkborder(const int x, const int lim);
    
    /* randomly generate positions on the grid that lie
       within distance <radius> from current position <pos> */
    void generate(position<int> & pos, const int radius, position<int> & temp);
    void generate(position<double> & pos, const int radius, position<double> & temp);

    /* write-read access to grid cells */
    int &operator()(int i, int j);

    /* randomly return another position stored within index */
    const position<int> & next(); 

    /* add data to grid and update index */
    void add(position<int> & pos, const int data);
    void add(position<double> & pos, const int data);

    /* return grid position for data item with identifier <i> */
    position<int> & getposition(int i);

    /* remove data from grid and update index */
    const void remove(position<int> & pos);

    /* remove data from grid to initialize ant */
    const int remove_init(position<int> * pos);

    /* exchange two data items */
    const void replace(position<int> & pos, int data, int replaced);

    /* neighbourhood function */
    const double f(const int data, position<int> & pos, const int radius, const int nsize, const double scalefactor, int clusterphase);

    const double fold(const int data, position<int> & pos, const int radius, const int nsize, const double scalefactor);

    /* local comparison (of two elements) */
    const double dissimilarity(const int data1, const int data2);

    /* search for nearby dropping site */
    const position<int> searchdroppingsite(position<int> & pos, const int data);
    const position<double> searchdroppingsite(position<double> & pos, const int data);

    /* print grid data to file */
    void print();
    double square(double);

    /* Euclidean distance */
    double spatialdistance(position<double> *, position<double> *, int torus);
    double spatialdistance(position<int> *, position<int> *, int torus);

    

};	

double max(double i, double j);
double min(double i, double j);
int max(int i, int j);
int min(int i, int j);
double abs(double x);


#endif