/**
   * DATA STRUCTURES
   */
  
  typedef struct MM {
      float   x;
      float   y;
      int     carbone;
      int     dormance;
  } MM;
  
  typedef struct OM {
      float   x;
      float   y;
      int     carbone;
      int     lock;
  } OM;
  
  typedef struct MiorWorld {
      int     nbMM;
      int     nbOM;
      int     RA;
      float   RR;
      float   GR;
      float   K;
      int     width;
      int     minSize;
      int     CO2;
      int     lock;
  } MiorWorld;
  
  
  typedef struct RandomGen {
  	ulong a;
  	ulong b;
  	ulong c;
  } RandomGen;
  
  
  /**
   * CONSTANTS
   */
  
  #define OFFER_INVALID -1
  #define OFFER_UNINIT  -2
  
  /**
   * HELPER FUNCTIONS
   */
  
  // Compatibility macros for OpenCL <= 1.1
  
  #if __OPENCL_VERSION__ <= CL_VERSION_1_0
      #define atomic_cmpxchg(p, o, v) atom_cmpxchg(p, o, v)
  #endif
  
  // End of compatibility macros
  
  
  #define LOCK_P(lock, id) while (atomic_cmpxchg(&(lock), -1, id) != id) {}
  #define LOCK_V(lock, id) while (atomic_cmpxchg(&(lock), id, -1) != -1) {}
  
  // RNG
  
  void rng_init(RandomGen *r, long seed)
  {
      r->a = seed;
      r->b = 0;
      r->c = 362436;
  }
  
  unsigned long rng_rand(RandomGen *r)
  {
      const long old = r->b;
      r->b = r->a * 1103515245 + 12345;
      r->a = (~old ^ (r->b >> 3)) - r->c++;
      return r->b;
  }
  
  float rng_rand_01(RandomGen *r)
  {
      return (rng_rand(r) & 4294967295) / 4294967295.0f;
  }
  
  void shuffle_indexes(global int * array, int size, RandomGen *r)
  {   
      for (int i = size - 1; i >= 1; i--) {
  		const int j = rng_rand_01(r) * (i + 1);
  		
  		const int t = array[j];
  		array[j] = array[i];
  		array[i] = t;
  	}
  }
  
  void shuffle_help(global int * array, int size, RandomGen *r)
  {   
      for (int i = size - 1; i >= 1; i--) {
  		const int j = rng_rand_01(r) * (i + 1);
  		
  		const int t = array[j];
  		array[j] = array[i];
  		array[i] = t;
  	}
  }
  
  
  kernel void shuffle_test(global int * array, int size)
  {
  	RandomGen rng;
  	rng_init(&rng, 42L);
  	
  	for (int i = 0; i < size; i++) {
  		array[i] = i;
  	}
  	
  	shuffle_help(array, size, &rng);
  }
  	
  // Cleanup
  
  void topo_clean(global int * targets, int size)
  {
      for (int i = 0; i < size; i++) {
          if (targets[i] != OFFER_INVALID) {
              targets[i] = OFFER_UNINIT;
          }
      }
  }
  
  /**
   * KERNELS
   */
  
  kernel void topology(
      global MM *mmList,
      global OM *omList,
      global int *topo,
      global MiorWorld *world)
  {
      const int iMM = get_global_id(0);
      const int iOM = get_global_id(1);
      
  	//float dx = omList[iOM].x - mmList[iMM].x;
  	//float dy = omList[iOM].y - mmList[iMM].y;
  	//float distance = sqrt(dx * dx + dy * dy);
  	
      //if (distance <= world->RA) {
  	//    topo[iMM * world->nbOM + iOM] = OFFER_UNINIT;
  	//} else {
  	//    topo[iMM * world->nbOM + iOM] = OFFER_INVALID;
  	//}
  	
  	const float dx = omList[iOM].x - mmList[iMM].x;
  	const float dy = omList[iOM].y - mmList[iMM].y;
  	const float distance = hypot(dx, dy);
  	
  	if (distance <= world->RA) {
  	    topo[iMM * world->nbOM + iOM] = OFFER_UNINIT;
  	} else {
  	    topo[iMM * world->nbOM + iOM] = OFFER_INVALID;
  	}
  }
  
  int live_breath(
      int iMM,
      global MM * mmList,
      global OM * omList,
      global int * targets,
      global MiorWorld * world,
      global int *omIndexes)
  {
      global MM * currentMM = mmList + iMM;
      global OM * currentOM;
      
      const int totalNeed = currentMM->carbone * world->RR;
      int remainingNeed = totalNeed;
      const int nbOM = world->nbOM;
      int i = 0, iOM = 0;
      int offer, consum;
      
      while (i < nbOM && remainingNeed > 0) {
          iOM = omIndexes[i];
          
     		if (targets[iOM] != OFFER_INVALID) {
      		currentOM = omList + iOM;
              
              offer = world->K * currentOM->carbone;
              consum = min(offer, remainingNeed);
              remainingNeed -= consum;
      	}
      	
      	i++;
      }
      
      if (remainingNeed > 0) {
      	currentMM->dormance = 1;
      } else {
      	currentMM->dormance = 0;
      	remainingNeed = totalNeed;
    
  		i = 0;
  		while (i < nbOM && remainingNeed > 0) {
  		    iOM = omIndexes[i];
  		    
  		    if (targets[iOM] != OFFER_INVALID) {
  		        currentOM = omList + iOM;
  		         
  		        LOCK_P(currentOM->lock, iMM);
  		        
  		        if (targets[iOM] != OFFER_UNINIT) {
  		            offer = targets[iOM];
  		        } else {
  		            offer = world->K * currentOM->carbone;
  		        }
  		        
  		        consum = min(offer, remainingNeed);
  		        
  		        remainingNeed -= consum;
  		        currentOM->carbone -= consum;
  		        
  		        LOCK_V(currentOM->lock, iMM);
  		        
  		        LOCK_P(world->lock, iMM);
  		        world->CO2 += consum;
  		        LOCK_V(world->lock, iMM);
  		        
  		        targets[iOM] = offer - consum;
  		    }
  		    
  		    i++;
  		}
  	}
      
      return remainingNeed;
  }
  
  int live_grow(
      int iMM,
      global MM * mmList,
      global OM * omList,
      global int * targets,
      global MiorWorld * world,
      global int *omIndexes)
  {
      global MM * currentMM = mmList + iMM;
      global OM * currentOM;
      
      const int totalNeed = currentMM->carbone * world->GR;
      int remainingNeed = totalNeed;
      const int nbOM = world->nbOM;
      int i = 0, iOM = 0;
      int offer, consum;
      
      while (i < nbOM && remainingNeed > 0) {
          iOM = omIndexes[i];
          
          if (targets[iOM] != OFFER_INVALID) {
              currentOM = omList + iOM;
              
              LOCK_P(currentOM->lock, iMM);
              
              if (targets[iOM] != OFFER_UNINIT) {
                  offer = targets[iOM];
              } else {
                  offer = world->K * currentOM->carbone;
              }
              
              consum = min(offer, remainingNeed);
              
              remainingNeed -= consum;
              currentOM->carbone -= consum;
              
              LOCK_V(currentOM->lock, iMM);
              
              currentMM->carbone += consum;
          }
          
          i++;
      }
      
      return remainingNeed;
  }
  
  kernel void live(
      global MM *mmList,
      global OM *omList,
      global int *topo,
      global MiorWorld *world,
      global int *omIndexes,
      long   seed)
  {
      int iMM = get_global_id(0);
      global int * targets = topo + iMM * world->nbOM;
      global int * indexes = omIndexes + iMM * world->nbOM;
      RandomGen rng;
      
      for (int i = 0; i < world->nbOM; i++) {
          indexes[i] = i;
      }
      
      if (seed != 0) {
          rng_init(&rng, seed + iMM);
          shuffle_indexes(indexes, world->nbOM, &rng);
      }
      
      // BREATHING
      live_breath(iMM, mmList, omList, targets, world, indexes);
      
      if (mmList[iMM].dormance == 0) {
      
      	// GROWTH
      	live_grow(iMM, mmList, omList, targets, world, indexes);
      }
      
      // CLEANUP
      topo_clean(targets, world->nbOM);
  }
  
  kernel void autolive(
      global MM *mmList,
      global OM *omList,
      global int *topo,
      global MiorWorld *world,
      global int *omIndexes,
      long   seed)
  {
      LOCK_P(world->lock, get_global_id(0));
      int CO2 = world->CO2;
      LOCK_V(world->lock, get_global_id(0));
      
      int oldCO2 = -1;
      
      while (CO2 != oldCO2) {
          live(mmList, omList, topo, world, omIndexes, seed);
          
          oldCO2 = CO2;
          LOCK_P(world->lock, get_global_id(0));
          CO2 = world->CO2;
          LOCK_V(world->lock, get_global_id(0));
      }   
  }