[cgds.git] / test / t.PriorityQueue.c

#include <stdlib.h>
#include "cgds/PriorityQueue.h"
#include "test/helpers.h"
#include "test/lut.h"

void t_priorityqueue_clear() //FTEST
{
	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 2);

	// NOTE: items with same priorities are supported; 
	// since it is unused in this test, we arbitrarily choose 0.0
	priorityqueue_insert(pq, 0, 0.0);
	priorityqueue_insert(pq, 0, 0.0);
	priorityqueue_insert(pq, 0, 0.0);

	priorityqueue_clear(pq);
	lu_assert(priorityqueue_empty(pq));

	priorityqueue_destroy(pq);
}

void t_priorityqueue_size() //FTEST
{
	PriorityQueue* pq = priorityqueue_new(double, MAX_T, 3);

	priorityqueue_insert(pq, 0.0, 0.0);
	priorityqueue_insert(pq, 0.0, 0.0);
	priorityqueue_insert(pq, 0.0, 0.0);
	lu_assert_int_eq(priorityqueue_size(pq), 3);

	priorityqueue_insert(pq, 0.0, 0.0);
	priorityqueue_insert(pq, 0.0, 0.0);
	lu_assert_int_eq(priorityqueue_size(pq), 5);

	priorityqueue_insert(pq, 0.0, 0.0);
	priorityqueue_insert(pq, 0.0, 0.0);
	priorityqueue_insert(pq, 0.0, 0.0);
	lu_assert_int_eq(priorityqueue_size(pq), 8);

	priorityqueue_destroy(pq);
}

void t_priorityqueue_push_pop_basic() //FTEST
{
	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);

	priorityqueue_insert(pq, 1, 1.0);
	priorityqueue_insert(pq, 2, 3.0);
	priorityqueue_insert(pq, 3, 2.0);
	priorityqueue_insert(pq, 4, 4.0);
	priorityqueue_insert(pq, 5, 0.0);

	int a;
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 5); //5 has "highest" priority (0.0, MIN_T)
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 1); //1 -> 1.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 3); //3 -> 2.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 2); //2 -> 3.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 4); //4 -> 4.0
	priorityqueue_pop(pq);
	lu_assert(priorityqueue_empty(pq));

	pq->heap->hType = MAX_T; //HACK... (why not?)
	priorityqueue_insert(pq, 1, 1.0);
	priorityqueue_insert(pq, 2, 3.0);
	priorityqueue_insert(pq, 3, 2.0);
	priorityqueue_insert(pq, 4, 4.0);
	priorityqueue_insert(pq, 5, 0.0);
	priorityqueue_insert(pq, 6, 0.0);
	priorityqueue_insert(pq, 7, 6.0);
	priorityqueue_remove(pq, 6);
	priorityqueue_remove(pq, 7);
	priorityqueue_set(pq, 3, 5.0);
	priorityqueue_set(pq, 5, 2.0);

	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 3); //3 has highest priority (5.0, MAX_T)
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 4); //4 -> 4.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 2); //2 -> 3.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 5); //5 -> 2.0
	priorityqueue_pop(pq);
	priorityqueue_peek(pq, a);
	lu_assert_int_eq(a, 1); // 1 -> 1.0
	priorityqueue_pop(pq);

	lu_assert(priorityqueue_empty(pq));
	priorityqueue_destroy(pq);
}

void t_priorityqueue_push_pop_evolved() //FTEST
{
	int n = 10;

	PriorityQueue* pq = priorityqueue_new(StructTest1, MAX_T, 2);
	StructTest1* st1 = (StructTest1*) safe_malloc(n * sizeof (StructTest1));
	for (int i = n - 1; i >= 0; i--)
	{
		st1[i].a = i;
		st1[i].b = (double) rand() / RAND_MAX;
		priorityqueue_insert(pq, *(st1 + i), i); //item i has priority i
	}
	for (int i = n - 1; i >= 0; i--)
	{
		StructTest1 st1Cell;
		priorityqueue_peek(pq, st1Cell);
		lu_assert_int_eq(st1Cell.a, i);
		priorityqueue_pop(pq);
	}
	safe_free(st1);
	priorityqueue_destroy(pq);

	pq = priorityqueue_new(StructTest2*, MAX_T, 4);
	StructTest2* st2 = (StructTest2*) safe_malloc(n * sizeof (StructTest2));
	for (int i = n - 1; i >= 0; i--)
	{
		st2[i].a = (float) rand() / RAND_MAX;
		st2[i].b = (StructTest1*) safe_malloc(sizeof (StructTest1));
		st2[i].b->a = i;
		st2[i].b->b = (double) rand() / RAND_MAX;
		// item i has priority i+1 if i is even, i-1 if i is odd
		// that is to say, priorities are 1 0 3 2 5 4 ...
		priorityqueue_insert(pq, st2 + i, i % 2 == 0 ? i + 1 : i - 1);
	}
	for (int i = n - 1; i >= 0; i--)
	{
		StructTest2* st2Cell;
		priorityqueue_peek(pq, st2Cell);
		// NOTE: i |--> i%2==0 ? i+1 : i-1 is an involution
		lu_assert_int_eq(st2Cell->b->a, i % 2 == 0 ? i + 1 : i - 1);
		priorityqueue_pop(pq);
		safe_free(st2Cell->b);
	}
	safe_free(st2);
	priorityqueue_destroy(pq);
}

void t_priorityqueue_copy() //FTEST
{
	int n = 10;

	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);
	for (int i = 0; i < n; i++)
		priorityqueue_insert(pq, rand() % 42, (double) rand() / RAND_MAX);
	PriorityQueue* pqc = priorityqueue_copy(pq);

	lu_assert_int_eq(priorityqueue_size(pq), priorityqueue_size(pqc));
	int a, b;
	for (int i = 0; i < n; i++)
	{
		priorityqueue_peek(pq, a);
		priorityqueue_peek(pqc, b);
		lu_assert_int_eq(a, b);
		priorityqueue_pop(pq);
		priorityqueue_pop(pqc);
	}
	priorityqueue_destroy(pq);
	priorityqueue_destroy(pqc);
}
Commit	Line	Data
a7868768 BA	1	#include <stdlib.h>
	2	#include "cgds/PriorityQueue.h"
	3	#include "test/helpers.h"
	4	#include "test/lut.h"
	5
	6	void t_priorityqueue_clear() //FTEST
	7	{
	8	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 2);
	9
	10	// NOTE: items with same priorities are supported;
	11	// since it is unused in this test, we arbitrarily choose 0.0
	12	priorityqueue_insert(pq, 0, 0.0);
	13	priorityqueue_insert(pq, 0, 0.0);
	14	priorityqueue_insert(pq, 0, 0.0);
	15
	16	priorityqueue_clear(pq);
	17	lu_assert(priorityqueue_empty(pq));
	18
	19	priorityqueue_destroy(pq);
	20	}
	21
	22	void t_priorityqueue_size() //FTEST
	23	{
	24	PriorityQueue* pq = priorityqueue_new(double, MAX_T, 3);
	25
	26	priorityqueue_insert(pq, 0.0, 0.0);
	27	priorityqueue_insert(pq, 0.0, 0.0);
	28	priorityqueue_insert(pq, 0.0, 0.0);
	29	lu_assert_int_eq(priorityqueue_size(pq), 3);
	30
	31	priorityqueue_insert(pq, 0.0, 0.0);
	32	priorityqueue_insert(pq, 0.0, 0.0);
	33	lu_assert_int_eq(priorityqueue_size(pq), 5);
	34
	35	priorityqueue_insert(pq, 0.0, 0.0);
	36	priorityqueue_insert(pq, 0.0, 0.0);
	37	priorityqueue_insert(pq, 0.0, 0.0);
	38	lu_assert_int_eq(priorityqueue_size(pq), 8);
	39
	40	priorityqueue_destroy(pq);
	41	}
	42
	43	void t_priorityqueue_push_pop_basic() //FTEST
	44	{
	45	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);
	46
	47	priorityqueue_insert(pq, 1, 1.0);
	48	priorityqueue_insert(pq, 2, 3.0);
	49	priorityqueue_insert(pq, 3, 2.0);
	50	priorityqueue_insert(pq, 4, 4.0);
	51	priorityqueue_insert(pq, 5, 0.0);
	52
	53	int a;
	54	priorityqueue_peek(pq, a);
	55	lu_assert_int_eq(a, 5); //5 has "highest" priority (0.0, MIN_T)
	56	priorityqueue_pop(pq);
	57	priorityqueue_peek(pq, a);
	58	lu_assert_int_eq(a, 1); //1 -> 1.0
	59	priorityqueue_pop(pq);
	60	priorityqueue_peek(pq, a);
	61	lu_assert_int_eq(a, 3); //3 -> 2.0
	62	priorityqueue_pop(pq);
	63	priorityqueue_peek(pq, a);
	64	lu_assert_int_eq(a, 2); //2 -> 3.0
65	priorityqueue_pop(pq);
66	priorityqueue_peek(pq, a);
67	lu_assert_int_eq(a, 4); //4 -> 4.0
68	priorityqueue_pop(pq);
69	lu_assert(priorityqueue_empty(pq));
70
71	pq->heap->hType = MAX_T; //HACK... (why not?)
72	priorityqueue_insert(pq, 1, 1.0);
73	priorityqueue_insert(pq, 2, 3.0);
74	priorityqueue_insert(pq, 3, 2.0);
75	priorityqueue_insert(pq, 4, 4.0);
76	priorityqueue_insert(pq, 5, 0.0);
77	priorityqueue_insert(pq, 6, 0.0);
78	priorityqueue_insert(pq, 7, 6.0);
79	priorityqueue_remove(pq, 6);
80	priorityqueue_remove(pq, 7);
81	priorityqueue_set(pq, 3, 5.0);
82	priorityqueue_set(pq, 5, 2.0);
83
84	priorityqueue_peek(pq, a);
85	lu_assert_int_eq(a, 3); //3 has highest priority (5.0, MAX_T)
86	priorityqueue_pop(pq);
87	priorityqueue_peek(pq, a);
88	lu_assert_int_eq(a, 4); //4 -> 4.0
89	priorityqueue_pop(pq);
90	priorityqueue_peek(pq, a);
91	lu_assert_int_eq(a, 2); //2 -> 3.0
92	priorityqueue_pop(pq);
93	priorityqueue_peek(pq, a);
94	lu_assert_int_eq(a, 5); //5 -> 2.0
95	priorityqueue_pop(pq);
96	priorityqueue_peek(pq, a);
97	lu_assert_int_eq(a, 1); // 1 -> 1.0
98	priorityqueue_pop(pq);
99
100	lu_assert(priorityqueue_empty(pq));
101	priorityqueue_destroy(pq);
102	}
103
104	void t_priorityqueue_push_pop_evolved() //FTEST
105	{
106	int n = 10;
107
108	PriorityQueue* pq = priorityqueue_new(StructTest1, MAX_T, 2);
109	StructTest1* st1 = (StructTest1) safe_malloc(n sizeof (StructTest1));
110	for (int i = n - 1; i >= 0; i--)
111	{
112	st1[i].a = i;
113	st1[i].b = (double) rand() / RAND_MAX;
114	priorityqueue_insert(pq, *(st1 + i), i); //item i has priority i
115	}
116	for (int i = n - 1; i >= 0; i--)
117	{
118	StructTest1 st1Cell;
119	priorityqueue_peek(pq, st1Cell);
120	lu_assert_int_eq(st1Cell.a, i);
121	priorityqueue_pop(pq);
122	}
123	safe_free(st1);
124	priorityqueue_destroy(pq);
125
126	pq = priorityqueue_new(StructTest2*, MAX_T, 4);
127	StructTest2* st2 = (StructTest2) safe_malloc(n sizeof (StructTest2));
128	for (int i = n - 1; i >= 0; i--)
129	{
130	st2[i].a = (float) rand() / RAND_MAX;
131	st2[i].b = (StructTest1*) safe_malloc(sizeof (StructTest1));
132	st2[i].b->a = i;
133	st2[i].b->b = (double) rand() / RAND_MAX;
134	// item i has priority i+1 if i is even, i-1 if i is odd
135	// that is to say, priorities are 1 0 3 2 5 4 ...
136	priorityqueue_insert(pq, st2 + i, i % 2 == 0 ? i + 1 : i - 1);
137	}
138	for (int i = n - 1; i >= 0; i--)
139	{
140	StructTest2* st2Cell;
141	priorityqueue_peek(pq, st2Cell);
142	// NOTE: i \|--> i%2==0 ? i+1 : i-1 is an involution
143	lu_assert_int_eq(st2Cell->b->a, i % 2 == 0 ? i + 1 : i - 1);
144	priorityqueue_pop(pq);
145	safe_free(st2Cell->b);
146	}
147	safe_free(st2);
148	priorityqueue_destroy(pq);
149	}
150
151	void t_priorityqueue_copy() //FTEST
152	{
153	int n = 10;
154
155	PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);
156	for (int i = 0; i < n; i++)
157	priorityqueue_insert(pq, rand() % 42, (double) rand() / RAND_MAX);
158	PriorityQueue* pqc = priorityqueue_copy(pq);
159
160	lu_assert_int_eq(priorityqueue_size(pq), priorityqueue_size(pqc));
161	int a, b;
162	for (int i = 0; i < n; i++)
163	{
164	priorityqueue_peek(pq, a);
165	priorityqueue_peek(pqc, b);
166	lu_assert_int_eq(a, b);
167	priorityqueue_pop(pq);
168	priorityqueue_pop(pqc);
169	}
170	priorityqueue_destroy(pq);
171	priorityqueue_destroy(pqc);
172	}