;
; Support for term indices (pointers to subterms of terms)
; Chris Pressey, March 2008
;

; SPDX-FileCopyrightText: (c) 2008-2024 Chris Pressey, Cat's Eye Technologies
; This file is distributed under a 2-clause BSD license.  For more information see:
; SPDX-License-Identifier: LicenseRef-BSD-2-Clause-X-Treacle

;
; A term index is represented by a list of integers.  It uniquely
; identifies a subterm position of a term.
;

;
; Create a basic term index that refers to the entire term.
;
(define mk-base-index
  (lambda ()
    '()))

;
; Return a term index which points to the leftmost subterm of the
; term pointed to by the given term index.
;
(define descend-index
  (lambda (index)
    (cons 0 index)))

;
; Return a term index which points to the closest sibling term to
; the right of term pointed to by the given term index.
;
(define next-index
  (lambda (index)
    (cons (+ (car index) 1) (cdr index))))

;
; Retrieve the subterm of the given term at the given term index.
;
(define term-index-fetch
  (lambda (term index)
    (cond ((null? index)
            term)
          (else
            (term-index-fetch (list-ref term (car index)) (cdr index))))))

;
; Return a new term where the subterm at the given term index is replaced
; by the given replacement subterm.
;
(define term-index-store
  (lambda (term index replacement)
    (cond ((null? index)
            replacement)
          (else
            (let* ((nth-subterm (list-ref term (car index)))
                   (new-index   (cdr index))
                   (new-subterm (term-index-store nth-subterm new-index replacement)))
              (list-replace term (car index) new-subterm))))))

;
; Helper function for term-index-store.
;
(define list-replace
  (lambda (elems pos elem)
    (cond ((eq? pos 0)
            (cons elem (cdr elems)))
          (else
            (cons (car elems) (list-replace (cdr elems) (- pos 1) elem))))))