gistfile1.txt

[2:25pm][wlynch@watermelon /tmp] cat foo.c 
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct _list {
    int key;
    int freq;
    struct _list *next;
    struct _list *prev;
} list;

list* head;
list* tail;

void RemoveNode(list *node) {
    if (node->prev)
        node->prev->next = node->next;
    if (node->next)
        node->next->prev = node->prev;
}

void InsertNodeBetween(list *lhs, list *node, list *rhs) {
    if (lhs) assert(lhs->next == rhs);
    if (rhs) assert(rhs->prev == lhs);

    if (lhs) lhs->next = node;
    if (rhs) rhs->prev = node;

    node->prev = lhs;
    node->next = rhs;
}

void InsertAtTail(int value) {
    list *newNode;
    newNode = (list*)malloc(sizeof(list));
    newNode->key = value;

    newNode->freq = 0;
    newNode->prev = NULL;
    newNode->next = NULL;

    if(head == NULL)
        head = newNode;

    if (tail != NULL) {
        tail->next = newNode;
        newNode->prev = tail;
    }

    tail = newNode;
}

int SearchAndIncrement(int x, list** head) {
    int contapos = 0;
    list* i;

    // Let's find the element with the matching key
    for (i = *head; i != NULL; i = i->next, contapos++)
        if (i->key == x)
            break;

    // If we did not find the node, return -1 to denote failure.
    if (i == NULL)
        return -1;

    // Increase frequency
    i->freq++;

    while (i->prev && (i->freq > i->prev->freq)) {
        list *prev = i->prev->prev;
        list *next = i->prev;
        RemoveNode(i);
        InsertNodeBetween(prev, i, next);
    }


    // The head might have been moved.
    while ((*head)->prev != NULL)
        (*head) = (*head)->prev;

    // Return the original position
    return contapos;
}

int main () {
    int N;
    scanf("%d", &N);

    head = NULL;
    tail = NULL;

    int i, value;
    for (i=0; i<N; i++) {
        scanf("%d", &value);
        InsertAtTail(value);
    }

    /* Initializing frequencies */
    list* aus;
    for (aus=head; aus; aus = aus ->next) {
        aus->freq = 0;
    }

    int x, pos;
    do {
        scanf("%d", &x);
        pos = SearchAndIncrement(x, &head);
        printf("User Input(%d) Position(%d) ", x, pos);
        printf("[");
        aus = head;
        while (aus!=NULL) {
            printf("(%d, %d) ", aus->key, aus->freq);
            aus = aus->next;
        }
        printf("]\n");
    } while (pos != -1);

    return 0;
}
[2:25pm][wlynch@watermelon /tmp] make foo
cc     foo.c   -o foo
[2:25pm][wlynch@watermelon /tmp] ./foo
4
1 2 3 4
1
User Input(1) Position(0) [(1, 1) (2, 0) (3, 0) (4, 0) ]
1
User Input(1) Position(0) [(1, 2) (2, 0) (3, 0) (4, 0) ]
1
User Input(1) Position(0) [(1, 3) (2, 0) (3, 0) (4, 0) ]
2
User Input(2) Position(1) [(1, 3) (2, 1) (3, 0) (4, 0) ]
2
User Input(2) Position(1) [(1, 3) (2, 2) (3, 0) (4, 0) ]
2
User Input(2) Position(1) [(1, 3) (2, 3) (3, 0) (4, 0) ]
2
User Input(2) Position(1) [(2, 4) (1, 3) (3, 0) (4, 0) ]
3
User Input(3) Position(2) [(2, 4) (1, 3) (3, 1) (4, 0) ]
3
User Input(3) Position(2) [(2, 4) (1, 3) (3, 2) (4, 0) ]
3
User Input(3) Position(2) [(2, 4) (1, 3) (3, 3) (4, 0) ]
3
User Input(3) Position(2) [(2, 4) (3, 4) (1, 3) (4, 0) ]
3
User Input(3) Position(1) [(3, 5) (2, 4) (1, 3) (4, 0) ]
3
User Input(3) Position(0) [(3, 6) (2, 4) (1, 3) (4, 0) ]
3
User Input(3) Position(0) [(3, 7) (2, 4) (1, 3) (4, 0) ]
100
User Input(100) Position(-1) [(3, 7) (2, 4) (1, 3) (4, 0) ]

[2:33pm][wlynch@watermelon /tmp] ./foo
3
1 2 3
3
User Input(3) Position(2) [(3, 1) (1, 0) (2, 0) ]
2
User Input(2) Position(2) [(3, 1) (2, 1) (1, 0) ]
^C