funnysort.c

   1 /* funnysort.c */
   2 #include <stdio.h>
   3 #include <assert.h>
   4 #include <stdlib.h>
   5 #include <pthread.h>
   6 #include <unistd.h>
   7 #include <stdbool.h>
   8 #include <signal.h>
   9
  10 #include "congl.h"
  11
  12 #define WIDTH 50
  13 #define HEIGHT 30
  14 #define NCYCLES 1000000
  15 #define SLEEP_TIME 0
  16 #define SORTER_MOVE_TRIES 100
  17 #define FREE_PER_ITEM 50
  18
  19 typedef enum {A=0, EMPTY, SORTER} item_t;
  20
  21 struct board_s {
  22     unsigned int width;
  23     unsigned int height;
  24     bool size_valid;
  25     item_t **surface;
  26     bool surface_valid;
  27 };
  28 typedef struct board_s board_t;
  29
  30 struct sorter_s {
  31         unsigned int line;
  32         unsigned int column;
  33 };
  34 typedef struct sorter_s sorter_t;
  35
  36 void count_item (board_t *, item_t *, unsigned int *);
  37 void drop_item (unsigned int, unsigned int, board_t *, item_t *);
  38 void erase_board (board_t *);
  39 void fetch_item(unsigned int, unsigned int, item_t *);
  40 void finish_board(board_t *);
  41 void move_sorter (board_t *, sorter_t *);
  42 void peek_item (unsigned int, unsigned int, board_t *, item_t *);
  43 void pick_item (unsigned int, unsigned int, board_t *, item_t *);
  44 void poke_item (unsigned int, unsigned int, board_t *, item_t);
  45 void print_board (board_t *);
  46 void print_item (unsigned int, unsigned int, item_t);
  47 void launch_sorter (board_t *);
  48 void setup_board(board_t *);
  49
  50 /* Erase the output medium. */
  51 void erase_board (board_t *board)
  52 {
  53         conglReset();
  54         conglClearScreen();
  55 }
  56
  57 void move_sorter(board_t *board, sorter_t *sorter)
  58 {
  59         assert(sorter != NULL);
  60         assert(sorter->line < HEIGHT);
  61         assert(sorter->column < WIDTH);
  62
  63         int h, v;
  64         unsigned int newcolumn, newline;
  65         unsigned int ncycles;
  66         item_t item, sorter_item;
  67
  68         ncycles = 0;
  69         do {
  70                 /* Select random displacement. */
  71                 h = random()%3 - 1;
  72                 v = random()%3 - 1;
  73
  74                 newcolumn = (sorter->column + (h+WIDTH)) % WIDTH;
  75                 newline = (sorter->line + (v+HEIGHT)) % HEIGHT;
  76
  77                 peek_item(newcolumn, newline, board, &item);
  78                 ++ncycles;
  79         } while ((item != EMPTY) && (ncycles < SORTER_MOVE_TRIES));
  80
  81         /* If sorter failed to move, respawn in random position */
  82         if (ncycles == SORTER_MOVE_TRIES) {
  83                 do {
  84                         newcolumn = random()%WIDTH;
  85                         newline = random()%HEIGHT;
  86                         peek_item(newcolumn, newline, board, &item);
  87                 } while (item != EMPTY);
  88         }
  89
  90         /* Update board. */
  91
  92         /* Don't reset the item if sorter just droped one. */
  93         /* If an item was droped, it will be different of SORTER. */
  94         peek_item(sorter->column, sorter->line, board, &sorter_item);
  95         if (sorter_item == SORTER) {
  96                 poke_item (sorter->column, sorter->line, board, EMPTY);
  97         }
  98         poke_item(newcolumn, newline, board, SORTER);
  99         sorter->column = newcolumn;
 100         sorter->line = newline;
 101
 102         assert(sorter->line < HEIGHT);
 103         assert(sorter->column < WIDTH);
 104 }
 105
 106 void launch_sorter (board_t *board)
 107 {
 108         int itera;
 109         item_t item;
 110         unsigned int column;
 111         unsigned int line;
 112         sorter_t sorter;
 113
 114         /* Place sorter in some free position. */
 115         do {
 116                 column = random()%WIDTH;
 117                 line = random()%HEIGHT;
 118                 peek_item(column, line, board, &item);
 119         } while (item != EMPTY);
 120         poke_item(column, line, board, SORTER);
 121         sorter.column = column;
 122         sorter.line = line;
 123
 124         for (itera = 0; itera <= NCYCLES; ++itera) {
 125         //for (itera = 0; 0==0; ++itera) {
 126                 do {
 127                         move_sorter(board, &sorter);
 128                         pick_item(sorter.column, sorter.line, board, &item);
 129                         usleep(SLEEP_TIME);
 130                 } while (item == EMPTY);
 131
 132                 /* because the sorter allways moves, if it drops the item it will not
 133                  * remain on the top of it */
 134                 while (item != EMPTY) {
 135                         drop_item(sorter.column, sorter.line, board, &item);
 136                         move_sorter(board, &sorter);
 137                         usleep(SLEEP_TIME);
 138                 }
 139
 140                 /* leave the premisses */
 141                 //for (r = 0; (r < 10); ++r) {
 142                 //      move(board, sorter);
 143                 //}
 144         }
 145 }
 146
 147 /* Try to pick an item. Don't pick other sorters :) */
 148 void pick_item (unsigned int column, unsigned int line, board_t *board, item_t *item)
 149 {
 150         assert (board != NULL);
 151         assert (board->size_valid);
 152         assert (board->surface_valid);
 153         assert (column < board->width);
 154         assert (line < board->height);
 155         assert (item != NULL);
 156         assert (*item == EMPTY);
 157
 158         int newcolumn, newline;
 159         item_t newitem;
 160         int h, v; /* h: horizontal; v: vertical */
 161
 162         for (h = -1; (h <= 1) && (*item == EMPTY); ++h) {
 163                 for (v = -1; (v <= 1) && (*item == EMPTY); ++v) {
 164                         /* newcolumn and newline need to be allawys positive */
 165                         newcolumn = (column+(h+WIDTH))%WIDTH;
 166                         newline = (line+(v+HEIGHT))%HEIGHT;
 167
 168                         //pthread_mutex_lock(&(tabuleiro.mutex[newcolumn][newline]));
 169                         peek_item(newcolumn, newline, board, &newitem);
 170                         if((newitem != EMPTY) && (newitem != SORTER)) {
 171                                 *item = newitem;
 172                                 poke_item(newcolumn, newline, board, EMPTY);
 173                                 //pthread_mutex_unlock(&(tabuleiro.mutex[newcolumn][newline]));
 174                                 /* we have the item */
 175                         }
 176                         //pthread_mutex_unlock(&(tabuleiro.mutex[newcolumn][newline]));
 177                 }
 178         }
 179
 180         /* we either pick an item or leave it as it is */
 181         assert ((*item == newitem) || (*item == EMPTY));
 182         assert (*item != SORTER);
 183 }
 184
 185 /* Try to drop one item. The item needs to be droped in a position adjacent to
 186  * a similar item.
 187  */
 188 void drop_item (unsigned int column, unsigned int line, board_t *board, item_t *item)
 189 {
 190         assert (board != NULL);
 191         assert (board->size_valid);
 192         assert (board->surface_valid);
 193         assert (column < board->width);
 194         assert (line < board->height);
 195         assert (item != NULL);
 196         assert (*item != EMPTY);
 197         assert (*item != SORTER);
 198
 199         int newcolumn, newline;
 200         int h, v; /* h: horizontal, v: vertical */
 201         item_t newitem;
 202
 203         for (h = -1; (h <= 1) && (*item != EMPTY); ++h) {
 204                 for (v = -1; (v <= 1) && (*item != EMPTY); ++v) {
 205                         /* newcolumn and newline need to be allawys positive */
 206                         newcolumn = (column+h+WIDTH)%WIDTH;
 207                         newline = (line+v+HEIGHT)%HEIGHT;
 208
 209                         //pthread_mutex_lock(&(tabuleiro.mutex[xnovo][ynovo]));
 210                         peek_item(newcolumn, newline, board, &newitem);
 211                         if(newitem == *item) {
 212                                 poke_item(column, line, board, newitem);
 213                                 *item = EMPTY;
 214                                 /* and the item is down */
 215                         }
 216                         //pthread_mutex_unlock(&(tabuleiro.mutex[xnovo][ynovo]));
 217                 }
 218         }
 219         //pthread_mutex_unlock(&(tabuleiro.mutex[column][line]));
 220 }
 221
 222 /* Print the base of the board, without any items. */
 223 void print_board(board_t *board)
 224 {
 225         assert(board->size_valid);
 226         assert(board->surface_valid);
 227
 228         conglClearScreen();
 229         conglMoveCursor(1, 1);
 230 }
 231
 232 void print_item(unsigned int column, unsigned int line, item_t item)
 233 {
 234         struct properties_s {
 235                 conglColor_t bg;
 236                 conglColor_t fg;
 237                 char symbol;
 238         };
 239         typedef struct properties_s properties_t;
 240
 241         properties_t properties[] = {
 242                 {congl_magenta, congl_white, ' '},
 243                 {congl_green, congl_white, ' '},
 244                 {congl_black, congl_white, ' '}
 245         //{'i'}, {'f'}, {'s'}
 246         };
 247
 248         properties_t p;
 249
 250         p = properties[item];
 251         conglDrawCharFull(column+1, line+1, p.symbol, p.fg, p.bg);
 252
 253         //printf("%c: %d,%d\n", p.symbol, line, column);
 254 }
 255
 256 /* Read an item from the board. */
 257 void peek_item (unsigned int column, unsigned int line, board_t *board, item_t *item)
 258 {
 259         assert(board != NULL);
 260         assert(board->size_valid);
 261         assert(board->surface_valid);
 262         assert(line < board->height);
 263         assert(column < board->width);
 264         assert(item != NULL);
 265
 266         *item = board->surface[line][column];
 267
 268         assert(*item == board->surface[line][column]);
 269 }
 270
 271 /* Write an item in position (line,column) of the board. At the same time update
 272  * any output medium.
 273  */
 274 void poke_item (unsigned int column, unsigned int line, board_t *board, item_t item)
 275 {
 276         assert(board != NULL);
 277         assert(board->size_valid);
 278         assert(board->surface_valid);
 279         assert(line < board->height);
 280         assert(column < board->width);
 281
 282         board->surface[line][column] = item;
 283
 284         print_item (column, line, item);
 285
 286         assert(board->surface[line][column] == item);
 287 }
 288
 289 /* Fetch an item from somewhere. The purpose of this functin is to allow the
 290  * user to load one pattern every time the program runs. For now all items are
 291  * random (sort of).
 292  */
 293 void fetch_item(unsigned int column, unsigned int line, item_t *item)
 294 {
 295         assert(item != NULL);
 296
 297         int number;
 298
 299         /* generate one block in every FREE_PER_ITEM board cells */
 300         number = random()%FREE_PER_ITEM;
 301         switch (number) {
 302                 case 0:
 303                         *item = A;
 304                         break;
 305                 default:
 306                         *item = EMPTY;
 307                         break;
 308         }
 309 }
 310 void setup_board(board_t *board)
 311 {
 312     assert (board->size_valid);
 313         assert (!board->surface_valid);
 314
 315         unsigned int line, column;
 316         item_t item;
 317
 318         //printf("Preparing board.\n");
 319
 320         /* allocate space for the board */
 321         board->surface = calloc (board->height, sizeof(board->surface));
 322         if (board->surface == NULL) {
 323                 perror("board_setup");
 324                 return;
 325         }
 326         for (line = 0; line < board->height; ++line) {
 327                 board->surface[line] = calloc (board->width, sizeof(item_t));
 328                 if (board->surface[line] == NULL) {
 329                         perror("board_setup");
 330                         return;
 331                 }
 332         }
 333         board->surface_valid = true;
 334
 335         //printf("Printing board.\n");
 336         print_board(board);
 337         //printf("Board printed.\n");
 338
 339         /* fill the board with initial values */
 340         for (line = 0; line < board->height; ++line) {
 341                 for (column = 0; column < board->width; ++column) {
 342                         fetch_item(line, column, &item);
 343                         poke_item(column, line, board, item);
 344                 }
 345         }
 346
 347     assert (board->surface_valid);
 348 }
 349
 350 void finish_board (board_t *board)
 351 {
 352         assert (board->surface_valid);
 353
 354         int line;
 355
 356         for (line = 0; line < board->height; ++line) {
 357                 free (board->surface[line]);
 358         }
 359         free (board->surface);
 360         board->surface_valid = false;
 361
 362         erase_board(board);
 363
 364         assert (!board->surface_valid);
 365 }
 366
 367 void count_items(board_t *board, item_t *item, unsigned int *nitems)
 368 {
 369         assert (board != NULL);
 370         assert (item != NULL);
 371         assert (nitems != NULL);
 372
 373         unsigned int column, line;
 374         item_t this_item;
 375         unsigned int count;
 376
 377         count = 0;
 378         for (line = 0; line < board->height; ++line) {
 379                 for (column = 0; column < board->width; ++column) {
 380                         peek_item(column, line, board, &this_item);
 381                         if (this_item == *item) count++;
 382                 }
 383         }
 384
 385         *nitems = count;
 386 }
 387
 388 int main (int argc, char *argv[])
 389 {
 390     board_t board;
 391         unsigned int nitems_begin, nitems_finish;
 392         item_t item;
 393
 394     board.width = WIDTH;
 395     board.height = HEIGHT;
 396     board.size_valid = true;
 397         board.surface_valid = false;
 398
 399         /* intialize random number generator */
 400         srandom((unsigned int)time(NULL));
 401
 402         setup_board (&board);
 403         sleep(1);
 404
 405         item = A;
 406         count_items(&board, &item, &nitems_begin);
 407
 408         /* launch sorters */
 409         launch_sorter(&board);
 410
 411         count_items(&board, &item, &nitems_finish);
 412
 413         /* make shure the sorter isn't eating items */
 414         assert(nitems_begin == nitems_finish);
 415
 416         finish_board (&board);
 417
 418         printf("All good.\n");
 419
 420         exit(0);
 421 }
 422