diff options
Diffstat (limited to 'sql/gcalc_tools.cc')
| -rw-r--r-- | sql/gcalc_tools.cc | 915 |
1 files changed, 495 insertions, 420 deletions
diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 25e71d7bfca..ab173803323 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -106,13 +106,26 @@ int Gcalc_function::reserve_op_buffer(uint n_ops) int Gcalc_function::alloc_states() { - if (function_buffer.reserve((n_shapes+1) * sizeof(int))) + if (function_buffer.reserve((n_shapes+1) * 2 * sizeof(int))) return 1; i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); + saved_i_states= i_states + (n_shapes + 1); return 0; } +void Gcalc_function::save_states() +{ + memcpy(saved_i_states, i_states, (n_shapes+1) * sizeof(int)); +} + + +void Gcalc_function::restore_states() +{ + memcpy(i_states, saved_i_states, (n_shapes+1) * sizeof(int)); +} + + int Gcalc_function::count_internal() { int c_op= uint4korr(cur_func); @@ -170,36 +183,64 @@ void Gcalc_function::reset() int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) { + const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events; + while (scan_it.more_points()) { if (scan_it.step()) return -1; - Gcalc_scan_events ev= scan_it.get_event(); - const Gcalc_scan_iterator::point *evpos= scan_it.get_event_position(); - if (ev & (scev_point | scev_end | scev_two_ends)) + events= scan_it.get_events(); + + /* these kinds of events don't change the function */ + if (events->simple_event()) continue; + Gcalc_point_iterator pit(&scan_it); clear_state(); - for (Gcalc_point_iterator pit(&scan_it); pit.point() != evpos; ++pit) + /* Walk to the event, marking polygons we met */ + for (; pit.point() != scan_it.get_event_position(); ++pit) { gcalc_shape_info si= pit.point()->get_shape(); if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) invert_state(si); } - invert_state(evpos->get_shape()); - - if (ev == scev_intersection) - { - const Gcalc_scan_iterator::point *evnext= evpos->c_get_next(); - if ((get_shape_kind(evpos->get_shape()) != - Gcalc_function::shape_polygon) || - (get_shape_kind(evnext->get_shape()) != - Gcalc_function::shape_polygon)) - invert_state(evnext->get_shape()); - } + save_states(); + /* Check the status of the event point */ + for (; events; events= events->get_next()) + set_on_state(events->get_shape()); if (count()) return 1; + + if (scan_it.get_event_position() == scan_it.get_event_end()) + continue; + + /* Check the status after the event */ + restore_states(); + eq_start= pit.point(); + do + { + ++pit; + if (pit.point() != scan_it.get_event_end() && + eq_start->cmp_dx_dy(pit.point()) == 0) + continue; + save_states(); + for (cur_eq= eq_start; cur_eq != pit.point(); + cur_eq= cur_eq->get_next()) + set_on_state(cur_eq->get_shape()); + if (count()) + return 1; + restore_states(); + for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) + { + gcalc_shape_info si= cur_eq->get_shape(); + if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) + invert_state(si); + } + if (count()) + return 1; + eq_start= pit.point(); + } while (pit.point() != scan_it.get_event_end()); } return 0; } @@ -457,6 +498,10 @@ void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) m_fn= fn; m_mode= mode; m_first_active_thread= NULL; + m_lines= NULL; + m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; + m_poly_borders= NULL; + m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; } @@ -470,10 +515,10 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : inline int Gcalc_operation_reducer::continue_range(active_thread *t, - const Gcalc_heap::Info *p) + const Gcalc_heap::Info *p, + int horiz_dir, double dx_dy) { - DBUG_ASSERT(t->result_range); - res_point *rp= add_res_point(); + res_point *rp= add_res_point(t->rp->type); if (!rp) return 1; rp->glue= NULL; @@ -482,16 +527,17 @@ inline int Gcalc_operation_reducer::continue_range(active_thread *t, rp->intersection_point= false; rp->pi= p; t->rp= rp; + t->horiz_dir= horiz_dir; + t->dx_dy= dx_dy; return 0; } inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) + double x, double y, + int horiz_dir, double dx_dy) { - DBUG_ASSERT(t->result_range); - res_point *rp= add_res_point(); + res_point *rp= add_res_point(t->rp->type); if (!rp) return 1; rp->glue= NULL; @@ -499,133 +545,10 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, t->rp->up= rp; rp->intersection_point= true; rp->x= x; - rp->pi= p; - rp->y= y; - t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::start_range(active_thread *t, - const Gcalc_heap::Info *p) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->down= NULL; - rp->intersection_point= false; - rp->pi= p; - t->result_range= 1; - t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::start_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->down= NULL; - rp->intersection_point= true; - rp->x= x; rp->y= y; - rp->pi= p; - t->result_range= 1; t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::end_range(active_thread *t, - const Gcalc_heap::Info *p) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= NULL; - rp->down= t->rp; - rp->intersection_point= false; - rp->pi= p; - t->rp->up= rp; - t->result_range= 0; - return 0; -} - -inline int Gcalc_operation_reducer::end_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= NULL; - rp->down= t->rp; - rp->intersection_point= true; - rp->x= x; - rp->pi= p; - rp->y= y; - t->rp->up= rp; - t->result_range= 0; - return 0; -} - -int Gcalc_operation_reducer::start_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p, - const active_thread *prev_range) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->glue= rp1; - rp1->glue= rp0; - rp0->intersection_point= rp1->intersection_point= false; - rp0->down= rp1->down= NULL; - rp0->pi= rp1->pi= p; - t0->rp= rp0; - t1->rp= rp1; - if (prev_range) - { - rp0->outer_poly= prev_range->thread_start; - t1->thread_start= prev_range->thread_start; - } - else - { - rp0->outer_poly= 0; - t0->thread_start= rp0; - } - return 0; -} - -int Gcalc_operation_reducer::start_i_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - double x, double y, - const active_thread *prev_range) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->glue= rp1; - rp1->glue= rp0; - rp0->pi= p0; - rp1->pi= p1; - rp0->intersection_point= rp1->intersection_point= true; - rp0->down= rp1->down= NULL; - rp0->x= rp1->x= x; - rp0->y= rp1->y= y; - t0->result_range= t1->result_range= 1; - t0->rp= rp0; - t1->rp= rp1; - if (prev_range) - { - rp0->outer_poly= prev_range->thread_start; - t1->thread_start= prev_range->thread_start; - } - else - { - rp0->outer_poly= 0; - t0->thread_start= rp0; - } + t->horiz_dir= horiz_dir; + t->dx_dy= dx_dy; return 0; } @@ -633,8 +556,9 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p) { res_point *rp0, *rp1; - DBUG_ASSERT(t1->result_range); - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + DBUG_ASSERT(t0->rp->type == t1->rp->type); + if (!(rp0= add_res_point(t0->rp->type)) || + !(rp1= add_res_point(t0->rp->type))) return 1; rp0->down= t0->rp; rp1->down= t1->rp; @@ -645,341 +569,492 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, t1->rp->up= rp1; rp0->intersection_point= rp1->intersection_point= false; rp0->pi= rp1->pi= p; - t0->result_range= t1->result_range= 0; return 0; } -int Gcalc_operation_reducer::end_i_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - double x, double y) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->down= t0->rp; - rp1->down= t1->rp; - rp0->pi= p0; - rp1->pi= p1; - rp1->glue= rp0; - rp0->glue= rp1; - rp0->up= rp1->up= NULL; - rp0->intersection_point= rp1->intersection_point= true; - rp0->x= rp1->x= x; - rp0->y= rp1->y= y; - t0->result_range= t1->result_range= 0; - t0->rp->up= rp0; - t1->rp->up= rp1; - return 0; -} -int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p) +int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= rp->down= NULL; - rp->intersection_point= false; - rp->pi= p; - rp->x= p->x; - rp->y= p->y; - return 0; -} + Gcalc_point_iterator pi(si); + const Gcalc_heap::Info *event_point= NULL; + int prev_state= 0; + int sav_prev_state; + active_thread *prev_range= NULL; + const Gcalc_scan_iterator::point *events; + const Gcalc_scan_iterator::point *eq_start; + active_thread **cur_t_hook= &m_first_active_thread; + active_thread **starting_t_hook; + active_thread *bottom_threads= NULL; + active_thread *eq_thread, *point_thread;; -int Gcalc_operation_reducer::add_i_single_point(const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= rp->down= NULL; - rp->intersection_point= true; - rp->x= x; - rp->pi= p; - rp->y= y; - return 0; -} + m_fn->clear_state(); + /* Walk to the event, remembering what is needed. */ + for (; pi.point() != si->get_event_position(); + ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) + { + active_thread *cur_t= *cur_t_hook; + if (cur_t->enabled() && + cur_t->rp->type == Gcalc_function::shape_polygon) + { + prev_state^= 1; + prev_range= prev_state ? cur_t : 0; + } + if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(pi.get_shape()); + } -int Gcalc_operation_reducer:: -handle_lines_intersection(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, const Gcalc_heap::Info *p1, - double x, double y) -{ - m_fn->invert_state(p0->shape); - if (p0->shape != p1->shape) - m_fn->invert_state(p1->shape); - int intersection_state= m_fn->count(); - if ((t0->result_range | t1->result_range) == intersection_state) + events= si->get_events(); + if (events->simple_event()) + { + active_thread *cur_t= *cur_t_hook; + switch (events->event) + { + case scev_point: + { + if (cur_t->enabled() && + continue_range(cur_t, events->pi, events->horiz_dir, events->dx_dy)) + return 1; + break; + } + case scev_end: + { + if (cur_t->enabled() && end_line(cur_t, events->pi, si)) + return 1; + *cur_t_hook= cur_t->get_next(); + free_item(cur_t); + break; + } + case scev_two_ends: + { + if (cur_t->enabled() && + end_couple(cur_t, cur_t->get_next(), events->pi)) + return 1; + *cur_t_hook= cur_t->get_next()->get_next(); + free_item(cur_t->next); + free_item(cur_t); + break; + } + default: + DBUG_ASSERT(0); + } return 0; + } - if (t0->result_range && - (end_i_range(t0, p1, x, y) || start_i_range(t0, p1, x, y))) - return 1; + starting_t_hook= cur_t_hook; + sav_prev_state= prev_state; - if (t1->result_range && - (end_i_range(t1, p0, x, y) || start_i_range(t1, p0, x, y))) - return 1; + /* Walk through the event, collecting all the 'incoming' threads */ + for (; events; events= events->get_next()) + { + active_thread *cur_t= *cur_t_hook; - if (intersection_state && - add_i_single_point(p0, x, y)) - return 1; - - return 0; -} + if (!event_point && events->event != scev_intersection) + event_point= events->pi; + if (events->event == scev_single_point) + continue; -inline int Gcalc_operation_reducer:: -handle_line_polygon_intersection(active_thread *l, const Gcalc_heap::Info *pl, - int line_state, int poly_state, - double x, double y) -{ - int range_after= ~poly_state & line_state; - if (l->result_range == range_after) - return 0; - return range_after ? start_i_range(l, pl, x, y) : end_i_range(l, pl, x, y); -} + if (events->event == scev_thread || + events->event == scev_two_threads) + { + active_thread *new_t= new_active_thread(); + if (!new_t) + return 1; + new_t->rp= NULL; + /* Insert into the main thread list before the current */ + new_t->next= cur_t; + *cur_t_hook= new_t; + cur_t_hook= (active_thread **) &new_t->next; + } + else + { + if (events->is_bottom()) + { + /* Move thread from the main list to the bottom_threads. */ + *cur_t_hook= cur_t->get_next(); + cur_t->next= bottom_threads; + bottom_threads= cur_t; + } + if (cur_t->enabled()) + { + if (cur_t->rp->type == Gcalc_function::shape_line) + { + DBUG_ASSERT(!prev_state); + add_line(1, cur_t, events); + } + else + { + add_poly_border(1, cur_t, prev_state, events); + prev_state^= 1; + } + if (!events->is_bottom()) + { + active_thread *new_t= new_active_thread(); + if (!new_t) + return 1; + new_t->rp= NULL; + /* Replace the current thread with the new. */ + new_t->next= cur_t->next; + *cur_t_hook= new_t; + cur_t_hook= (active_thread **) &new_t->next; + /* And move old to the bottom list */ + cur_t->next= bottom_threads; + bottom_threads= cur_t; + } + } + else if (!events->is_bottom()) + cur_t_hook= (active_thread **) &cur_t->next; + } + } + prev_state= sav_prev_state; + cur_t_hook= starting_t_hook; -static inline void switch_athreads(Gcalc_operation_reducer::active_thread *t0, - Gcalc_operation_reducer::active_thread *t1, - Gcalc_dyn_list::Item **hook) -{ - *hook= t1; - t0->next= t1->next; - t1->next= t0; -} + eq_start= pi.point(); + eq_thread= point_thread= *starting_t_hook; + while (eq_start != si->get_event_end()) + { + const Gcalc_scan_iterator::point *cur_eq; + int in_state, after_state; -inline int Gcalc_operation_reducer:: -handle_polygons_intersection(active_thread *t0, active_thread *t1, - Gcalc_dyn_list::Item **t_hook, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - int prev_state, double x, double y, - const active_thread *prev_range) -{ - m_fn->invert_state(p0->shape); - int state_11= m_fn->count(); - m_fn->invert_state(p1->shape); - int state_2= m_fn->count(); - int state_01= prev_state ^ t0->result_range; - if ((prev_state == state_01) && (prev_state == state_2)) + ++pi; + point_thread= point_thread->get_next(); + + if (pi.point() != si->get_event_end() && + eq_start->cmp_dx_dy(pi.point()) == 0) + continue; + + m_fn->save_states(); + for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) + m_fn->set_on_state(cur_eq->get_shape()); + in_state= m_fn->count(); + + m_fn->restore_states(); + for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) + { + gcalc_shape_info si= cur_eq->get_shape(); + if ((m_fn->get_shape_kind(si) == Gcalc_function::shape_polygon)) + m_fn->invert_state(si); + } + after_state= m_fn->count(); + if (prev_state != after_state) + { + if (add_poly_border(0, eq_thread, prev_state, eq_start)) + return 1; + } + else if (!prev_state /* &&!after_state */ && in_state) + { + if (add_line(0, eq_thread, eq_start)) + return 1; + } + + prev_state= after_state; + eq_start= pi.point(); + eq_thread= point_thread; + } + + if (!sav_prev_state && !m_poly_borders && !m_lines) { - if (state_11 == prev_state) + /* Check if we need to add the event point itself */ + m_fn->clear_state(); + for (pi.restart(si); pi.point() != si->get_event_position(); ++pi) { - switch_athreads(t0, t1, t_hook); - return 0; + if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(pi.get_shape()); } - return start_i_couple(t0, t1, p0, p1, x, y, prev_range); + for (events= si->get_events(); events; events= events->get_next()) + m_fn->set_on_state(events->get_shape()); + + return m_fn->count() ? add_single_point(event_point, si) : 0; } - if (prev_state == state_2) + + if (m_poly_borders) { - if (state_01 == state_11) + *m_poly_borders_hook= NULL; + while (m_poly_borders) { - if (m_mode & polygon_selfintersections_allowed) - { - switch_athreads(t0, t1, t_hook); - return 0; - } - if (prev_state != (m_mode & prefer_big_with_holes)) - return continue_i_range(t0, p0, x, y) || continue_i_range(t1, p1, x, y); - return end_i_couple(t0, t1, p0, p1, x, y) || - start_i_couple(t0, t1, p0, p1, x, y, prev_range); + poly_border *pb1, *pb2; + pb1= m_poly_borders; + DBUG_ASSERT(m_poly_borders->next); + + pb2= get_pair_border(pb1); + /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */ + m_poly_borders= pb1->get_next(); + if (connect_threads(pb1->incoming, pb2->incoming, + pb1->t, pb2->t, pb1->p, pb2->p, + prev_range, event_point, si, + Gcalc_function::shape_polygon)) + return 1; + + free_item(pb1); + free_item(pb2); } - else - return end_i_couple(t0, t1, p0, p1, x, y); + m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; + m_poly_borders= NULL; } - if (state_01 ^ state_11) + + if (m_lines) { - switch_athreads(t0, t1, t_hook); - return 0; + *m_lines_hook= NULL; + if (m_lines->get_next() && + !m_lines->get_next()->get_next()) + { + if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming, + m_lines->t, m_lines->get_next()->t, + m_lines->p, m_lines->get_next()->p, NULL, + event_point, si, Gcalc_function::shape_line)) + return 1; + } + else + { + for (line *cur_line= m_lines; cur_line; cur_line= cur_line->get_next()) + { + if (cur_line->incoming) + { + if (end_line(cur_line->t, event_point, si)) + return 1; + } + else + start_line(cur_line->t, cur_line->p, event_point, si); + } + } + free_list(m_lines); + m_lines= NULL; + m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; } - active_thread *thread_to_continue; - const Gcalc_heap::Info *way_to_go; - if (prev_state == state_01) + if (bottom_threads) + free_list(bottom_threads); + + return 0; +} + + +int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p, + const Gcalc_scan_iterator *si) +{ + res_point *rp= add_res_point(Gcalc_function::shape_point); + if (!rp) + return 1; + rp->glue= rp->up= rp->down= NULL; + if (p) { - thread_to_continue= t1; - way_to_go= p1; + rp->intersection_point= false; + rp->pi= p; } - else + else { - thread_to_continue= t0; - way_to_go= p0; + rp->intersection_point= true; + rp->x= si->get_y(); + rp->y= si->get_events()->x; } - return continue_i_range(thread_to_continue, way_to_go, x, y); + return 0; } -int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) -{ - Gcalc_point_iterator pi(si); - active_thread *cur_t= m_first_active_thread; - Gcalc_dyn_list::Item **at_hook= (Gcalc_dyn_list::Item **)&m_first_active_thread; - const active_thread *prev_range; - int prev_state; - if (si->get_event() & (scev_point | scev_end | scev_two_ends)) +Gcalc_operation_reducer::poly_border + *Gcalc_operation_reducer::get_pair_border(poly_border *b1) +{ + poly_border *prev_b= b1; + poly_border *result= b1->get_next(); + if (b1->prev_state) { - for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) - at_hook= &cur_t->next; - - switch (si->get_event()) + if (b1->incoming) { - case scev_point: + /* Find the first outgoing, otherwise the last one. */ + while (result->incoming && result->get_next()) { - if (cur_t->result_range && - continue_range(cur_t, pi.get_pi())) - return 1; - break; + prev_b= result; + result= result->get_next(); } - case scev_end: + } + else + { + /* Get the last one */ + while (result->get_next()) { - if (cur_t->result_range && - end_range(cur_t, pi.get_pi())) - return 1; - *at_hook= cur_t->next; - free_item(cur_t); - break; + prev_b= result; + result= result->get_next(); } - case scev_two_ends: + } + } + else /* !b1->prev_state */ + { + if (b1->incoming) + { + /* Get the next incoming, otherwise the last one. */ + while (!result->incoming && result->get_next()) { - active_thread *cur_t1= cur_t->get_next(); - if (cur_t->result_range && - end_couple(cur_t, cur_t1, pi.get_pi())) - return 1; - - *at_hook= cur_t1->next; - free_list(cur_t, &cur_t1->next); - break; + prev_b= result; + result= result->get_next(); } - default: - DBUG_ASSERT(0); } - return 0; + else + { + /* Just pick the next one */ + } } + /* Delete the result from the list. */ + prev_b->next= result->next; + return result; +} - prev_state= 0; - prev_range= 0; - m_fn->clear_state(); - for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) +int Gcalc_operation_reducer::connect_threads( + int incoming_a, int incoming_b, + active_thread *ta, active_thread *tb, + const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, + active_thread *prev_range, const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) +{ + if (incoming_a && incoming_b) { - if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + res_point *rpa, *rpb; + DBUG_ASSERT(ta->rp->type == tb->rp->type); + if (!(rpa= add_res_point(ta->rp->type)) || + !(rpb= add_res_point(ta->rp->type))) + return 1; + rpa->down= ta->rp; + rpb->down= tb->rp; + rpb->glue= rpa; + rpa->glue= rpb; + rpa->up= rpb->up= NULL; + ta->rp->up= rpa; + tb->rp->up= rpb; + if (ev_p) { - m_fn->invert_state(pi.get_shape()); - prev_state^= cur_t->result_range; + rpa->intersection_point= rpb->intersection_point= false; + rpa->pi= rpb->pi= ev_p; + } + else + { + rpa->intersection_point= rpb->intersection_point= true; + rpa->x= rpb->x= si->get_events()->x; + rpa->y= rpb->y= si->get_y(); } - at_hook= &cur_t->next; - if (cur_t->result_range) - prev_range= prev_state ? cur_t : 0; - } - switch (si->get_event()) - { - case scev_thread: - { - active_thread *new_t= new_active_thread(); - if (!new_t) - return 1; - m_fn->invert_state(pi.get_shape()); - new_t->result_range= ~prev_state & m_fn->count(); - new_t->next= *at_hook; - *at_hook= new_t; - if (new_t->result_range && - start_range(new_t, pi.get_pi())) - return 1; - break; + ta->rp= tb->rp= NULL; + return 0; } - case scev_two_threads: + if (!incoming_a) { - active_thread *new_t0, *new_t1; - int fn_result; - const Gcalc_heap::Info *p= pi.get_pi(); - bool line= m_fn->get_shape_kind(p->shape) == Gcalc_function::shape_line; - if (!(new_t0= new_active_thread()) || !(new_t1= new_active_thread())) + DBUG_ASSERT(!incoming_b); + + res_point *rp0, *rp1; + if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) return 1; - - m_fn->invert_state(pi.get_shape()); - fn_result= m_fn->count(); - if (line) - new_t0->result_range= new_t1->result_range= ~prev_state & fn_result; + rp0->glue= rp1; + rp1->glue= rp0; + if (ev_p) + { + rp0->intersection_point= rp1->intersection_point= false; + rp0->pi= rp1->pi= ev_p; + } else - new_t0->result_range= new_t1->result_range= prev_state ^ fn_result; - new_t1->next= *at_hook; - new_t0->next= new_t1; - *at_hook= new_t0; - if (new_t0->result_range && - start_couple(new_t0, new_t1, pi.get_pi(), prev_range)) - return 1; - break; - } - case scev_intersection: - { - active_thread *cur_t1= cur_t->get_next(); - const Gcalc_heap::Info *p0, *p1; - p0= pi.get_pi(); - ++pi; - p1= pi.get_pi(); - bool line0= m_fn->get_shape_kind(p0->shape) == Gcalc_function::shape_line; - bool line1= m_fn->get_shape_kind(p1->shape) == Gcalc_function::shape_line; - - if (!line0 && !line1) /* two polygons*/ { - if (handle_polygons_intersection(cur_t, cur_t1, at_hook, p0, p1, - prev_state, pi.get_x(), si->get_y(), - prev_range)) - return 1; + rp0->intersection_point= rp1->intersection_point= true; + rp0->x= rp1->x= si->get_events()->x; + rp0->y= rp1->y= si->get_y(); } - else if (line0 && line1) + rp0->down= rp1->down= NULL; + ta->rp= rp0; + tb->rp= rp1; + ta->horiz_dir= pa->horiz_dir; + ta->dx_dy= pa->dx_dy; + + tb->horiz_dir= pb->horiz_dir; + tb->dx_dy= pb->dx_dy; + + if (prev_range) { - if (!prev_state && - handle_lines_intersection(cur_t, cur_t1, - p0, p1, pi.get_x(), si->get_y())) - return 1; - switch_athreads(cur_t, cur_t1, at_hook); + rp0->outer_poly= prev_range->thread_start; + tb->thread_start= prev_range->thread_start; } else { - int poly_state; - int line_state; - const Gcalc_heap::Info *line; - active_thread *line_t; - m_fn->invert_state(p0->shape); - if (line0) - { - line_state= m_fn->count(); - poly_state= prev_state; - line= p0; - line_t= cur_t1; - } - else - { - poly_state= m_fn->count(); - m_fn->invert_state(p1->shape); - line_state= m_fn->count(); - line= p1; - line_t= cur_t; - } - if (handle_line_polygon_intersection(line_t, line, - line_state, poly_state, - pi.get_x(), si->get_y())) - return 1; - switch_athreads(cur_t, cur_t1, at_hook); + rp0->outer_poly= 0; + ta->thread_start= rp0; } - break; + return 0; } - case scev_single_point: + /* else, if only ta is incoming */ + + DBUG_ASSERT(tb != ta); + tb->rp= ta->rp; + tb->thread_start= ta->thread_start; + if (Gcalc_scan_iterator::point:: + compare_dx_dy(ta->horiz_dir, ta->dx_dy, + pb->horiz_dir, pb->dx_dy) != 0) { - m_fn->invert_state(pi.get_shape()); - if ((prev_state ^ m_fn->count()) && - add_single_point(pi.get_pi())) + if (ev_p ? continue_range(tb, ev_p, pb->horiz_dir, pb->dx_dy): + continue_i_range(tb, + si->get_events()->x, si->get_y(), + pb->horiz_dir, pb->dx_dy)) return 1; - break; } - default: - DBUG_ASSERT(0); + else + { + tb->horiz_dir= pb->horiz_dir; + tb->dx_dy= pb->dx_dy; + } + + return 0; +} + + +int Gcalc_operation_reducer::start_line(active_thread *t, + const Gcalc_scan_iterator::point *p, + const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si) +{ + res_point *rp= add_res_point(Gcalc_function::shape_line); + if (!rp) + return 1; + rp->glue= rp->down= NULL; + if (ev_p) + { + rp->intersection_point= false; + rp->pi= ev_p; + } + else + { + rp->intersection_point= true; + rp->x= si->get_events()->x; + rp->y= si->get_y(); + } + t->rp= rp; + t->horiz_dir= p->horiz_dir; + t->dx_dy= p->dx_dy; + return 0; +} + + +int Gcalc_operation_reducer::end_line(active_thread *t, + const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si) +{ + DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); + res_point *rp= add_res_point(Gcalc_function::shape_line); + if (!rp) + return 1; + rp->glue= rp->up= NULL; + rp->down= t->rp; + if (ev_p) + { + rp->intersection_point= false; + rp->pi= ev_p; + } + else + { + rp->intersection_point= true; + rp->x= si->get_events()->x; + rp->y= si->get_y(); } + t->rp->up= rp; + t->rp= NULL; return 0; } + int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) { Gcalc_scan_iterator si; @@ -1014,7 +1089,7 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, return 1; } else - if (storage->single_point(res->x, res->y)) + if (storage->single_point(res->pi->x, res->pi->y)) return 1; free_result(res); return 0; @@ -1113,13 +1188,13 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) *m_res_hook= NULL; while (m_result) { - if (!m_result->up) + Gcalc_function::shape_type shape= m_result->type; + if (shape == Gcalc_function::shape_point) { if (get_single_result(m_result, storage)) return 1; continue; } - Gcalc_function::shape_type shape= m_fn->get_shape_kind(m_result->pi->shape); if (shape == Gcalc_function::shape_polygon) { if (m_result->outer_poly) |