swh:1:snp:9dcf3ab72851691ef27e40da9b2a50243c1bdd22
Tip revision: 5f23fb0b6e1d50d996ac54daaa7e637e5d8decaf authored by Software Heritage on 05 May 2020, 00:00:00 UTC
ipol: Deposit 1363 in collection ipol
ipol: Deposit 1363 in collection ipol
Tip revision: 5f23fb0
abstract_dsf.c
/*
* abstract_dsf.c
*
* Copyright (C) 2019, Enric Meinhardt-Llopis, CMLA, ÉNS Paris-Saclay.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include <assert.h>
// API
void adsf_assert_consistency(int *t, int n)
{
assert(n > 0);
assert(t);
for (int i = 0; i < n; i++)
{
assert(t[i] >= 0);
assert(t[i] < n);
}
}
// API
void adsf_begin(int *t, int n)
{
for (int i = 0; i < n; i++)
t[i] = i;
}
// API
int adsf_find(int *t, int n, int a)
{
assert(a >= 0 && a < n);
if (a != t[a])
t[a] = adsf_find(t, n, t[a]);
return t[a];
}
static int adsf_make_link(int *t, int n, int a, int b)
{
(void)n;
if (a < b) // arbitrary choice
{
t[b] = a;
return a;
}
else
{
t[a] = b;
return b;
}
}
// API
int adsf_union(int *t, int n, int a, int b)
{
assert(a >= 0 && a < n);
assert(b >= 0 && b < n);
a = adsf_find(t, n, a);
b = adsf_find(t, n, b);
if (a != b)
b = adsf_make_link(t, n, a, b);
return b;
}