Merge branch 'master' of git://factorcode.org/git/factor

diff --git a/extra/math/binpack/authors.txt b/extra/math/binpack/authors.txt
new file mode 100644 (file)
index 0000000..e091bb8
--- /dev/null
+++ b/extra/math/binpack/authors.txt
@@ -0,0 +1 @@
+John Benediktsson

diff --git a/extra/math/binpack/binpack-docs.factor b/extra/math/binpack/binpack-docs.factor
new file mode 100644 (file)
index 0000000..36a29c7
--- /dev/null
+++ b/extra/math/binpack/binpack-docs.factor
@@ -0,0 +1,19 @@
+! Copyright (C) 2008 John Benediktsson
+! See http://factorcode.org/license.txt for BSD license
+
+USING: help.syntax help.markup kernel assocs sequences quotations ;
+
+IN: math.binpack 
+
+HELP: binpack
+{ $values { "assoc" assoc } { "n" "number of bins" } { "bins" "packed bins" } }
+{ $description "Packs the (key, value) pairs into the specified number of bins, using the value as a weight." } ;
+
+HELP: binpack*
+{ $values { "items" sequence } { "n" "number of bins" } { "bins" "packed bins" } } 
+{ $description "Packs a sequence of numbers into the specified number of bins." } ;
+
+HELP: binpack!
+{ $values { "items" sequence } { "quot" quotation } { "n" "number of bins" } { "bins" "packed bins" } } 
+{ $description "Packs a sequence of items into the specified number of bins, using the quotatino to determine the weight." } ;
+

diff --git a/extra/math/binpack/binpack-tests.factor b/extra/math/binpack/binpack-tests.factor
new file mode 100644 (file)
index 0000000..d0d4630
--- /dev/null
+++ b/extra/math/binpack/binpack-tests.factor
@@ -0,0 +1,13 @@
+! Copyright (C) 2008 John Benediktsson
+! See http://factorcode.org/license.txt for BSD license
+
+USING: kernel tools.test math.binpack ;
+
+[ t ] [ { V{ } } { } 1 binpack = ] unit-test
+
+[ t ] [ { { 3 } { 2 1 } } { 1 2 3 } 2 binpack* = ] unit-test
+
+[ t ] [ { { 1000 } { 100 60 30 7 } { 70 60 40 23 3 } } 
+        { 100 23 40 60 1000 30 60 07 70 03 } 3 binpack* = ] unit-test
+
+

diff --git a/extra/math/binpack/binpack.factor b/extra/math/binpack/binpack.factor
new file mode 100644 (file)
index 0000000..e3a009f
--- /dev/null
+++ b/extra/math/binpack/binpack.factor
@@ -0,0 +1,22 @@
+! Copyright (C) 2008 John Benediktsson
+! See http://factorcode.org/license.txt for BSD license
+
+USING: sequences kernel arrays vectors accessors assocs sorting math math.functions ;
+
+IN: math.binpack 
+
+: (binpack) ( bins item -- )
+    [ [ values sum ] map ] keep
+    zip sort-keys values first push ;
+
+: binpack ( assoc n -- bins )
+    [ sort-values <reversed> dup length ] dip
+    tuck / ceiling <array> [ <vector> ] map
+    tuck [ (binpack) ] curry each ;
+
+: binpack* ( items n -- bins )
+    [ dup zip ] dip binpack [ keys ] map ;
+
+: binpack! ( items quot n -- bins ) 
+    [ dupd map zip ] dip binpack [ keys ] map ;
+

diff --git a/extra/math/binpack/summary.txt b/extra/math/binpack/summary.txt
new file mode 100644 (file)
index 0000000..c8b9196
--- /dev/null
+++ b/extra/math/binpack/summary.txt
@@ -0,0 +1 @@
+Bin-packing algorithms.