Implement lower_bound() and upper_bound() methods for ZTable

3 files changed, 43 insertions, 4 deletions

diff --git a/lib/Slic3r/Print/Object.pm b/lib/Slic3r/Print/Object.pm
index ae7228ff3..1c21206d0 100644
--- a/lib/Slic3r/Print/Object.pm
+++ b/lib/Slic3r/Print/Object.pm
@@ -16,7 +16,7 @@ has 'copies'            => (is => 'rw', trigger => 1);  # in scaled coordinates
 has 'layers'            => (is => 'rw', default => sub { [] });
 has 'layer_height_ranges' => (is => 'rw', default => sub { [] }); # [ z_min, z_max, layer_height ]
 has 'fill_maker'        => (is => 'lazy');
-has '_z_table'          => (is => 'lazy');
+has '_slice_z_table'    => (is => 'lazy');
 
 sub BUILD {
     my $self = shift;
@@ -84,7 +84,7 @@ sub _build_fill_maker {
     return Slic3r::Fill->new(object => $self);
 }
 
-sub _build__z_table {
+sub _build__slice_z_table {
     my $self = shift;
     return Slic3r::Object::XS::ZTable->new([ map $_->slice_z, @{$self->layers} ]);
 }
@@ -105,7 +105,13 @@ sub layer_count {
 
 sub get_layer_range {
     my $self = shift;
-    return @{ $self->_z_table->get_range(@_) };
+    my ($min_z, $max_z) = @_;
+    
+    my $min_layer = $self->_slice_z_table->lower_bound($min_z); # first layer whose slice_z is >= $min_z
+    return (
+        $min_layer,
+        $self->_slice_z_table->upper_bound($max_z, $min_layer)-1, # last layer whose slice_z is <= $max_z
+    );
 }
 
 sub bounding_box {
diff --git a/xs/t/02_object.t b/xs/t/02_object.t
index 4ceddeda3..53a6f869b 100644
--- a/xs/t/02_object.t
+++ b/xs/t/02_object.t
@@ -4,9 +4,22 @@ use strict;
 use warnings;
 
 use Slic3r::XS;
-use Test::More tests => 1;
+use Test::More tests => 10;
 
 my $table = Slic3r::Object::XS::ZTable->new([ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]);
+is_deeply $table->get_range(31, 61), [2, 6], 'get_layer_range';
 is_deeply $table->get_range(39, 69), [2, 6], 'get_layer_range';
+is_deeply $table->get_range(30, 60), [2, 5], 'get_layer_range';
+
+# upper_bound points to the first element that is greater than argument
+is $table->upper_bound(30), 3, 'upper_bound';
+is $table->upper_bound(31), 3, 'upper_bound';
+is $table->upper_bound(39), 3, 'upper_bound';
+is $table->upper_bound(39, 4), 4, 'upper_bound with offset';
+
+# lower_bound points to the first element that is not less than argument
+is $table->lower_bound(31), 3, 'lower_bound';
+is $table->lower_bound(39), 3, 'lower_bound';
+is $table->lower_bound(40), 3, 'lower_bound';
 
 __END__
diff --git a/xs/xsp/Object.xsp b/xs/xsp/Object.xsp
index 2f8a0601e..9e800cdf8 100644
--- a/xs/xsp/Object.xsp
+++ b/xs/xsp/Object.xsp
@@ -8,6 +8,7 @@
 
 %name{Slic3r::Object::XS::ZTable} class ZTable {
     ZTable(std::vector<unsigned int>* z_array);
+    ~ZTable();
 
 %{
 std::vector<unsigned int>
@@ -47,6 +48,25 @@ get_range(THIS, min_z, max_z)
         }
     OUTPUT:
         RETVAL
+
+unsigned int
+ZTable::lower_bound(z, offset = 0)
+    unsigned int z
+    unsigned int offset
+    CODE:
+        RETVAL = std::lower_bound(THIS->z.begin() + offset, THIS->z.end(), z) - THIS->z.begin();
+    OUTPUT:
+        RETVAL
+
+unsigned int
+ZTable::upper_bound(z, offset = 0)
+    unsigned int z
+    unsigned int offset
+    CODE:
+        RETVAL = std::upper_bound(THIS->z.begin() + offset, THIS->z.end(), z) - THIS->z.begin();
+    OUTPUT:
+        RETVAL
+
 %}
 
 };