Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * SeaDragon 0.91 - A sequencer program for A207324 at oeis.org
- *
- * 2012 Sept. R.J. Cano <aallggoorriitthhmmuuss@gmail.com>
- *
- * This program was devised and written for documentation purposes and is
- * subject to the terms of use of the On Line Encyclopedia Of Integer Sequences.
- *
- *
- * Changes:
- *
- * This update has no leaks at all, and runs a litte bit faster than older versions.
- *
- * About A055998 and the memory leaks present in older versions of this code:
- *
- * The counting of memory blocks leaked by missed calls to free(), a bug already fixed for
- * the present version of this program, behaved as an arithmetical progession documented
- * in oeis.org as the A055998 sequence adding 2 in each one of its terms. Such +2 addition
- * was caused by an implementation mistake of the author. The actual counting is the shown
- * by A055998. Also, the leaks were caused by a forgotten "memory release instruction",
- * omited by the author when translating his pseudocode interpretation of the SJT Algorithm
- * into a C program. There is no design errors neither in the SJT Algorithm nor in the
- * operational interpretation made of it.
- *
- * Hints:
- *
- * For authors and contributors about C programs:
- *
- * It is suggested when compiling C programs verify if it's written in an
- * acceptable way using a command like: "gcc -O2 -W -Wall my_oeis_program.c"
- *
- * (Thanks to: Joerg Arndt)
- *
- *
- */
- #include <stdio.h>
- #include <stdlib.h>
- /*---------> non-standard datatype definitions <-----------------------------------------------------------*/
- typedef struct matrix_linear_stack {
- long integer_value;
- struct matrix_linear_stack *arrow;
- } matrix_linear_stack;
- /*---------> non-standard constant values definition <------------------------------------------------------*/
- const long __mode_ZERO = 0;
- const long __mode_EQUAL = 1;
- const long __mode_DETERMINANT = 2;
- const long __TOKEN_TEMPLATE = 0;
- const long __UNIT = 1;
- long generator_settings = 0;
- long __config_generator[3][2];
- /*---------> Suitable globals <-----------------------------------------------------------------------------*/
- matrix_linear_stack *__the_ring_stckPointerReference_HEAD, *__the_ring_stckPointerReference_TAIL;
- // About the ring:
- // Warning: After calling close__the_ring() a first time, don't call it again before a call to open_the_ring() of course
- // for the same parameter list (Else it would have possible harmful and unpredictible consequences).
- /*---------> non-standards called by main(); <-----------------------------------------------------*/
- void configure_modes(void);
- void runSequencer(int, long);
- /*---------> non-standards called by others; <-----------------------------------------------------*/
- void finalizer_matrix(matrix_linear_stack **, matrix_linear_stack**);
- void print_matrix(matrix_linear_stack **);
- void apply_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack**, matrix_linear_stack**, long);
- void mode_matrix_waterfall(void);
- matrix_linear_stack* generate_square_matrix(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, long);
- void initializer_matrix(matrix_linear_stack **, matrix_linear_stack**);
- matrix_linear_stack* extract_first_nodes(matrix_linear_stack**, matrix_linear_stack**, long);
- void concat_matrices_node_by_node(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**);
- /*---------> additional non-standards (some of them called by more than one function); <-----------------------------------------------------*/
- long only_initialized(matrix_linear_stack**);
- long absolute_value(long);
- matrix_linear_stack* insert_new_node(long, matrix_linear_stack**);
- void close__the_ring(matrix_linear_stack**, matrix_linear_stack**);
- void open_the_ring(matrix_linear_stack**, matrix_linear_stack**);
- long LeibnitzLaplaceSignature(long);
- /*------------------------------------------------------------------------------------------------------------------------------*/
- int main(void) {
- int j, _OScurrentExecutionFeedbackCode = EXIT_SUCCESS;
- long N;
- configure_modes(); // Don't change this, it is for initialization.
- printf("%s%s","\n\nDemonstration program: ", "\n\n\tShould be run the sequencer only for a particular SJT-array? (1=yes, 0=No) ");
- scanf("%i", &j);
- getchar();
- printf("%s","\n\n\tWhich is the upper size? (try first 1-11 on 32-bit machines): ");
- scanf("%li", &N);
- getchar();
- runSequencer(j, N);
- return _OScurrentExecutionFeedbackCode;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void configure_modes(void) {
- __config_generator[__mode_ZERO][__TOKEN_TEMPLATE] = 0;
- __config_generator[__mode_ZERO][__UNIT] = 0;
- __config_generator[__mode_EQUAL][__TOKEN_TEMPLATE] = 0;
- __config_generator[__mode_EQUAL][__UNIT] = 1;
- __config_generator[__mode_DETERMINANT][__TOKEN_TEMPLATE] = 1;
- __config_generator[__mode_DETERMINANT][__UNIT] = 0;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void runSequencer(int just_for_the_Nth_array, long N) {
- long k;
- matrix_linear_stack *J0_head, *J0_tail;
- for (k=(just_for_the_Nth_array ? N : 1);k<=N;k++) {
- apply_SteinhausJohnsonTrotterAlgorithm(&J0_head, &J0_tail, k);
- print_matrix(&J0_head);
- finalizer_matrix(&J0_head, &J0_tail);
- }
- printf("\n\n\tSequencer execution completed successfully.\n");
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void finalizer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
- while (*stckPointerReference_HEAD != NULL) {
- (*stckPointerReference_TAIL) = (*stckPointerReference_HEAD);
- (*stckPointerReference_HEAD) = (*stckPointerReference_HEAD)->arrow;
- free( *stckPointerReference_TAIL );
- }
- (*stckPointerReference_TAIL) = NULL;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void print_matrix(matrix_linear_stack **stckPointerReference_HEAD) {
- matrix_linear_stack* focus= *stckPointerReference_HEAD;
- if ( NULL == focus ) {
- printf(" Not initialized! ");
- } else {
- if ( -1 == (focus->integer_value) ) {
- focus = (*stckPointerReference_HEAD)->arrow;
- if ( NULL == focus ) {
- printf(" initialized but empty. ");
- } else {;}
- } else {
- }
- while ( NULL != focus ) {
- printf("\n%li", (focus->integer_value) );
- focus = focus->arrow;
- }
- }
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void apply_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack **J_head, matrix_linear_stack **J_tail, long _SIZE) {
- matrix_linear_stack *JJ_head;
- matrix_linear_stack *JJ_tail;
- matrix_linear_stack *P_head;
- matrix_linear_stack *P_tail;
- matrix_linear_stack *Q_head;
- matrix_linear_stack *Q_tail;
- long diagonal;
- long _CASE = 1;
- mode_matrix_waterfall();
- initializer_matrix(J_head, J_tail);
- insert_new_node(1, J_tail);
- while (_CASE < _SIZE) {
- _CASE++;
- diagonal = -1;
- initializer_matrix(&JJ_head, &JJ_tail);
- while ( !only_initialized(J_head) ) {
- P_head = extract_first_nodes(J_head, &P_tail, (_CASE-1)) ;
- generate_square_matrix(&P_head, &P_tail, &Q_head, &Q_tail, _CASE*diagonal);
- concat_matrices_node_by_node(&JJ_tail, &Q_head, &Q_tail);
- finalizer_matrix(&P_head, &P_tail);
- diagonal *= -1;
- }
- finalizer_matrix(J_head, J_tail);
- *J_head = JJ_head;
- *J_tail = JJ_tail;
- JJ_head = NULL;
- JJ_tail = NULL;
- }
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void mode_matrix_waterfall(void) {
- generator_settings = __mode_DETERMINANT;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- matrix_linear_stack* generate_square_matrix(matrix_linear_stack **baseRef_head, matrix_linear_stack **baseRef_tail, matrix_linear_stack **ref_answer_head, matrix_linear_stack **ref_answer_tail, long TOKEN_TEMPLATE) {
- long counting_L = 1;
- long counting_X = 1;
- long counting_Y = 1;
- long matrix_size = absolute_value(TOKEN_TEMPLATE);
- long newValuetobeIncluded;
- matrix_linear_stack* BASE_head = *baseRef_head;
- matrix_linear_stack* BASE_tail = *baseRef_tail;
- close__the_ring(&BASE_head, &BASE_tail);
- initializer_matrix(ref_answer_head, ref_answer_tail);
- matrix_size = absolute_value(TOKEN_TEMPLATE);
- while (counting_L <= (matrix_size*matrix_size)) {
- if (BASE_head->integer_value == -1) { BASE_head = BASE_head->arrow; }
- newValuetobeIncluded = (TOKEN_TEMPLATE < 0) ? ( ( counting_X + counting_Y == (matrix_size+1) ) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) ) : ( (counting_X - counting_Y == 0) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) );
- if ( ( 0 == newValuetobeIncluded ) && ( __mode_ZERO != generator_settings) ) {
- newValuetobeIncluded+= (BASE_head->integer_value);
- BASE_head = BASE_head->arrow;
- }
- insert_new_node(newValuetobeIncluded, ref_answer_tail);
- counting_L++;
- counting_X++;
- if (counting_X > matrix_size) {
- counting_X = 1;
- counting_Y++;
- }
- }
- open_the_ring(&BASE_head, &BASE_tail);
- return (*ref_answer_head);
- }
- /*----------------------------------------------------------------------------------------------------------------------(OJO)---*/
- void initializer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
- (*stckPointerReference_HEAD) = NULL;
- (*stckPointerReference_TAIL) = insert_new_node( -1, stckPointerReference_HEAD );
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- matrix_linear_stack* extract_first_nodes(matrix_linear_stack** refSource, matrix_linear_stack** refRemainderTail, long extractions) {
- matrix_linear_stack* newRefSource= *refSource;
- matrix_linear_stack* answer= (*refSource)->arrow;
- matrix_linear_stack* cursor= (*refSource);
- long steps= (0 == extractions) ? 1 : extractions;
- long counter=0;
- while (counter < steps) {
- cursor= cursor->arrow;
- counter++;
- }
- newRefSource->arrow= cursor->arrow;
- cursor->arrow= NULL;
- (*refRemainderTail)= cursor;
- *refSource = newRefSource;
- return answer;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void concat_matrices_node_by_node(matrix_linear_stack **operand_left_tail, matrix_linear_stack **operand_right_head, matrix_linear_stack **operand_right_tail) {
- matrix_linear_stack *slayer = *operand_right_head;
- *operand_right_head = NULL;
- (*operand_left_tail)->arrow = slayer->arrow;
- slayer->arrow = NULL;
- free(slayer);
- *operand_left_tail = *operand_right_tail;
- *operand_right_tail = NULL;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- long only_initialized(matrix_linear_stack** stckPointerReference_HEAD) {
- if ( 0 != ( NULL != stckPointerReference_HEAD ) ) {
- if ( 0 != ( NULL != *stckPointerReference_HEAD ) ) {
- if ( 0 != ( NULL == (*stckPointerReference_HEAD)->arrow ) ) {
- if ( -1 == (*stckPointerReference_HEAD)->integer_value ) {
- return 1;
- }
- }
- }
- }
- return 0;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- long absolute_value(long argument) {
- return ( argument * LeibnitzLaplaceSignature(argument) );
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- matrix_linear_stack* insert_new_node(long value_assigned, matrix_linear_stack **stckPointerReference_TAIL) {
- matrix_linear_stack *focus;
- matrix_linear_stack *inserto = (matrix_linear_stack *)( malloc( sizeof( matrix_linear_stack ) ) );
- matrix_linear_stack *answer_ref = inserto;
- inserto->integer_value = value_assigned;
- inserto->arrow = NULL;
- if (( NULL == (*stckPointerReference_TAIL) ) && (-1 == value_assigned)) {
- (*stckPointerReference_TAIL) = inserto;
- } else if ( NULL != (*stckPointerReference_TAIL) ) {
- focus = (*stckPointerReference_TAIL);
- while ( NULL != focus->arrow ) { focus = focus->arrow; }
- focus->arrow = inserto;
- if ( focus == (*stckPointerReference_TAIL) ) { (*stckPointerReference_TAIL) = inserto; }
- }
- return answer_ref;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void close__the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
- __the_ring_stckPointerReference_HEAD = *stckPointerReference_HEAD;
- __the_ring_stckPointerReference_TAIL = *stckPointerReference_TAIL;
- (*stckPointerReference_TAIL)->arrow = *stckPointerReference_HEAD;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- void open_the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
- (*stckPointerReference_HEAD) = __the_ring_stckPointerReference_HEAD;
- (*stckPointerReference_TAIL) = __the_ring_stckPointerReference_TAIL;
- (*stckPointerReference_TAIL)->arrow = NULL;
- }
- /*------------------------------------------------------------------------------------------------------------------------------*/
- long LeibnitzLaplaceSignature(long argument) {
- long answer;
- answer = (argument < 0) ? (-1) : (1) ;
- return answer;
- }
- /*
- *
- * << If people do not believe that mathematics is simple, it is only because
- * they do not realize how complicated life is. >>
- *
- * --John von Neumann
- *
- */
- // The end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement