Changeset 27052 in project


Ignore:
Timestamp:
07/12/12 05:10:43 (8 years ago)
Author:
Ivan Raikov
Message:

kd-tree: bug fixes related to changed internal node representation

Location:
release/4/kd-tree/trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • release/4/kd-tree/trunk/kd-tree.scm

    r27050 r27052  
    1919   kd-tree-fold-right*
    2020   kd-tree-subtrees
    21    kd-tree-points
    22    kd-tree-indices
     21   kd-tree-node-points
     22   kd-tree-node-indices
    2323   kd-tree-min-index
    2424   kd-tree-max-index
     
    180180            (pp (lambda (lst) (every point? lst)))
    181181            (vv (lambda (v) (or (list? v) (not v))))
    182             (axis integer?) )
     182            (axis positive-or-zero-integer?) )
    183183    )
    184184
     
    188188           (KdLeaf (ii pp vv axis) (cis:empty? ii))
    189189           (else #f)))
    190 
    191  
    192   (define (kd-tree->list t)
    193     (kd-tree-fold-right cons '() t))
    194 
    195  
    196   (define (kd-tree->list* t)
    197     (kd-tree-fold-right*
    198      (lambda (i v x ax) (cons (if v (list i v x) (list i x)) ax))
    199      '() t))
    200190
    201191 
     
    226216  (define (kd-tree-for-each* f t)
    227217    (cases kd-tree t
    228            (KdLeaf (ii pp vv axis) (for-each f (reverse (cis:elements ii)) vv pp))
     218           (KdLeaf (ii pp vv axis)
     219                   (if vv (for-each f (zip (reverse (cis:elements ii)) vv) pp)
     220                       (for-each f (reverse (cis:elements ii)) pp)))
    229221           (KdNode (l x i v r axis ci)
    230222                   (begin
    231223                     (kd-tree-for-each* f l)
    232                      (f i v x)
     224                     (if v (f (list i v) x) (f i x))
    233225                     (kd-tree-for-each* f r)
    234226                     ))
     
    251243           (KdLeaf (ii pp vv axis)
    252244                   (if vv
    253                        (fold-right f init (zip (reverse (cis:elements ii)) vv) pp)
     245                       (fold-right f init (reverse (cis:elements ii)) vv pp)
    254246                       (fold-right f init (reverse (cis:elements ii)) pp)))
    255247           (KdNode (l x i v r axis ci)
    256248                   (let* ((init2 (kd-tree-fold-right* f init r))
    257                           (init3 (f i v x init2)))
     249                          (init3 (if v (f (list i v) x init2) (f i x init2))))
    258250                     (kd-tree-fold-right* f init3 l)))
    259251           ))
    260252 
    261253 
     254
     255 
     256  (define (kd-tree->list t)
     257    (kd-tree-fold-right cons '() t))
     258
     259 
     260  (define (kd-tree->list* t)
     261    (kd-tree-fold-right*
     262     (lambda (iv x ax) (cons (list iv x) ax))
     263     '() t))
    262264 
    263265 
     
    275277
    276278 
    277   (define (kd-tree-points t)
     279  (define (kd-tree-node-points t)
    278280    (cases kd-tree t
    279281                  (KdLeaf (ii pp vv axis)  pp)
     
    281283                  ))
    282284 
    283   (define (kd-tree-indices t)
     285  (define (kd-tree-node-indices t)
    284286    (cases kd-tree t
    285287                  (KdLeaf (ii pp vv axis) (cis:elements ii))
     
    287289                  ))
    288290 
    289   (define (kd-tree-values t)
     291  (define (kd-tree-node-values t)
    290292    (cases kd-tree t
    291293                  (KdLeaf (ii pp vv axis) vv)
     
    296298    (cases kd-tree t
    297299           (KdLeaf (ii pp vv axis) (cis:cardinal ii))
    298            (KdNode (l x i r axis ci) (cis:cardinal ci))))
     300           (KdNode (l x i v r axis ci) (cis:cardinal ci))))
    299301
    300302  (define (kd-tree-min-index t)
    301303    (cases kd-tree t
    302304           (KdLeaf (ii pp vv axis) (cis:get-min ii))
    303            (KdNode (l x i r axis ci) (cis:get-min ci))))
     305           (KdNode (l x i v r axis ci) (cis:get-min ci))))
    304306
    305307  (define (kd-tree-max-index t)
    306308    (cases kd-tree t
    307309           (KdLeaf (ii pp vv axis) (cis:get-max ii))
    308            (KdNode (l x i r axis ci) (cis:get-max ci))))
     310           (KdNode (l x i v r axis ci) (cis:get-max ci))))
    309311
    310312
     
    364366                             (i (+ m median-index offset))
    365367                             (p (make-point median))
    366                              (v (or (and make-value (list i (make-value i median))) i))
     368                             (v (and make-value (make-value i median)))
    367369                             (axis (modulo depth (dimension p))))
    368370                       
     
    643645                                                             pp (map cadr ips)))
    644646                                                  )
    645                                                    (KdLeaf ii1 pp1 vv axis))
     647                                              (KdLeaf ii1 pp1 vv axis))
    646648                                            ))
    647649                                     ))
     
    654656                                 (if (equal? p p-kill)
    655657
    656                                      (if (integer? i)
    657                                          (let ((pts1 (append (kd-tree->list l) (kd-tree->list r))))
    658                                            (list->kd-tree 0 (length pts1) pts1 axis))
    659                                          (let ((pts1 (append (kd-tree->list* l) (kd-tree->list* r))))
    660                                            (list->kd-tree* 0 (length pts1) pts1 axis)))
     658                                     (let ((offset (if (kd-tree-empty? l) (+ i 1) (kd-tree-min-index l))))
     659                                       (if v
     660                                           (let ((pts1 (append (kd-tree->list* l) (kd-tree->list* r))))
     661                                             (list->kd-tree* 0 (length pts1) pts1 axis offset: offset))
     662                                           (let ((pts1 (append (kd-tree->list l) (kd-tree->list r))))
     663                                             (list->kd-tree 0 (length pts1) pts1 axis offset: offset))
     664                                         ))
    661665
    662666                                     (if (< (coord axis p-kill)
     
    828832
    829833      (make-<KdTree>
    830        (lambda (points #!key (leaf-factor 10) (point-ref identity) (make-value #f))
    831          ((list->kd-tree/depth point-ref make-value) 0 (length points) points 0 leaf-factor: leaf-factor))
     834       (lambda (points #!key
     835                       (leaf-factor 10)
     836                       (make-point identity)
     837                       (make-value #f)
     838                       (offset 0)
     839                       )
     840         ((list->kd-tree/depth make-point make-value)
     841          0 (length points) points 0
     842          leaf-factor: leaf-factor offset: offset))
    832843
    833844       (make-kd-tree-nearest-neighbor point-class)
  • release/4/kd-tree/trunk/kd-tree.setup

    r27040 r27052  
    44  (make-pathname #f fn ##sys#load-dynamic-extension))   
    55
    6 (compile -d0 -O2  -S -s kd-tree.scm -j kd-tree)
     6(compile -d -O2  -S -s kd-tree.scm -j kd-tree)
    77(compile -s kd-tree.import.scm)
    88
     
    1616 
    1717  ;; Assoc list with properties for your extension:
    18   '((version 2.11)
     18  '((version 3.0)
    1919    ))
Note: See TracChangeset for help on using the changeset viewer.