# HG changeset patch # User Mike Becker # Date 1740927984 -3600 # Node ID 2c8514b3891bef654e674dadba1f52776184cb67 # Parent 98adda6171d1b9c8de582caa838b856beb5640a7 add number highlighting fixes #393 diff -r 98adda6171d1 -r 2c8514b3891b src/highlighter.c --- a/src/highlighter.c Sun Mar 02 12:47:31 2025 +0100 +++ b/src/highlighter.c Sun Mar 02 16:06:24 2025 +0100 @@ -75,6 +75,107 @@ return 1; } +static size_t check_number(const char *str) { + /* this function is not precise, but a good over-approximation */ + size_t i = 0; + if (str[0] == '+' || str[0] == '-') { + i++; + } + bool hex = str[i] == '0' && (str[i + 1] == 'x' || str[i + 1] == 'X'); + bool bin = str[i] == '0' && (str[i + 1] == 'b' || str[i + 1] == 'B'); + if (hex || bin) { + i += 2; + } + bool flt = false; + bool exp = false; + bool dot = false; + bool digit_seen = false; + if (str[i] == '.') { + dot = true; + flt = true; + i++; + } + char exp_char_low = hex ? 'p' : 'e'; + char exp_char_up = hex ? 'P' : 'E'; + while (str[i] != '\0' && str[i] != '\n') { + /* ignore grouping char */ + if (str[i] == '\'') { + i++; + continue; + } + /* binary is always integer, nothing else allowed */ + if (bin) { + if (str[i] != '0' && str[i] != '1') { + break; + } else { + i++; + digit_seen = true; + } + } else { + /* detect decimal and exponent separators */ + if ((!dot && str[i] == '.') || + (!exp && digit_seen && + (str[i] == exp_char_low || str[i] == exp_char_up) + ) + ) { + if (str[i] == '.') { + dot = true; + } else { + exp = true; + /* a sign may directly follow */ + if (str[i+1] == '+' || str[i+1] == '-') { + i++; + } + } + flt = true; + i++; + continue; + } + /* check for allowed digits */ + if ((str[i] >= '0' && str[i] <= '9') || (hex && ( + (str[i] >= 'a' && str[i] <= 'f') + || (str[i] >= 'A' && str[i] <= 'F') + ))) { + digit_seen = true; + i++; + } else { + break; + } + } + } + /* have we seen at least one digit? */ + if (!digit_seen) return 0; + + /* check if we are already done (over-approximation) */ + if (!isalpha(str[i])) return i; + + /* check suffixes (must check with decreasing length) */ + const char *const flt_suffixes[] = { + "f128", "bf16", "F128", "BF16", + "f16", "f32", "f64", "F16", "F32", "F64", + "df", "DF", "dd", "DD", "dl", "DL", + "d", "D", "f", "l", "F", "L", + }; + const unsigned flt_suffixes_len = 22; + const char *const int_suffixes[] = { + "ull", "ULL", + "ul", "UL", "ll", "LL", "wb", "WB", + "u", "U", "l", "L", + }; + const unsigned int_suffixes_len = 12; + const char * const *allowed_suffixes = flt ? flt_suffixes : int_suffixes; + const unsigned allowed_suffixes_len = flt ? flt_suffixes_len : int_suffixes_len; + for (unsigned j = 0 ; j < allowed_suffixes_len ; j++) { + cxstring suffix = cx_str(allowed_suffixes[j]); + const char *testee = str+i; + if (memcmp(testee, suffix.ptr, suffix.length) == 0) { + return i+suffix.length; + } + } + /* no suffix matched */ + return 0; +} + /* Plaintext Highlighter */ void c2html_plain_highlighter(char const *src, CxBuffer *dest, @@ -246,6 +347,22 @@ } else { if (isstring) { put_htmlescaped(dest, c); + } else if (wbuf->size == 0 && + (isdigit(c) || c == '+' || c == '-' || c == '.') + ) { + /* might be a number */ + size_t numlen = check_number(src+sp); + if (numlen > 0) { + start_span("number"); + put_htmlescapedstr(dest, cx_strn(src+sp, numlen)); + stop_span; + sp += numlen - 1; + c = src[sp]; + continue; + } else { + /* start a new buffered word */ + cxBufferPut(wbuf, c); + } } else if (isalnum(c) || c == '_' || c == '#') { /* buffer the current word */ cxBufferPut(wbuf, c); @@ -271,8 +388,14 @@ if (closespan) { stop_span; } + + /* reset word buffer */ + wbuf->pos = wbuf->size = 0; + + /* re-test current char */ + c = src[--sp]; + continue; } - wbuf->pos = wbuf->size = 0; /* reset word buffer */ /* write current character */ put_htmlescaped(dest, c); @@ -367,6 +490,23 @@ } else { if (isstring) { put_htmlescaped(dest, c); + } else if (wbuf->size == 0 && + (isdigit(c) || c == '+' || c == '-' || c == '.') + ) { + /* might be a number */ + size_t numlen = check_number(src+sp); + if (numlen > 0) { + cxBufferPutString(dest, + ""); + put_htmlescapedstr(dest, cx_strn(src+sp, numlen)); + cxBufferPutString(dest, ""); + sp += numlen - 1; + c = src[sp]; + continue; + } else { + /* start a new buffered word */ + cxBufferPut(wbuf, c); + } } else if (isalnum(c) || c == '_' || c == '@') { /* buffer the current word */ cxBufferPut(wbuf, c); @@ -395,8 +535,14 @@ if (closespan) { cxBufferPutString(dest, ""); } + + /* reset word buffer */ + wbuf->pos = wbuf->size = 0; + + /* re-test current char */ + c = src[--sp]; + continue; } - wbuf->pos = wbuf->size = 0; /* reset buffer */ /* write current character */ put_htmlescaped(dest, c); diff -r 98adda6171d1 -r 2c8514b3891b test/gs/bigtest.html --- a/test/gs/bigtest.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/gs/bigtest.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; } @@ -98,15 +101,15 @@ 45 } 46 47 void gamestate_init(GameState *gamestate) { - 48 memset(gamestate, 0, sizeof(GameState)); + 48 memset(gamestate, 0, sizeof(GameState)); 49 50 Board initboard = { 51 {WROOK, WKNIGHT, WBISHOP, WQUEEN, WKING, WBISHOP, WKNIGHT, WROOK}, 52 {WPAWN, WPAWN, WPAWN, WPAWN, WPAWN, WPAWN, WPAWN, WPAWN}, - 53 {0, 0, 0, 0, 0, 0, 0, 0}, - 54 {0, 0, 0, 0, 0, 0, 0, 0}, - 55 {0, 0, 0, 0, 0, 0, 0, 0}, - 56 {0, 0, 0, 0, 0, 0, 0, 0}, + 53 {0, 0, 0, 0, 0, 0, 0, 0}, + 54 {0, 0, 0, 0, 0, 0, 0, 0}, + 55 {0, 0, 0, 0, 0, 0, 0, 0}, + 56 {0, 0, 0, 0, 0, 0, 0, 0}, 57 {BPAWN, BPAWN, BPAWN, BPAWN, BPAWN, BPAWN, BPAWN, BPAWN}, 58 {BROOK, BKNIGHT, BBISHOP, BQUEEN, BKING, BBISHOP, BKNIGHT, BROOK} 59 }; @@ -128,21 +131,21 @@ 75 char *string = move->string; 76 77 /* at least 8 characters should be available, wipe them out */ - 78 memset(string, 0, 8); + 78 memset(string, 0, 8); 79 80 /* special formats for castling */ 81 if ((move->piece&PIECE_MASK) == KING && - 82 abs(move->tofile-move->fromfile) == 2) { + 82 abs(move->tofile-move->fromfile) == 2) { 83 if (move->tofile==fileidx('c')) { - 84 memcpy(string, "O-O-O", 5); + 84 memcpy(string, "O-O-O", 5); 85 } else { - 86 memcpy(string, "O-O", 3); + 86 memcpy(string, "O-O", 3); 87 } 88 } 89 90 /* start by notating the piece character */ - 91 string[0] = getpiecechr(move->piece); - 92 int idx = string[0] ? 1 : 0; + 91 string[0] = getpiecechr(move->piece); + 92 int idx = string[0] ? 1 : 0; 93 94 /* find out how many source information we do need */ 95 uint8_t piece = move->piece & PIECE_MASK; @@ -151,13 +154,13 @@ 98 string[idx++] = filechr(move->fromfile); 99 } 100 } else if (piece != KING) { -101 Move threats[16]; +101 Move threats[16]; 102 uint8_t threatcount; 103 get_real_threats(gamestate, move->torow, move->tofile, 104 move->piece&COLOR_MASK, threats, &threatcount); -105 if (threatcount > 1) { -106 int ambrows = 0, ambfiles = 0; -107 for (uint8_t i = 0 ; i < threatcount ; i++) { +105 if (threatcount > 1) { +106 int ambrows = 0, ambfiles = 0; +107 for (uint8_t i = 0 ; i < threatcount ; i++) { 108 if (threats[i].fromrow == move->fromrow) { 109 ambrows++; 110 } @@ -166,11 +169,11 @@ 113 } 114 } 115 /* ambiguous row, name file */ -116 if (ambrows > 1) { +116 if (ambrows > 1) { 117 string[idx++] = filechr(move->fromfile); 118 } 119 /* ambiguous file, name row */ -120 if (ambfiles > 1) { +120 if (ambfiles > 1) { 121 string[idx++] = filechr(move->fromrow); 122 } 123 } @@ -213,7 +216,7 @@ 160 uint64_t sec = curtimestamp.tv_sec - lasttstamp->tv_sec; 161 suseconds_t micros; 162 if (curtimestamp.tv_usec < lasttstamp->tv_usec) { -163 micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec); +163 micros = 1e6L-(lasttstamp->tv_usec - curtimestamp.tv_usec); 164 sec--; 165 } else { 166 micros = curtimestamp.tv_usec - lasttstamp->tv_usec; @@ -225,8 +228,8 @@ 172 gamestate->lastmove->next = elem; 173 gamestate->lastmove = elem; 174 } else { -175 elem->move.movetime.tv_usec = 0; -176 elem->move.movetime.tv_sec = 0; +175 elem->move.movetime.tv_usec = 0; +176 elem->move.movetime.tv_sec = 0; 177 gamestate->movelist = gamestate->lastmove = elem; 178 } 179 } @@ -249,7 +252,7 @@ 196 case 'B': return BISHOP; 197 case 'Q': return QUEEN; 198 case 'K': return KING; -199 default: return 0; +199 default: return 0; 200 } 201 } 202 @@ -259,25 +262,25 @@ 206 207 /* en passant capture */ 208 if (move->capture && piece == PAWN && -209 mdst(gamestate->board, move) == 0) { -210 gamestate->board[move->fromrow][move->tofile] = 0; +209 mdst(gamestate->board, move) == 0) { +210 gamestate->board[move->fromrow][move->tofile] = 0; 211 } 212 213 /* remove old en passant threats */ -214 for (uint8_t file = 0 ; file < 8 ; file++) { -215 gamestate->board[3][file] &= ~ENPASSANT_THREAT; -216 gamestate->board[4][file] &= ~ENPASSANT_THREAT; +214 for (uint8_t file = 0 ; file < 8 ; file++) { +215 gamestate->board[3][file] &= ~ENPASSANT_THREAT; +216 gamestate->board[4][file] &= ~ENPASSANT_THREAT; 217 } 218 219 /* add new en passant threat */ 220 if (piece == PAWN && ( -221 (move->fromrow == 1 && move->torow == 3) || -222 (move->fromrow == 6 && move->torow == 4))) { +221 (move->fromrow == 1 && move->torow == 3) || +222 (move->fromrow == 6 && move->torow == 4))) { 223 move->piece |= ENPASSANT_THREAT; 224 } 225 226 /* move (and maybe capture or promote) */ -227 msrc(gamestate->board, move) = 0; +227 msrc(gamestate->board, move) = 0; 228 if (move->promotion) { 229 mdst(gamestate->board, move) = move->promotion; 230 } else { @@ -288,16 +291,16 @@ 235 if (piece == KING && move->fromfile == fileidx('e')) { 236 237 if (move->tofile == fileidx('g')) { -238 gamestate->board[move->torow][fileidx('h')] = 0; +238 gamestate->board[move->torow][fileidx('h')] = 0; 239 gamestate->board[move->torow][fileidx('f')] = color|ROOK; 240 } else if (move->tofile == fileidx('c')) { -241 gamestate->board[move->torow][fileidx('a')] = 0; +241 gamestate->board[move->torow][fileidx('a')] = 0; 242 gamestate->board[move->torow][fileidx('d')] = color|ROOK; 243 } 244 } 245 246 if (!simulate) { -247 if (!move->string[0]) { +247 if (!move->string[0]) { 248 format_move(gamestate, move); 249 } 250 } @@ -306,7 +309,7 @@ 253 } 254 255 void apply_move(GameState *gamestate, Move *move) { -256 apply_move_impl(gamestate, move, 0); +256 apply_move_impl(gamestate, move, 0); 257 } 258 259 static int validate_move_rules(GameState *gamestate, Move *move) { @@ -333,8 +336,8 @@ 280 } 281 282 /* must capture, if and only if destination is occupied */ -283 if ((mdst(gamestate->board, move) == 0 && move->capture) || -284 (mdst(gamestate->board, move) != 0 && !move->capture)) { +283 if ((mdst(gamestate->board, move) == 0 && move->capture) || +284 (mdst(gamestate->board, move) != 0 && !move->capture)) { 285 return INVALID_MOVE_SYNTAX; 286 } 287 @@ -383,9 +386,9 @@ 330 /* find kings for check validation */ 331 uint8_t piececolor = (move->piece & COLOR_MASK); 332 -333 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0; -334 for (uint8_t row = 0 ; row < 8 ; row++) { -335 for (uint8_t file = 0 ; file < 8 ; file++) { +333 uint8_t mykingfile = 0, mykingrow = 0, opkingfile = 0, opkingrow = 0; +334 for (uint8_t row = 0 ; row < 8 ; row++) { +335 for (uint8_t file = 0 ; file < 8 ; file++) { 336 if (gamestate->board[row][file] == 337 (piececolor == WHITE?WKING:BKING)) { 338 mykingfile = file; @@ -401,7 +404,7 @@ 348 /* simulate move for check validation */ 349 GameState simulation = gamestate_copy_sim(gamestate); 350 Move simmove = *move; -351 apply_move_impl(&simulation, &simmove, 1); +351 apply_move_impl(&simulation, &simmove, 1); 352 353 /* don't move into or stay in check position */ 354 if (is_covered(&simulation, mykingrow, mykingfile, @@ -418,17 +421,17 @@ 365 } 366 367 /* correct check and checkmate flags (move is still valid) */ -368 Move threats[16]; +368 Move threats[16]; 369 uint8_t threatcount; 370 move->check = get_threats(&simulation, opkingrow, opkingfile, 371 piececolor, threats, &threatcount); 372 373 if (move->check) { 374 /* determine possible escape fields */ -375 _Bool canescape = 0; -376 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) { -377 for (int df = -1 ; df <= 1 && !canescape ; df++) { -378 if (!(dr == 0 && df == 0) && +375 _Bool canescape = 0; +376 for (int dr = -1 ; dr <= 1 && !canescape ; dr++) { +377 for (int df = -1 ; df <= 1 && !canescape ; df++) { +378 if (!(dr == 0 && df == 0) && 379 isidx(opkingrow + dr) && isidx(opkingfile + df)) { 380 381 /* escape field neither blocked nor covered */ @@ -441,14 +444,14 @@ 388 } 389 } 390 /* can't escape, can he capture? */ -391 if (!canescape && threatcount == 1) { -392 canescape = is_attacked(&simulation, threats[0].fromrow, -393 threats[0].fromfile, opponent_color(piececolor)); +391 if (!canescape && threatcount == 1) { +392 canescape = is_attacked(&simulation, threats[0].fromrow, +393 threats[0].fromfile, opponent_color(piececolor)); 394 } 395 396 /* can't capture, can he block? */ -397 if (!canescape && threatcount == 1) { -398 Move *threat = &(threats[0]); +397 if (!canescape && threatcount == 1) { +398 Move *threat = &(threats[0]); 399 uint8_t threatpiece = threat->piece & PIECE_MASK; 400 401 /* knight, pawns and the king cannot be blocked */ @@ -456,7 +459,7 @@ 403 || threatpiece == QUEEN) { 404 if (threat->fromrow == threat->torow) { 405 /* rook aspect (on row) */ -406 int d = threat->tofile > threat->fromfile ? 1 : -1; +406 int d = threat->tofile > threat->fromfile ? 1 : -1; 407 uint8_t file = threat->fromfile; 408 while (!canescape && file != threat->tofile - d) { 409 file += d; @@ -465,7 +468,7 @@ 412 } 413 } else if (threat->fromfile == threat->tofile) { 414 /* rook aspect (on file) */ -415 int d = threat->torow > threat->fromrow ? 1 : -1; +415 int d = threat->torow > threat->fromrow ? 1 : -1; 416 uint8_t row = threat->fromrow; 417 while (!canescape && row != threat->torow - d) { 418 row += d; @@ -474,8 +477,8 @@ 421 } 422 } else { 423 /* bishop aspect */ -424 int dr = threat->torow > threat->fromrow ? 1 : -1; -425 int df = threat->tofile > threat->fromfile ? 1 : -1; +424 int dr = threat->torow > threat->fromrow ? 1 : -1; +425 int df = threat->tofile > threat->fromfile ? 1 : -1; 426 427 uint8_t row = threat->fromrow; 428 uint8_t file = threat->fromfile; @@ -491,7 +494,7 @@ 438 } 439 440 if (!canescape) { -441 gamestate->checkmate = 1; +441 gamestate->checkmate = 1; 442 } 443 } 444 @@ -502,13 +505,13 @@ 449 450 _Bool get_threats(GameState *gamestate, uint8_t row, uint8_t file, 451 uint8_t color, Move *threats, uint8_t *threatcount) { -452 Move candidates[32]; -453 int candidatecount = 0; -454 for (uint8_t r = 0 ; r < 8 ; r++) { -455 for (uint8_t f = 0 ; f < 8 ; f++) { +452 Move candidates[32]; +453 int candidatecount = 0; +454 for (uint8_t r = 0 ; r < 8 ; r++) { +455 for (uint8_t f = 0 ; f < 8 ; f++) { 456 if ((gamestate->board[r][f] & COLOR_MASK) == color) { 457 // non-capturing move -458 memset(&(candidates[candidatecount]), 0, sizeof(Move)); +458 memset(&(candidates[candidatecount]), 0, sizeof(Move)); 459 candidates[candidatecount].piece = gamestate->board[r][f]; 460 candidates[candidatecount].fromrow = r; 461 candidates[candidatecount].fromfile = f; @@ -518,24 +521,24 @@ 465 466 // capturing move 467 memcpy(&(candidates[candidatecount]), -468 &(candidates[candidatecount-1]), sizeof(Move)); -469 candidates[candidatecount].capture = 1; +468 &(candidates[candidatecount-1]), sizeof(Move)); +469 candidates[candidatecount].capture = 1; 470 candidatecount++; 471 } 472 } 473 } 474 475 if (threatcount) { -476 *threatcount = 0; +476 *threatcount = 0; 477 } 478 479 -480 _Bool result = 0; +480 _Bool result = 0; 481 -482 for (int i = 0 ; i < candidatecount ; i++) { +482 for (int i = 0 ; i < candidatecount ; i++) { 483 if (validate_move_rules(gamestate, &(candidates[i])) 484 == VALID_MOVE_SEMANTICS) { -485 result = 1; +485 result = 1; 486 if (threats && threatcount) { 487 threats[(*threatcount)++] = candidates[i]; 488 } @@ -548,9 +551,9 @@ 495 _Bool is_pinned(GameState *gamestate, Move *move) { 496 uint8_t color = move->piece & COLOR_MASK; 497 -498 uint8_t kingfile = 0, kingrow = 0; -499 for (uint8_t row = 0 ; row < 8 ; row++) { -500 for (uint8_t file = 0 ; file < 8 ; file++) { +498 uint8_t kingfile = 0, kingrow = 0; +499 for (uint8_t row = 0 ; row < 8 ; row++) { +500 for (uint8_t file = 0 ; file < 8 ; file++) { 501 if (gamestate->board[row][file] == (color|KING)) { 502 kingfile = file; 503 kingrow = row; @@ -572,17 +575,17 @@ 519 uint8_t color, Move *threats, uint8_t *threatcount) { 520 521 if (threatcount) { -522 *threatcount = 0; +522 *threatcount = 0; 523 } 524 -525 Move candidates[16]; +525 Move candidates[16]; 526 uint8_t candidatecount; 527 if (get_threats(gamestate, row, file, color, candidates, &candidatecount)) { 528 -529 _Bool result = 0; -530 uint8_t kingfile = 0, kingrow = 0; -531 for (uint8_t row = 0 ; row < 8 ; row++) { -532 for (uint8_t file = 0 ; file < 8 ; file++) { +529 _Bool result = 0; +530 uint8_t kingfile = 0, kingrow = 0; +531 for (uint8_t row = 0 ; row < 8 ; row++) { +532 for (uint8_t file = 0 ; file < 8 ; file++) { 533 if (gamestate->board[row][file] == (color|KING)) { 534 kingfile = file; 535 kingrow = row; @@ -590,13 +593,13 @@ 537 } 538 } 539 -540 for (uint8_t i = 0 ; i < candidatecount ; i++) { +540 for (uint8_t i = 0 ; i < candidatecount ; i++) { 541 GameState simulation = gamestate_copy_sim(gamestate); 542 Move simmove = candidates[i]; 543 apply_move(&simulation, &simmove); 544 if (!is_covered(&simulation, kingrow, kingfile, 545 opponent_color(color))) { -546 result = 1; +546 result = 1; 547 if (threats && threatcount) { 548 threats[(*threatcount)++] = candidates[i]; 549 } @@ -605,16 +608,16 @@ 552 553 return result; 554 } else { -555 return 0; +555 return 0; 556 } 557 } 558 559 static int getlocation(GameState *gamestate, Move *move) { 560 561 uint8_t color = move->piece & COLOR_MASK; -562 _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0; +562 _Bool incheck = gamestate->lastmove?gamestate->lastmove->move.check:0; 563 -564 Move threats[16], *threat = NULL; +564 Move threats[16], *threat = NULL; 565 uint8_t threatcount; 566 567 if (get_threats(gamestate, move->torow, move->tofile, color, @@ -623,7 +626,7 @@ 570 int reason = INVALID_POSITION; 571 572 // find threats for the specified position -573 for (uint8_t i = 0 ; i < threatcount ; i++) { +573 for (uint8_t i = 0 ; i < threatcount ; i++) { 574 if ((threats[i].piece & (PIECE_MASK | COLOR_MASK)) 575 == move->piece && 576 (move->fromrow == POS_UNSPECIFIED || @@ -657,120 +660,120 @@ 604 } 605 606 int eval_move(GameState *gamestate, char *mstr, Move *move, uint8_t color) { -607 memset(move, 0, sizeof(Move)); +607 memset(move, 0, sizeof(Move)); 608 move->fromfile = POS_UNSPECIFIED; 609 move->fromrow = POS_UNSPECIFIED; 610 611 size_t len = strlen(mstr); -612 if (len < 1 || len > 6) { +612 if (len < 1 || len > 6) { 613 return INVALID_MOVE_SYNTAX; 614 } 615 616 /* evaluate check/checkmate flags */ -617 if (mstr[len-1] == '+') { +617 if (mstr[len-1] == '+') { 618 len--; mstr[len] = '\0'; -619 move->check = 1; -620 } else if (mstr[len-1] == '#') { +619 move->check = 1; +620 } else if (mstr[len-1] == '#') { 621 len--; mstr[len] = '\0'; 622 /* ignore - validation should set game state */ 623 } 624 625 /* evaluate promotion */ -626 if (len > 3 && mstr[len-2] == '=') { -627 move->promotion = getpiece(mstr[len-1]); +626 if (len > 3 && mstr[len-2] == '=') { +627 move->promotion = getpiece(mstr[len-1]); 628 if (!move->promotion) { 629 return INVALID_MOVE_SYNTAX; 630 } else { 631 move->promotion |= color; -632 len -= 2; -633 mstr[len] = 0; +632 len -= 2; +633 mstr[len] = 0; 634 } 635 } 636 -637 if (len == 2) { +637 if (len == 2) { 638 /* pawn move (e.g. "e4") */ 639 move->piece = PAWN; -640 move->tofile = fileidx(mstr[0]); -641 move->torow = rowidx(mstr[1]); -642 } else if (len == 3) { -643 if (strcmp(mstr, "O-O") == 0) { +640 move->tofile = fileidx(mstr[0]); +641 move->torow = rowidx(mstr[1]); +642 } else if (len == 3) { +643 if (strcmp(mstr, "O-O") == 0) { 644 /* king side castling */ 645 move->piece = KING; 646 move->fromfile = fileidx('e'); 647 move->tofile = fileidx('g'); -648 move->fromrow = move->torow = color == WHITE ? 0 : 7; +648 move->fromrow = move->torow = color == WHITE ? 0 : 7; 649 } else { 650 /* move (e.g. "Nf3") */ -651 move->piece = getpiece(mstr[0]); -652 move->tofile = fileidx(mstr[1]); -653 move->torow = rowidx(mstr[2]); +651 move->piece = getpiece(mstr[0]); +652 move->tofile = fileidx(mstr[1]); +653 move->torow = rowidx(mstr[2]); 654 } -655 } else if (len == 4) { -656 move->piece = getpiece(mstr[0]); +655 } else if (len == 4) { +656 move->piece = getpiece(mstr[0]); 657 if (!move->piece) { 658 move->piece = PAWN; -659 move->fromfile = fileidx(mstr[0]); +659 move->fromfile = fileidx(mstr[0]); 660 } -661 if (mstr[1] == 'x') { +661 if (mstr[1] == 'x') { 662 /* capture (e.g. "Nxf3", "dxe5") */ -663 move->capture = 1; +663 move->capture = 1; 664 } else { 665 /* move (e.g. "Ndf3", "N2c3", "e2e4") */ -666 if (isfile(mstr[1])) { -667 move->fromfile = fileidx(mstr[1]); +666 if (isfile(mstr[1])) { +667 move->fromfile = fileidx(mstr[1]); 668 if (move->piece == PAWN) { -669 move->piece = 0; +669 move->piece = 0; 670 } 671 } else { -672 move->fromrow = rowidx(mstr[1]); +672 move->fromrow = rowidx(mstr[1]); 673 } 674 } -675 move->tofile = fileidx(mstr[2]); -676 move->torow = rowidx(mstr[3]); -677 } else if (len == 5) { -678 if (strcmp(mstr, "O-O-O") == 0) { +675 move->tofile = fileidx(mstr[2]); +676 move->torow = rowidx(mstr[3]); +677 } else if (len == 5) { +678 if (strcmp(mstr, "O-O-O") == 0) { 679 /* queen side castling "O-O-O" */ 680 move->piece = KING; 681 move->fromfile = fileidx('e'); 682 move->tofile = fileidx('c'); -683 move->fromrow = move->torow = color == WHITE ? 0 : 7; +683 move->fromrow = move->torow = color == WHITE ? 0 : 7; 684 } else { -685 move->piece = getpiece(mstr[0]); -686 if (mstr[2] == 'x') { -687 move->capture = 1; +685 move->piece = getpiece(mstr[0]); +686 if (mstr[2] == 'x') { +687 move->capture = 1; 688 if (move->piece) { 689 /* capture (e.g. "Ndxf3") */ -690 move->fromfile = fileidx(mstr[1]); +690 move->fromfile = fileidx(mstr[1]); 691 } else { 692 /* long notation capture (e.g. "e5xf6") */ 693 move->piece = PAWN; -694 move->fromfile = fileidx(mstr[0]); -695 move->fromrow = rowidx(mstr[1]); +694 move->fromfile = fileidx(mstr[0]); +695 move->fromrow = rowidx(mstr[1]); 696 } 697 } else { 698 /* long notation move (e.g. "Nc5a4") */ -699 move->fromfile = fileidx(mstr[1]); -700 move->fromrow = rowidx(mstr[2]); +699 move->fromfile = fileidx(mstr[1]); +700 move->fromrow = rowidx(mstr[2]); 701 } -702 move->tofile = fileidx(mstr[3]); -703 move->torow = rowidx(mstr[4]); +702 move->tofile = fileidx(mstr[3]); +703 move->torow = rowidx(mstr[4]); 704 } -705 } else if (len == 6) { +705 } else if (len == 6) { 706 /* long notation capture (e.g. "Nc5xf3") */ -707 if (mstr[3] == 'x') { -708 move->capture = 1; -709 move->piece = getpiece(mstr[0]); -710 move->fromfile = fileidx(mstr[1]); -711 move->fromrow = rowidx(mstr[2]); -712 move->tofile = fileidx(mstr[4]); -713 move->torow = rowidx(mstr[5]); +707 if (mstr[3] == 'x') { +708 move->capture = 1; +709 move->piece = getpiece(mstr[0]); +710 move->fromfile = fileidx(mstr[1]); +711 move->fromrow = rowidx(mstr[2]); +712 move->tofile = fileidx(mstr[4]); +713 move->torow = rowidx(mstr[5]); 714 } 715 } 716 717 718 if (move->piece) { 719 if (move->piece == PAWN -720 && move->torow == (color==WHITE?7:0) +720 && move->torow == (color==WHITE?7:0) 721 && !move->promotion) { 722 return NEED_PROMOTION; 723 } @@ -790,29 +793,29 @@ 737 _Bool is_protected(GameState *gamestate, uint8_t row, uint8_t file, 738 uint8_t color) { 739 -740 Move threats[16]; +740 Move threats[16]; 741 uint8_t threatcount; 742 if (get_real_threats(gamestate, row, file, color, threats, &threatcount)) { -743 for (int i = 0 ; i < threatcount ; i++) { +743 for (int i = 0 ; i < threatcount ; i++) { 744 if (threats[i].piece != (color|KING)) { -745 return 1; +745 return 1; 746 } 747 } -748 return 0; +748 return 0; 749 } else { -750 return 0; +750 return 0; 751 } 752 } 753 754 uint16_t remaining_movetime(GameInfo *gameinfo, GameState *gamestate, 755 uint8_t color) { 756 if (!gameinfo->timecontrol) { -757 return 0; +757 return 0; 758 } 759 760 if (gamestate->movelist) { 761 uint16_t time = gameinfo->time; -762 suseconds_t micros = 0; +762 suseconds_t micros = 0; 763 764 MoveList *movelist = color == WHITE ? 765 gamestate->movelist : gamestate->movelist->next; @@ -822,7 +825,7 @@ 769 770 struct movetimeval *movetime = &(movelist->move.movetime); 771 if (movetime->tv_sec >= time) { -772 return 0; +772 return 0; 773 } 774 775 time -= movetime->tv_sec; @@ -840,16 +843,16 @@ 787 micros += currenttstamp.tv_usec - lastmovetstamp->tv_usec; 788 sec = currenttstamp.tv_sec - lastmovetstamp->tv_sec; 789 if (sec >= time) { -790 return 0; +790 return 0; 791 } 792 793 time -= sec; 794 } 795 -796 sec = micros / 1e6L; +796 sec = micros / 1e6L; 797 798 if (sec >= time) { -799 return 0; +799 return 0; 800 } 801 802 time -= sec; diff -r 98adda6171d1 -r 2c8514b3891b test/gs/ctest.html --- a/test/gs/ctest.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/gs/ctest.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; } @@ -101,7 +104,7 @@ 48 #include "crypto.h" 49 #include "webdav.h" 50 - 51 #define MACRO1337 1337L + 51 #define MACRO1337 1337L 52 53 static const char* continuation_test = "this is a string\ 54 with a continuation"; @@ -120,44 +123,44 @@ 67 time_t util_parse_lastmodified(char *str) { 68 // example: Thu, 29 Nov 2012 21:35:35 GMT 69 if(!str) { - 70 return 0; + 70 return 0; 71 } else { 72 return curl_getdate(str, NULL); 73 } 74 } 75 76 int util_getboolean(char *v) { - 77 if(v[0] == 'T' || v[0] == 't') { - 78 return 1; + 77 if(v[0] == 'T' || v[0] == 't') { + 78 return 1; 79 } - 80 return 0; + 80 return 0; 81 } 82 83 int util_strtoint(char *str, int64_t *value) { 84 char *end; - 85 int64_t val = strtoll(str, &end, 0); - 86 if(strlen(end) == 0) { + 85 int64_t val = strtoll(str, &end, 0); + 86 if(strlen(end) == 0) { 87 *value = val; - 88 return 1; + 88 return 1; 89 } else { - 90 return 0; + 90 return 0; 91 } 92 } 93 94 char* util_url_path(char *url) { 95 char *path = NULL; 96 size_t len = strlen(url); - 97 int slashcount = 0; + 97 int slashcount = 0; 98 int slmax; - 99 if(len > 7 && !strncasecmp(url, "http://", 7)) { -100 slmax = 3; -101 } else if(len > 8 && !strncasecmp(url, "https://", 8)) { -102 slmax = 3; + 99 if(len > 7 && !strncasecmp(url, "http://", 7)) { +100 slmax = 3; +101 } else if(len > 8 && !strncasecmp(url, "https://", 8)) { +102 slmax = 3; 103 } else { -104 slmax = 1; +104 slmax = 1; 105 } 106 char c; -107 for(int i=0;i<len;i++) { +107 for(int i=0;i<len;i++) { 108 c = url[i]; 109 if(c == '/') { 110 slashcount++; @@ -178,24 +181,24 @@ 125 } 126 127 char* util_resource_name(char *url) { -128 int si = 0; -129 int osi = 0; -130 int i = 0; -131 int p = 0; +128 int si = 0; +129 int osi = 0; +130 int i = 0; +131 int p = 0; 132 char c; -133 while((c = url[i]) != 0) { +133 while((c = url[i]) != 0) { 134 if(c == '/') { 135 osi = si; 136 si = i; -137 p = 1; +137 p = 1; 138 } 139 i++; 140 } 141 142 char *name = url + si + p; -143 if(name[0] == 0) { +143 if(name[0] == 0) { 144 name = url + osi + p; -145 if(name[0] == 0) { +145 if(name[0] == 0) { 146 return url; 147 } 148 } @@ -217,25 +220,25 @@ 164 if(p) { 165 path = sstr(p); 166 } else { -167 path = sstrn("", 0); +167 path = sstrn("", 0); 168 } 169 -170 int add_separator = 0; -171 if(base.ptr[base.length-1] == '/') { -172 if(path.ptr[0] == '/') { +170 int add_separator = 0; +171 if(base.ptr[base.length-1] == '/') { +172 if(path.ptr[0] == '/') { 173 base.length--; 174 } 175 } else { -176 if(path.length == 0 || path.ptr[0] != '/') { -177 add_separator = 1; +176 if(path.length == 0 || path.ptr[0] != '/') { +177 add_separator = 1; 178 } 179 } 180 181 sstr_t url; 182 if(add_separator) { -183 url = sstrcat(3, base, sstr("/"), path); +183 url = sstrcat(3, base, sstr("/"), path); 184 } else { -185 url = sstrcat(2, base, path); +185 url = sstrcat(2, base, path); 186 } 187 188 return url.ptr; @@ -248,40 +251,40 @@ 195 char *base_path = util_url_path(sn->base_url); 196 base.length -= strlen(base_path); 197 -198 sstr_t url = sstrcat(2, base, href_str); +198 sstr_t url = sstrcat(2, base, href_str); 199 200 curl_easy_setopt(sn->handle, CURLOPT_URL, url.ptr); 201 free(url.ptr); 202 } 203 204 char* util_path_to_url(DavSession *sn, char *path) { -205 char *space = malloc(256); -206 UcxBuffer *url = ucx_buffer_new(space, 256, CX_BUFFER_AUTO_EXTEND); +205 char *space = malloc(256); +206 UcxBuffer *url = ucx_buffer_new(space, 256, CX_BUFFER_AUTO_EXTEND); 207 208 // add base url -209 ucx_buffer_write(sn->base_url, 1, strlen(sn->base_url), url); +209 ucx_buffer_write(sn->base_url, 1, strlen(sn->base_url), url); 210 // remove trailing slash -211 ucx_buffer_seek(url, -1, SEEK_CUR); +211 ucx_buffer_seek(url, -1, SEEK_CUR); 212 213 sstr_t p = sstr(path); -214 ssize_t ntk = 0; +214 ssize_t ntk = 0; 215 sstr_t *tks = sstrsplit(p, S("/"), &ntk); 216 -217 for(int i=0;i<ntk;i++) { +217 for(int i=0;i<ntk;i++) { 218 sstr_t node = tks[i]; -219 if(node.length > 0) { +219 if(node.length > 0) { 220 char *esc = curl_easy_escape(sn->handle, node.ptr, node.length); 221 ucx_buffer_putc(url, '/'); -222 ucx_buffer_write(esc, 1, strlen(esc), url); +222 ucx_buffer_write(esc, 1, strlen(esc), url); 223 curl_free(esc); 224 } 225 free(node.ptr); 226 } 227 free(tks); -228 if(path[p.length-1] == '/') { +228 if(path[p.length-1] == '/') { 229 ucx_buffer_putc(url, '/'); 230 } -231 ucx_buffer_putc(url, 0); +231 ucx_buffer_putc(url, 0); 232 233 space = url->space; 234 ucx_buffer_free(url); @@ -294,7 +297,7 @@ 241 size_t namelen = strlen(name); 242 size_t pathlen = strlen(path); 243 size_t parentlen = pathlen - namelen; -244 char *parent = malloc(parentlen + 1); +244 char *parent = malloc(parentlen + 1); 245 memcpy(parent, path, parentlen); 246 parent[parentlen] = '\0'; 247 return parent; @@ -314,13 +317,13 @@ 261 262 263 char* util_base64decode(char *in) { -264 int len = 0; +264 int len = 0; 265 return util_base64decode_len(in, &len); 266 } 267 268 char* util_base64decode_len(char* in, int *outlen) { 269 size_t len = strlen(in); -270 char *out = calloc(1, len); +270 char *out = calloc(1, len); 271 272 BIO* b = BIO_new_mem_buf(in, len); 273 BIO *d = BIO_new(BIO_f_base64()); @@ -347,8 +350,8 @@ 294 295 BIO_get_mem_ptr(e, &mem); 296 char *out = malloc(mem->length); -297 memcpy(out, mem->data, mem->length -1); -298 out[mem->length - 1] = '\0'; +297 memcpy(out, mem->data, mem->length -1); +298 out[mem->length - 1] = '\0'; 299 300 BIO_free_all(e); 301 @@ -384,8 +387,8 @@ 331 } 332 */ 333 char* util_random_str() { -334 unsigned char *str = malloc(25); -335 str[24] = '\0'; +334 unsigned char *str = malloc(25); +335 str[24] = '\0'; 336 337 sstr_t t = S( 338 "01234567890" @@ -393,8 +396,8 @@ 340 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"); 341 const unsigned char *table = (const unsigned char*)t.ptr; 342 -343 RAND_pseudo_bytes(str, 24); -344 for(int i=0;i<24;i++) { +343 RAND_pseudo_bytes(str, 24); +344 for(int i=0;i<24;i++) { 345 int c = str[i] % t.length; 346 str[i] = table[c]; 347 } @@ -409,30 +412,30 @@ 356 */ 357 sstr_t util_getsubstr_until_token(sstr_t str, sstr_t token, sstr_t *sub) { 358 int i; -359 int token_start = -1; -360 int token_end = -1; -361 for(i=0;i<=str.length;i++) { +359 int token_start = -1; +360 int token_end = -1; +361 for(i=0;i<=str.length;i++) { 362 int c; 363 if(i == str.length) { 364 c = ' '; 365 } else { 366 c = str.ptr[i]; 367 } -368 if(c < 33) { -369 if(token_start != -1) { +368 if(c < 33) { +369 if(token_start != -1) { 370 token_end = i; 371 size_t len = token_end - token_start; 372 sstr_t tk = sstrsubsl(str, token_start, len); 373 //printf("token: {%.*s}\n", token.length, token.ptr); 374 if(!sstrcmp(tk, token)) { -375 *sub = sstrtrim(sstrsubsl(str, 0, token_start)); +375 *sub = sstrtrim(sstrsubsl(str, 0, token_start)); 376 break; 377 } -378 token_start = -1; -379 token_end = -1; +378 token_start = -1; +379 token_end = -1; 380 } 381 } else { -382 if(token_start == -1) { +382 if(token_start == -1) { 383 token_start = i; 384 } 385 } @@ -442,7 +445,7 @@ 389 return sstrtrim(sstrsubs(str, i)); 390 } else { 391 str.ptr = NULL; -392 str.length = 0; +392 str.length = 0; 393 return str; 394 } 395 } diff -r 98adda6171d1 -r 2c8514b3891b test/gs/javatest.html --- a/test/gs/javatest.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/gs/javatest.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; } @@ -44,181 +47,246 @@
1 /* - 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - 3 * - 4 * Copyright 2014 Mike Becker. All rights reserved. - 5 * - 6 * Redistribution and use in source and binary forms, with or without - 7 * modification, are permitted provided that the following conditions are met: - 8 * - 9 * 1. Redistributions of source code must retain the above copyright - 10 * notice, this list of conditions and the following disclaimer. - 11 * - 12 * 2. Redistributions in binary form must reproduce the above copyright - 13 * notice, this list of conditions and the following disclaimer in the - 14 * documentation and/or other materials provided with the distribution. - 15 * - 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - 26 * POSSIBILITY OF SUCH DAMAGE. - 27 * - 28 */ - 29 - 30 package de.uapcore.sigred.doc.base; + 2 * Copyright 2013 Mike Becker. All rights reserved. + 3 * + 4 * Redistribution and use in source and binary forms, with or without + 5 * modification, are permitted provided that the following conditions are met: + 6 * + 7 * 1. Redistributions of source code must retain the above copyright + 8 * notice, this list of conditions and the following disclaimer. + 9 * + 10 * 2. Redistributions in binary form must reproduce the above copyright + 11 * notice, this list of conditions and the following disclaimer in the + 12 * documentation and/or other materials provided with the distribution. + 13 * + 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + 15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + 18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + 19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + 20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + 21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + 22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + 24 * POSSIBILITY OF SUCH DAMAGE. + 25 */ + 26 + 27 package de.uapcore.sudoku; + 28 + 29 import java.util.ArrayList; + 30 import java.util.List; 31 - 32 import de.uapcore.sigred.doc.Resources; - 33 import de.uapcore.sigrapi.impl.Digraph; - 34 import de.uapcore.sigrapi.impl.Graph; - 35 import de.uapcore.sigrapi.IGraph; - 36 import java.io.IOException; - 37 import java.io.InputStream; - 38 import java.io.OutputStream; - 39 import java.util.concurrent.atomic.AtomicBoolean; - 40 import java.util.concurrent.atomic.AtomicReference; - 41 import org.apache.xerces.impl.Constants; - 42 import org.dom4j.Document; - 43 import org.dom4j.DocumentException; - 44 import org.dom4j.DocumentHelper; - 45 import org.dom4j.Element; - 46 import org.dom4j.Namespace; - 47 import org.dom4j.QName; - 48 import org.dom4j.io.OutputFormat; - 49 import org.dom4j.io.SAXReader; - 50 import org.dom4j.io.XMLWriter; - 51 import org.xml.sax.ErrorHandler; - 52 import org.xml.sax.SAXException; - 53 import org.xml.sax.SAXParseException; - 54 - 55 public abstract class AbstractGraphDocument<T extends IGraph> - 56 extends FileBackedDocument { - 57 - 58 protected static final Namespace NAMESPACE = Namespace.get("sigred", - 59 "http://develop.uap-core.de/sigred/"); - 60 - 61 private static final - 62 QName TAG_GRAPHDOC = QName.get("graph-document", NAMESPACE); - 63 private static final - 64 QName TAG_GRAPH = QName.get("graph", NAMESPACE); - 65 private static final - 66 QName TAG_DIGRAPH = QName.get("digraph", NAMESPACE); - 67 private static final - 68 QName TAG_METADATA = QName.get("metadata", NAMESPACE); - 69 - 70 protected final T graph; + 32 /** + 33 * Implements the backtracking algorithm for solving the Sudoku. + 34 */ + 35 public final class Solver { + 36 + 37 public static final int VERSION = 0x1000; + 38 + 39 private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { + 40 Integer c = candidates[x][y].remove(0); + 41 f.setCellValue(x, y, c); + 42 f.setCellModified(x, y, true); + 43 for (int i = 0 ; i < 9 ; i++) { + 44 candidates[x][i].remove(c); + 45 candidates[i][y].remove(c); + 46 } + 47 for (int i = 0 ; i < 3 ; i++) { + 48 for (int j = 0 ; j < 3 ; j++) { + 49 candidates[x-x%3+i][y-y%3+j].remove(c); + 50 } + 51 } + 52 return c; + 53 } + 54 + 55 private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { + 56 for (int x = 0 ; x < 9 ; x++) { + 57 for (int y = 0 ; y < 9 ; y++) { + 58 candidatesBackup[x][y] = new ArrayList<>(9); + 59 candidatesBackup[x][y].addAll(candidates[x][y]); + 60 } + 61 } + 62 } + 63 + 64 private void makeBackup(Field f, int[][] fieldBackup) { + 65 for (int x = 0 ; x < 9 ; x++) { + 66 for (int y = 0 ; y < 9 ; y++) { + 67 fieldBackup[x][y] = f.getCellValue(x, y); + 68 } + 69 } + 70 } 71 - 72 private final GraphDocumentMetadata metadata; - 73 - 74 public AbstractGraphDocument(Class<T> graphType) { - 75 T g; - 76 try { - 77 g = graphType.newInstance(); - 78 } catch (ReflectiveOperationException e) { - 79 assert false; - 80 g = null; // for the compiler - 81 } - 82 graph = g; - 83 metadata = new GraphDocumentMetadata(); - 84 } - 85 - 86 public T getGraph() { - 87 return graph; - 88 } - 89 - 90 public GraphDocumentMetadata getMetadata() { - 91 return metadata; - 92 } - 93 - 94 protected abstract void writeGraph(Element rootNode) throws IOException; - 95 protected abstract void readGraph(Element rootNode) throws IOException; - 96 - 97 @Override - 98 public void writeTo(OutputStream out) throws IOException { - 99 Document doc = DocumentHelper.createDocument(); -100 -101 Element rootNode = doc.addElement(TAG_GRAPHDOC); -102 -103 Element metadataNode = rootNode.addElement(TAG_METADATA); -104 -105 metadata.write(metadataNode); -106 -107 if (graph instanceof Graph) { -108 writeGraph(rootNode.addElement(TAG_GRAPH)); -109 } else if (graph instanceof Digraph) { -110 writeGraph(rootNode.addElement(TAG_DIGRAPH)); -111 } else { -112 throw new IOException("unsupported graph type"); -113 } -114 -115 XMLWriter writer = new XMLWriter(out, OutputFormat.createPrettyPrint()); -116 writer.write(doc); -117 writer.flush(); -118 } -119 -120 @Override -121 public void readFrom(InputStream in) throws IOException { -122 try { -123 SAXReader reader = new SAXReader(true); -124 reader.setStripWhitespaceText(true); -125 -126 reader.setFeature(Constants.XERCES_FEATURE_PREFIX+ -127 Constants.SCHEMA_VALIDATION_FEATURE, true); -128 reader.setProperty(Constants.XERCES_PROPERTY_PREFIX + -129 Constants.SCHEMA_LOCATION, String.format("%s %s", -130 NAMESPACE.getURI(), Resources.class.getResource( -131 "graph-document.xsd").toExternalForm())); -132 -133 final AtomicBoolean passed = new AtomicBoolean(true); -134 final AtomicReference<SAXParseException> xmlerror = new AtomicReference<>(); -135 // TODO: we should do more detailed error handling here -136 reader.setErrorHandler(new ErrorHandler() { -137 @Override -138 public void warning(SAXParseException exception) throws SAXException { -139 } -140 -141 @Override -142 public void error(SAXParseException exception) throws SAXException { -143 xmlerror.set(exception); -144 passed.set(false); -145 } -146 -147 @Override -148 public void fatalError(SAXParseException exception) throws SAXException { -149 xmlerror.set(exception); -150 passed.set(false); -151 } -152 -153 }); -154 Document doc = reader.read(in); -155 if (!passed.get()) { -156 // TODO: provide details (maybe via separate error object?) -157 throw xmlerror.get(); -158 } -159 -160 doc.normalize(); -161 -162 Element root = doc.getRootElement(); -163 metadata.read(root.element(TAG_METADATA)); -164 -165 if (graph instanceof Graph) { -166 readGraph(root.element(TAG_GRAPH)); -167 } else if (graph instanceof Digraph) { -168 readGraph(root.element(TAG_DIGRAPH)); -169 } else { -170 throw new IOException("unsupported graph type"); -171 } -172 } catch (DocumentException | SAXException ex) { -173 throw new IOException(ex); -174 } -175 } -176 } + 72 private void restoreBackup(Field f, int[][] fieldBackup) { + 73 for (int x = 0 ; x < 9 ; x++) { + 74 for (int y = 0 ; y < 9 ; y++) { + 75 f.setCellValue(x, y, fieldBackup[x][y]); + 76 } + 77 } + 78 } + 79 + 80 private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { + 81 for (int x = 0 ; x < 9 ; x++) { + 82 for (int y = 0 ; y < 9 ; y++) { + 83 candidates[x][y].clear(); + 84 candidates[x][y].addAll(candidatesBackup[x][y]); + 85 } + 86 } + 87 } + 88 + 89 private boolean solve(Field f, List<Integer>[][] candidates) { + 90 + 91 // Make backup + 92 List<Integer>[][] candidatesBackup = new List[9][9]; + 93 int[][] fieldBackup = new int[9][9]; + 94 makeBackup(candidates, candidatesBackup); + 95 makeBackup(f, fieldBackup); + 96 + 97 // Fill in distinct solutions + 98 boolean fillDistinct; + 99 do { +100 fillDistinct = false; +101 for (int x = 0 ; x < 9 ; x++) { +102 for (int y = 0 ; y < 9 ; y++) { +103 if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { +104 fillInCandidate(f, candidates, x, y); +105 fillDistinct = true; +106 } +107 } +108 } +109 } while (fillDistinct); +110 +111 // Try out remaining candidates +112 for (int x = 0 ; x < 9 ; x++) { +113 for (int y = 0 ; y < 9 ; y++) { +114 if (f.isCellEmpty(x, y)) { +115 while (candidates[x][y].size() > 0) { +116 List<Integer>[][] cb = new List[9][9]; +117 makeBackup(candidates, cb); +118 Integer c = fillInCandidate(f, candidates, x, y); +119 if (solve(f, candidates)) { +120 break; +121 } else { +122 f.clearCellValue(x, y); +123 restoreBackup(candidates, cb); +124 // Remove current candidate anyway +125 candidates[x][y].remove(c); +126 } +127 } +128 } +129 if (f.isCellEmpty(x, y)) { +130 restoreBackup(f, fieldBackup); +131 restoreBackup(candidates, candidatesBackup); +132 return false; +133 } +134 } +135 } +136 +137 return true; +138 } +139 +140 /** +141 * Attempts to solve the given Sudoku field. +142 * +143 * The solution, if any, is directly entered into the field. +144 * All solved fields will be in modified state. +145 * The already given fields are left untouched. +146 * +147 * @param f the field to solve +148 * @return true if a solution could be found, false if the field is unsolvable +149 */ +150 public boolean solve(Field f) { +151 +152 // Calculate initial candidates +153 List<Integer>[][] candidates = new List[9][9]; +154 for (int x = 0 ; x < 9 ; x++) { +155 for (int y = 0 ; y < 9 ; y++) { +156 candidates[x][y] = new ArrayList<>(9); +157 if (f.getCellValue(x, y) == 0) { +158 // All numbers are candidates +159 for (int c = 1 ; c <= 9 ; c++) { +160 candidates[x][y].add(c); +161 } +162 // Remove row duplicates +163 int[] line = f.getRow(y); +164 for (Integer c : line) { +165 candidates[x][y].remove(c); +166 } +167 // Remove column duplicates +168 line = f.getColumn(x); +169 for (Integer c : line) { +170 candidates[x][y].remove(c); +171 } +172 // Remove square duplicates +173 int[][] square = f.getSquare(x/3, y/3); +174 for (int[] sq : square) { +175 for (Integer c : sq) { +176 candidates[x][y].remove(c); +177 } +178 } +179 } +180 } +181 } +182 +183 // Backtrack +184 return solve(f, candidates); +185 } +186 +187 /** +188 * Performs a fast check whether any field violates the Sudoku rules. +189 * +190 * @param f the field to check +191 * @return true, if the check succeeds, false otherwise +192 */ +193 public boolean check(Field f) { +194 int[] line; +195 for (int i = 0 ; i < 9 ; i++) { +196 line = f.getRow(i); +197 if (!valid(line)) { +198 return false; +199 } +200 line = f.getColumn(i); +201 if (!valid(line)) { +202 return false; +203 } +204 } +205 +206 int[][] square; +207 for (int x = 0 ; x < 3 ; x++) { +208 for (int y = 0 ; y < 3 ; y++) { +209 square = f.getSquare(x, y); +210 if (!valid(square)) { +211 return false; +212 } +213 } +214 } +215 +216 return true; +217 } +218 +219 private boolean valid(int[] line) { +220 int[] numbers; +221 numbers = new int[9]; +222 for (int i = 0 ; i < 9 ; i++) { +223 int l = line[i]-1; +224 if (l >= 0) { +225 if ((++numbers[l]) > 1) { +226 return false; +227 } +228 } +229 } +230 +231 return true; +232 } +233 +234 private boolean valid(int[][] square) { +235 int[] line = new int[9]; +236 for (int x = 0 ; x < 3 ; x++) { +237 System.arraycopy(square[x], 0, line, 3*x, 3); +238 } +239 return valid(line); +240 } +241 }
diff -r 98adda6171d1 -r 2c8514b3891b test/gs/plain.html --- a/test/gs/plain.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/gs/plain.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; } diff -r 98adda6171d1 -r 2c8514b3891b test/header.html --- a/test/header.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/header.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; } diff -r 98adda6171d1 -r 2c8514b3891b test/javatest.java --- a/test/javatest.java Sun Mar 02 12:47:31 2025 +0100 +++ b/test/javatest.java Sun Mar 02 16:06:24 2025 +0100 @@ -1,18 +1,16 @@ /* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2014 Mike Becker. All rights reserved. - * + * Copyright 2013 Mike Becker. All rights reserved. + * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE @@ -24,153 +22,220 @@ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. - * */ -package de.uapcore.sigred.doc.base; +package de.uapcore.sudoku; + +import java.util.ArrayList; +import java.util.List; + +/** + * Implements the backtracking algorithm for solving the Sudoku. + */ +public final class Solver { + + public static final int VERSION = 0x1000; -import de.uapcore.sigred.doc.Resources; -import de.uapcore.sigrapi.impl.Digraph; -import de.uapcore.sigrapi.impl.Graph; -import de.uapcore.sigrapi.IGraph; -import java.io.IOException; -import java.io.InputStream; -import java.io.OutputStream; -import java.util.concurrent.atomic.AtomicBoolean; -import java.util.concurrent.atomic.AtomicReference; -import org.apache.xerces.impl.Constants; -import org.dom4j.Document; -import org.dom4j.DocumentException; -import org.dom4j.DocumentHelper; -import org.dom4j.Element; -import org.dom4j.Namespace; -import org.dom4j.QName; -import org.dom4j.io.OutputFormat; -import org.dom4j.io.SAXReader; -import org.dom4j.io.XMLWriter; -import org.xml.sax.ErrorHandler; -import org.xml.sax.SAXException; -import org.xml.sax.SAXParseException; - -public abstract class AbstractGraphDocument - extends FileBackedDocument { + private Integer fillInCandidate(Field f, List[][] candidates, int x, int y) { + Integer c = candidates[x][y].remove(0); + f.setCellValue(x, y, c); + f.setCellModified(x, y, true); + for (int i = 0 ; i < 9 ; i++) { + candidates[x][i].remove(c); + candidates[i][y].remove(c); + } + for (int i = 0 ; i < 3 ; i++) { + for (int j = 0 ; j < 3 ; j++) { + candidates[x-x%3+i][y-y%3+j].remove(c); + } + } + return c; + } - protected static final Namespace NAMESPACE = Namespace.get("sigred", - "http://develop.uap-core.de/sigred/"); - - private static final - QName TAG_GRAPHDOC = QName.get("graph-document", NAMESPACE); - private static final - QName TAG_GRAPH = QName.get("graph", NAMESPACE); - private static final - QName TAG_DIGRAPH = QName.get("digraph", NAMESPACE); - private static final - QName TAG_METADATA = QName.get("metadata", NAMESPACE); - - protected final T graph; + private void makeBackup(List[][] candidates, List[][] candidatesBackup) { + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + candidatesBackup[x][y] = new ArrayList<>(9); + candidatesBackup[x][y].addAll(candidates[x][y]); + } + } + } - private final GraphDocumentMetadata metadata; + private void makeBackup(Field f, int[][] fieldBackup) { + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + fieldBackup[x][y] = f.getCellValue(x, y); + } + } + } - public AbstractGraphDocument(Class graphType) { - T g; - try { - g = graphType.newInstance(); - } catch (ReflectiveOperationException e) { - assert false; - g = null; // for the compiler + private void restoreBackup(Field f, int[][] fieldBackup) { + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + f.setCellValue(x, y, fieldBackup[x][y]); + } } - graph = g; - metadata = new GraphDocumentMetadata(); - } - - public T getGraph() { - return graph; } - public GraphDocumentMetadata getMetadata() { - return metadata; + private void restoreBackup(List[][] candidates, List[][] candidatesBackup) { + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + candidates[x][y].clear(); + candidates[x][y].addAll(candidatesBackup[x][y]); + } + } + } + + private boolean solve(Field f, List[][] candidates) { + + // Make backup + List[][] candidatesBackup = new List[9][9]; + int[][] fieldBackup = new int[9][9]; + makeBackup(candidates, candidatesBackup); + makeBackup(f, fieldBackup); + + // Fill in distinct solutions + boolean fillDistinct; + do { + fillDistinct = false; + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { + fillInCandidate(f, candidates, x, y); + fillDistinct = true; + } + } + } + } while (fillDistinct); + + // Try out remaining candidates + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + if (f.isCellEmpty(x, y)) { + while (candidates[x][y].size() > 0) { + List[][] cb = new List[9][9]; + makeBackup(candidates, cb); + Integer c = fillInCandidate(f, candidates, x, y); + if (solve(f, candidates)) { + break; + } else { + f.clearCellValue(x, y); + restoreBackup(candidates, cb); + // Remove current candidate anyway + candidates[x][y].remove(c); + } + } + } + if (f.isCellEmpty(x, y)) { + restoreBackup(f, fieldBackup); + restoreBackup(candidates, candidatesBackup); + return false; + } + } + } + + return true; } - protected abstract void writeGraph(Element rootNode) throws IOException; - protected abstract void readGraph(Element rootNode) throws IOException; - - @Override - public void writeTo(OutputStream out) throws IOException { - Document doc = DocumentHelper.createDocument(); - - Element rootNode = doc.addElement(TAG_GRAPHDOC); - - Element metadataNode = rootNode.addElement(TAG_METADATA); - - metadata.write(metadataNode); - - if (graph instanceof Graph) { - writeGraph(rootNode.addElement(TAG_GRAPH)); - } else if (graph instanceof Digraph) { - writeGraph(rootNode.addElement(TAG_DIGRAPH)); - } else { - throw new IOException("unsupported graph type"); + /** + * Attempts to solve the given Sudoku field. + * + * The solution, if any, is directly entered into the field. + * All solved fields will be in modified state. + * The already given fields are left untouched. + * + * @param f the field to solve + * @return true if a solution could be found, false if the field is unsolvable + */ + public boolean solve(Field f) { + + // Calculate initial candidates + List[][] candidates = new List[9][9]; + for (int x = 0 ; x < 9 ; x++) { + for (int y = 0 ; y < 9 ; y++) { + candidates[x][y] = new ArrayList<>(9); + if (f.getCellValue(x, y) == 0) { + // All numbers are candidates + for (int c = 1 ; c <= 9 ; c++) { + candidates[x][y].add(c); + } + // Remove row duplicates + int[] line = f.getRow(y); + for (Integer c : line) { + candidates[x][y].remove(c); + } + // Remove column duplicates + line = f.getColumn(x); + for (Integer c : line) { + candidates[x][y].remove(c); + } + // Remove square duplicates + int[][] square = f.getSquare(x/3, y/3); + for (int[] sq : square) { + for (Integer c : sq) { + candidates[x][y].remove(c); + } + } + } + } } - - XMLWriter writer = new XMLWriter(out, OutputFormat.createPrettyPrint()); - writer.write(doc); - writer.flush(); + + // Backtrack + return solve(f, candidates); } - @Override - public void readFrom(InputStream in) throws IOException { - try { - SAXReader reader = new SAXReader(true); - reader.setStripWhitespaceText(true); - - reader.setFeature(Constants.XERCES_FEATURE_PREFIX+ - Constants.SCHEMA_VALIDATION_FEATURE, true); - reader.setProperty(Constants.XERCES_PROPERTY_PREFIX + - Constants.SCHEMA_LOCATION, String.format("%s %s", - NAMESPACE.getURI(), Resources.class.getResource( - "graph-document.xsd").toExternalForm())); - - final AtomicBoolean passed = new AtomicBoolean(true); - final AtomicReference xmlerror = new AtomicReference<>(); - // TODO: we should do more detailed error handling here - reader.setErrorHandler(new ErrorHandler() { - @Override - public void warning(SAXParseException exception) throws SAXException { - } - - @Override - public void error(SAXParseException exception) throws SAXException { - xmlerror.set(exception); - passed.set(false); + /** + * Performs a fast check whether any field violates the Sudoku rules. + * + * @param f the field to check + * @return true, if the check succeeds, false otherwise + */ + public boolean check(Field f) { + int[] line; + for (int i = 0 ; i < 9 ; i++) { + line = f.getRow(i); + if (!valid(line)) { + return false; + } + line = f.getColumn(i); + if (!valid(line)) { + return false; + } + } + + int[][] square; + for (int x = 0 ; x < 3 ; x++) { + for (int y = 0 ; y < 3 ; y++) { + square = f.getSquare(x, y); + if (!valid(square)) { + return false; } - - @Override - public void fatalError(SAXParseException exception) throws SAXException { - xmlerror.set(exception); - passed.set(false); - } - - }); - Document doc = reader.read(in); - if (!passed.get()) { - // TODO: provide details (maybe via separate error object?) - throw xmlerror.get(); } - - doc.normalize(); - - Element root = doc.getRootElement(); - metadata.read(root.element(TAG_METADATA)); - - if (graph instanceof Graph) { - readGraph(root.element(TAG_GRAPH)); - } else if (graph instanceof Digraph) { - readGraph(root.element(TAG_DIGRAPH)); - } else { - throw new IOException("unsupported graph type"); + } + + return true; + } + + private boolean valid(int[] line) { + int[] numbers; + numbers = new int[9]; + for (int i = 0 ; i < 9 ; i++) { + int l = line[i]-1; + if (l >= 0) { + if ((++numbers[l]) > 1) { + return false; + } } - } catch (DocumentException | SAXException ex) { - throw new IOException(ex); } + + return true; + } + + private boolean valid(int[][] square) { + int[] line = new int[9]; + for (int x = 0 ; x < 3 ; x++) { + System.arraycopy(square[x], 0, line, 3*x, 3); + } + return valid(line); } } diff -r 98adda6171d1 -r 2c8514b3891b test/jheader.html --- a/test/jheader.html Sun Mar 02 12:47:31 2025 +0100 +++ b/test/jheader.html Sun Mar 02 16:06:24 2025 +0100 @@ -33,6 +33,9 @@ span.c2html-string { color: darkorange; } + span.c2html-number { + color: dodgerblue; + } span.c2html-comment { color: grey; }