Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Arbitrarily Nested Loops

by ikegami (Patriarch)
on Feb 03, 2006 at 20:53 UTC ( [id://527810]=note: print w/replies, xml ) Need Help??


in reply to Arbitrarily Nested Loops

Here's a complete (but untested) solution:

#ifndef _NESTED_LOOPS_H #define _NESTED_LOOPS_H /* -------------------- */ /* nested_loops.h */ struct NestedLoop_List { int length; void** ptr; /* arr of ptrs */ void (*free)(struct NestedLoop_List* list); /* frees ptr */ void* free_pad; /* closure-like */ }; #define NestedLoop_PT_ARRAY 0 #define NestedLoop_PT_FUNC 1 struct NestedLoop_ArrayArg { int length; void** ptr; }; struct NestedLoop_FuncArg void (*ptr)(struct NestedLoop_List* list, void* pad); void* pad; /* closure-like */ }; struct NestedLoop_Arg { int ptr_type; /* NestedLoop_PT_* */ union { struct NestedLoop_ArrayArg array; struct NestedLoop_FuncArg func; } ptr; }; struct NestedLoop_Iter { int num_loops; struct NestedLoopArg* loops; int* indexes; struct NestedLoop_List* vals; struct NestedLoop_List list; }; void NestedLoop_no_free(void*); void NestedLoops_array_to_list( struct NestedLoop_List* list, void* array, int array_size, int elem_size ); void NestedLoops_array_to_ptr_array( void** ptr_array_ptr, void* array, int array_size, int elem_size ); void NestedLoops_free_list(struct NestedLoop_List* list); void NestedLoops_get_iter( struct NestedLoop_Iter* iter, int num_loops, struct NestedLoop_Arg* loops ); BOOL NestedLoops_fetch( struct NestedLoop_Iter* iter ); void NestedLoops_done( struct NestedLoop_Iter* iter ); #endif
/* -------------------- */ /* nested_loops.c */ #include "nested_loops.h" void NestedLoop_list_free_none(void*) { /* Do nothing */ } void NestedLoops_array_to_list( struct NestedLoop_List* list, void* array, int array_size, int elem_size ) { (*list).length = array_size; (*list).free = &free; NestedLoops_to_ptr_array( &((*list).ptr), array, array_size, elem_size ); } void NestedLoops_to_ptr_array( void** ptr_array_ptr, void* array, int array_size, int elem_size ) { int src; void* dst; int i; ptr_array_ptr = (void**)calloc(ptr_array_size, sizeof(void*)); src = (int)array; dst = *ptr_array_ptr; for (i=array_size; i--; ) { *dst = (void*)src; dst++; src += elem_size; } } void NestedLoops_free_list(struct NestedLoop_List* list) { if ((*list).ptr != NULL) { (*list).free(list); (*list).length = 0; (*list).ptr = NULL; (*list).free = &NestedLoop_no_free; (*list).free_pad = NULL; } } void NestedLoops_get_iter( struct NestedLoop_Iter* iter, int num_loops, struct NestedLoop_Arg* loops, ) { (*iter).num_loops = num_loops; (*iter).loops = loops; (*iter).indexes = (int*)calloc(num_loops, sizeof(int)); (*iter).vals = (struct NestedLoop_List*)calloc(num_loops, si +zeof(struct NestedLoop_List)) (*iter).list.length = 0; (*iter).list.ptr = (void**)calloc(num_loops, sizeof(void*)); (*iter).list.free = &free; { int i = (*iter).num_loops; struct NestedLoop_Arg* loop = (*iter).loops; struct NestedLoop_List* loop_vals = (*iter).vals; while (i--) { if ((*loop).ptr_type == NestedLoop_PT_ARRAY) { (*loop_vals).length = (*loop).ptr.array.length; (*loop_vals).ptr = (*loop).ptr.array.ptr; (*loop_vals).free = &NestedLoop_no_free; (*loop_vals).free_pad = NULL; } else /* if ((*loop).ptr_type == NestedLoop_PT_FUNC) */ { (*loop_vals).length = 0; (*loop_vals).ptr = NULL; (*loop_vals).free = &NestedLoop_no_free; (*loop_vals).free_pad = NULL; } loop++; loop_vals++; } } } BOOL NestedLoops_fetch( struct NestedLoop_Iter* iter ) { int last_loop_idx = (*iter).num_loops - 1; int last_list_idx = (*iter).list.length - 1; /* Save on return! */ int* indexes = (*iter).indexes; if (last_list_idx < last_loop_idx) { struct NestedLoopArg* loops = (*iter).loops; indexes[++last_list_idx] = -1; if (loops[last_list_idx].ptr_type == NestedLoop_PT_FUNC) { struct NestedLoop_Arg* loop = &{loops[last_list_idx]); struct NestedLoop_List* loop_vals = &(vals [last_list_idx]); NestedLoops_free_list(loop_vals); (*(*arg).ptr.func.ptr)(loop_vals, (*arg).ptr.func.pad); } } /* If the last loop is done, */ /* increment the index of the previous loop. */ /* Exit if every loop is at its last index. */ for (;;) { struct NestedLoop_List* loop_vals = &(vals[last_list_idx]); ++indexes[last_list_idx]; if (indexes[last_list_idx] >= (*loop_vals).length) { break; } --last_list_idx; if (last_list_idx < 0) { (*iter).list.length = last_list_idx + 1; return FALSE; } } /* Populate the list. */ (*iter).list.ptr[last_list_idx] = vals[last_list_idx].ptr[indexes[last_list_idx]]; (*iter).list.length = last_list_idx + 1; return TRUE; } void NestedLoops_done( struct NestedLoop_Iter* iter ) { NestedLoops_free_list((*iter).list); { int i = (*iter).num_loops; struct NestedLoop_List* loop_vals = (*iter).vals; while (i--) { NestedLoops_free_list(loop_vals++); } } free((*iter).indexes); (*iter).indexes = NULL; }
/* -------------------- */ /* example.c */ /* Simple example: */ /* - No function pointers. */ /* - Data type is already a pointer. */ /* use Algorithm::Loops qw( NestedLoops ); my $iter = NestedLoops( [ [ qw( apple banana coconut ) ], [ qw( asparagus brocoli cauliflower ) ], [ qw( beef chicken ) ], ], ); while (@list = $iter->()) { print(join(' ', @list), "\n"); } */ #include <stdio.h> #include "nested_loops.h" void main() { /* This could be built dynamically. */ /* The args must remain accessible until done. */ /* NL's caller (i.e. us) handles cleanup of args. */ struct NestedLoop_Arg args[3]; char* fruits[3]; char* veggies[3]; char* meats[2]; fruits[0] = "apple"; fruits[1] = "banana"; fruits[2] = "coconut"; veggies[0] = "asparagus"; veggies[1] = "brocoli"; veggies[2] = "cauliflower"; meats[0] = "beef"; meats[1] = "chicken"; args[0].ptr_type = NestedLoop_PT_ARRAY; args[0].ptr.array.length = sizeof(fruits)/sizeof(fruits[0]); args[0].ptr.array.ptr = fruits; args[1].ptr_type = NestedLoop_PT_ARRAY; args[1].ptr.array.length = sizeof(veggies)/sizeof(veggies[0]); args[1].ptr.array.ptr = veggies; args[2].ptr_type = NestedLoop_PT_ARRAY; args[2].ptr.array.length = sizeof(meats)/sizeof(meats[0]); args[2].ptr.array.ptr = meats; { struct NestedLoop_Iter iter; NestedLoops_get_iter(&iter, sizeof(args)/sizeof(args[0]), args); while (NestedLoops_fetch(&iter)) { int i; /* Skip results without an element from each loop. */ if (iter.list.length != iter.num_loops) { continue; } for (i=0; i<iter.list.length; i++) { /* Would normally need to typecast */ /* the item from void* to char*, */ /* but printf doesn't care. */ printf("%s ", iter.list.ptr[i]); } printf("\n"); } NestedLoops_done(&iter); } }
/* -------------------- */ /* example2.c */ /* Example using a non-pointer type. */ /* use Algorithm::Loops qw( NestedLoops ); my $iter = NestedLoops( [ [ qw( a b c ) ], [ qw( ! @ # ) ], [ qw( 1 2 3 ) ], ], ); while (@list = $iter->()) { print(join(' ', @list), "\n"); } */ #include <stdio.h> #include "nested_loops.h" void main() { /* This could be built dynamically. */ /* The args must remain accessible until done. */ /* NL's caller (i.e. us) handles cleanup of args. */ struct NestedLoop_Arg args[3]; char* chars = "abc!@#123"; args[0].ptr_type = NestedLoop_PT_ARRAY; args[0].ptr.array.length = 3; NestedLoops_to_ptr_array(&(args[0].ptr.array.ptr), chars+0*3, 3, si +zeof(char)); args[1].ptr_type = NestedLoop_PT_ARRAY; args[1].ptr.array.length = 3; NestedLoops_to_ptr_array(&(args[1].ptr.array.ptr), chars+1*3, 3, si +zeof(char)); args[2].ptr_type = NestedLoop_PT_ARRAY; args[2].ptr.array.length = 3; NestedLoops_to_ptr_array(&(args[2].ptr.array.ptr), chars+2*3, 3, si +zeof(char)); { struct NestedLoop_Iter iter; NestedLoops_get_iter(&iter, sizeof(args)/sizeof(args[0]), args); while (NestedLoops_fetch(&iter)) { int i; /* Skip results without an element from each loop. */ if (iter.list.length != iter.num_loops) { continue; } for (i=0; i<iter.list.length; i++) { printf("%c ", *((char*)(iter.list.ptr[i])); } printf("\n"); } NestedLoops_done(&iter); } free(args[2].ptr.array.ptr); free(args[1].ptr.array.ptr); free(args[0].ptr.array.ptr); }
/* -------------------- */ /* example3.c */ /* Example using function pointers. */ /* use Algorithm::Loops qw( NestedLoops ); my $depth = 3; my $max = 4; my $iter = NestedLoops( [ [ 0 .. $max ], ( sub { [$_+1..$max] } ) x ($depth-1), ] ); while (@list = $iter->()) { print(join(' ', @list), "\n"); } */ #include <stdio.h> #include "nested_loops.h" struct RangePad { int min; int max; int* data; }; struct RangeIncPad { int max; int* data; }; void range_free(struct NestedLoop_List* list) { RangePad* pad; pad = (RangePad*)((*list).free_pad); free((*pad).data); (*pad).data = NULL; free((*list).ptr); (*list).ptr = NULL; } void range(struct NestedLoop_List* list, RangePad* pad) { int min; int max; int count; min = (*pad).min; max = (*pad).max; count = max - min + 1; if (count < 0) { count = 0; } free((*pad).data); (*pad).data = (int*)calloc(count, sizeof(int*)); { int* dst = (*pad).data; int i; for (i=min; i<=max; i++) { *(dst++) = i; } } (*list).length = count; (*list).free = &range_free; (*list).free_pad = pad; NestedLoops_to_ptr_array(&((*list).ptr), (*pad).data, count, sizeof +(int)); } void range_inc_free(struct NestedLoop_List* list) { RangeIncPad* pad; pad = (RangeIncPad*)((*list).free_pad); free((*pad).data); (*pad).data = NULL; free((*list).ptr); (*list).ptr = NULL; } void range_inc(struct NestedLoop_List* list, RangeIncPad* pad) { int min; int max; int count; min = (*list).ptr[(*list).length - 2] + 1; max = (*pad).max; count = max - min + 1; if (count < 0) { count = 0; } { int* dst = (*pad).data; int i; for (i=min; i<=max; i++) { *(dst++) = i; } } free((*pad).data); (*pad).data = (int*)calloc(count, sizeof(int*)); (*list).length = count; (*list).free = &range_inc_free; (*list).free_pad = pad; NestedLoops_to_ptr_array(&((*list).ptr), (*pad).data, count, sizeof +(int)); } void main() { /* This could be built dynamically. */ /* The args must remain accessible until done. */ /* NL's caller (i.e. us) handles cleanup of args. */ struct NestedLoop_Arg args[3]; struct RangePad pad0; struct RangeIncPad pad[2]; pad0.min = 1; pad0.max = 4; pad0.data = NULL; args[0].ptr_type = NestedLoop_PT_FUNC; args[0].ptr.func.ptr = &range; args[0].ptr.func.pad = &(pad[0]); pad[1-1].max = 4; pad[1-1].data = NULL; args[1].ptr_type = NestedLoop_PT_FUNC; args[1].ptr.func.ptr = &range_inc; args[1].ptr.func.pad = &(pad[1-1]); pad[2-1].max = 4; pad[2-1].data = NULL; args[2].ptr_type = NestedLoop_PT_FUNC; args[2].ptr.func.ptr = &range_inc; args[2].ptr.func.pad = &(pad[2-1]); { struct NestedLoop_Iter iter; NestedLoops_get_iter(&iter, sizeof(args)/sizeof(args[0]), args); while (NestedLoops_fetch(&iter)) { int i; /* Skip results without an element from each loop. */ if (iter.list.length != iter.num_loops) { continue; } for (i=0; i<iter.list.length; i++) { printf("%d ", *((int*)(iter.list.ptr[i])); } printf("\n"); } NestedLoops_done(&iter); } }

The core logic is a direct translation of tye's Algorithm::Loops's NestedLoops.

ug! It would have been much easier in C++!

  • Mini objects would replace pads.
  • Destructors would handle memory management.
  • (*type). would be replaced with type->.
  • Most occurances of the word struct could be omitted.
  • Wrapper classes would handle type issues.
  • Variable declerations wouldn't need to be seperated from their initialisation code.

Optimizing trick: In the last example, you know the maximum size of data, so you could allocate data outside of NestedLoops (and modify range and range_inc accordingly).

Update: Added Perl equivalent to examples.

Update: min's initialization was wrong in both range and range_inc.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://527810]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2024-03-28 12:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found