#include <stdio.h>
#include <stdint.h>
int edges_start[3000];
int edges_end[3000];
float edges_len[3000];
int g_links_id[1000][100];
float g_links_weight[1000][100];
int cache_id[1000];
float cache_distance[1000];
int cache_prev[1000];
int cache_links_id[1000][100];
float cache_links_weight[1000][100];
int queue_id[1000];
float queue_distance[1000];
int queue_prev[1000];
int queue_links_id[1000][100];
float queue_links_weight[1000][100];
int queue_links_id_len[1000];
// MUSL memset implementation:
// https://github.com/esmil/musl/blob/master/src/string/memset.c
#include <stdint.h>
#include <string.h>
void* __attribute__((weak)) memset(void* dest, int c, size_t n)
{
unsigned char* s = dest;
size_t k;
if(!n)
{
return dest;
}
s[0] = s[n - 1] = (unsigned char)c;
if(n <= 2)
{
return dest;
}
s[1] = s[n - 2] = (unsigned char)c;
s[2] = s[n - 3] = (unsigned char)c;
if(n <= 6)
{
return dest;
}
s[3] = s[n - 4] = (unsigned char)c;
if(n <= 8)
{
return dest;
}
k = -(uintptr_t)s & 3;
s += k;
n -= k;
n &= (unsigned long)-4;
n /= 4;
// Cast to void first to prevent alignment warning
uint32_t* ws = (uint32_t*)(void*)s;
uint32_t wc = c & 0xFF;
wc |= ((wc << 8) | (wc << 16) | (wc << 24));
/* Pure C fallback with no aliasing violations. */
for(; n; n--, ws++)
{
*ws = wc;
}
return dest;
}
#include <string.h>
typedef int word;
#define wsize sizeof(word)
#define wmask (wsize - 1)
void* memcpy(void* dst0, const void* src0, size_t length)
{
char* dst = dst0;
const char* src = src0;
size_t t;
if(length == 0 || dst == src)
{
/* nothing to do */
goto done;
}
#define TLOOP(s) if (t) TLOOP1(s)
#define TLOOP1(s) do { s; } while (--t)
if((uintptr_t)dst < (uintptr_t)src)
{
t = (uintptr_t)src; /* only need low bits */
if((t | (uintptr_t)dst) & wmask)
{
if((t ^ (uintptr_t)dst) & wmask || length < wsize)
{
t = length;
}
else
{
t = wsize - (t & wmask);
}
length -= t;
TLOOP1(*dst++ = *src++);
}
t = length / wsize;
// Silence warning for alignment change by casting to void*
TLOOP(*(word*)(void*)dst = *(const word*)(const void*)src; src += wsize; dst += wsize);
t = length & wmask;
TLOOP(*dst++ = *src++);
}
else
{
src += length;
dst += length;
t = (uintptr_t)src;
if((t | (uintptr_t)dst) & wmask)
{
if((t ^ (uintptr_t)dst) & wmask || length <= wsize)
{
t = length;
}
else
{
t &= wmask;
}
length -= t;
TLOOP1(*--dst = *--src);
}
t = length / wsize;
// Silence warning for alignment change by casting to void*
TLOOP(src -= wsize; dst -= wsize; *(word*)(void*)dst = *(const word*)(const void*)src);
t = length & wmask;
TLOOP(*--dst = *--src);
}
done:
return (dst0);
}
void init_cpp(int L) {
for (int i=0; i < L; i++) {
queue_links_id_len[i] = 0;
cache_id[i] = -2;
queue_id[i] = -2;
cache_distance[i] = 100000;
queue_distance[i] = 100000;
cache_prev[i] = -2;
queue_prev[i] = -2;
for (int j=0; j < 100; j++) {
queue_links_id[i][j] = -2;
queue_links_weight[i][j] = 100000;
cache_links_id[i][j] = -2;
cache_links_weight[i][j] = 100000;
}
}
}
void init_edges_cpp() {
for (int i=0; i < 3000; i++) {
edges_start[i] = -2;
edges_end[i] = -2;
edges_len[i] = -2.0;
}
for (int i=0; i < 1000; i++) {
for (int j=0; j < 100; j++) {
g_links_id[i][j] = -2;
g_links_weight[i][j] = -2.0;
}
}
}
void add_edge_cpp(int index, int start, int end, float len) {
edges_start[index] = start;
edges_end[index] = end;
edges_len[index] = len;
}
void fill_graph_cpp() {
for (int i=0; i < 3000; i++) {
int s = edges_start[i];
int e = edges_end[i];
float len = edges_len[i];
if (s == -2) {
break;
}
int links_len = 0;
for (int j=0; j < 100; j++) {
if (g_links_id[s][j] == -2) {
links_len = j;
break;
}
}
g_links_id[s][links_len] = e;
g_links_weight[s][links_len] = len;
for (int j=0; j < 100; j++) {
if (g_links_id[e][j] == -2) {
links_len = j;
break;
}
}
g_links_id[e][links_len] = s;
g_links_weight[e][links_len] = len;
}
}
void get_dists_cpp(int a, int L) {
int i = L;
while (--i >= 0) {
for (int j = 0; j < 100; j++) {
//console.log()
if (g_links_id[i][j] == -2) {
break;
}
cache_links_id[i][j] = g_links_id[i][j];
cache_links_weight[i][j] = g_links_weight[i][j];
}
cache_id[i] = i;
}
queue_id[0] = cache_id[a];
cache_distance[a] = 0;
queue_distance[0] = cache_distance[a];
queue_prev[0] = queue_prev[a];
for (int j=0; j < 100; j++) {
if (cache_links_id[a][j] == -2) {
queue_links_id_len[0] = j;
break;
}
queue_links_id[0][j] = cache_links_id[a][j];
queue_links_weight[0][j] = cache_links_weight[a][j];
}
i=0;
int queue_len = 1;
while (i < queue_len) {
int node_id = queue_id[i];
float node_distance = queue_distance[i];
int node_prev = queue_prev[i];
/*
int j=0;
for (int k=0; k < 100; k++) {
if (queue_links_id[i][k] == -2) {
j=k;
break;
}
}
*/
int j = queue_links_id_len[i];
while (--j >= 0) {
int link_id = queue_links_id[i][j];
float link_weight = queue_links_weight[i][j];
int c_id = cache_id[link_id];
float c_distance = cache_distance[link_id];
int c_prev = cache_prev[link_id];
float d = node_distance + link_weight;
if (d <= c_distance) {
cache_prev[link_id] = node_id;
cache_distance[link_id] = d;
queue_id[queue_len] = cache_id[link_id];
queue_distance[queue_len] = cache_distance[link_id];
for (int k=0; k < 100; k++) {
if (cache_links_id[link_id][k] == -2) {
queue_links_id_len[queue_len] = k;
break;
}
queue_links_id[queue_len][k] = cache_links_id[link_id][k];
queue_links_weight[queue_len][k] = cache_links_weight[link_id][k];
}
queue_prev[queue_len] = cache_prev[link_id];
queue_len++;
}
}
i++;
}
}
int get_edges_start(int index) {
return edges_start[index];
}
float get_cache_distance(int index) {
return cache_distance[index];
}
int get_cache_prev(int index) {
return cache_prev[index];
}
int main() {
init_edges_cpp();
init_cpp(5);
add_edge_cpp(0, 0, 2, 1);
add_edge_cpp(1, 0, 1, 1);
add_edge_cpp(2, 1, 2, 1);
add_edge_cpp(3, 2, 3, 1);
add_edge_cpp(4, 2, 4, 1);
add_edge_cpp(5, 3, 4, 1);
fill_graph_cpp();
get_dists_cpp(0, 5);
for (int i=0; i < 5; i++) {
printf("vert: %d ", i);
printf("dist: %f ", get_cache_distance(i));
printf("prev: %d\n", get_cache_prev(i));
}
return 0;
}
