;============================================================
;  アルゴリズム 36〜40: データ構造
;    36. Union-Find (DSU, path compression + union by rank)
;    37. Fenwick Tree (BIT, 区間和 + 点更新)
;    38. Priority Queue (Min-Heap)
;    39. Stack (LIFO)
;    40. Queue (FIFO)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 36. Union-Find -----
#module
#deffunc uf_init array _par, array _rk, int _n
	dim _par, _n
	dim _rk, _n
	repeat _n : _par(cnt) = cnt : loop
	return

#defcfunc uf_find array _par, int _x, local _r
	_r = _x
	repeat
		if _par(_r) == _r : break
		_r = _par(_r)
	loop
	return _r

#defcfunc uf_union array _par, array _rk, int _x, int _y, local _a, local _b
	_a = uf_find(_par, _x)
	_b = uf_find(_par, _y)
	if _a == _b : return 0
	if _rk(_a) < _rk(_b) {
		_par(_a) = _b
		return 1
	}
	if _rk(_a) > _rk(_b) {
		_par(_b) = _a
		return 1
	}
	_par(_b) = _a
	_rk(_a)++
	return 1
#global

; ----- 37. Fenwick Tree -----
#module
#deffunc bit_init array _bit, int _n
	dim _bit, _n + 1
	return

#deffunc bit_add array _bit, int _n, int _i, int _v, local _idx
	_idx = _i + 1
	repeat
		if _idx > _n : break
		_bit(_idx) += _v
		_idx += _idx & (-_idx)
	loop
	return

#defcfunc bit_sum array _bit, int _i, local _idx, local _s
	_s = 0 : _idx = _i + 1
	repeat
		if _idx <= 0 : break
		_s += _bit(_idx)
		_idx -= _idx & (-_idx)
	loop
	return _s
#global

; ----- 38. Priority Queue (Min-Heap) -----
#module
#deffunc pq_init array _pq, var _size
	dim _pq, 1024
	_size = 0
	return

#deffunc pq_push array _pq, var _size, int _v, local _i, local _p, local _t
	_pq(_size) = _v
	_i = _size
	_size++
	repeat
		if _i <= 0 : break
		_p = (_i - 1) / 2
		if _pq(_p) <= _pq(_i) : break
		_t = _pq(_p) : _pq(_p) = _pq(_i) : _pq(_i) = _t
		_i = _p
	loop
	return

#defcfunc pq_pop array _pq, var _size, local _top, local _i, local _l, local _r, local _s, local _t
	_top = _pq(0)
	_size--
	_pq(0) = _pq(_size)
	_i = 0
	repeat
		_l = 2 * _i + 1
		_r = 2 * _i + 2
		_s = _i
		if _l < _size : if _pq(_l) < _pq(_s) : _s = _l
		if _r < _size : if _pq(_r) < _pq(_s) : _s = _r
		if _s == _i : break
		_t = _pq(_i) : _pq(_i) = _pq(_s) : _pq(_s) = _t
		_i = _s
	loop
	return _top
#global

; ----- 39. Stack -----
#module
#deffunc stk_init array _stk, var _size
	dim _stk, 1024
	_size = 0
	return

#deffunc stk_push array _stk, var _size, int _v
	_stk(_size) = _v
	_size++
	return

#defcfunc stk_pop array _stk, var _size
	_size--
	return _stk(_size)
#global

; ----- 40. Queue (FIFO) - リングバッファ -----
#module
#deffunc q_init array _q, var _front, var _rear
	dim _q, 1024
	_front = 0 : _rear = 0
	return

#deffunc q_enqueue array _q, var _front, var _rear, int _v
	_q(_rear) = _v
	_rear++
	return

#defcfunc q_dequeue array _q, var _front, var _rear, local _v
	_v = _q(_front)
	_front++
	return _v
#global

; ===== デモ =====
	mes "=== Union-Find ==="
	uf_init par, rk, 5
	r = uf_union(par, rk, 0, 1)
	r = uf_union(par, rk, 2, 3)
	r = uf_union(par, rk, 1, 2)
	same = uf_find(par, 0) == uf_find(par, 3)
	mes strf("find(0)=find(3)? %d", same)

	mes ""
	mes "=== Fenwick Tree ==="
	bit_init bit, 10
	bit_add bit, 10, 3, 5
	bit_add bit, 10, 5, 3
	bit_add bit, 10, 8, 2
	mes strf("sum[0..5] = %d (期待: 8)",  bit_sum(bit, 5))
	mes strf("sum[0..9] = %d (期待: 10)", bit_sum(bit, 9))

	mes ""
	mes "=== Priority Queue (min-heap) ==="
	pq_init pq, sz
	pq_push pq, sz, 3
	pq_push pq, sz, 1
	pq_push pq, sz, 4
	pq_push pq, sz, 1
	pq_push pq, sz, 5
	sdim pline, 128
	pline = "pops: "
	repeat
		if sz <= 0 : break
		pline += "" + pq_pop(pq, sz) + " "
	loop
	mes pline

	mes ""
	mes "=== Stack ==="
	stk_init st, ssz
	stk_push st, ssz, 10
	stk_push st, ssz, 20
	stk_push st, ssz, 30
	mes strf("pop: %d, %d, %d", stk_pop(st, ssz), stk_pop(st, ssz), stk_pop(st, ssz))

	mes ""
	mes "=== Queue ==="
	q_init q, qf, qr
	q_enqueue q, qf, qr, 100
	q_enqueue q, qf, qr, 200
	q_enqueue q, qf, qr, 300
	mes strf("dequeue: %d, %d, %d", q_dequeue(q, qf, qr), q_dequeue(q, qf, qr), q_dequeue(q, qf, qr))
	end 0