1; Copyright (C) 2001-2010 MIYAMOTO Takanori
2; gnet-partslist-common.scm
3;
4; This program is free software; you can redistribute it and/or modify
5; it under the terms of the GNU General Public License as published by
6; the Free Software Foundation; either version 2 of the License, or
7; (at your option) any later version.
8;
9; This program is distributed in the hope that it will be useful,
10; but WITHOUT ANY WARRANTY; without even the implied warranty of
11; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12; GNU General Public License for more details.
13;
14; You should have received a copy of the GNU General Public License
15; along with this program; if not, write to the Free Software
16; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
18(define (get-parts-table packages)
19  (if (null? packages)
20      '()
21      (let ((package (car packages)))
22	(if (string=? (get-device package) "include")
23	    (get-parts-table (cdr packages))
24	    (cons (list package
25			(get-device package)
26			(get-value package)
27			(gnetlist:get-package-attribute package "footprint")) ;; sdb change
28		  (get-parts-table (cdr packages)))))))
29
30(define (write-one-row ls separator end-char port)
31  (if (null? ls)
32      '()
33      (begin (display (car ls) port)
34	     (for-each (lambda (st) (display separator port)(display st port)) (cdr ls))
35	     (display end-char port))))
36
37(define (get-sortkey-value ls key-column)
38  (list-ref (car ls) key-column))
39
40(define (marge-sort-sub ls1 ls2 key-column)
41  (if (or (null? ls1) (null? ls2))
42      (append ls1 ls2)
43      (if (string-ci<=? (get-sortkey-value ls1  key-column) (get-sortkey-value ls2 key-column))
44	  (cons (car ls1) (marge-sort-sub (cdr ls1) ls2 key-column))
45	  (cons (car ls2) (marge-sort-sub ls1 (cdr ls2) key-column)))))
46
47(define (marge-sort ls key-column)
48  (let ((midpoint (inexact->exact (floor (/ (length ls) 2)))))
49    (if (<= (length ls) 1)
50	(append ls)
51	(let ((top-half (reverse (list-tail (reverse ls) midpoint)))
52	      (bottom-half (list-tail ls (- (length ls) midpoint))))
53	  (set! top-half (marge-sort top-half key-column))
54	  (set! bottom-half (marge-sort bottom-half key-column))
55	  (marge-sort-sub top-half bottom-half key-column)))))
56
57(define (marge-sort-with-multikey ls key-columns)
58  (if (or (<= (length ls) 1) (null? key-columns))
59      (append ls)
60      (let* ((key-column (car key-columns))
61	     (sorted-ls (marge-sort ls key-column))
62	     (key-column-only-ls
63	      ((lambda (ls) (let loop ((l ls))
64			      (if (null? l)
65				  '()
66				  (cons (get-sortkey-value l key-column) (loop (cdr l))))))
67	       sorted-ls))
68	     (first-value (get-sortkey-value sorted-ls key-column))
69	     (match-length (length (member first-value (reverse key-column-only-ls))))
70	     (first-ls (list-tail (reverse sorted-ls) (- (length sorted-ls) match-length)))
71	     (rest-ls (list-tail sorted-ls match-length)))
72	(append (marge-sort-with-multikey first-ls (cdr key-columns))
73		(marge-sort-with-multikey rest-ls key-columns)))))
74