Is there a name for this algorithm?

Question

Apologies for the non-descriptive question; if you can think of a better one, I'm all ears.

I'm writing some Perl to implement an algorithm and the code I have smells fishy. Since I don't have a CS background, I don't have a lot of knowledge of standard algorithms in my back pocket, but this seems like something that it might be.

Let me describe what I'm doing by way of metaphor:

• You have a conveyor belt of oranges. The oranges pass you one by one. You also have an unlimited supply of flat-packed boxes.
• For each orange, check it. If it is rotten, dispose of it
• If it is good, put it in a box. If you don't have a box, grab a new one and construct it.
• If the box has 10 oranges in it, close it up and put it on a pallet. Do not construct a new one.
• Repeat until you have no more oranges
• If you have a constructed box with some oranges in it, close it up and put it on a pallet

So, we have an algorithm for processing items in a list, if they meet some criteria, they should be added to a structure which, when it meets some other criteria, should be 'closed out'. Also, once the list has been processed, if there's an 'open' structure, it should be 'closed out' as well.

Naively, I assume that the algorithm consists of a loop acting over the list, with a conditional to see if the list element belongs in the structure and a conditional to see if the structure needs to be 'closed'. Outside the loop, there would be one more conditional to close any outstanding structures.

So, here are my questions:

1. Is this a description of a well-known algorithm? If so, does it have a name?
2. Is there an effective way to coalesce the 'closing out the box' activity into a single place, as opposed to once inside the loop and once outside of the loop?

I tagged this as 'Perl' because Perlish approaches are of interest, but I'd be interested to hear of any other languages that have neat solutions to this.

Answer 1

It's a nice fit with a functional approach - you're iterating over a stream of Oranges, testing, grouping and operating on them. In Scala, it would be something like:

 val oranges:Stream[Oranges] = ... // generate a stream of Oranges

 oranges.filter(_.isNotRotten).grouped(10).foreach{ o => {(new Box).fillBox(o)}}

(grouped does the right thing with the partial box at the end)

There's probably Perl equivalents.

Answer 2

Is there an effective way to coalesce the 'closing out the box' activity into a single place, as opposed to once inside the loop and once outside of the loop?

Yes. Simply add "... or there are no more oranges" to the "does the structure need to be closed" function. The easiest way of doing this is a do/while construct (technically speaking it's NOT a loop in Perl, though it looks like one):

my $current_container;
my $more_objects;
do {
    my $object = get_next_object();  # Easiest implementation returns undef if no more 
    $more_objects = more_objects($object) # Easiest to implement as "defined $object"
    if (!$more_objects || can_not_pack_more($current_container) { 
        close_container($current_container);
        $current_container = open_container() if $more_objects;
    }
    pack($object, $current_container) if $more_objects;
} while ($more_objects);

IMHO, this doesn't really win you anything if the close_container() is encapsulated into a method - there's no major technical or code quality cost to calling it both inside and outside the loop. Actually, I'm strongly of the opinion that a convoluted workaround like I presented above is WORSE code quality wise than a straightforward:

my $current_container;
while (my $more_objects = more_objects(my $object = get_next_object())) {
    if (can_not_pack_more($current_container)) { # false on undef
        close_container($current_container);
    }
    $current_container = open_container_if_closed($current_container); # if defined
    pack($object, $current_container);
}
close_container($current_container);