/* ex: set ai ts=2 et: */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/*
 * here is an example of how to determine the minimal work necessary to
 * update a list of items after one has been removed. in this case, we
 * must do work on all items that occur AFTER any that have been flagged
 * for deletion.
 * the goal of this example is algorithmic efficiency.
 */


static struct cell {
  char name[8]; /* our data, what we are sorted on */
  unsigned isflagged, /* are we flagged for deletion? */
           flagcnt; /* if we're not flagged for deletion, how many before us are? */
} Slots[8];

static unsigned N = 0;

/* initialize a single cell */
void init1(unsigned idx)
{
  snprintf(Slots[idx].name, sizeof Slots[idx].name, "%c%c",
    'A' + (int)(rand() % 25),
    '0' + (int)(rand() % 8)); /* random name */
  Slots[idx].isflagged = 0;
  Slots[idx].flagcnt = 0;
}

/* randomly flag 0+ items for deletion */
void flag(void)
{
  unsigned i;
  for (i = 0; i < sizeof Slots / sizeof Slots[0]; i++)
    if (rand() % 100 > 70)
      Slots[i].isflagged = 1;
}

static int cellcmp(const void *va, const void *vb)
{
  const struct cell *a = va, *b = vb;
  return strcmp(a->name, b->name);
}

/* print state of cells */
void display(void)
{
  unsigned i;
  printf("N=%u ", N);
  for (i = 0; i < N; i++) {
    printf("[%2u:%s%s%s(%u)] ",
      i, Slots[i].name,
      (Slots[i].isflagged ? "!" : ""),
      (Slots[i].flagcnt ? "*" : ""),
      Slots[i].flagcnt);
  }
  printf("\n");
}

/* zero or more cells have been flagged for deletion, calculate
 * which cells need work based on their sort pos */
void deal_with_update(void)
{
  unsigned i, n,
           flagpos, flagcnt = 0;
  for (i = 0; i < N; i++) {
    if (Slots[i].isflagged) {
      if (0 == flagcnt++)
        flagpos = i;
    } else {
      Slots[i].flagcnt = flagcnt;
    }
  }
  printf("before: "); display(); 
  if (0 == flagcnt) {
    printf("\n");
    return; /* no change */
  }
  /* delete flagged cells */
  for (i = flagpos; i < N; i++) {
    if (Slots[i].isflagged)
      continue;/* shift non-flagged cell forward */
    memcpy(Slots + i - Slots[i].flagcnt, Slots + i, sizeof Slots[i]);
  }
  N -= flagcnt; /* adjust global count */
  qsort(Slots, N, sizeof Slots[0], cellcmp);
  printf("after: "); display(); printf("\n");
}

int main(void)
{
  unsigned i;
  srand((int)time(NULL));

  N = (unsigned)(sizeof Slots / sizeof Slots[0]);;
  for (i = 0; i < N; i++)
    init1(i);
  qsort(Slots, N, sizeof Slots[0], cellcmp);

  printf("inited: "); display();
  for (i = 0; i < 3; i++) {
    flag();
    deal_with_update();
  }
  return 0;
}