PostGIS  2.1.10dev-r@@SVN_REVISION@@
rt_quantile rt_band_get_quantiles_stream ( rt_band  band,
int  exclude_nodata_value,
double  sample,
uint64_t  cov_count,
struct quantile_llist **  qlls,
uint32_t *  qlls_count,
double *  quantiles,
int  quantiles_count,
uint32_t *  rtn_count 
)

Compute the default set of or requested quantiles for a coverage.

This function is based upon the algorithm described in:

A One-Pass Space-Efficient Algorithm for Finding Quantiles (1995) by Rakesh Agrawal, Arun Swami in Proc. 7th Intl. Conf. Management of Data (COMAD-95)

http://www.almaden.ibm.com/cs/projects/iis/hdb/Publications/papers/comad95.pdf

In the future, it may be worth exploring algorithms that don't require the size of the coverage

Parameters
band: the band to include in the quantile search
exclude_nodata_value: if non-zero, ignore nodata values
sample: percentage of pixels to sample
cov_count: number of values in coverage
qlls: set of quantile_llist structures
qlls_count: the number of quantile_llist structures
quantiles: the quantiles to be computed if bot qlls and quantiles provided, qlls is used
quantiles_count: the number of quantiles to be computed
rtn_count: the number of quantiles being returned
Returns
the default set of or requested quantiles for a band or NULL

Definition at line 4156 of file rt_api.c.

References quantile_llist::algeq, genraster::count, quantile_llist::count, quantile_llist_element::count, ovdump::data, ES_NONE, FLT_EQ, rt_quantile_t::has_value, quantile_llist::head, rt_band_t::height, quantile_llist::index, quantile_llist::index_max, quantile_llist_element::next, quantile_llist_element::prev, rt_quantile_t::quantile, quantile_llist::quantile, quantile_llist_delete(), quantile_llist_index_delete(), quantile_llist_index_reset(), quantile_llist_index_search(), quantile_llist_index_update(), quantile_llist_insert(), quantile_llist_search(), quicksort(), RASTER_DEBUG, RASTER_DEBUGF, ROUND, rt_band_get_data(), rt_band_get_hasnodata_flag(), rt_band_get_isnodata_flag(), rt_band_get_pixel(), rtalloc(), rtdealloc(), rterror(), quantile_llist::sum1, quantile_llist::sum2, quantile_llist::tail, quantile_llist::tau, genraster::value, rt_quantile_t::value, quantile_llist_element::value, rt_band_t::width, pixval::x, and pixval::y.

Referenced by RASTER_quantileCoverage(), and test_band_stats().

4163  {
4164  rt_quantile rtn = NULL;
4165  int init_quantiles = 0;
4166 
4167  struct quantile_llist *qll = NULL;
4168  struct quantile_llist_element *qle = NULL;
4169  struct quantile_llist_element *qls = NULL;
4170  const uint32_t MAX_VALUES = 750;
4171 
4172  uint8_t *data = NULL;
4173  double value;
4174  int isnodata = 0;
4175 
4176  uint32_t a = 0;
4177  uint32_t i = 0;
4178  uint32_t j = 0;
4179  uint32_t k = 0;
4180  uint32_t x = 0;
4181  uint32_t y = 0;
4182  uint32_t z = 0;
4183  uint32_t idx = 0;
4184  uint32_t offset = 0;
4185  uint32_t diff = 0;
4186  uint8_t exists = 0;
4187 
4188  uint32_t do_sample = 0;
4189  uint32_t sample_size = 0;
4190  uint32_t sample_per = 0;
4191  uint32_t sample_int = 0;
4192  int status;
4193 
4194  RASTER_DEBUG(3, "starting");
4195 
4196  assert(NULL != band);
4197  assert(cov_count > 1);
4198  assert(NULL != rtn_count);
4199  RASTER_DEBUGF(3, "cov_count = %d", cov_count);
4200 
4201  data = rt_band_get_data(band);
4202  if (data == NULL) {
4203  rterror("rt_band_get_summary_stats: Cannot get band data");
4204  return NULL;
4205  }
4206 
4207  if (!rt_band_get_hasnodata_flag(band))
4208  exclude_nodata_value = 0;
4209  RASTER_DEBUGF(3, "exclude_nodata_value = %d", exclude_nodata_value);
4210 
4211  /* quantile_llist not provided */
4212  if (NULL == *qlls) {
4213  /* quantiles not provided */
4214  if (NULL == quantiles) {
4215  /* quantile count not specified, default to quartiles */
4216  if (quantiles_count < 2)
4217  quantiles_count = 5;
4218 
4219  quantiles = rtalloc(sizeof(double) * quantiles_count);
4220  init_quantiles = 1;
4221  if (NULL == quantiles) {
4222  rterror("rt_band_get_quantiles_stream: Could not allocate memory for quantile input");
4223  return NULL;
4224  }
4225 
4226  quantiles_count--;
4227  for (i = 0; i <= quantiles_count; i++)
4228  quantiles[i] = ((double) i) / quantiles_count;
4229  quantiles_count++;
4230  }
4231 
4232  /* check quantiles */
4233  for (i = 0; i < quantiles_count; i++) {
4234  if (quantiles[i] < 0. || quantiles[i] > 1.) {
4235  rterror("rt_band_get_quantiles_stream: Quantile value not between 0 and 1");
4236  if (init_quantiles) rtdealloc(quantiles);
4237  return NULL;
4238  }
4239  }
4240  quicksort(quantiles, quantiles + quantiles_count - 1);
4241 
4242  /* initialize linked-list set */
4243  *qlls_count = quantiles_count * 2;
4244  RASTER_DEBUGF(4, "qlls_count = %d", *qlls_count);
4245  *qlls = rtalloc(sizeof(struct quantile_llist) * *qlls_count);
4246  if (NULL == *qlls) {
4247  rterror("rt_band_get_quantiles_stream: Could not allocate memory for quantile output");
4248  if (init_quantiles) rtdealloc(quantiles);
4249  return NULL;
4250  }
4251 
4252  j = (uint32_t) floor(MAX_VALUES / 100.) + 1;
4253  for (i = 0; i < *qlls_count; i++) {
4254  qll = &((*qlls)[i]);
4255  qll->quantile = quantiles[(i * quantiles_count) / *qlls_count];
4256  qll->count = 0;
4257  qll->sum1 = 0;
4258  qll->sum2 = 0;
4259  qll->head = NULL;
4260  qll->tail = NULL;
4261 
4262  /* initialize index */
4263  qll->index = rtalloc(sizeof(struct quantile_llist_index) * j);
4264  if (NULL == qll->index) {
4265  rterror("rt_band_get_quantiles_stream: Could not allocate memory for quantile output");
4266  if (init_quantiles) rtdealloc(quantiles);
4267  return NULL;
4268  }
4269  qll->index_max = j;
4271 
4272  /* AL-GEQ */
4273  if (!(i % 2)) {
4274  qll->algeq = 1;
4275  qll->tau = (uint64_t) ROUND(cov_count - (cov_count * qll->quantile), 0);
4276  if (qll->tau < 1) qll->tau = 1;
4277  }
4278  /* AL-GT */
4279  else {
4280  qll->algeq = 0;
4281  qll->tau = cov_count - (*qlls)[i - 1].tau + 1;
4282  }
4283 
4284  RASTER_DEBUGF(4, "qll init: (algeq, quantile, count, tau, sum1, sum2) = (%d, %f, %d, %d, %d, %d)",
4285  qll->algeq, qll->quantile, qll->count, qll->tau, qll->sum1, qll->sum2);
4286  RASTER_DEBUGF(4, "qll init: (head, tail) = (%p, %p)", qll->head, qll->tail);
4287  }
4288 
4289  if (init_quantiles) rtdealloc(quantiles);
4290  }
4291 
4292  /* clamp percentage */
4293  if (
4294  (sample < 0 || FLT_EQ(sample, 0.0)) ||
4295  (sample > 1 || FLT_EQ(sample, 1.0))
4296  ) {
4297  do_sample = 0;
4298  sample = 1;
4299  }
4300  else
4301  do_sample = 1;
4302  RASTER_DEBUGF(3, "do_sample = %d", do_sample);
4303 
4304  /* sample all pixels */
4305  if (!do_sample) {
4306  sample_size = band->width * band->height;
4307  sample_per = band->height;
4308  }
4309  /*
4310  randomly sample a percentage of available pixels
4311  sampling method is known as
4312  "systematic random sample without replacement"
4313  */
4314  else {
4315  sample_size = round((band->width * band->height) * sample);
4316  sample_per = round(sample_size / band->width);
4317  sample_int = round(band->height / sample_per);
4318  srand(time(NULL));
4319  }
4320  RASTER_DEBUGF(3, "sampling %d of %d available pixels w/ %d per set"
4321  , sample_size, (band->width * band->height), sample_per);
4322 
4323  for (x = 0, j = 0, k = 0; x < band->width; x++) {
4324  y = -1;
4325  diff = 0;
4326 
4327  /* exclude_nodata_value = TRUE and band is NODATA */
4328  if (exclude_nodata_value && rt_band_get_isnodata_flag(band)) {
4329  RASTER_DEBUG(3, "Skipping quantile calcuation as band is NODATA");
4330  break;
4331  }
4332 
4333  for (i = 0, z = 0; i < sample_per; i++) {
4334  if (do_sample != 1)
4335  y = i;
4336  else {
4337  offset = (rand() % sample_int) + 1;
4338  y += diff + offset;
4339  diff = sample_int - offset;
4340  }
4341  RASTER_DEBUGF(5, "(x, y, z) = (%d, %d, %d)", x, y, z);
4342  if (y >= band->height || z > sample_per) break;
4343 
4344  status = rt_band_get_pixel(band, x, y, &value, &isnodata);
4345 
4346  j++;
4347  if (status == ES_NONE && (!exclude_nodata_value || (exclude_nodata_value && !isnodata))) {
4348 
4349  /* process each quantile */
4350  for (a = 0; a < *qlls_count; a++) {
4351  qll = &((*qlls)[a]);
4352  qls = NULL;
4353  RASTER_DEBUGF(4, "%d of %d (%f)", a + 1, *qlls_count, qll->quantile);
4354  RASTER_DEBUGF(5, "qll before: (algeq, quantile, count, tau, sum1, sum2) = (%d, %f, %d, %d, %d, %d)",
4355  qll->algeq, qll->quantile, qll->count, qll->tau, qll->sum1, qll->sum2);
4356  RASTER_DEBUGF(5, "qll before: (head, tail) = (%p, %p)", qll->head, qll->tail);
4357 
4358  /* OPTIMIZATION: shortcuts for quantiles of zero or one */
4359  if (FLT_EQ(qll->quantile, 0.)) {
4360  if (NULL != qll->head) {
4361  if (value < qll->head->value)
4362  qll->head->value = value;
4363  }
4364  else {
4365  qle = quantile_llist_insert(qll->head, value, NULL);
4366  qll->head = qle;
4367  qll->tail = qle;
4368  qll->count = 1;
4369  }
4370 
4371  RASTER_DEBUGF(4, "quantile shortcut for %f\n\n", qll->quantile);
4372  continue;
4373  }
4374  else if (FLT_EQ(qll->quantile, 1.)) {
4375  if (NULL != qll->head) {
4376  if (value > qll->head->value)
4377  qll->head->value = value;
4378  }
4379  else {
4380  qle = quantile_llist_insert(qll->head, value, NULL);
4381  qll->head = qle;
4382  qll->tail = qle;
4383  qll->count = 1;
4384  }
4385 
4386  RASTER_DEBUGF(4, "quantile shortcut for %f\n\n", qll->quantile);
4387  continue;
4388  }
4389 
4390  /* value exists in list */
4391  /* OPTIMIZATION: check to see if value exceeds last value */
4392  if (NULL != qll->tail && value > qll->tail->value)
4393  qle = NULL;
4394  /* OPTIMIZATION: check to see if value equals last value */
4395  else if (NULL != qll->tail && FLT_EQ(value, qll->tail->value))
4396  qle = qll->tail;
4397  /* OPTIMIZATION: use index if possible */
4398  else {
4399  qls = quantile_llist_index_search(qll, value, &idx);
4400  qle = quantile_llist_search(qls, value);
4401  }
4402 
4403  /* value found */
4404  if (NULL != qle) {
4405  RASTER_DEBUGF(4, "%f found in list", value);
4406  RASTER_DEBUGF(5, "qle before: (value, count) = (%f, %d)", qle->value, qle->count);
4407 
4408  qle->count++;
4409  qll->sum1++;
4410 
4411  if (qll->algeq)
4412  qll->sum2 = qll->sum1 - qll->head->count;
4413  else
4414  qll->sum2 = qll->sum1 - qll->tail->count;
4415 
4416  RASTER_DEBUGF(4, "qle after: (value, count) = (%f, %d)", qle->value, qle->count);
4417  }
4418  /* can still add element */
4419  else if (qll->count < MAX_VALUES) {
4420  RASTER_DEBUGF(4, "Adding %f to list", value);
4421 
4422  /* insert */
4423  /* OPTIMIZATION: check to see if value exceeds last value */
4424  if (NULL != qll->tail && (value > qll->tail->value || FLT_EQ(value, qll->tail->value))) {
4425  idx = qll->count;
4426  qle = quantile_llist_insert(qll->tail, value, &idx);
4427  }
4428  /* OPTIMIZATION: use index if possible */
4429  else
4430  qle = quantile_llist_insert(qls, value, &idx);
4431  if (NULL == qle) return NULL;
4432  RASTER_DEBUGF(5, "value added at index: %d => %f", idx, value);
4433  qll->count++;
4434  qll->sum1++;
4435 
4436  /* first element */
4437  if (NULL == qle->prev)
4438  qll->head = qle;
4439  /* last element */
4440  if (NULL == qle->next)
4441  qll->tail = qle;
4442 
4443  if (qll->algeq)
4444  qll->sum2 = qll->sum1 - qll->head->count;
4445  else
4446  qll->sum2 = qll->sum1 - qll->tail->count;
4447 
4448  /* index is only needed if there are at least 100 values */
4449  quantile_llist_index_update(qll, qle, idx);
4450 
4451  RASTER_DEBUGF(5, "qle, prev, next, head, tail = %p, %p, %p, %p, %p", qle, qle->prev, qle->next, qll->head, qll->tail);
4452  }
4453  /* AL-GEQ */
4454  else if (qll->algeq) {
4455  RASTER_DEBUGF(4, "value, head->value = %f, %f", value, qll->head->value);
4456 
4457  if (value < qll->head->value) {
4458  /* ignore value if test isn't true */
4459  if (qll->sum1 >= qll->tau) {
4460  RASTER_DEBUGF(4, "skipping %f", value);
4461  }
4462  else {
4463 
4464  /* delete last element */
4465  RASTER_DEBUGF(4, "deleting %f from list", qll->tail->value);
4466  qle = qll->tail->prev;
4467  RASTER_DEBUGF(5, "to-be tail is %f with count %d", qle->value, qle->count);
4468  qle->count += qll->tail->count;
4469  quantile_llist_index_delete(qll, qll->tail);
4471  qll->tail = qle;
4472  qll->count--;
4473  RASTER_DEBUGF(5, "tail is %f with count %d", qll->tail->value, qll->tail->count);
4474 
4475  /* insert value */
4476  RASTER_DEBUGF(4, "adding %f to list", value);
4477  /* OPTIMIZATION: check to see if value exceeds last value */
4478  if (NULL != qll->tail && (value > qll->tail->value || FLT_EQ(value, qll->tail->value))) {
4479  idx = qll->count;
4480  qle = quantile_llist_insert(qll->tail, value, &idx);
4481  }
4482  /* OPTIMIZATION: use index if possible */
4483  else {
4484  qls = quantile_llist_index_search(qll, value, &idx);
4485  qle = quantile_llist_insert(qls, value, &idx);
4486  }
4487  if (NULL == qle) return NULL;
4488  RASTER_DEBUGF(5, "value added at index: %d => %f", idx, value);
4489  qll->count++;
4490  qll->sum1++;
4491 
4492  /* first element */
4493  if (NULL == qle->prev)
4494  qll->head = qle;
4495  /* last element */
4496  if (NULL == qle->next)
4497  qll->tail = qle;
4498 
4499  qll->sum2 = qll->sum1 - qll->head->count;
4500 
4501  quantile_llist_index_update(qll, qle, idx);
4502 
4503  RASTER_DEBUGF(5, "qle, head, tail = %p, %p, %p", qle, qll->head, qll->tail);
4504 
4505  }
4506  }
4507  else {
4508  qle = qll->tail;
4509  while (NULL != qle) {
4510  if (qle->value < value) {
4511  qle->count++;
4512  qll->sum1++;
4513  qll->sum2 = qll->sum1 - qll->head->count;
4514  RASTER_DEBUGF(4, "incremented count of %f by 1 to %d", qle->value, qle->count);
4515  break;
4516  }
4517 
4518  qle = qle->prev;
4519  }
4520  }
4521  }
4522  /* AL-GT */
4523  else {
4524  RASTER_DEBUGF(4, "value, tail->value = %f, %f", value, qll->tail->value);
4525 
4526  if (value > qll->tail->value) {
4527  /* ignore value if test isn't true */
4528  if (qll->sum1 >= qll->tau) {
4529  RASTER_DEBUGF(4, "skipping %f", value);
4530  }
4531  else {
4532 
4533  /* delete last element */
4534  RASTER_DEBUGF(4, "deleting %f from list", qll->head->value);
4535  qle = qll->head->next;
4536  RASTER_DEBUGF(5, "to-be tail is %f with count %d", qle->value, qle->count);
4537  qle->count += qll->head->count;
4538  quantile_llist_index_delete(qll, qll->head);
4540  qll->head = qle;
4541  qll->count--;
4542  quantile_llist_index_update(qll, NULL, 0);
4543  RASTER_DEBUGF(5, "tail is %f with count %d", qll->head->value, qll->head->count);
4544 
4545  /* insert value */
4546  RASTER_DEBUGF(4, "adding %f to list", value);
4547  /* OPTIMIZATION: check to see if value exceeds last value */
4548  if (NULL != qll->tail && (value > qll->tail->value || FLT_EQ(value, qll->tail->value))) {
4549  idx = qll->count;
4550  qle = quantile_llist_insert(qll->tail, value, &idx);
4551  }
4552  /* OPTIMIZATION: use index if possible */
4553  else {
4554  qls = quantile_llist_index_search(qll, value, &idx);
4555  qle = quantile_llist_insert(qls, value, &idx);
4556  }
4557  if (NULL == qle) return NULL;
4558  RASTER_DEBUGF(5, "value added at index: %d => %f", idx, value);
4559  qll->count++;
4560  qll->sum1++;
4561 
4562  /* first element */
4563  if (NULL == qle->prev)
4564  qll->head = qle;
4565  /* last element */
4566  if (NULL == qle->next)
4567  qll->tail = qle;
4568 
4569  qll->sum2 = qll->sum1 - qll->tail->count;
4570 
4571  quantile_llist_index_update(qll, qle, idx);
4572 
4573  RASTER_DEBUGF(5, "qle, head, tail = %p, %p, %p", qle, qll->head, qll->tail);
4574 
4575  }
4576  }
4577  else {
4578  qle = qll->head;
4579  while (NULL != qle) {
4580  if (qle->value > value) {
4581  qle->count++;
4582  qll->sum1++;
4583  qll->sum2 = qll->sum1 - qll->tail->count;
4584  RASTER_DEBUGF(4, "incremented count of %f by 1 to %d", qle->value, qle->count);
4585  break;
4586  }
4587 
4588  qle = qle->next;
4589  }
4590  }
4591  }
4592 
4593  RASTER_DEBUGF(5, "sum2, tau = %d, %d", qll->sum2, qll->tau);
4594  if (qll->sum2 >= qll->tau) {
4595  /* AL-GEQ */
4596  if (qll->algeq) {
4597  RASTER_DEBUGF(4, "deleting first element %f from list", qll->head->value);
4598 
4599  if (NULL != qll->head->next) {
4600  qle = qll->head->next;
4601  qll->sum1 -= qll->head->count;
4602  qll->sum2 = qll->sum1 - qle->count;
4603  quantile_llist_index_delete(qll, qll->head);
4605  qll->head = qle;
4606  qll->count--;
4607 
4608  quantile_llist_index_update(qll, NULL, 0);
4609  }
4610  else {
4612  qll->head = NULL;
4613  qll->tail = NULL;
4614  qll->sum1 = 0;
4615  qll->sum2 = 0;
4616  qll->count = 0;
4617 
4619  }
4620  }
4621  /* AL-GT */
4622  else {
4623  RASTER_DEBUGF(4, "deleting first element %f from list", qll->tail->value);
4624 
4625  if (NULL != qll->tail->prev) {
4626  qle = qll->tail->prev;
4627  qll->sum1 -= qll->tail->count;
4628  qll->sum2 = qll->sum1 - qle->count;
4629  quantile_llist_index_delete(qll, qll->tail);
4631  qll->tail = qle;
4632  qll->count--;
4633  }
4634  else {
4636  qll->head = NULL;
4637  qll->tail = NULL;
4638  qll->sum1 = 0;
4639  qll->sum2 = 0;
4640  qll->count = 0;
4641 
4643  }
4644  }
4645  }
4646 
4647  RASTER_DEBUGF(5, "qll after: (algeq, quantile, count, tau, sum1, sum2) = (%d, %f, %d, %d, %d, %d)",
4648  qll->algeq, qll->quantile, qll->count, qll->tau, qll->sum1, qll->sum2);
4649  RASTER_DEBUGF(5, "qll after: (head, tail) = (%p, %p)\n\n", qll->head, qll->tail);
4650  }
4651 
4652  }
4653  else {
4654  RASTER_DEBUGF(5, "skipping value at (x, y) = (%d, %d)", x, y);
4655  }
4656 
4657  z++;
4658  }
4659  }
4660 
4661  /* process quantiles */
4662  *rtn_count = *qlls_count / 2;
4663  rtn = rtalloc(sizeof(struct rt_quantile_t) * *rtn_count);
4664  if (NULL == rtn) return NULL;
4665 
4666  RASTER_DEBUGF(3, "returning %d quantiles", *rtn_count);
4667  for (i = 0, k = 0; i < *qlls_count; i++) {
4668  qll = &((*qlls)[i]);
4669 
4670  exists = 0;
4671  for (x = 0; x < k; x++) {
4672  if (FLT_EQ(qll->quantile, rtn[x].quantile)) {
4673  exists = 1;
4674  break;
4675  }
4676  }
4677  if (exists) continue;
4678 
4679  RASTER_DEBUGF(5, "qll: (algeq, quantile, count, tau, sum1, sum2) = (%d, %f, %d, %d, %d, %d)",
4680  qll->algeq, qll->quantile, qll->count, qll->tau, qll->sum1, qll->sum2);
4681  RASTER_DEBUGF(5, "qll: (head, tail) = (%p, %p)", qll->head, qll->tail);
4682 
4683  rtn[k].quantile = qll->quantile;
4684  rtn[k].has_value = 0;
4685 
4686  /* check that qll->head and qll->tail have value */
4687  if (qll->head == NULL || qll->tail == NULL)
4688  continue;
4689 
4690  /* AL-GEQ */
4691  if (qll->algeq)
4692  qle = qll->head;
4693  /* AM-GT */
4694  else
4695  qle = qll->tail;
4696 
4697  exists = 0;
4698  for (j = i + 1; j < *qlls_count; j++) {
4699  if (FLT_EQ((*qlls)[j].quantile, qll->quantile)) {
4700 
4701  RASTER_DEBUGF(5, "qlls[%d]: (algeq, quantile, count, tau, sum1, sum2) = (%d, %f, %d, %d, %d, %d)",
4702  j, (*qlls)[j].algeq, (*qlls)[j].quantile, (*qlls)[j].count, (*qlls)[j].tau, (*qlls)[j].sum1, (*qlls)[j].sum2);
4703  RASTER_DEBUGF(5, "qlls[%d]: (head, tail) = (%p, %p)", j, (*qlls)[j].head, (*qlls)[j].tail);
4704 
4705  exists = 1;
4706  break;
4707  }
4708  }
4709 
4710  /* weighted average for quantile */
4711  if (exists) {
4712  if ((*qlls)[j].algeq) {
4713  rtn[k].value = ((qle->value * qle->count) + ((*qlls)[j].head->value * (*qlls)[j].head->count)) / (qle->count + (*qlls)[j].head->count);
4714  RASTER_DEBUGF(5, "qlls[%d].head: (value, count) = (%f, %d)", j, (*qlls)[j].head->value, (*qlls)[j].head->count);
4715  }
4716  else {
4717  rtn[k].value = ((qle->value * qle->count) + ((*qlls)[j].tail->value * (*qlls)[j].tail->count)) / (qle->count + (*qlls)[j].tail->count);
4718  RASTER_DEBUGF(5, "qlls[%d].tail: (value, count) = (%f, %d)", j, (*qlls)[j].tail->value, (*qlls)[j].tail->count);
4719  }
4720  }
4721  /* straight value for quantile */
4722  else {
4723  rtn[k].value = qle->value;
4724  }
4725  rtn[k].has_value = 1;
4726  RASTER_DEBUGF(3, "(quantile, value) = (%f, %f)\n\n", rtn[k].quantile, rtn[k].value);
4727 
4728  k++;
4729  }
4730 
4731  RASTER_DEBUG(3, "done");
4732  return rtn;
4733 }
uint64_t sum1
Definition: rt_api.h:2322
static void quicksort(double *left, double *right)
Definition: rt_api.c:183
void rtdealloc(void *mem)
Definition: rt_api.c:882
tuple data
Definition: ovdump.py:103
double quantile
Definition: rt_api.h:2311
struct quantile_llist_element * prev
Definition: rt_api.h:2330
void * rt_band_get_data(rt_band band)
Get pointer to raster band data.
Definition: rt_api.c:1710
double quantile
Definition: rt_api.h:2303
uint16_t height
Definition: rt_api.h:2242
static void quantile_llist_index_reset(struct quantile_llist *qll)
Definition: rt_api.c:4118
int rt_band_get_isnodata_flag(rt_band band)
Get isnodata flag value.
Definition: rt_api.c:2042
double value
Definition: rt_api.h:2304
struct quantile_llist_element * next
Definition: rt_api.h:2331
#define RASTER_DEBUG(level, msg)
Definition: rt_api.h:281
struct quantile_llist_element * tail
Definition: rt_api.h:2315
#define RASTER_DEBUGF(level, msg,...)
Definition: rt_api.h:285
uint64_t tau
Definition: rt_api.h:2312
rt_errorstate rt_band_get_pixel(rt_band band, int x, int y, double *value, int *nodata)
Get pixel value.
Definition: rt_api.c:2549
int count
Definition: genraster.py:57
uint32_t index_max
Definition: rt_api.h:2320
static int quantile_llist_delete(struct quantile_llist_element *element)
Definition: rt_api.c:4002
#define FLT_EQ(x, y)
Definition: rt_api.h:2159
uint16_t width
Definition: rt_api.h:2241
tuple x
Definition: pixval.py:53
static struct quantile_llist_element * quantile_llist_search(struct quantile_llist_element *element, double needle)
Definition: rt_api.c:3927
void * rtalloc(size_t size)
Raster core memory management functions.
Definition: rt_api.c:867
void rterror(const char *fmt,...)
Raster core error and info handlers.
Definition: rt_api.c:895
static void quantile_llist_index_delete(struct quantile_llist *qll, struct quantile_llist_element *qle)
Definition: rt_api.c:4066
static struct quantile_llist_element * quantile_llist_insert(struct quantile_llist_element *element, double value, uint32_t *idx)
Definition: rt_api.c:3943
struct quantile_llist_index * index
Definition: rt_api.h:2319
uint32_t has_value
Definition: rt_api.h:2305
static void quantile_llist_index_update(struct quantile_llist *qll, struct quantile_llist_element *qle, uint32_t idx)
Definition: rt_api.c:4045
uint8_t algeq
Definition: rt_api.h:2310
uint32_t count
Definition: rt_api.h:2316
static struct quantile_llist_element * quantile_llist_index_search(struct quantile_llist *qll, double value, uint32_t *index)
Definition: rt_api.c:4083
struct quantile_llist_element * head
Definition: rt_api.h:2314
int rt_band_get_hasnodata_flag(rt_band band)
Get hasnodata flag value.
Definition: rt_api.c:2002
tuple y
Definition: pixval.py:54
#define ROUND(x, y)
Definition: rt_api.h:2166
uint64_t sum2
Definition: rt_api.h:2323

Here is the call graph for this function:

Here is the caller graph for this function: