1/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved.
2 Copyright (C) 2011 Monty Program Ab.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
16
17
18#include "mariadb.h"
19
20#ifdef HAVE_SPATIAL
21
22#include "gcalc_tools.h"
23#include "spatial.h"
24
25#define float_to_coord(d) ((double) d)
26
27
28/*
29 Adds new shape to the relation.
30 After that it can be used as an argument of an operation.
31*/
32
33gcalc_shape_info Gcalc_function::add_new_shape(uint32 shape_id,
34 shape_type shape_kind)
35{
36 shapes_buffer.q_append((uint32) shape_kind);
37 return n_shapes++;
38}
39
40
41/*
42 Adds new operation to the constructed relation.
43 To construct the complex relation one has to specify operations
44 in prefix style.
45*/
46
47void Gcalc_function::add_operation(uint operation, uint32 n_operands)
48{
49 uint32 op_code= (uint32 ) operation + n_operands;
50 function_buffer.q_append(op_code);
51}
52
53
54/*
55 Sometimes the number of arguments is unknown at the moment the operation
56 is added. That allows to specify it later.
57*/
58
59void Gcalc_function::add_operands_to_op(uint32 operation_pos, uint32 n_operands)
60{
61 uint32 op_code= uint4korr(function_buffer.ptr() + operation_pos) + n_operands;
62 function_buffer.write_at_position(operation_pos, op_code);
63}
64
65
66/*
67 Just like the add_operation() but the result will be the inverted
68 value of an operation.
69*/
70
71void Gcalc_function::add_not_operation(op_type operation, uint32 n_operands)
72{
73 uint32 op_code= ((uint32) op_not | (uint32 ) operation) + n_operands;
74 function_buffer.q_append(op_code);
75}
76
77
78int Gcalc_function::single_shape_op(shape_type shape_kind, gcalc_shape_info *si)
79{
80 if (reserve_shape_buffer(1) || reserve_op_buffer(1))
81 return 1;
82 *si= add_new_shape(0, shape_kind);
83 add_operation(op_shape, *si);
84 return 0;
85}
86
87
88int Gcalc_function::repeat_expression(uint32 exp_pos)
89{
90 if (reserve_op_buffer(1))
91 return 1;
92 add_operation(op_repeat, exp_pos);
93 return 0;
94}
95
96
97/*
98 Specify how many arguments we're going to have.
99*/
100
101int Gcalc_function::reserve_shape_buffer(uint n_shapes)
102{
103 return shapes_buffer.reserve(n_shapes * 4, 512);
104}
105
106
107/*
108 Specify how many operations we're going to have.
109*/
110
111int Gcalc_function::reserve_op_buffer(uint n_ops)
112{
113 return function_buffer.reserve(n_ops * 4, 512);
114}
115
116
117int Gcalc_function::alloc_states()
118{
119 if (function_buffer.reserve((n_shapes+1) * 2 * sizeof(int)))
120 return 1;
121 i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length()));
122 b_states= i_states + (n_shapes + 1);
123 return 0;
124}
125
126
127int Gcalc_function::count_internal(const char *cur_func, uint set_type,
128 const char **end)
129{
130 uint c_op= uint4korr(cur_func);
131 op_type next_func= (op_type) (c_op & op_any);
132 int mask= (c_op & op_not) ? 1:0;
133 uint n_ops= c_op & ~(op_any | op_not | v_mask);
134 uint n_shape= c_op & ~(op_any | op_not | v_mask); /* same as n_ops */
135 value v_state= (value) (c_op & v_mask);
136 int result= 0;
137 const char *sav_cur_func= cur_func;
138
139 // GCALC_DBUG_ENTER("Gcalc_function::count_internal");
140
141 cur_func+= 4;
142 if (next_func == op_shape)
143 {
144 if (set_type == 0)
145 result= i_states[n_shape] | b_states[n_shape];
146 /* the last call for the count_internal outside of all shapes. */
147 else if (set_type == 1)
148 result= 0;
149 else if (set_type == op_border)
150 result= b_states[n_shape];
151 else if (set_type == op_internals)
152 result= i_states[n_shape] && !b_states[n_shape];
153 goto exit;
154 }
155
156 if (next_func == op_false)
157 {
158 result= 0;
159 goto exit;
160 }
161
162 if (next_func == op_border || next_func == op_internals)
163 {
164 result= count_internal(cur_func,
165 (set_type == 1) ? set_type : next_func, &cur_func);
166 goto exit;
167 }
168
169 if (next_func == op_repeat)
170 {
171 result= count_internal(function_buffer.ptr() + n_ops, set_type, 0);
172 goto exit;
173 }
174
175 if (n_ops == 0)
176 return mask;
177 //GCALC_DBUG_RETURN(mask);
178
179 result= count_internal(cur_func, set_type, &cur_func);
180
181 while (--n_ops)
182 {
183 int next_res= count_internal(cur_func, set_type, &cur_func);
184 switch (next_func)
185 {
186 case op_union:
187 if (result == result_true || next_res == result_true)
188 result= result_true;
189 else if (result == result_unknown || next_res == result_unknown)
190 result= result_unknown;
191 else
192 result= result_false;
193 break;
194 case op_intersection:
195 if (result == result_false || next_res == result_false)
196 result= result_false;
197 else if (result == result_unknown || next_res == result_unknown)
198 result= result_unknown;
199 else
200 result= result_true;
201 break;
202 case op_symdifference:
203 if (result == result_unknown || next_res == result_unknown)
204 result= result_unknown;
205 else
206 result= result ^ next_res;
207 break;
208 case op_difference:
209 if (result == result_false || next_res == result_true)
210 result= result_false;
211 else if (result == result_unknown || next_res == result_unknown)
212 result= result_unknown;
213 else
214 result= result_true;
215 break;
216 default:
217 GCALC_DBUG_ASSERT(FALSE);
218 };
219 }
220
221exit:
222 if (result != result_unknown)
223 result^= mask;
224 if (v_state != v_empty)
225 {
226 switch (v_state)
227 {
228 case v_find_t:
229 if (result == result_true)
230 {
231 c_op= (c_op & ~v_mask) | v_t_found;
232 int4store(sav_cur_func, c_op);
233 }
234 else
235 {
236 if (set_type != 1)
237 result= result_unknown;
238 }
239 break;
240 case v_find_f:
241 if (result == result_false)
242 {
243 c_op= (c_op & ~v_mask) | v_f_found;
244 int4store(sav_cur_func, c_op);
245 }
246 else
247 {
248 if (set_type != 1)
249 result= result_unknown;
250 }
251 break;
252 case v_t_found:
253 result= 1;
254 break;
255 case v_f_found:
256 result= 0;
257 break;
258 default:
259 GCALC_DBUG_ASSERT(0);
260 };
261 }
262
263 if (end)
264 *end= cur_func;
265 return result;
266 //GCALC_DBUG_RETURN(result);
267}
268
269
270void Gcalc_function::clear_i_states()
271{
272 for (uint i= 0; i < n_shapes; i++)
273 i_states[i]= 0;
274}
275
276
277void Gcalc_function::clear_b_states()
278{
279 for (uint i= 0; i < n_shapes; i++)
280 b_states[i]= 0;
281}
282
283
284/*
285 Clear the state of the object.
286*/
287
288void Gcalc_function::reset()
289{
290 n_shapes= 0;
291 shapes_buffer.length(0);
292 function_buffer.length(0);
293}
294
295
296int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it)
297{
298 const Gcalc_scan_iterator::point *eq_start, *cur_eq;
299 const Gcalc_scan_iterator::event_point *events;
300 int result;
301 GCALC_DBUG_ENTER("Gcalc_function::check_function");
302
303 while (scan_it.more_points())
304 {
305 if (scan_it.step())
306 GCALC_DBUG_RETURN(-1);
307 events= scan_it.get_events();
308
309 /* these kinds of events don't change the function */
310 Gcalc_point_iterator pit(&scan_it);
311 clear_b_states();
312 clear_i_states();
313 /* Walk to the event, marking polygons we met */
314 for (; pit.point() != scan_it.get_event_position(); ++pit)
315 {
316 gcalc_shape_info si= pit.point()->get_shape();
317 if ((get_shape_kind(si) == Gcalc_function::shape_polygon))
318 invert_i_state(si);
319 }
320 if (events->simple_event())
321 {
322 if (events->event == scev_end)
323 set_b_state(events->get_shape());
324
325 if ((result= count()) != result_unknown)
326 GCALC_DBUG_RETURN(result);
327 clear_b_states();
328 continue;
329 }
330
331 /* Check the status of the event point */
332 for (; events; events= events->get_next())
333 {
334 gcalc_shape_info si= events->get_shape();
335 if (events->event == scev_thread ||
336 events->event == scev_end ||
337 (get_shape_kind(si) == Gcalc_function::shape_polygon))
338 set_b_state(si);
339 else if (events->event == scev_single_point ||
340 get_shape_kind(si) == Gcalc_function::shape_line)
341 set_i_state(si);
342 }
343
344 if ((result= count()) != result_unknown)
345 GCALC_DBUG_RETURN(result);
346
347 /* Set back states changed in the loop above. */
348 for (events= scan_it.get_events(); events; events= events->get_next())
349 {
350 gcalc_shape_info si= events->get_shape();
351 if (events->event == scev_thread ||
352 events->event == scev_end ||
353 get_shape_kind(si) == Gcalc_function::shape_polygon)
354 clear_b_state(si);
355 else if (events->event == scev_single_point ||
356 get_shape_kind(si) == Gcalc_function::shape_line)
357 clear_i_state(si);
358 }
359
360 if (scan_it.get_event_position() == scan_it.get_event_end())
361 continue;
362
363 /* Check the status after the event */
364 eq_start= pit.point();
365 do
366 {
367 ++pit;
368 if (pit.point() != scan_it.get_event_end() &&
369 eq_start->cmp_dx_dy(pit.point()) == 0)
370 continue;
371 for (cur_eq= eq_start; cur_eq != pit.point();
372 cur_eq= cur_eq->get_next())
373 {
374 gcalc_shape_info si= cur_eq->get_shape();
375 if (get_shape_kind(si) == Gcalc_function::shape_polygon)
376 set_b_state(si);
377 else
378 invert_i_state(si);
379 }
380 if ((result= count()) != result_unknown)
381 GCALC_DBUG_RETURN(result);
382
383 for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next())
384 {
385 gcalc_shape_info si= cur_eq->get_shape();
386 if ((get_shape_kind(si) == Gcalc_function::shape_polygon))
387 {
388 clear_b_state(si);
389 invert_i_state(si);
390 }
391 else
392 invert_i_state(cur_eq->get_shape());
393 }
394 if ((result= count()) != result_unknown)
395 GCALC_DBUG_RETURN(result);
396
397 eq_start= pit.point();
398 } while (pit.point() != scan_it.get_event_end());
399 }
400 GCALC_DBUG_RETURN(count_last());
401}
402
403
404int Gcalc_operation_transporter::single_point(double x, double y)
405{
406 gcalc_shape_info si;
407 return m_fn->single_shape_op(Gcalc_function::shape_point, &si) ||
408 int_single_point(si, x, y);
409}
410
411
412int Gcalc_operation_transporter::start_line()
413{
414 int_start_line();
415 return m_fn->single_shape_op(Gcalc_function::shape_line, &m_si);
416}
417
418
419int Gcalc_operation_transporter::complete_line()
420{
421 int_complete_line();
422 return 0;
423}
424
425
426int Gcalc_operation_transporter::start_poly()
427{
428 int_start_poly();
429 return m_fn->single_shape_op(Gcalc_function::shape_polygon, &m_si);
430}
431
432
433int Gcalc_operation_transporter::complete_poly()
434{
435 int_complete_poly();
436 return 0;
437}
438
439
440int Gcalc_operation_transporter::start_ring()
441{
442 int_start_ring();
443 return 0;
444}
445
446
447int Gcalc_operation_transporter::complete_ring()
448{
449 int_complete_ring();
450 return 0;
451}
452
453
454int Gcalc_operation_transporter::add_point(double x, double y)
455{
456 return int_add_point(m_si, x, y);
457}
458
459
460int Gcalc_operation_transporter::start_collection(int n_objects)
461{
462 if (m_fn->reserve_shape_buffer(n_objects) || m_fn->reserve_op_buffer(1))
463 return 1;
464 m_fn->add_operation(Gcalc_function::op_union, n_objects);
465 return 0;
466}
467
468
469int Gcalc_operation_transporter::empty_shape()
470{
471 if (m_fn->reserve_op_buffer(1))
472 return 1;
473 m_fn->add_operation(Gcalc_function::op_false, 0);
474 return 0;
475}
476
477
478int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape)
479{
480 GCALC_DBUG_ENTER("Gcalc_result_receiver::start_shape");
481 if (buffer.reserve(4*2, 512))
482 GCALC_DBUG_RETURN(1);
483 cur_shape= shape;
484 shape_pos= buffer.length();
485 buffer.length(shape_pos + ((shape == Gcalc_function::shape_point) ? 4:8));
486 n_points= 0;
487 shape_area= 0.0;
488
489 GCALC_DBUG_RETURN(0);
490}
491
492
493int Gcalc_result_receiver::add_point(double x, double y)
494{
495 GCALC_DBUG_ENTER("Gcalc_result_receiver::add_point");
496 if (n_points && x == prev_x && y == prev_y)
497 GCALC_DBUG_RETURN(0);
498
499 if (!n_points++)
500 {
501 prev_x= first_x= x;
502 prev_y= first_y= y;
503 GCALC_DBUG_RETURN(0);
504 }
505
506 shape_area+= prev_x*y - prev_y*x;
507
508 if (buffer.reserve(8*2, 512))
509 GCALC_DBUG_RETURN(1);
510 buffer.q_append(prev_x);
511 buffer.q_append(prev_y);
512 prev_x= x;
513 prev_y= y;
514 GCALC_DBUG_RETURN(0);
515}
516
517
518int Gcalc_result_receiver::complete_shape()
519{
520 GCALC_DBUG_ENTER("Gcalc_result_receiver::complete_shape");
521 if (n_points == 0)
522 {
523 buffer.length(shape_pos);
524 GCALC_DBUG_RETURN(0);
525 }
526 if (n_points == 1)
527 {
528 if (cur_shape != Gcalc_function::shape_point)
529 {
530 if (cur_shape == Gcalc_function::shape_hole)
531 {
532 buffer.length(shape_pos);
533 GCALC_DBUG_RETURN(0);
534 }
535 cur_shape= Gcalc_function::shape_point;
536 buffer.length(buffer.length()-4);
537 }
538 }
539 else
540 {
541 GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_point);
542 if (cur_shape == Gcalc_function::shape_hole)
543 {
544 shape_area+= prev_x*first_y - prev_y*first_x;
545 if (fabs(shape_area) < 1e-8)
546 {
547 buffer.length(shape_pos);
548 GCALC_DBUG_RETURN(0);
549 }
550 }
551
552 if ((cur_shape == Gcalc_function::shape_polygon ||
553 cur_shape == Gcalc_function::shape_hole) &&
554 prev_x == first_x && prev_y == first_y)
555 {
556 n_points--;
557 buffer.write_at_position(shape_pos+4, n_points);
558 goto do_complete;
559 }
560 buffer.write_at_position(shape_pos+4, n_points);
561 }
562
563 if (buffer.reserve(8*2, 512))
564 GCALC_DBUG_RETURN(1);
565 buffer.q_append(prev_x);
566 buffer.q_append(prev_y);
567
568do_complete:
569 buffer.write_at_position(shape_pos, (uint32) cur_shape);
570
571 if (!n_shapes++)
572 {
573 GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole);
574 common_shapetype= cur_shape;
575 }
576 else if (cur_shape == Gcalc_function::shape_hole)
577 {
578 ++n_holes;
579 }
580 else if (!collection_result && (cur_shape != common_shapetype))
581 {
582 collection_result= true;
583 }
584 GCALC_DBUG_RETURN(0);
585}
586
587
588int Gcalc_result_receiver::single_point(double x, double y)
589{
590 return start_shape(Gcalc_function::shape_point) ||
591 add_point(x, y) ||
592 complete_shape();
593}
594
595
596int Gcalc_result_receiver::done()
597{
598 return 0;
599}
600
601
602void Gcalc_result_receiver::reset()
603{
604 buffer.length(0);
605 collection_result= FALSE;
606 n_shapes= n_holes= 0;
607}
608
609
610int Gcalc_result_receiver::get_result_typeid()
611{
612 if (!n_shapes || collection_result)
613 return Geometry::wkb_geometrycollection;
614
615 switch (common_shapetype)
616 {
617 case Gcalc_function::shape_polygon:
618 return (n_shapes - n_holes == 1) ?
619 Geometry::wkb_polygon : Geometry::wkb_multipolygon;
620 case Gcalc_function::shape_point:
621 return (n_shapes == 1) ? Geometry::wkb_point : Geometry::wkb_multipoint;
622 case Gcalc_function::shape_line:
623 return (n_shapes == 1) ? Geometry::wkb_linestring :
624 Geometry::wkb_multilinestring;
625 default:
626 GCALC_DBUG_ASSERT(0);
627 }
628 return 0;
629}
630
631
632int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_position,
633 uint32 *position_shift)
634{
635 char *ptr;
636 int source_len;
637 GCALC_DBUG_ENTER("Gcalc_result_receiver::move_hole");
638 GCALC_DBUG_PRINT(("ps %d %d", dest_position, source_position));
639
640 *position_shift= source_len= buffer.length() - source_position;
641
642 if (dest_position == source_position)
643 GCALC_DBUG_RETURN(0);
644
645 if (buffer.reserve(source_len, MY_ALIGN(source_len, 512)))
646 GCALC_DBUG_RETURN(1);
647
648 ptr= (char *) buffer.ptr();
649 memmove(ptr + dest_position + source_len, ptr + dest_position,
650 buffer.length() - dest_position);
651 memcpy(ptr + dest_position, ptr + buffer.length(), source_len);
652 GCALC_DBUG_RETURN(0);
653}
654
655
656Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) :
657 Gcalc_dyn_list(blk_size, sizeof(res_point)),
658#ifndef GCALC_DBUG_OFF
659 n_res_points(0),
660#endif /*GCALC_DBUG_OFF*/
661 m_res_hook((Gcalc_dyn_list::Item **)&m_result),
662 m_first_active_thread(NULL)
663{}
664
665
666void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode)
667{
668 m_fn= fn;
669 m_mode= mode;
670 m_first_active_thread= NULL;
671 m_lines= NULL;
672 m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines;
673 m_poly_borders= NULL;
674 m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders;
675 GCALC_SET_TERMINATED(killed, 0);
676}
677
678
679Gcalc_operation_reducer::
680Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) :
681 Gcalc_dyn_list(blk_size, sizeof(res_point)),
682 m_res_hook((Gcalc_dyn_list::Item **)&m_result)
683{
684 init(fn, mode);
685}
686
687
688void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si)
689{
690 intersection_point= si->intersection_step();
691 pi= si->get_cur_pi();
692}
693
694
695Gcalc_operation_reducer::res_point *
696 Gcalc_operation_reducer::add_res_point(Gcalc_function::shape_type type)
697{
698 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_res_point");
699 res_point *result= (res_point *)new_item();
700 *m_res_hook= result;
701 result->prev_hook= m_res_hook;
702 m_res_hook= &result->next;
703 result->type= type;
704#ifndef GCALC_DBUG_OFF
705 result->point_n= n_res_points++;
706#endif /*GCALC_DBUG_OFF*/
707 GCALC_DBUG_RETURN(result);
708}
709
710int Gcalc_operation_reducer::add_line(int incoming, active_thread *t,
711 const Gcalc_scan_iterator::point *p)
712{
713 line *l= new_line();
714 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_line");
715 if (!l)
716 GCALC_DBUG_RETURN(1);
717 l->incoming= incoming;
718 l->t= t;
719 l->p= p;
720 *m_lines_hook= l;
721 m_lines_hook= &l->next;
722 GCALC_DBUG_RETURN(0);
723}
724
725
726int Gcalc_operation_reducer::add_poly_border(int incoming,
727 active_thread *t, int prev_state, const Gcalc_scan_iterator::point *p)
728{
729 poly_border *b= new_poly_border();
730 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_poly_border");
731 if (!b)
732 GCALC_DBUG_RETURN(1);
733 b->incoming= incoming;
734 b->t= t;
735 b->prev_state= prev_state;
736 b->p= p;
737 *m_poly_borders_hook= b;
738 m_poly_borders_hook= &b->next;
739 GCALC_DBUG_RETURN(0);
740}
741
742
743int Gcalc_operation_reducer::continue_range(active_thread *t,
744 const Gcalc_heap::Info *p,
745 const Gcalc_heap::Info *p_next)
746{
747 res_point *rp= add_res_point(t->rp->type);
748 GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_range");
749 if (!rp)
750 GCALC_DBUG_RETURN(1);
751 rp->glue= NULL;
752 rp->down= t->rp;
753 t->rp->up= rp;
754 rp->intersection_point= false;
755 rp->pi= p;
756 t->rp= rp;
757 t->p1= p;
758 t->p2= p_next;
759 GCALC_DBUG_RETURN(0);
760}
761
762
763inline int Gcalc_operation_reducer::continue_i_range(active_thread *t,
764 const Gcalc_heap::Info *ii)
765{
766 res_point *rp= add_res_point(t->rp->type);
767 GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range");
768 if (!rp)
769 GCALC_DBUG_RETURN(1);
770 rp->glue= NULL;
771 rp->down= t->rp;
772 t->rp->up= rp;
773 rp->intersection_point= true;
774 rp->pi= ii;
775 t->rp= rp;
776 GCALC_DBUG_RETURN(0);
777}
778
779int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1,
780 const Gcalc_heap::Info *p)
781{
782 res_point *rp0, *rp1;
783 GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_couple");
784 GCALC_DBUG_ASSERT(t0->rp->type == t1->rp->type);
785 if (!(rp0= add_res_point(t0->rp->type)) ||
786 !(rp1= add_res_point(t0->rp->type)))
787 GCALC_DBUG_RETURN(1);
788 rp0->down= t0->rp;
789 rp1->down= t1->rp;
790 rp1->glue= rp0;
791 rp0->glue= rp1;
792 rp0->up= rp1->up= NULL;
793 t0->rp->up= rp0;
794 t1->rp->up= rp1;
795 rp0->intersection_point= rp1->intersection_point= false;
796 rp0->pi= rp1->pi= p;
797 GCALC_DBUG_RETURN(0);
798}
799
800
801int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si)
802{
803 Gcalc_point_iterator pi(si);
804 int prev_state= 0;
805 int sav_prev_state;
806 active_thread *prev_range= NULL;
807 const Gcalc_scan_iterator::event_point *events;
808 const Gcalc_scan_iterator::point *eq_start;
809 active_thread **cur_t_hook= &m_first_active_thread;
810 active_thread **starting_t_hook;
811 active_thread *bottom_threads= NULL;
812 active_thread *eq_thread, *point_thread;;
813 GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_slice");
814
815 m_fn->clear_i_states();
816 /* Walk to the event, remembering what is needed. */
817 for (; pi.point() != si->get_event_position();
818 ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next)
819 {
820 active_thread *cur_t= *cur_t_hook;
821 if (cur_t->enabled() &&
822 cur_t->rp->type == Gcalc_function::shape_polygon)
823 {
824 prev_state^= 1;
825 prev_range= prev_state ? cur_t : 0;
826 }
827 if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon)
828 m_fn->invert_i_state(pi.get_shape());
829 }
830
831 events= si->get_events();
832 if (events->simple_event())
833 {
834 active_thread *cur_t= *cur_t_hook;
835 switch (events->event)
836 {
837 case scev_point:
838 {
839 if (cur_t->enabled() &&
840 continue_range(cur_t, events->pi, events->next_pi))
841 GCALC_DBUG_RETURN(1);
842 break;
843 }
844 case scev_end:
845 {
846 if (cur_t->enabled() && end_line(cur_t, si))
847 GCALC_DBUG_RETURN(1);
848 *cur_t_hook= cur_t->get_next();
849 free_item(cur_t);
850 break;
851 }
852 case scev_two_ends:
853 {
854 if (cur_t->enabled() && cur_t->get_next()->enabled())
855 {
856 /* When two threads are ended here */
857 if (end_couple(cur_t, cur_t->get_next(), events->pi))
858 GCALC_DBUG_RETURN(1);
859 }
860 else if (cur_t->enabled() || cur_t->get_next()->enabled())
861 {
862 /* Rare case when edges of a polygon coincide */
863 if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), si))
864 GCALC_DBUG_RETURN(1);
865 }
866 *cur_t_hook= cur_t->get_next()->get_next();
867 free_item(cur_t->next);
868 free_item(cur_t);
869 break;
870 }
871 default:
872 GCALC_DBUG_ASSERT(0);
873 }
874 GCALC_DBUG_RETURN(0);
875 }
876
877 starting_t_hook= cur_t_hook;
878 sav_prev_state= prev_state;
879
880 /* Walk through the event, collecting all the 'incoming' threads */
881 for (; events; events= events->get_next())
882 {
883 active_thread *cur_t= *cur_t_hook;
884
885 if (events->event == scev_single_point)
886 continue;
887
888 if (events->event == scev_thread ||
889 events->event == scev_two_threads)
890 {
891 active_thread *new_t= new_active_thread();
892 if (!new_t)
893 GCALC_DBUG_RETURN(1);
894 new_t->rp= NULL;
895 /* Insert into the main thread list before the current */
896 new_t->next= cur_t;
897 *cur_t_hook= new_t;
898 cur_t_hook= (active_thread **) &new_t->next;
899 }
900 else
901 {
902 if (events->is_bottom())
903 {
904 /* Move thread from the main list to the bottom_threads. */
905 *cur_t_hook= cur_t->get_next();
906 cur_t->next= bottom_threads;
907 bottom_threads= cur_t;
908 }
909 if (cur_t->enabled())
910 {
911 if (cur_t->rp->type == Gcalc_function::shape_line)
912 {
913 GCALC_DBUG_ASSERT(!prev_state);
914 add_line(1, cur_t, events);
915 }
916 else
917 {
918 add_poly_border(1, cur_t, prev_state, events);
919 prev_state^= 1;
920 }
921 if (!events->is_bottom())
922 {
923 active_thread *new_t= new_active_thread();
924 if (!new_t)
925 GCALC_DBUG_RETURN(1);
926 new_t->rp= NULL;
927 /* Replace the current thread with the new. */
928 new_t->next= cur_t->next;
929 *cur_t_hook= new_t;
930 cur_t_hook= (active_thread **) &new_t->next;
931 /* And move old to the bottom list */
932 cur_t->next= bottom_threads;
933 bottom_threads= cur_t;
934 }
935 }
936 else if (!events->is_bottom())
937 cur_t_hook= (active_thread **) &cur_t->next;
938 }
939 }
940 prev_state= sav_prev_state;
941 cur_t_hook= starting_t_hook;
942
943 eq_start= pi.point();
944 eq_thread= point_thread= *starting_t_hook;
945 m_fn->clear_b_states();
946 while (eq_start != si->get_event_end())
947 {
948 const Gcalc_scan_iterator::point *cur_eq;
949 int in_state, after_state;
950
951 ++pi;
952 point_thread= point_thread->get_next();
953
954 if (pi.point() != si->get_event_end() &&
955 eq_start->cmp_dx_dy(pi.point()) == 0)
956 continue;
957
958 for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next())
959 m_fn->set_b_state(cur_eq->get_shape());
960 in_state= m_fn->count();
961
962 m_fn->clear_b_states();
963 for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next())
964 {
965 gcalc_shape_info si= cur_eq->get_shape();
966 if ((m_fn->get_shape_kind(si) == Gcalc_function::shape_polygon))
967 m_fn->invert_i_state(si);
968 }
969 after_state= m_fn->count();
970 if (prev_state != after_state)
971 {
972 if (add_poly_border(0, eq_thread, prev_state, eq_start))
973 GCALC_DBUG_RETURN(1);
974 }
975 else if (!prev_state /* &&!after_state */ && in_state)
976 {
977 if (add_line(0, eq_thread, eq_start))
978 GCALC_DBUG_RETURN(1);
979 }
980
981 prev_state= after_state;
982 eq_start= pi.point();
983 eq_thread= point_thread;
984 }
985
986 if (!sav_prev_state && !m_poly_borders && !m_lines)
987 {
988 /* Check if we need to add the event point itself */
989 m_fn->clear_i_states();
990 /* b_states supposed to be clean already */
991 for (pi.restart(si); pi.point() != si->get_event_position(); ++pi)
992 {
993 if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon)
994 m_fn->invert_i_state(pi.get_shape());
995 }
996 for (events= si->get_events(); events; events= events->get_next())
997 m_fn->set_b_state(events->get_shape());
998
999 GCALC_DBUG_RETURN(m_fn->count() ? add_single_point(si) : 0);
1000 }
1001
1002 if (m_poly_borders)
1003 {
1004 *m_poly_borders_hook= NULL;
1005 while (m_poly_borders)
1006 {
1007 poly_border *pb1, *pb2;
1008 pb1= m_poly_borders;
1009 GCALC_DBUG_ASSERT(m_poly_borders->next);
1010
1011 pb2= get_pair_border(pb1);
1012 /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */
1013 m_poly_borders= pb1->get_next();
1014 if (connect_threads(pb1->incoming, pb2->incoming,
1015 pb1->t, pb2->t, pb1->p, pb2->p,
1016 prev_range, si, Gcalc_function::shape_polygon))
1017 GCALC_DBUG_RETURN(1);
1018
1019 free_item(pb1);
1020 free_item(pb2);
1021 }
1022 m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders;
1023 m_poly_borders= NULL;
1024 }
1025
1026 if (m_lines)
1027 {
1028 *m_lines_hook= NULL;
1029 if (m_lines->get_next() &&
1030 !m_lines->get_next()->get_next())
1031 {
1032 if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming,
1033 m_lines->t, m_lines->get_next()->t,
1034 m_lines->p, m_lines->get_next()->p,
1035 NULL, si, Gcalc_function::shape_line))
1036 GCALC_DBUG_RETURN(1);
1037 }
1038 else
1039 {
1040 for (line *cur_line= m_lines; cur_line; cur_line= cur_line->get_next())
1041 {
1042 if (cur_line->incoming)
1043 {
1044 if (end_line(cur_line->t, si))
1045 GCALC_DBUG_RETURN(1);
1046 }
1047 else
1048 start_line(cur_line->t, cur_line->p, si);
1049 }
1050 }
1051 free_list(m_lines);
1052 m_lines= NULL;
1053 m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines;
1054 }
1055
1056 if (bottom_threads)
1057 free_list(bottom_threads);
1058
1059 GCALC_DBUG_RETURN(0);
1060}
1061
1062
1063int Gcalc_operation_reducer::add_single_point(const Gcalc_scan_iterator *si)
1064{
1065 res_point *rp= add_res_point(Gcalc_function::shape_point);
1066 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_single_point");
1067 if (!rp)
1068 GCALC_DBUG_RETURN(1);
1069 rp->glue= rp->up= rp->down= NULL;
1070 rp->set(si);
1071 GCALC_DBUG_RETURN(0);
1072}
1073
1074
1075Gcalc_operation_reducer::poly_border
1076 *Gcalc_operation_reducer::get_pair_border(poly_border *b1)
1077{
1078 poly_border *prev_b= b1;
1079 poly_border *result= b1->get_next();
1080 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_pair_border");
1081 if (b1->prev_state)
1082 {
1083 if (b1->incoming)
1084 {
1085 /* Find the first outgoing, otherwise the last one. */
1086 while (result->incoming && result->get_next())
1087 {
1088 prev_b= result;
1089 result= result->get_next();
1090 }
1091 }
1092 else
1093 {
1094 /* Get the last one */
1095 while (result->get_next())
1096 {
1097 prev_b= result;
1098 result= result->get_next();
1099 }
1100 }
1101 }
1102 else /* !b1->prev_state */
1103 {
1104 if (b1->incoming)
1105 {
1106 /* Get the next incoming, otherwise the last one. */
1107 while (!result->incoming && result->get_next())
1108 {
1109 prev_b= result;
1110 result= result->get_next();
1111 }
1112 }
1113 else
1114 {
1115 /* Just pick the next one */
1116 }
1117 }
1118 /* Delete the result from the list. */
1119 prev_b->next= result->next;
1120 GCALC_DBUG_RETURN(result);
1121}
1122
1123
1124int Gcalc_operation_reducer::connect_threads(
1125 int incoming_a, int incoming_b,
1126 active_thread *ta, active_thread *tb,
1127 const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb,
1128 active_thread *prev_range,
1129 const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t)
1130{
1131 GCALC_DBUG_ENTER("Gcalc_operation_reducer::connect_threads");
1132 GCALC_DBUG_PRINT(("incoming %d %d", incoming_a, incoming_b));
1133 if (incoming_a && incoming_b)
1134 {
1135 res_point *rpa, *rpb;
1136 GCALC_DBUG_ASSERT(ta->rp->type == tb->rp->type);
1137 if (!(rpa= add_res_point(ta->rp->type)) ||
1138 !(rpb= add_res_point(ta->rp->type)))
1139 GCALC_DBUG_RETURN(1);
1140 rpa->down= ta->rp;
1141 rpb->down= tb->rp;
1142 rpb->glue= rpa;
1143 rpa->glue= rpb;
1144 rpa->up= rpb->up= NULL;
1145 ta->rp->up= rpa;
1146 tb->rp->up= rpb;
1147 rpa->set(si);
1148 rpb->set(si);
1149 ta->rp= tb->rp= NULL;
1150 GCALC_DBUG_RETURN(0);
1151 }
1152 if (!incoming_a)
1153 {
1154 GCALC_DBUG_ASSERT(!incoming_b);
1155
1156 res_point *rp0, *rp1;
1157 if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t)))
1158 GCALC_DBUG_RETURN(1);
1159 rp0->glue= rp1;
1160 rp1->glue= rp0;
1161 rp0->set(si);
1162 rp1->set(si);
1163 rp0->down= rp1->down= NULL;
1164 ta->rp= rp0;
1165 tb->rp= rp1;
1166 ta->p1= pa->pi;
1167 ta->p2= pa->next_pi;
1168
1169 tb->p1= pb->pi;
1170 tb->p2= pb->next_pi;
1171
1172 if (prev_range)
1173 {
1174 rp0->outer_poly= prev_range->thread_start;
1175 tb->thread_start= prev_range->thread_start;
1176 /* Chack if needed */
1177 ta->thread_start= prev_range->thread_start;
1178 }
1179 else
1180 {
1181 rp0->outer_poly= 0;
1182 ta->thread_start= rp0;
1183 /* Chack if needed */
1184 tb->thread_start= rp0;
1185 }
1186 GCALC_DBUG_RETURN(0);
1187 }
1188 /* else, if only ta is incoming */
1189
1190 GCALC_DBUG_ASSERT(tb != ta);
1191 tb->rp= ta->rp;
1192 tb->thread_start= ta->thread_start;
1193 if (Gcalc_scan_iterator::point::
1194 cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0)
1195 {
1196 if (si->intersection_step() ?
1197 continue_i_range(tb, si->get_cur_pi()) :
1198 continue_range(tb, si->get_cur_pi(), pb->next_pi))
1199 GCALC_DBUG_RETURN(1);
1200 }
1201 tb->p1= pb->pi;
1202 tb->p2= pb->next_pi;
1203
1204 GCALC_DBUG_RETURN(0);
1205}
1206
1207
1208int Gcalc_operation_reducer::start_line(active_thread *t,
1209 const Gcalc_scan_iterator::point *p,
1210 const Gcalc_scan_iterator *si)
1211{
1212 res_point *rp= add_res_point(Gcalc_function::shape_line);
1213 GCALC_DBUG_ENTER("Gcalc_operation_reducer::start_line");
1214 if (!rp)
1215 GCALC_DBUG_RETURN(1);
1216 rp->glue= rp->down= NULL;
1217 rp->set(si);
1218 t->rp= rp;
1219 t->p1= p->pi;
1220 t->p2= p->next_pi;
1221 GCALC_DBUG_RETURN(0);
1222}
1223
1224
1225int Gcalc_operation_reducer::end_line(active_thread *t,
1226 const Gcalc_scan_iterator *si)
1227{
1228 GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_line");
1229 GCALC_DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line);
1230 res_point *rp= add_res_point(Gcalc_function::shape_line);
1231 if (!rp)
1232 GCALC_DBUG_RETURN(1);
1233 rp->glue= rp->up= NULL;
1234 rp->down= t->rp;
1235 rp->set(si);
1236 t->rp->up= rp;
1237 t->rp= NULL;
1238
1239 GCALC_DBUG_RETURN(0);
1240}
1241
1242
1243int Gcalc_operation_reducer::count_all(Gcalc_heap *hp)
1244{
1245 Gcalc_scan_iterator si;
1246 GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_all");
1247 si.init(hp);
1248 GCALC_SET_TERMINATED(si.killed, killed);
1249 while (si.more_points())
1250 {
1251 if (si.step())
1252 GCALC_DBUG_RETURN(1);
1253 if (count_slice(&si))
1254 GCALC_DBUG_RETURN(1);
1255 }
1256 GCALC_DBUG_RETURN(0);
1257}
1258
1259inline void Gcalc_operation_reducer::free_result(res_point *res)
1260{
1261 if ((*res->prev_hook= res->next))
1262 {
1263 res->get_next()->prev_hook= res->prev_hook;
1264 }
1265 free_item(res);
1266}
1267
1268
1269inline int Gcalc_operation_reducer::get_single_result(res_point *res,
1270 Gcalc_result_receiver *storage)
1271{
1272 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_single_result");
1273 if (res->intersection_point)
1274 {
1275 double x, y;
1276 res->pi->calc_xy(&x, &y);
1277 if (storage->single_point(x,y))
1278 GCALC_DBUG_RETURN(1);
1279 }
1280 else
1281 if (storage->single_point(res->pi->node.shape.x, res->pi->node.shape.y))
1282 GCALC_DBUG_RETURN(1);
1283 free_result(res);
1284 GCALC_DBUG_RETURN(0);
1285}
1286
1287
1288int Gcalc_operation_reducer::get_result_thread(res_point *cur,
1289 Gcalc_result_receiver *storage,
1290 int move_upward,
1291 res_point *first_poly_node)
1292{
1293 res_point *next;
1294 bool glue_step= false;
1295 double x, y;
1296 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result_thread");
1297 while (cur)
1298 {
1299 if (!glue_step)
1300 {
1301 if (cur->intersection_point)
1302 {
1303 cur->pi->calc_xy(&x, &y);
1304 }
1305 else
1306 {
1307 x= cur->pi->node.shape.x;
1308 y= cur->pi->node.shape.y;
1309 }
1310 if (storage->add_point(x, y))
1311 GCALC_DBUG_RETURN(1);
1312 }
1313
1314 next= move_upward ? cur->up : cur->down;
1315 if (!next && !glue_step)
1316 {
1317 next= cur->glue;
1318 move_upward^= 1;
1319 glue_step= true;
1320 if (next)
1321 next->glue= NULL;
1322 }
1323 else
1324 glue_step= false;
1325
1326 cur->first_poly_node= first_poly_node;
1327 free_result(cur);
1328 cur= next;
1329 }
1330 GCALC_DBUG_RETURN(0);
1331}
1332
1333
1334int Gcalc_operation_reducer::get_polygon_result(res_point *cur,
1335 Gcalc_result_receiver *storage,
1336 res_point *first_poly_node)
1337{
1338 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_polygon_result");
1339 res_point *glue= cur->glue;
1340 glue->up->down= NULL;
1341 free_result(glue);
1342 GCALC_DBUG_RETURN(get_result_thread(cur, storage, 1, first_poly_node) ||
1343 storage->complete_shape());
1344}
1345
1346
1347int Gcalc_operation_reducer::get_line_result(res_point *cur,
1348 Gcalc_result_receiver *storage)
1349{
1350 res_point *next;
1351 res_point *cur_orig= cur;
1352 int move_upward= 1;
1353 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_line_result");
1354 if (cur->glue)
1355 {
1356 /* Here we have to find the beginning of the line */
1357 next= cur->up;
1358 move_upward= 1;
1359 while (next)
1360 {
1361 cur= next;
1362 next= move_upward ? next->up : next->down;
1363 if (!next)
1364 {
1365 next= cur->glue;
1366 if (next == cur_orig)
1367 {
1368 /* It's the line loop */
1369 cur= cur_orig;
1370 cur->glue->glue= NULL;
1371 move_upward= 1;
1372 break;
1373 }
1374 move_upward^= 1;
1375 }
1376 }
1377 }
1378
1379 GCALC_DBUG_RETURN(get_result_thread(cur, storage, move_upward, 0) ||
1380 storage->complete_shape());
1381}
1382
1383
1384int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage)
1385{
1386 poly_instance *polygons= NULL;
1387
1388 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result");
1389 *m_res_hook= NULL;
1390
1391 /* This is to workaround an old gcc's bug */
1392 if (m_res_hook == (Gcalc_dyn_list::Item **) &m_result)
1393 goto done;
1394
1395 while (m_result)
1396 {
1397 Gcalc_function::shape_type shape= m_result->type;
1398 if (shape == Gcalc_function::shape_point)
1399 {
1400 if (get_single_result(m_result, storage))
1401 GCALC_DBUG_RETURN(1);
1402 continue;
1403 }
1404 if (shape == Gcalc_function::shape_polygon)
1405 {
1406 if (m_result->outer_poly)
1407 {
1408 uint32 insert_position, hole_position, position_shift;
1409 poly_instance *cur_poly;
1410 insert_position= m_result->outer_poly->first_poly_node->poly_position;
1411 GCALC_DBUG_ASSERT(insert_position);
1412 hole_position= storage->position();
1413 storage->start_shape(Gcalc_function::shape_hole);
1414 if (get_polygon_result(m_result, storage,
1415 m_result->outer_poly->first_poly_node) ||
1416 storage->move_hole(insert_position, hole_position,
1417 &position_shift))
1418 GCALC_DBUG_RETURN(1);
1419 for (cur_poly= polygons;
1420 cur_poly && *cur_poly->after_poly_position >= insert_position;
1421 cur_poly= cur_poly->get_next())
1422 *cur_poly->after_poly_position+= position_shift;
1423 }
1424 else
1425 {
1426 uint32 *poly_position= &m_result->poly_position;
1427 poly_instance *p= new_poly();
1428 p->after_poly_position= poly_position;
1429 p->next= polygons;
1430 polygons= p;
1431 storage->start_shape(Gcalc_function::shape_polygon);
1432 if (get_polygon_result(m_result, storage, m_result))
1433 GCALC_DBUG_RETURN(1);
1434 *poly_position= storage->position();
1435 }
1436 }
1437 else
1438 {
1439 storage->start_shape(shape);
1440 if (get_line_result(m_result, storage))
1441 GCALC_DBUG_RETURN(1);
1442 }
1443 }
1444
1445done:
1446 m_res_hook= (Gcalc_dyn_list::Item **)&m_result;
1447 storage->done();
1448 GCALC_DBUG_RETURN(0);
1449}
1450
1451
1452void Gcalc_operation_reducer::reset()
1453{
1454 free_list((Gcalc_heap::Item **) &m_result, m_res_hook);
1455 m_res_hook= (Gcalc_dyn_list::Item **)&m_result;
1456 free_list(m_first_active_thread);
1457}
1458
1459#endif /*HAVE_SPATIAL*/
1460
1461