#include once "crt.bi"

#include once "tree.bi"

dim shared as node_t ptr tree_root
dim shared as integer    tree_size
dim shared as any ptr    tree_mutex

sub tree_init _
	( _
	)

	tree_mutex = mutexcreate( )

end sub

sub tree_deinit _
	( _
	)

	mutexdestroy( tree_mutex )

end sub

function tree_find _
	( _
		byval s as zstring ptr _
	) as node_t ptr ptr

	mutexlock( tree_mutex )

	dim as node_t ptr ptr node = @tree_root

	while *node
		dim as integer result = strcmp( strptr( (*node)->s ), s )
		if result > 0 then
			node = @(*node)->l
		elseif result < 0 then
			node = @(*node)->r
		else
			exit while
		end if
	wend

	function = node

	mutexunlock( tree_mutex )

end function

sub tree_add _
	( _
		byref s as string _
	)

	dim as node_t ptr ptr node = tree_find( s )

	mutexlock( tree_mutex )

	if *node = NULL then
		*node = callocate( sizeof( node_t ) )
		(*node)->s = s
		tree_size += 1
	end if

	(*node)->count += 1

	mutexunlock( tree_mutex )

end sub

dim shared as node_t ptr ptr list
dim shared as integer        list_len

sub tree_to_list _
	( _
		byval node as node_t ptr _
	)

	if node then
		tree_to_list( node->l )
		if node->count >= 10 then
			list[list_len] = node
			list_len += 1
		end if
		tree_to_list( node->r )
	end if

end sub

function mycmp cdecl _
	( _
		byval _l as any ptr, _
		byval _r as any ptr _
	) as integer

	dim as node_t ptr l = *cast( node_t ptr ptr, _l )
	dim as node_t ptr r = *cast( node_t ptr ptr, _r )

	if l->count > r->count then
		function = -1
	elseif l->count < r->count then
		function = 1
	end if

end function

sub tree_output _
	( _
	)

	list = callocate( tree_size * sizeof( node_t ptr ) )

	tree_to_list( tree_root )

	qsort( list, list_len, sizeof( node_t ptr ), @mycmp )

	for i as integer = 0 to list_len - 1
		printf( !"%i %s\n", list[i]->count, list[i]->s )
	next i

	deallocate( list )

end sub