четверг, 30 апреля 2015 г.

Binary search

Finds an index to put a element to if it's absent. Return true if it's there. Helps to find an index to insert an element. Not content with this one. Must be somehow redone. Looks like shit actually. Requires size_t slot be initialized by '0'


bool find_slot(const char * buffer, 
const size_t size, 
const char elem, 
size_t * slot) {

    const size_t m = (size_t)(size / 2);

    if ( m == 0 )
        return false;

    if ( elem > buffer[m - 1] ) {
        *slot += m;
        if ( elem < buffer[m] )
            return false;
        return find_slot(buffer + m, size - m, elem, slot);
    }

    if ( elem < buffer[m - 1] ) {
        if ( elem > buffer[m - 2] )
            return false;
        return find_slot(buffer, size - m, elem, slot);
    }
    return true;
}

вторник, 28 апреля 2015 г.

Reverse string


void reverse(char * str) {

    char temp;

    for ( int i = strlen(str) - 1, j = 0; 
              j < (int)(strlen(str) / 2); --i, ++j) {

        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

    }
}

понедельник, 27 апреля 2015 г.

Permutations


void permute(permtype * p, const char * expr) {
    p->perms[0][0] = expr[0];

    for (size_t i = 1; i < p->LEN; ++i)
        merge(p, i, expr[i]);

}

void merge(permtype * p, const size_t index, const char elem) {

    const size_t Nprev = index > 0 ? factorial(index) : 0;
    assert(p->N > Nprev);
    size_t j = Nprev;

    for (size_t i = 0; i < Nprev; ++i) {
        for ( size_t k = 0; k < index; ++k )
            splice(&(p->perms[j++]), p->perms[i], elem, k, index);

        p->perms[i][index] = elem;
    }

}

четверг, 16 апреля 2015 г.

This brilliant code snippet takes a node offset by the index from the head and swaps its value with the node offset by the index from the tail.


void swapAt(Node *head, int index) {

    Node * node = head;
    Node * begin, trailer;

    for (int i = 0; node != NULL; node = node->next, ++i ) {

         if ( i == index ) {
            begin = node;
            trailer = head;
         }

         if ( i > index)
             trailer = trailer->next;

    }

    int temp = begin.val;
    begin.val = trailer.val;
    trailer.val = temp;
}