pqueue.c

用改进的数据结构快速计算复杂网络的社区划分

/*-
 * Copyright (c) 2008, Alexandre P. Francisco <[e-mail]>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <limits.h>
#include <stdlib.h>
#include <string.h>

#include <assert.h>

#include "pqueue.h"

typedef int (*cmp_function)(KEY_T, KEY_T);

struct _pqueue {
	size_t	size, max_size, *heap, *map;
	KEY_T 	*key;
	cmp_function	cmp;
};

#define LEFT(x)	   ((((x) + 1) << 1) - 1)
#define RIGHT(x)    (((x) + 1) << 1)
#define PARENT(x)  ((((x) + 1) >> 1) - 1)

static void	_local_exchange(pqueue *, size_t, size_t);
static void	_fix_down(pqueue *, size_t);
static void	_fix_up(pqueue *, size_t);

pqueue *
pqueue_new(size_t size, KEY_T *k, int (*cmp)(KEY_T, KEY_T))
{
	pqueue * q;

	q = (struct _pqueue *) malloc(sizeof(struct _pqueue));
	q->max_size = size;
	q->size = 0;
	q->heap = (size_t *) malloc(sizeof(size_t)*size);
	memset(q->heap, 0xFF, sizeof(size_t)*size);
	q->map = (size_t *) malloc(sizeof(size_t)*size);
	memset(q->map, 0xFF, sizeof(size_t)*size);

	q->key = k;
	q->cmp = cmp;

	return q;
}

void
pqueue_free(pqueue *q)
{
	free(q->heap);
	free(q->map);
	free(q);
}

int
pqueue_empty(pqueue *q)
{
	return q->size == 0;
}

int
pqueue_has(pqueue *q, size_t id){
	return q->map[id] < q->size;
}

void
pqueue_push(pqueue *q, size_t id)
{
	if (q->map[id] >= ULONG_MAX) {
		if (q->size >= q->max_size)
			abort();

		q->map[id] = q->size;
		q->heap[q->size] = id;
		q->size ++;
	}
	_fix_up(q, q->map[id]);
	_fix_down(q, q->map[id]);
}

void
pqueue_update(pqueue *q, size_t id)
{
	pqueue_push(q, id);
}

size_t
pqueue_top(pqueue *q)
{
	return q->heap[0];
}

void
pqueue_pop(pqueue *q){
	size_t r;

	r = q->heap[0];
	q->size--;
	_local_exchange(q, q->size, 0);
	_fix_down(q, 0);
	q->heap[q->size] = ULONG_MAX;
	q->map[r] = ULONG_MAX;
}

static void
_local_exchange(pqueue *q, size_t i, size_t j)
{
	size_t v;

	assert(q->map[q->heap[i]] == i && q->map[q->heap[j]] == j);

	q->map[q->heap[i]] = j;
	q->map[q->heap[j]] = i;
	v = q->heap[i];
	q->heap[i] = q->heap[j];
	q->heap[j] = v;

	assert(q->map[q->heap[i]] == i && q->map[q->heap[j]] == j);
}

static void
_fix_down(pqueue *q, size_t id)
{
	size_t l = LEFT(id), r = RIGHT(id), m = id;

	if (l < q->size &&
	    q->cmp(q->key[q->heap[l]], q->key[q->heap[m]]) > 0)
		m = l;
	if (r < q->size &&
	    q->cmp(q->key[q->heap[r]], q->key[q->heap[m]]) > 0)
		m = r;
	if (m == id) return;
	_local_exchange(q, id, m);
	_fix_down(q, m);
}

static void
_fix_up(pqueue *q, size_t id)
{
	size_t p = PARENT(id);

	if(p >= ULONG_MAX ||
	    q->cmp(q->key[q->heap[p]], q->key[q->heap[id]]) > 0)
		return;
	_local_exchange(q, id, p);
	_fix_up(q, p);
}