; SEARCH - search symbol tree for an ASCII string
; Mike Gabrielson   8/10/78
; accepts: BC = address of string to look for, terminated by NUL
;          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

	entry	search

search:
	ld	a,h		; Is the pointer grounded,
	or	l		; Indicating end of tree?
	scf			; (assume "yes")
	ret	z		; Yes, end of tree, string not found
	push	bc		; No, save address of caller's string
	push	hl		; Save address of node
	inc	hl		; Skip past the node's
	inc	hl		; Left and right subtree pointers
	inc	hl		; And stop at the first character
	inc	hl		; Of the node's string
nextc:
	ld	a,(bc)		; Get character from caller's string.
	cp	(hl)		; Same as character in node's string?
	jr	nz,tested	; No, wrong node
	inc	bc		; Yes,
	inc	hl		; Point to next character pair
	cp	null		; Was that the end of the strings?
	jr	nz,nextc	; No, test next pair
tested:
	pop	hl		; Restore address of node
	pop	bc		; Restore address of caller's string
	ret	z		; Done if strings matched (carry's cleared)
	jr	c,left		; Pick left subtree if caller's string is low
	inc	hl		; Else get address of right subtree pointer
	inc	hl
left:
	ld	d,(hl)		; Get address of subtree into DE
	inc	hl
	ld	e,(hl)
	ex	de,hl		; Then into HL
	dec	de		; Leave DE pointing to last node accessed
	jr	search		; Continue searching down the tree

	end