;; binary search in S2
;;  P. Chongstitvatana  12 Feb 2007

;; register convention
;; r31  system stack
;; r30  display
;; r29  link register
;; r28  return value

.symbol
  NIL -1
  NO  0
  YES 1

;; list operators
;; input in r1, (and r2 for cons)
;; return r28

.code 200
:head
  ld r28 @0 r1
  ret r29

:tail
  ld r28 @1 r1
  ret r29

:isatom
  ld r28 @0 r1   ;; get head
  lt r28 r28 #10 ;; value < 10 is atom
  ret r29

:atom
  trap 5         ;; get a cell
  st @0 r28 r0   ;; set head slot to type int
  st @1 r28 r1   ;; set tail to be data
  ret r29

:cons            ;; cons r1 r2
  trap 5         ;; get a cell
  st @0 r28 r1
  st @1 r28 r2
  ret r29

;; ---- bsearch ------

;; let r1 = input

:left
  push r31 r29
  jal r29 tail
  mv r1 r28
  jal r29 head
  pop r31 r29
  ret r29

:right
  push r31 r29
  jal r29 tail
  mv r1 r28
  jal r29 tail
  mv r1 r28
  jal r29 head
  pop r31 r29
  ret r29

;; get data from head(t)
:value
  push r31 r29
  jal r29 head
  mv r1 r28
  jal r29 tail
  pop r31 r29
  ret r29

;;  member(x,t)
;;   if t == NIL return NO
;;   if x == head(t) return YES
;;   if x < head(t) return member(x,left(t))
;;   return member(x,right(t))

;; let r1 = x, r2 = list, r3 = test, r4 = temp
:member
  push r31 r29
  push r31 r1
  push r31 r2
  push r31 r3
  push r31 r4
  eq r3 r2 #NIL
  jf r3 mem2
  mv r28 #NO
  jmp mem_ret
:mem2
  mv r4 r1       ;; save x in r4
  mv r1 r2       ;; pass t
  jal r29 value  ;; r28 = value(head(t))
  eq r3 r4 r28   ;; x == head(t)?
  jf r3 mem3
  mv r28 #YES
  jmp mem_ret
:mem3
  lt r3 r4 r28   ;; x < head(t)?
  jf r3 mem4
  mv r1 r2       ;; pass t
  jal r29 left
  mv r1 r4       ;; pass x
  mv r2 r28      ;; pass left(t)
  jal r29 member
  jmp mem_ret
:mem4
  mv r1 r2       ;; pass t
  jal r29 right
  mv r1 r4       ;; pass x
  mv r2 r28      ;; pass right(t)
  jal r29 member
:mem_ret
  pop r31 r4
  pop r31 r3
  pop r31 r2
  pop r31 r1
  pop r31 r29
  ret r29

;; Now we try it.  Make a list of
;; (2 (1 () ())(3 () (4 () ()))
;; and call member(3,t).

.code 0
:main
  mv r31 #1000    ;; system stack at 1000
  jal r29 make_t
  mv r30 r28
  trap 6          ;; display t
  mv r1 #3
  mv r2 r28
  jal r29 member  ;; member(3,t)
  mv r30 r28
  trap 1          ;; display result
  trap 0

;; input r1 = data, r2 = left, r3 = right
;; r4 =temp, r5 = temp
;; return (data left right)
:make_node
  push r31 r29
  push r31 r1
  push r31 r2
  push r31 r3
  push r31 r4
  push r31 r5
  jal r29 atom
  mv r4 r28    ;; save atom(data)
  mv r5 r2     ;; save left
  mv r1 r3
  mv r2 #NIL
  jal r29 cons
  mv r1 r5
  mv r2 r28    ;; r28 = (right)
  jal r29 cons ;; r28 = (left right)
  mv r1 r4     ;; atom(data)
  mv r2 r28
  jal r29 cons ;; r28 = (data left right)
  pop r31 r5
  pop r31 r4
  pop r31 r3
  pop r31 r2
  pop r31 r1
  pop r31 r29
  ret r29

;; Make a list of (2 (1 () ()) (3 () (4 () ())))
;; use r1, r2, r3, r4
:make_t
  push r31 r29
  mv r1 #4
  mv r2 #NIL
  mv r3 #NIL
  jal r29 make_node
  mv r1 #3
  mv r2 #NIL
  mv r3 r28
  jal r29 make_node
  mv r4 r28    ;; save (3 () (4 () ()))
  mv r1 #1
  mv r2 #NIL
  mv r3 #NIL
  jal r29 make_node
  mv r1 #2
  mv r2 r28   ;; r2 = (1 () ())
  mv r3 r4
  jal r29 make_node
  pop r31 r29
  ret r29

.end