Index: trunk/src/global_typedefs.h
===================================================================
--- trunk/src/global_typedefs.h	(revision 9638)
+++ trunk/src/global_typedefs.h	(revision 9639)
@@ -44,6 +44,7 @@
 typedef struct pcb_pad_s pcb_pad_t;
 typedef struct pcb_pin_s pcb_pin_t;
 typedef struct pcb_rtree_s pcb_rtree_t;
+typedef struct pcb_rtree_it_s pcb_rtree_it_t;
 typedef struct pcb_ratspatch_line_s pcb_ratspatch_line_t;
 typedef struct pcb_element_s pcb_element_t;
 typedef struct pcb_subc_s pcb_subc_t;
Index: trunk/src/rtree.c
===================================================================
--- trunk/src/rtree.c	(revision 9638)
+++ trunk/src/rtree.c	(revision 9639)
@@ -53,10 +53,7 @@
  * This requires that the corner points not be equal!
  */
 
-/* the number of entries in each rtree node
- * 4 - 7 seem to be pretty good settings
- */
-#define M_SIZE 6
+#define M_SIZE PCB_RTREE_SIZE
 
 /* it seems that sorting the leaf order slows us down
  * but sometimes gives better routes
@@ -1003,3 +1000,79 @@
 #endif
 	return r;
 }
+
+
+static pcb_box_t *pcb_r_next_(pcb_rtree_it_t *it, struct rtree_node *curr)
+{
+	int n;
+
+	/* as long as we have boxes ready, ignore the tree */
+	if (it->num_ready > 0) {
+/*		printf("rdy1 get [%d]: %p\n", it->num_ready-1, it->ready[it->num_ready-1]);*/
+		return it->ready[--it->num_ready];
+	}
+
+	if (curr == NULL) {
+
+		got_filled:;
+
+		/* Next: get an element from the open list */
+		if (it->used <= 0)
+			return NULL;
+
+		curr = it->open[--it->used];
+/*		printf("open get [%d]: %p\n", it->used, curr);*/
+	}
+
+	if (curr->flags.is_leaf) {
+		/* current is leaf: copy children to the ready list and return the first */
+		for(it->num_ready = 0; it->num_ready < M_SIZE; it->num_ready++) {
+			if (curr->u.rects[it->num_ready].bptr == NULL)
+				break;
+			it->ready[it->num_ready] = curr->u.rects[it->num_ready].bptr;
+/*			printf("rdy  add [%d]: %p\n", it->num_ready, it->ready[it->num_ready]);*/
+		}
+		if (it->num_ready > 0) {
+/*			printf("rdy2 get [%d]: %p\n", it->num_ready-1, it->ready[it->num_ready-1]);*/
+			return it->ready[--it->num_ready];
+		}
+		assert(!"pcb_r_next_: empty leaf?!");
+	}
+
+	/* current is a level, add to the open list and retry until a leaf is found */
+	for(n = 0; n < M_SIZE; n++) {
+		if (curr->u.kids[n] != NULL) {
+			if (it->used >= it->alloced) {
+				it->alloced += 128;
+				it->open = realloc(it->open, it->alloced * sizeof(struct rtree_node *));
+			}
+			it->open[it->used] = curr->u.kids[n];
+/*			printf("open add [%d]: %p\n", it->used, it->open[it->used]);*/
+			it->used++;
+		}
+	}
+	goto got_filled;
+}
+
+pcb_box_t *pcb_r_first(pcb_rtree_t *tree, pcb_rtree_it_t *it)
+{
+	it->open = NULL;
+	it->alloced = it->used = 0;
+	it->num_ready = 0;
+	return pcb_r_next_(it, tree->root);
+}
+
+pcb_box_t *pcb_r_next(pcb_rtree_it_t *it)
+{
+	struct rtree_node *curr;
+
+	return pcb_r_next_(it, NULL);
+}
+
+void pcb_r_end(pcb_rtree_it_t *it)
+{
+	free(it->open);
+	it->open = NULL;
+	it->alloced = it->used = 0;
+}
+
Index: trunk/src/rtree.h
===================================================================
--- trunk/src/rtree.h	(revision 9638)
+++ trunk/src/rtree.h	(revision 9639)
@@ -40,6 +40,19 @@
 	int size;											/* number of entries in tree */
 };
 
+/* the number of entries in each rtree node
+ * 4 - 7 seem to be pretty good settings
+ */
+#define PCB_RTREE_SIZE 6
+
+
+struct pcb_rtree_it_s {
+	struct rtree_node **open;
+	int used, alloced;
+	pcb_box_t *ready[PCB_RTREE_SIZE + 1];
+	int num_ready;
+};
+
 /* callback direction to the search engine */
 typedef enum pcb_r_dir_e {
 	PCB_R_DIR_NOT_FOUND = 0,         /* object not found or not accepted */
@@ -82,4 +95,17 @@
 
 void pcb_r_dump_tree(struct rtree_node *, int);
 
+
+/* -- Iterate through an rtree; DO NOT modify the tree while iterating -- */
+
+/* Get the first item, get fields of iterator set up; return can be casted to an object; returns NULL if rtree is empty */
+pcb_box_t *pcb_r_first(pcb_rtree_t *tree, pcb_rtree_it_t *it);
+
+/* Get the next item, return can be casted to an object; returns NULL if no more items */
+pcb_box_t *pcb_r_next(pcb_rtree_it_t *it);
+
+/* Free fields of the iterator */
+void pcb_r_end(pcb_rtree_it_t *it);
+
+
 #endif