; SEARCH - search symbol tree for an ASCII string
; Mike Gabrielson   8/10/78
; accepts: BC = address of string to look for, terminated by NULL
;          DE = address of ROOT pointer
;          HL = contents of ROOT pointer (equal to address of
;               first node if not grounded)
; returns: carry set if string not found in tree (DE = address
;               of last grounded pointer)
;          else carry cleared (string found, HL = address of
;               node containing the matching string)
;================================================================

NULL	EQU	0	;end of string character

SEARCH: MOV	A,H	;is the pointer grounded,
	ORA	L	;indicating end of tree?
	STC		;(assume "yes")
	RZ		;yes, end of tree, string not found
	PUSH	B	;no, save address of caller's string
	PUSH	H	;save address of node
	INX	H	;skip past the node's
	INX	H	;left and right subtree pointers
	INX	H	;and stop at the first character
	INX	H	;of the node's string
NEXTC:	LDAX	B	;get character from caller's string.
	CMP	M	;same as character in node's string?
	JNZ	TESTED	;no, wrong node
	INX	B	;yes,
	INX	H	;point to next character pair
	CPI	NULL	;was that the end of the strings?
	JNZ	NEXTC	;no, test next pair
TESTED:	POP	H	;restore address of node
	POP	B	;restore address of caller's string
	RZ		;done if strings matched (carry's cleared)
	JC	LEFT	;pick left subtree if caller's string is low
	INX	H	;else get address of right subtree pointer
	INX	H
LEFT:	MOV	D,M	;get address of subtree into DE
	INX	H
	MOV	E,M
	XCHG		;then into HL
	DCX	D	;leave DE pointing to last node accessed
	JMP	SEARCH	;continue searching down the tree

	END