;============================================================
;  アルゴリズム 16〜20: 探索
;    16. Binary Search
;    17. Ternary Search (単峰関数の最大化)
;    18. Interpolation Search
;    19. Jump Search
;    20. BFS / DFS (グラフ)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 16. Binary Search -----
#module
#defcfunc binary_search array _a, int _n, int _target, \
	local _lo, local _hi, local _mid
	_lo = 0 : _hi = _n - 1
	repeat
		if _lo > _hi : return -1
		_mid = (_lo + _hi) / 2
		if _a(_mid) == _target : return _mid
		if _a(_mid) < _target : _lo = _mid + 1 : else : _hi = _mid - 1
	loop
#global

; ----- 17. Ternary Search: f(x) = -(x-7)^2 + 50 の最大化 -----
#module
#defcfunc _f int _x
	return -(_x - 7) * (_x - 7) + 50

#defcfunc ternary_max int _ra, int _rb, \
	local _lo, local _hi, local _m1, local _m2, local _best, local _bestv, local _v, local _i
	_lo = _ra : _hi = _rb
	repeat
		if _hi - _lo <= 2 : break
		_m1 = _lo + (_hi - _lo) / 3
		_m2 = _hi - (_hi - _lo) / 3
		if _f(_m1) < _f(_m2) : _lo = _m1 + 1 : else : _hi = _m2 - 1
	loop
	_best = _lo : _bestv = _f(_lo)
	repeat _hi - _lo + 1
		_i = _lo + cnt
		_v = _f(_i)
		if _v > _bestv : _bestv = _v : _best = _i
	loop
	return _best
#global

; ----- 18. Interpolation Search -----
#module
#defcfunc interpolation_search array _a, int _n, int _target, \
	local _lo, local _hi, local _ix
	_lo = 0 : _hi = _n - 1
	repeat
		if _lo > _hi : return -1
		if _target < _a(_lo) : return -1
		if _target > _a(_hi) : return -1
		if _a(_hi) == _a(_lo) {
			if _a(_lo) == _target : return _lo
			return -1
		}
		_ix = _lo + ((_target - _a(_lo)) * (_hi - _lo)) / (_a(_hi) - _a(_lo))
		if _a(_ix) == _target : return _ix
		if _a(_ix) < _target : _lo = _ix + 1 : else : _hi = _ix - 1
	loop
#global

; ----- 19. Jump Search -----
#module
#defcfunc jump_search array _a, int _n, int _target, \
	local _stp, local _prev, local _i
	_stp = int(sqrt(1.0 * _n))
	if _stp < 1 : _stp = 1
	_prev = 0
	repeat
		if _prev >= _n : break
		if _a(_prev) >= _target : break
		_prev += _stp
	loop
	_i = _prev - _stp
	if _i < 0 : _i = 0
	repeat
		if _i >= _n : return -1
		if _a(_i) > _target : return -1
		if _a(_i) == _target : return _i
		_i++
	loop
#global

; ----- 20. BFS / DFS -----
#module
#deffunc bfs_dfs_demo array _edges, int _n_edges, int _n_nodes, int _start, \
	local _head, local _nx, local _to, local _ne, local _u, local _v, \
	local _front, local _rear, local _vertex, local _e, local _line, local _q, local _vis, \
	local _sp, local _st

	dim _head, _n_nodes
	repeat _n_nodes : _head(cnt) = -1 : loop
	dim _nx, _n_edges * 2
	dim _to, _n_edges * 2
	_ne = 0
	repeat _n_edges
		_u = _edges(cnt * 2)
		_v = _edges(cnt * 2 + 1)
		_to(_ne) = _v : _nx(_ne) = _head(_u) : _head(_u) = _ne : _ne++
		_to(_ne) = _u : _nx(_ne) = _head(_v) : _head(_v) = _ne : _ne++
	loop

	; BFS
	dim _vis, _n_nodes
	dim _q, _n_nodes
	_front = 0 : _rear = 0
	_q(_rear) = _start : _rear++
	_vis(_start) = 1
	sdim _line, 256
	_line = "BFS: " + _start
	repeat
		if _front >= _rear : break
		_vertex = _q(_front) : _front++
		_e = _head(_vertex)
		repeat
			if _e == -1 : break
			if _vis(_to(_e)) == 0 {
				_vis(_to(_e)) = 1
				_q(_rear) = _to(_e) : _rear++
				_line += " -> " + _to(_e)
			}
			_e = _nx(_e)
		loop
	loop
	mes _line

	; DFS (iterative)
	dim _vis, _n_nodes
	dim _st, _n_nodes * 2 + 16
	_sp = 0
	_st(_sp) = _start : _sp++
	_line = "DFS:"
	repeat
		if _sp <= 0 : break
		_sp--
		_vertex = _st(_sp)
		if _vis(_vertex) : continue
		_vis(_vertex) = 1
		_line += " " + _vertex
		_e = _head(_vertex)
		repeat
			if _e == -1 : break
			if _vis(_to(_e)) == 0 : _st(_sp) = _to(_e) : _sp++
			_e = _nx(_e)
		loop
	loop
	mes _line
	return
#global

; ===== デモ =====
	mes "=== Array Search ==="
	dim a, 10
	a = 2, 5, 7, 10, 14, 19, 23, 28, 35, 42
	mes "Array: 2 5 7 10 14 19 23 28 35 42"
	mes strf("BinarySearch(23) = %d",         binary_search(a, 10, 23))
	mes strf("InterpolationSearch(23) = %d",  interpolation_search(a, 10, 23))
	mes strf("JumpSearch(23) = %d",           jump_search(a, 10, 23))
	mes strf("BinarySearch(6) = %d (期待: -1)", binary_search(a, 10, 6))

	mes ""
	mes "=== Ternary Search ==="
	mes strf("argmax of -(x-7)^2+50 in [0,20] = %d (期待: 7)", ternary_max(0, 20))

	mes ""
	mes "=== Graph BFS/DFS ==="
	dim edges, 12
	edges = 0,1, 0,2, 1,3, 1,4, 2,5, 3,6
	bfs_dfs_demo edges, 6, 7, 0
	end 0