Inspired by TDWTF's Cheaters Never Prosper
story, I decided to put together an example in C.
Given that we'll be dealing with arrays of int and we'll have to pass size information around, first, I declare a struct that holds a pointer to the array and the current size:
struct int_array_with_size {
size_t size;
int *ary;
};
This is mostly to avoid longish argument lists. Besides, it's good to keep related information together.
Next, we need a way of creating such arrays:
static struct int_array_with_size *
new_int_array_with_size(
size_t n_elem
)
{
struct int_array_with_size *p = malloc(sizeof(*p));
if (!p) {
return NULL;
}
p->ary = malloc(n_elem * (sizeof(*(p->ary))));
if (!p->ary) {
return NULL;
}
p->size = n_elem;
return p;
}
We'd end up writing a lot of extra lines without a simple function to free such a struct:
static void free_int_array_with_size(
struct int_array_with_size **p
)
{
free((*p)->ary);
(*p)->ary = NULL;
free(*p);
*p = NULL;
return;
}
A function to fill such an array with a bunch of integers is useful as well:
static void
fill_int_array(
struct int_array_with_size *p,
int start,
int delta
)
{
size_t i;
size_t k = p->size;
for (i = 0; i < k; i += 1) {
(p->ary)[i] = start;
start += delta;
}
return;
}
And, of course, we might want to print the contents, too:
static void
print_int_array(
const struct int_array_with_size *p
)
{
size_t i;
size_t k = p->size;
printf("[ ");
for (i = 0; i < (k - 1); i += 1) {
printf("%d, ", (p->ary)[i]);
}
printf("%d ]\n", (p->ary)[i]);
return;
}
And, of course, we'll need min and max:
static size_t min_size_t(const size_t x, const size_t y)
{
return (x < y) ? x : y;
}
static size_t max_size_t(const size_t x, const size_t y)
{
return (x > y) ? x : y;
}
Sure, you can define a generic macro, but I am allergic to macros that evaluate expressions more than once.
The algorithm for merging is quite simple: Allocate a similar array that can hold all the elements of the arrays to be merged. Then, fill in the even indexed elements from the first array, and the odd-indexed elements from the second array, until you reach the end of the shorter one. Then, fill in the rest of the elements from the longer one:
struct int_array_with_size *
merge_int_arrays(
const struct int_array_with_size *x,
const struct int_array_with_size *y
)
{
int *end = NULL;
int *dest = NULL;
int *src = NULL;
size_t limit = 0;
size_t remainder_size = 0;
struct int_array_with_size *r = malloc(sizeof(*r));
if (!r) {
return NULL;
}
r->size = x->size + y->size;
r->ary = malloc(r->size * sizeof(*(r->ary)));
if (!r->ary) {
free(r);
return NULL;
}
limit = min_size_t(x->size, y->size);
src = x->ary;
end = r->ary + 2 * limit;
for (dest = r->ary; dest < end; dest += 2) {
*dest = *src;
src += 1;
}
src = y->ary;
for (dest = (1 + r->ary); dest < end; dest += 2) {
*dest = *src;
src += 1;
}
dest = end;
remainder_size = sizeof(*(r->ary)) *
(max_size_t(x->size, y->size) - limit);
src = (x->size > y->size) ? x->ary : y->ary;
src += limit;
memcpy(dest, src, remainder_size);
return r;
}
Note the one bit of premature optimization where instead of having a single for loop that copies elements from both arrays in one go, I first fill in the even-indexed elements and then the odd-indexed elements based on the assumption that not jumping between memory locations is going to be faster. No, I didn't measure anything … just wrote it that way at first and later thought about why I did that ;-)
Finally, here's a short main as proof that code works for some values of "works":
int main(void) {
struct int_array_with_size *r;
struct int_array_with_size *x = new_int_array_with_size(3);
struct int_array_with_size *y = new_int_array_with_size(5);
if (!x || !y) {
return EXIT_FAILURE;
}
fill_int_array(x, 1, 3);
print_int_array(x);
fill_int_array(y, 1000, 10);
print_int_array(y);
r = merge_int_arrays(x, y);
if (!r) {
return EXIT_FAILURE;
}
print_int_array(r);
free_int_array_with_size(&r);
free_int_array_with_size(&y);
free_int_array_with_size(&x);
return EXIT_SUCCESS;
}
Of course, what would we do without a Perl version?
#!/usr/bin/env perl
use 5.014;
use strict;
use warnings;
sub make_iterator {
my $array = shift;
return sub {
state $i = 0;
return $i <= $#$array ? $array->[$i++] : ();
};
}
sub make_merger {
my $iterators = shift;
return sub { map $_->(), @$iterators };
}
my @iterators = map make_iterator($_), [1 .. 3], [5 .. 10];
my $merger = make_merger(\@iterators);
my @merged;
while (my @stripe = $merger->()) {
push @merged, @stripe;
}
say "[ @merged ]";
OK, now I am being silly. That handles an arbitrary number of arrays as well as data types.
