;; TRIE  in S2
;;   P. Chongstitvatana   12 Feb 2007

.symbol
  SYM  10000     ;; symbol table at 10000
  freecell 500   ;; global: freecell
  wp   501       ;; global: wp, point to WORD
  WORD 600       ;; input word

.code 200
;; allocate a new node, set char to c
;; input r1 = c,  no check for overflow!
:newnode
  push r31 r29
  push r31 r1
  ld r28 freecell
  st @SYM r28 r1      ;; store char
  add r1 r28 #4
  st freecell r1
  pop r31 r1
  pop r31 r29
  ret r29

;; scan(i,c)
;;    if sym[i] == 0
;;      sym[i] = newnode(c)
;;    return sym[i]

;; check if empty then insert c
;; r1 = i, r2 = c, r3 = test, r4 = temp
;; return index to current cell
:scan
  push r31 r29
  push r31 r1
  push r31 r2
  push r31 r3
  push r31 r4
  ld r28 @SYM r1
  eq r3 r28 #0
  jf r3 scan_ret
  mv r4 r1       ;; save i to r4
  mv r1 r2
  jal r29 newnode
  st @SYM r4 r28
:scan_ret
  pop r31 r4
  pop r31 r3
  pop r31 r2
  pop r31 r1
  pop r31 r29
  ret r29

;;  assume input word is at WORD, pointed to by wp
;;  return a char in r28
:getc
  push r31 r29
  push r31 r1
  ld r1 wp
  ld r28 @0 r1
  add r1 r1 #1
  st wp r1
  pop r31 r1
  pop r31 r29
  ret r29

;; search
;;   i = 0
;;   c = getc()
;;   while c != 0
;;     i = scan i+2 c     move next
;;     while sym[i] != c
;;       i = scan i+1 c   move right (choice)
;;     c = getc()
;;   return i             index to last matched node

;; let r5 = i, r6 = c, r3 = test, r4 = temp
:search
  push r31 r29
  push r31 r1
  push r31 r2
  push r31 r3
  push r31 r4
  push r31 r5
  push r31 r6
  mv r5 #0
  jal r29 getc
  mv r6 r28        ;; c = getc()
:while2
  ne r3 r6 #0      ;; while c != 0
  jf r3 search_ret
  add r1 r5 #2
  mv r2 r6
  jal r29 scan
  mv r5 r28        ;; i = scan i+2 c
:while1
  ld r4 @SYM r5
  ne r3 r4 r6      ;; while sym[i] != c
  jf r3 ewhile1
  add r1 r5 #1
  mv r2 r6
  jal r29 scan
  mv r5 r28        ;; i = scan i+1 c
  jmp while1
:ewhile1
  jal r29 getc
  mv r6 r28        ;; c = getc()
  jmp while2
:search_ret
  mv r28 r5
  pop r31 r6
  pop r31 r5
  pop r31 r4
  pop r31 r3
  pop r31 r2
  pop r31 r1
  pop r31 r29
  ret r29

;; r1 = i, r2 = val
:setvalue
  push r31 r1
  add r1 r1 #3
  st @SYM r1 r2
  pop r31 r1
  ret r29

;; r1 = i
:getvalue
  push r31 r1
  add r1 r1 #3
  ld r28 @SYM r1
  pop r31 r1
  ret r29

;; now try it.

.code 0
:main
  mv r31 #1000     ;; system stack at 1000
  mv r1  #WORD
  st wp r1         ;; set wp, point to WORD
  mv r1 #4
  st freecell r1   ;; freecell = 4
  jal r29 search
  mv r1 r28
  mv r2 #11
  jal r29 setvalue ;; insert 123, val 11
  jal r29 search
  mv r1 r28
  mv r2 #22
  jal r29 setvalue ;; insert 1356, val 22
  jal r29 search
  mv r1 r28
  jal r29 getvalue ;; search 123
  mv r30 r28       ;; print val
  trap 1
  trap 0

.data 600
  1 2 3 0
  1 3 5 6 0
  1 2 3 0
.end