;;; Chickadee Game Toolkit
;;; Copyright © 2021 David Thompson <dthompson2@worcester.edu>
;;;
;;; Licensed under the Apache License, Version 2.0 (the "License");
;;; you may not use this file except in compliance with the License.
;;; You may obtain a copy of the License at
;;;
;;;    http://www.apache.org/licenses/LICENSE-2.0
;;;
;;; Unless required by applicable law or agreed to in writing, software
;;; distributed under the License is distributed on an "AS IS" BASIS,
;;; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;;; See the License for the specific language governing permissions and
;;; limitations under the License.

(define-module (tests quadtree)
  #:use-module (tests utils)
  #:use-module (srfi srfi-64)
  #:use-module (chickadee data quadtree)
  #:use-module (chickadee math rect))

(define (quadtree)
  (make-quadtree (make-rect 0 0 100 100) #:max-size 3 #:max-depth 2))

(with-tests "quadtree"
  (test-group "quadtree-insert!"
    (test-group "inserting a single object"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (test-equal (quadtree-size q) 1)
        (test-assert (quadtree-leaf? q))))
    (test-group "inserting maximum objects for one node"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'bar)
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
        (test-equal (quadtree-size q) 3)
        (test-assert (quadtree-leaf? q))))
    (test-group "splitting where all objects move to child nodes"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'foo)
        (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'bar)
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
        (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'frob)
        (test-equal (quadtree-size q) 0)
        (test-assert (not (quadtree-leaf? q)))))
    (test-group "splitting where all objects stay in parent node"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'foo)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'bar)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'baz)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'frob)
        (test-equal (quadtree-size q) 4)
        (test-assert (quadtree-leaf? q)))))
  (test-group "quadtree-delete!"
    (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (test-equal "deleting from a root node with 1 object"
          (quadtree-size q) 0))
    (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'bar)
        (quadtree-insert! q (make-rect 30.0 10.0 10.0 10.0) 'baz)
        (quadtree-delete! q (make-rect 30.0 10.0 10.0 10.0) 'bar)
        (test-equal "deleting from a root node with multiple objects"
          (quadtree-size q) 2))
    (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
        (quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
        (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
        (quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
        (test-assert "deleting from a lower node"
          (quadtree-delete! q (make-rect 25.0 10.0 10.0 10.0) 'frob)))
    (let ((q (quadtree)))
      (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
      (quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
      (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
      (quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
      (quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
      (test-assert "clearing out a level"
        (quadtree-leaf? (quadtree-q3 q)))))
  (test-group "quadtree-fold"
    (test-equal "rect within a single leaf node at level 0"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
        (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
        (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
        (quadtree-fold q (make-rect 0.0 0.0 40.0 40.0) '() cons))
      '(three five))
    (test-equal "rect spans multiple nodes at level 1"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
        (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
        (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
        (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
        (quadtree-fold q (make-rect 0.0 0.0 60.0 40.0) '() cons))
      '(four three five))
    (test-equal "rect within a single leaf node at level 2"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 80.0 80.0 10.0 10.0) 'one)
        (quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
        (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
        (quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
        (quadtree-insert! q (make-rect 65.0 65.0 10.0 10.0) 'five)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'six)
        (quadtree-fold q (make-rect 76.0 76.0 20.0 20.0) '() cons))
      '(one five six))
    (test-equal "rect spans multiple nodes at level 2"
      (let ((q (quadtree)))
        (quadtree-insert! q (make-rect 70.0 70.0 10.0 10.0) 'one)
        (quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
        (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
        (quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
        (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
        (quadtree-fold q (make-rect 70.0 70.0 20.0 20.0) '() cons))
      '(four three two one five))))