source: trunk/src/org/expeditee/io/flowlayout/XGroupItem.java@ 959

Last change on this file since 959 was 959, checked in by bln4, 9 years ago
  • Property svn:executable set to *
File size: 42.3 KB
Line 
1/**
2 * XGroupItem.java
3 * Copyright (C) 2010 New Zealand Digital Library, http://expeditee.org
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19package org.expeditee.io.flowlayout;
20
21import java.awt.Point;
22import java.awt.Polygon;
23import java.awt.Rectangle;
24import java.util.ArrayList;
25import java.util.Collection;
26import java.util.Collections;
27import java.util.Comparator;
28import java.util.HashSet;
29import java.util.Iterator;
30import java.util.LinkedList;
31import java.util.List;
32
33import org.expeditee.gui.Frame;
34import org.expeditee.gui.FrameUtils;
35import org.expeditee.items.Item;
36import org.expeditee.items.Line;
37import org.expeditee.items.Text;
38
39
40public class XGroupItem extends XItem
41{
42 public static final Text GROUPSEP_END = new Text('2' + ""); //ASCII '2' is start of text
43
44 public static final Text GROUPSEP_START = new Text('3' + ""); //ASCII '3' is end of text
45
46 enum FlowType { in_flow, out_of_flow_original, out_of_flow_faked_position };
47
48 public static boolean doImplicitBoxing = true;
49
50 class MultiArrowHeadComparable implements Comparator<Item>{
51
52 @Override
53 public int compare(Item o1, Item o2)
54 {
55 int o1y = o1.getY();
56 int o2y = o2.getY();
57
58 int order = 0; // default to assume they are identical
59
60 if (o1y<o2y) {
61 order = -1; // done, o1 is higher up the frame than o2 => our definition of 'before'
62 }
63 else if (o2y<o1y) {
64 order = +1; // also done, o1 is lower down the frame than o2 => our definition of 'after'
65
66 }
67 else {
68 // have identical 'y' values, so look to 'x' to tie-break
69
70 int o1x = o1.getX();
71 int o2x = o2.getX();
72
73 if (o1x<o2x) {
74 order = -1; // done, o1 is to the left of o2 => our definition of 'before'
75 }
76 else if (o2x<o1x) {
77 order = +1; // also done, o1 is to the right of o2 => our definition of 'after'
78 }
79 }
80
81 return order;
82 }
83 }
84
85 Frame frame;
86
87 protected int y_span_height;
88 protected YOverlappingItemsSpan[] yitems_span_array;
89
90 List<Text> raw_text_item_list;
91 List<XGroupItem> grouped_item_list;
92 List<Item> remaining_item_list;
93
94 FlowType out_of_flow;
95
96 protected XGroupItem()
97 {
98 frame = null;
99
100 y_span_height = 0;
101 yitems_span_array = null;
102
103 raw_text_item_list = null;
104 grouped_item_list = null;
105 remaining_item_list = null;
106
107 out_of_flow = FlowType.in_flow;
108 }
109
110 public XGroupItem(Frame frame, List<Item> y_ordered_items, Polygon enclosing_polygon)
111 {
112 this.frame = frame;
113 this.out_of_flow = FlowType.in_flow;;
114
115 if (enclosing_polygon == null) {
116 // e.g. when the top-level case, with no enclosing polygon at this stage
117 // => generate one based on the bounding box of the y_ordered_items
118 enclosing_polygon = DimensionExtent.boundingBoxPolygon(y_ordered_items);
119 }
120
121 Rectangle enclosing_bounding_rect = enclosing_polygon.getBounds();
122 initSpanArray(enclosing_bounding_rect);
123
124 // Step 1: Separate out the raw-text-items, the grouped-items and 'remaining' (e.g. points and lines)
125
126 raw_text_item_list = new ArrayList<Text>();
127 grouped_item_list = new ArrayList<XGroupItem>();
128 remaining_item_list = new ArrayList<Item>();
129
130 separateYOverlappingItems(frame, y_ordered_items, enclosing_polygon, raw_text_item_list, grouped_item_list, remaining_item_list);
131
132
133 // Step 2: Add in the raw-text items
134 for (Text text_item : raw_text_item_list) {
135
136 XRawItem x_raw_item = new XRawItem(text_item, this);
137 // overspill can occur (and is acceptable) when raw-text item spills out of enclosing shape (such as a rectangle)
138 mapInItem(x_raw_item);
139 }
140
141 }
142
143 public XGroupItem(Frame frame, List<Item> y_ordered_items)
144 {
145 this(frame,y_ordered_items,null);
146 }
147
148 protected XGroupItem(XGroupItem imprint, Rectangle copy_to_bounding_rect)
149 {
150 super();
151
152 // Implement a shallow copy => share references to frame, and item list, and y-span
153 // Only the bounding box is changed => set to the 'copy_to_bounding_rect' passed in
154
155 this.frame = imprint.frame;
156
157 y_span_height = imprint.y_span_height;
158 yitems_span_array = imprint.yitems_span_array;
159
160 this.raw_text_item_list = imprint.raw_text_item_list;
161 this.grouped_item_list = imprint.grouped_item_list;
162
163// int offX = imprint.getBoundingRect().x - copy_to_bounding_rect.x;
164// int offY = imprint.getBoundingRect().y - copy_to_bounding_rect.y;
165// this.grouped_item_list = new ArrayList<XGroupItem>();
166// for(XGroupItem newChild : imprint.grouped_item_list) {
167// Rectangle newRect = newChild.getBoundingRect();
168// newRect.x -= offX;
169// newRect.y -= offY;
170// this.grouped_item_list.add(new XGroupItem(newChild, newRect));
171// }
172 this.remaining_item_list = imprint.remaining_item_list;
173
174 this.out_of_flow = imprint.out_of_flow; // Or perhaps set it to FlowType.out_of_flow_fake_position straight away?
175
176 this.bounding_rect = new Rectangle(copy_to_bounding_rect); // deep copy to be on the safe side
177 }
178
179
180 protected void initSpanArray(Rectangle bounding_rect)
181 {
182 this.bounding_rect = bounding_rect;
183
184 int y_top = getBoundingYTop();
185 int y_bot = getBoundingYBot();
186
187 if (y_top<=y_bot) {
188 // => have non-trivial span
189
190 y_span_height = (y_bot - y_top) + 2; // Polygon in Java excludes right and bottom sides so need extra "+1" in calc
191
192 yitems_span_array = new YOverlappingItemsSpan[y_span_height];
193 }
194 else {
195 y_span_height = 0;
196 yitems_span_array = null;
197 }
198 }
199
200 public YOverlappingItemsSpan getSpanItemAt(int index) {
201 return yitems_span_array[index];
202 }
203
204 public void setOutOfFlow(FlowType flow_type)
205 {
206 out_of_flow = flow_type;
207 }
208
209 public FlowType getFlowItem()
210 {
211 return out_of_flow;
212 }
213
214 public boolean isOriginalOutOfFlowItem()
215 {
216 return out_of_flow == FlowType.out_of_flow_original;
217 }
218
219 public boolean isFakedOutOfFlowItem()
220 {
221 return out_of_flow == FlowType.out_of_flow_faked_position;
222 }
223
224
225 public List<Text> getRawTextItemList()
226 {
227 return raw_text_item_list;
228 }
229
230 public List<Text[]> getRawTextLines() {
231 final List<Text> rawText = getRawTextItemList();
232 final List<Text> lineStarts = new LinkedList<Text>();
233 for(final YOverlappingItemsSpan span : this.yitems_span_array) {
234 if(span instanceof YOverlappingItemsTopEdge) {
235 final YOverlappingItemsTopEdge topEdge = (YOverlappingItemsTopEdge) span;
236 final List<XItem> xLine = topEdge.getXOrderedLine().getXItemList();
237 for(final XItem xitem : xLine) {
238 if(xitem instanceof XRawItem) {
239 final Text item = (Text)((XRawItem) xitem).getItem();
240 lineStarts.add(item);
241 break;
242 }
243 }
244 }
245 }
246 final List<Integer> indexes = new LinkedList<Integer>();
247 for(final Text lineStart : lineStarts)
248 indexes.add(rawText.indexOf(lineStart));
249 final List<Text[]> ret = new LinkedList<Text[]>();
250 int rangeEnd = indexes.get(0);
251 int last = rangeEnd;
252 for(int i = 1; i < indexes.size(); i++) {
253 rangeEnd = indexes.get(i);
254 final List<Text> part = new LinkedList<Text>(rawText.subList(0, rangeEnd - last));
255 last = rangeEnd;
256 rawText.removeAll(part);
257 part.toArray(new Text[]{});
258 ret.add(part.toArray(new Text[]{}));
259 }
260 ret.add(rawText.toArray(new Text[]{}));
261 return ret;
262 }
263
264 public List<XGroupItem> getGroupedItemList()
265 {
266 return grouped_item_list;
267 }
268
269 public List<Item> getRemainingItemList()
270 {
271 return remaining_item_list;
272 }
273
274 public int getItemSpanLength() {
275 return yitems_span_array.length;
276 }
277
278 public YOverlappingItemsSpan getYOverlappingItemsSpan(int y)
279 {
280 int y_index = y - getBoundingYTop();
281
282 if ((y_index<0) || (y_index>=yitems_span_array.length)) {
283 int y_top = getBoundingYTop();
284 int y_bot = y_top + yitems_span_array.length -1;
285
286 System.err.println("Error in getYOverlappingItemsSpan(): index out of bounds for value " + y);
287 System.err.println(" => Operation mapped into local array: y-top=" + y_top + ", y-bot=" + y_bot);
288
289 return null;
290 }
291 return yitems_span_array[y_index];
292 }
293
294 protected int cropToTop(int y) {
295 int y_index = y - getBoundingYTop();
296
297 if (y_index<0) {
298 y = getBoundingYTop();
299 }
300
301 return y;
302 }
303
304 protected int cropToBot(int y) {
305 int y_index = y - getBoundingYTop();
306
307 if (y_index>=yitems_span_array.length) {
308 y = getBoundingYBot();
309 }
310
311 return y;
312 }
313
314 public void setYOverlappingItemsSpan(int y,YOverlappingItemsSpan yitems_span)
315 {
316 int y_index = y - getBoundingYTop();
317
318 if ((y_index<0) || (y_index>=yitems_span_array.length)) {
319
320 int y_top = getBoundingYTop();
321 int y_bot = y_top + yitems_span_array.length -1;
322
323 System.err.println("Error in setYOverlappingItemsSpan(): index out of bounds for value " + y);
324 System.err.println(" => Operation mapped into local array: y-top=" + y_top + ", y-bot=" + y_bot);
325
326 return;
327 }
328 yitems_span_array[y_index] = yitems_span;
329 }
330
331
332 protected List<Item> followLinesToArrowHeads(Collection<Item> visited, Item anchor_item, List<Line>used_in_lines)
333 {
334 List<Item> arrow_head_endpoints = new ArrayList<Item>();
335
336 for (Line line: used_in_lines) {
337
338 Item start_item = line.getStartItem();
339
340 if (start_item == anchor_item) {
341 // the line we're considering is heading in the right direction
342
343 Item end_item = line.getEndItem();
344
345 if (!visited.contains(end_item)) {
346 // Needs processing
347 visited.add(end_item);
348
349 List<Line> follow_lines = end_item.getLines();
350
351 if (follow_lines.size()==1) {
352 // reached an end-point
353 if (end_item.hasVisibleArrow()) {
354 arrow_head_endpoints.add(end_item);
355 }
356 }
357 else if (follow_lines.size()>1) {
358
359 List<Item> followed_arrow_heads = followLinesToArrowHeads(visited,end_item,follow_lines);
360 arrow_head_endpoints.addAll(followed_arrow_heads);
361 }
362 }
363 }
364
365 }
366 return arrow_head_endpoints;
367 }
368
369
370 protected XGroupItem innermostXGroup(Item arrow_head, List<XGroupItem> grouped_item_list)
371 {
372 XGroupItem innermost_item = null;
373
374 for (XGroupItem xgroup_item: grouped_item_list) {
375 if (xgroup_item.containsItem(arrow_head)) {
376
377 innermost_item = xgroup_item;
378
379 // Now see if it is in any of the nested ones?
380
381 List<XGroupItem> nested_group_item_list = xgroup_item.grouped_item_list;
382
383 XGroupItem potentially_better_item = innermostXGroup(arrow_head,nested_group_item_list);
384
385 if (potentially_better_item != null) {
386 innermost_item = potentially_better_item;
387 }
388 break;
389 }
390
391 }
392
393 return innermost_item;
394 }
395
396 protected void removeXGroupItem(XGroupItem remove_item, List<XGroupItem> grouped_item_list)
397 {
398
399 for (XGroupItem xgroup_item: grouped_item_list) {
400
401 if (xgroup_item == remove_item) {
402 grouped_item_list.remove(xgroup_item);
403 return;
404 }
405 else {
406 List<XGroupItem> nested_group_item_list = xgroup_item.grouped_item_list;
407 removeXGroupItem(remove_item,nested_group_item_list);
408
409 }
410 }
411 }
412
413
414
415 protected void repositionOutOfFlowGroupsFollowLine(XGroupItem toplevel_xgroup, Item remaining_item, Collection<XGroupItem> out_of_flow)
416 {
417 // See if this item is the start of a line
418 // Follow it if it is
419 // For each end of the line (potentially a multi-split poly-line) that has an arrow head:
420 // See if the arrow-head falls inside an XGroup area
421 // => Ignore endings that are in the same XGroupItem as the line started in
422
423 List<Line> used_in_lines = remaining_item.getLines();
424 if (used_in_lines.size()==1) {
425 // at the start (or end) of a line
426
427 Item start_item = used_in_lines.get(0).getStartItem();
428
429 if (remaining_item == start_item) {
430
431 // found the start of a line
432
433 Collection<Item> visited = new HashSet<Item>();
434 visited.add(remaining_item);
435
436 List<Item> arrow_head_endpoints = followLinesToArrowHeads(visited,remaining_item,used_in_lines);
437
438 //System.out.println("**** For Xgroup " + this + " with dot starting at " + remaining_item + " has " + arrow_head_endpoints.size() + " arrow head endpoints");
439
440 Collections.sort(arrow_head_endpoints, new MultiArrowHeadComparable());
441
442 for (Item arrow_head: arrow_head_endpoints) {
443 // find the inner-most group it falls within
444
445 List<XGroupItem> toplevel_grouped_item_list = toplevel_xgroup.getGroupedItemList();
446
447 XGroupItem xgroup_item = innermostXGroup(arrow_head,toplevel_grouped_item_list);
448
449 if (xgroup_item != null) {
450
451 // Ignore if the found 'xgroup_item' is 'this'
452 // (i.e. the found arrow head is at the same XGroupItem level we are currently processing)
453
454 if (xgroup_item != this) {
455
456 out_of_flow.add(xgroup_item);
457 // Can't delete here, as it causes a concurrent exception => add to 'out_of_flow' hashmap and perform removal later
458
459 //System.out.println("**** innermost XGroupItem = " + xgroup_item);
460
461 // Artificially rework its (x,y) org and dimension to make it appear where the start of the arrow is
462
463 Rectangle start_rect = start_item.getArea().getBounds();
464
465
466 XGroupItem xgroup_item_shallow_copy = new XGroupItem(xgroup_item,start_rect);
467
468 // Perhaps the following two lines should be moved to inside the constructor??
469
470 xgroup_item.setOutOfFlow(FlowType.out_of_flow_original);
471 xgroup_item_shallow_copy.setOutOfFlow(FlowType.out_of_flow_faked_position);
472
473
474 //xgroup_item.setBoundingRect(start_rect);
475 //xgroup_item.setOutOfFlow();
476
477 // Finally add it in
478 //mapInItem(xgroup_item);
479 mapInItem(xgroup_item_shallow_copy);
480 }
481 }
482 }
483 }
484
485 }
486 }
487
488 /**
489 * Look for any 'out-of-flow' XGroup boxes, signalled by the user drawing an arrow line to it
490 * => force an artificial change to such boxes so its dimensions becomes the starting point
491 * of the arrow line. This will make it sort to the desired spot in the YOverlapping span
492 */
493
494 public void repositionOutOfFlowGroupsRecursive(XGroupItem toplevel_xgroup, Collection<XGroupItem> out_of_flow)
495 {
496 // Map in all the items in the given list:
497 for (Item remaining_item: remaining_item_list) {
498
499 repositionOutOfFlowGroupsFollowLine(toplevel_xgroup,remaining_item,out_of_flow);
500 }
501
502 // Now recursively work through each item's nested x-groups
503 for (XGroupItem xgroup_item: grouped_item_list) {
504
505 if (!out_of_flow.contains(xgroup_item)) {
506 xgroup_item.repositionOutOfFlowGroupsRecursive(toplevel_xgroup,out_of_flow);
507 }
508 }
509 }
510
511
512 public void repositionOutOfFlowGroups(XGroupItem toplevel_xgroup)
513 {
514 Collection<XGroupItem> out_of_flow = new HashSet<XGroupItem>();
515
516 repositionOutOfFlowGroupsRecursive(toplevel_xgroup,out_of_flow);
517
518 List<XGroupItem >toplevel_grouped_item_list = toplevel_xgroup.getGroupedItemList();
519
520 // ****
521
522 // Want to remove the original "out-of-position" blocks that were found, as (for each arrow
523 // point to such an original) shallow-copies now exist with 'faked' positions that correspond
524 // to where the arrows start.
525
526
527 // No longer remove them from the nested grouped structure, rather, rely on these items being
528 // tagged "isOutOfFLow()" to be skipped by subsequent traversal calls (e.g., to generate
529 // the normal "in-flow" nested blocks)
530
531 // Structuring things this way, means that it is now possible to have multiple arrows
532 // pointing to the same block of code, and both "out-of-flow" arrows will be honoured,
533 // replicating the code at their respective start points
534
535 /*
536 for (XGroupItem xgroup_item: out_of_flow) {
537 removeXGroupItem(xgroup_item,toplevel_grouped_item_list);
538 }
539
540 */
541
542 }
543
544 /**
545 * Focusing only on enclosures that fit within the given polygon *and* have this item
546 * in it, the method finds the largest of these enclosures and
547 * returns all the items it contains
548 *
549 * @return
550 */
551 public Collection<Item> getItemsInNestedEnclosure(Item given_item, AreaPolygon outer_polygon)
552 {
553 Collection<Item> sameEnclosure = null;
554 Collection<Item> seen = new HashSet<Item>();
555
556 double enclosureArea = 0.0;
557
558 for (Item i : frame.getItems()) {
559
560 // Go through all the enclosures ...
561
562 if (!seen.contains(i) && i.isEnclosed()) {
563
564 Collection<Item> i_enclosing_dots_coll = i.getEnclosingDots();
565 List<Item> i_enclosing_dots = new ArrayList<Item>(i_enclosing_dots_coll); // Change to List of items
566
567 seen.addAll(i_enclosing_dots);
568
569 Polygon i_polygon = new Polygon();
570 for (int di=0; di<i_enclosing_dots.size(); di++) {
571 Item d = i_enclosing_dots.get(di);
572
573 i_polygon.addPoint(d.getX(), d.getY());
574 }
575
576 // ... looking for one that is completely contained in the 'outer_polygon' and ...
577 if (outer_polygon.completelyContains(i_polygon)) {
578
579 Collection<Item> enclosed = i.getEnclosedItems();
580
581 // ... includes this item
582 if (enclosed.contains(given_item)) {
583
584 // Remember it if it is larger than anything we've encountered before
585 if ((i.getEnclosedArea() > enclosureArea)) {
586 enclosureArea = i.getEnclosedArea();
587 sameEnclosure = enclosed;
588 }
589 }
590 }
591
592 }
593 }
594
595 if (sameEnclosure == null)
596 return new LinkedList<Item>();
597
598 return sameEnclosure;
599 }
600
601
602 public void separateYOverlappingItems(Frame frame, List<Item> item_list, Polygon enclosing_polygon,
603 List<Text> raw_text_item_list, List<XGroupItem> grouped_item_list, List<Item> remaining_item_list)
604 {
605 // raw_text_items_list => all the non-enclosed text items
606 // grouped_items_list => list of all enclosures containing text items
607 // remaining_item_list => whatever is left: mostly dots that form part of lines/polylines/polygons
608
609 AreaPolygon area_enclosing_polygon = new AreaPolygon(enclosing_polygon);
610
611 List<AreaPolygon> area_enclosed_polygon_list = new ArrayList<AreaPolygon>();
612
613 while (item_list.size()>0) {
614 Item item = item_list.remove(0); // shift
615
616 if (item instanceof Text) {
617 Text text = (Text)item;
618
619 Collection<Item> items_in_nested_enclosure_coll = getItemsInNestedEnclosure(text,area_enclosing_polygon);
620 List<Item> items_in_nested_enclosure = new ArrayList<Item>(items_in_nested_enclosure_coll); // Change to handling it as a list
621
622 if (items_in_nested_enclosure.size()==0) {
623// if(text.getPixelBoundsUnion().x >= this.getBoundingXLeft() && text.getPixelBoundsUnion().y >= this.getBoundingYTop())
624// raw_text_item_list.add(text);
625// else remaining_item_list.add(text);
626 raw_text_item_list.add(text);
627 }
628 else {
629
630 // Something other than just this text-item is around
631
632 while (items_in_nested_enclosure.size()>0) {
633
634 Item enclosure_item = items_in_nested_enclosure.remove(0); // shift
635
636 Polygon enclosed_polygon = enclosure_item.getEnclosedShape();
637
638 if (enclosed_polygon!=null) {
639 // Got a group
640 // => Remove any items-in-nested-enclosure from:
641 //
642 // 'item_list' (so we don't waste our time discovering and processing again these related items)
643 // and
644 // 'raw_text_item_list' and 'remaining_item_lst' (as we now know they are part of the nested enclosed group)
645
646 AreaPolygon area_enclosed_polygon = new AreaPolygon(enclosed_polygon);
647 area_enclosed_polygon_list.add(area_enclosed_polygon);
648
649 item_list.remove(enclosure_item);
650 item_list.removeAll(items_in_nested_enclosure);
651
652 raw_text_item_list.remove(enclosure_item);
653 raw_text_item_list.removeAll(items_in_nested_enclosure);
654
655 remaining_item_list.remove(enclosure_item);
656 remaining_item_list.removeAll(items_in_nested_enclosure);
657
658 // Now remove any of the just used enclosed-items if they formed part of the perimeter
659 List<Item> items_on_perimeter = new ArrayList<Item>();
660
661 Iterator<Item> item_iterator = items_in_nested_enclosure.iterator();
662 while (item_iterator.hasNext()) {
663 Item item_to_check = item_iterator.next();
664 Point pt_to_check = new Point(item_to_check.getX(),item_to_check.getY());
665
666 if (area_enclosed_polygon.isPerimeterPoint(pt_to_check)) {
667 items_on_perimeter.add(item_to_check);
668 }
669 }
670
671 items_in_nested_enclosure.removeAll(items_on_perimeter);
672 }
673
674 else {
675 // Text or single point (with no enclosure)
676
677 // This item doesn't feature at this level
678 // => will be subsequently capture by the group polygon below
679 // and processed by the recursive call
680
681 item_list.remove(enclosure_item);
682 }
683 }
684
685 }
686
687 } // end of Text test
688 else {
689 // non-text item => add to remaining_item_list
690 remaining_item_list.add(item);
691 }
692
693 }
694
695 // Sort areas, smallest to largest
696 Collections.sort(area_enclosed_polygon_list, new Comparator<AreaPolygon>() {
697
698 public int compare(AreaPolygon ap1, AreaPolygon ap2) {
699 Double ap1_area = ap1.getArea();
700 Double ap2_area = ap2.getArea();
701
702 return ap2_area.compareTo(ap1_area);
703 }
704 });
705
706 // Remove any enclosed polygon areas that are completely contained in a larger one
707
708 for (int ri=0; ri<area_enclosed_polygon_list.size(); ri++) {
709 // ri = remove index pos
710
711 AreaPolygon rpoly = area_enclosed_polygon_list.get(ri);
712
713 for (int ci=ri+1; ci<area_enclosed_polygon_list.size(); ci++) {
714 // ci = check index pos
715 AreaPolygon cpoly = area_enclosed_polygon_list.get(ci);
716 if (rpoly.completelyContains(cpoly)) {
717 area_enclosed_polygon_list.remove(ci);
718 ri--; // to offset to the outside loop increment
719 break;
720 }
721 }
722 }
723
724
725 // By this point, guaranteed that the remaining polygons are the largest ones
726 // that capture groups of items
727 //
728 // There may be sub-groupings within them, which is the reason for the recursive call below
729
730
731 for (AreaPolygon area_polygon: area_enclosed_polygon_list) {
732
733 Collection<Item> enclosed_items = FrameUtils.getItemsEnclosedBy(frame, area_polygon);
734 List<Item> enclosed_item_list = new ArrayList<Item>(enclosed_items);
735
736 int i=0;
737 while (i<enclosed_item_list.size()) {
738 Item enclosed_item = enclosed_item_list.get(i);
739
740 // Filter out enclosed-items points that are part of the polygon's perimeter
741 if (area_polygon.isPerimeterPoint(enclosed_item.getPosition())) {
742 enclosed_item_list.remove(i);
743 }
744 else {
745 i++;
746 }
747 }
748
749 // Recursively work on the identified sub-group
750
751 XGroupItem xgroup_item = new XGroupItem(frame, enclosed_item_list, area_polygon);
752
753 grouped_item_list.add(xgroup_item);
754 }
755 }
756
757
758
759 protected void castShadowIntoEmptySpace(YOverlappingItemsTopEdge y_item_span_top_edge, int yt, int yb)
760 {
761 // Assumes that all entries cast into are currently null
762 // => Use the more general castShadow() below, if this is not guaranteed to be the case
763
764 YOverlappingItemsShadow y_span_shadow = new YOverlappingItemsShadow(y_item_span_top_edge);
765
766 for (int y=yt; y<=yb; y++) {
767
768 setYOverlappingItemsSpan(y,y_span_shadow);
769 }
770 }
771
772 protected void castShadow(YOverlappingItemsTopEdge y_item_span_top_edge, int yt, int yb)
773 {
774 // Cast shadows only in places where there are currently no shadow entries
775
776 YOverlappingItemsShadow y_span_shadow = new YOverlappingItemsShadow(y_item_span_top_edge);
777
778 int y=yt;
779
780 while (y<=yb) {
781 YOverlappingItemsSpan y_item_span = getYOverlappingItemsSpan(y);
782
783 if (y_item_span==null) {
784 setYOverlappingItemsSpan(y,y_span_shadow);
785 y++;
786 }
787 else if (y_item_span instanceof YOverlappingItemsTopEdge) {
788 // Our shadow has run into another top-edged zone
789 // => need to extend the shadow to include this zone as well
790 // (making this encountered top-edge obsolete)
791
792 // Merge the newly encountered top-line in with the current one
793 // and change all its shadow references to our (dominant) one
794
795 XOrderedLine dominant_x_line = y_item_span_top_edge.getXOrderedLine();
796
797 YOverlappingItemsTopEdge obsolete_top_edge = (YOverlappingItemsTopEdge)y_item_span;
798 XOrderedLine obsolete_x_line = obsolete_top_edge.getXOrderedLine();
799
800 for (XItem xitem: obsolete_x_line.getXItemList()) {
801
802 dominant_x_line.orderedMergeItem(xitem);
803 }
804
805 while (y_item_span != null) {
806
807 setYOverlappingItemsSpan(y,y_span_shadow);
808
809 y++;
810
811 if (y<=yb) {
812 y_item_span = getYOverlappingItemsSpan(y);
813 }
814 else {
815 y_item_span = null;
816 }
817 }
818 }
819 else {
820 y++;
821 }
822 }
823 }
824
825 protected int autocropToTop(XItem xitem)
826 {
827 // top-edge over-spill can occur (and is acceptable) when (for example) the given xitem is a raw-text item
828 // that doesn't neatly fit in an enclosed area (i,e., is poking out the top of an enclosing rectangle)
829 // => cut down to the top of 'this' xgroupitem
830
831 int yt = xitem.getBoundingYTop();
832
833
834 yt = cropToTop(yt); // Only changes yt if in an over-spill situation
835
836 return yt;
837
838 }
839
840 protected int autocropToBot(XItem xitem)
841 {
842
843 // similar to autocropToTop(), bottom-edge over-spill can occur (and is acceptable) with
844 // a less than precise placed raw-text item
845
846 int yb = xitem.getBoundingYBot();
847
848 yb = cropToBot(yb); // Only changes yb if in an over-spill situation
849
850 return yb;
851 }
852
853 protected boolean yExtentIntersection(XGroupItem xgroup_item1, XGroupItem xgroup_item2)
854 {
855 // Computation applied to y-extent of each rectangle
856
857 // To intersect, either a point in item1 falls inside item2,
858 // or else item2 is completely within item1
859
860
861 int yt1 = xgroup_item1.getBoundingYTop();
862 int yb1 = xgroup_item1.getBoundingYBot();
863
864 int yt2 = xgroup_item2.getBoundingYTop();
865
866 // yt1 insides item2?
867 if (xgroup_item2.containedInYExtent(yt1)) {
868 return true;
869 }
870
871 // yb1 inside item2?
872 if (xgroup_item2.containedInYExtent(yb1)) {
873 return true;
874 }
875
876 // item2 completely inside item1?
877 //
878 // With the previous testing, this can be determined
879 // by checking only one of the values is inside.
880 // Doesn't matter which => choose yt2
881
882 if (xgroup_item1.containedInYExtent(yt2)) {
883 return true;
884 }
885
886 // Get to here if there is no intersection
887 return false;
888
889 }
890 protected ArrayList<XGroupItem> calcXGroupYExtentIntersection(XGroupItem xgroup_pivot_item, List<XGroupItem> xgroup_item_list)
891 {
892 ArrayList<XGroupItem> intersect_list = new ArrayList<XGroupItem>();
893
894 for (XGroupItem xgroup_item: xgroup_item_list) {
895
896 if (xgroup_item == xgroup_pivot_item) {
897 // Don't bother working out the intersection with itself!
898 continue;
899 }
900
901 if (yExtentIntersection(xgroup_pivot_item,xgroup_item)) {
902 intersect_list.add(xgroup_item);
903 }
904 }
905
906 return intersect_list;
907 }
908
909 protected ArrayList<YOverlappingItemsTopEdge> calcYSpanOverlap(XItem xitem)
910 {
911 int yt = autocropToTop(xitem);
912 int yb = autocropToBot(xitem);
913
914
915 ArrayList<YOverlappingItemsTopEdge> top_edge_list = new ArrayList<YOverlappingItemsTopEdge>();
916
917 for (int y=yt; y<=yb; y++) {
918
919 YOverlappingItemsSpan item_span = getYOverlappingItemsSpan(y);
920
921 if (item_span != null) {
922
923 if (item_span instanceof YOverlappingItemsTopEdge) {
924
925 YOverlappingItemsTopEdge y_item_span_top_edge = (YOverlappingItemsTopEdge)item_span;
926
927 top_edge_list.add(y_item_span_top_edge);
928 }
929 }
930
931 }
932
933 return top_edge_list;
934 }
935
936
937 protected boolean multipleYSpanOverlap(XItem xitem)
938 {
939 return calcYSpanOverlap(xitem).size() > 0;
940 }
941
942 public void mapInItem(XItem xitem)
943 {
944
945 int yt = autocropToTop(xitem);
946 int yb = autocropToBot(xitem);
947 /*
948 int yt = xitem.getBoundingYTop();
949 int yb = xitem.getBoundingYBot();
950
951 // top-edge over-spill can occur (and is acceptable) when (for example) the given xitem is a raw-text item
952 // that doesn't neatly fit in an enclosed area (i,e., is poking out the top of an enclosing rectangle)
953 yt = cropToTop(yt); // Only changes yt if in an over-spill situation
954
955 // similarly, bottom-edge over-spill can occur (and is acceptable) with a less than precise placed raw-text item
956 yb = cropToBot(yb); // Only changes yb if in an over-spill situation
957 */
958
959 // Merge into 'items_span' checking for overlaps (based on xitem's y-span)
960
961 boolean merged_item = false;
962 for (int y=yt; y<=yb; y++) {
963
964 YOverlappingItemsSpan item_span = getYOverlappingItemsSpan(y);
965
966 if (item_span != null) {
967
968 if (item_span instanceof YOverlappingItemsTopEdge) {
969
970 // Hit a top edge of an existing item
971
972 // Need to:
973 // 1. *Required* Insert new item into current x-ordered line
974 // 2. *Conditionally* Move entire x-ordered line up to higher 'y' top edge
975 // 3. *Required* Cast shadow for new item
976
977 // Note for Step 2:
978 // i) No need to do the move if y == yt
979 // (the case when the new top edge is exactly the same height as the existing one)
980 // ii) If moving top-edge (the case when y > yt) then no need to recalculate the top edge for existing shadows, as
981 // this 'connection' is stored as a reference
982
983
984 // Step 1: insert into existing top-edge
985
986 YOverlappingItemsTopEdge y_item_span_top_edge = (YOverlappingItemsTopEdge)item_span;
987 XOrderedLine xitem_span = y_item_span_top_edge.getXOrderedLine();
988
989 xitem_span.orderedMergeItem(xitem.getBoundingXLeft(),xitem);
990
991 // Step 2: if our new top-edge is higher than the existing one, then need to move existing top-edge
992 if (y>yt) {
993
994 // Move to new position
995 setYOverlappingItemsSpan(yt, y_item_span_top_edge);
996
997 // Old position needs to become a shadow reference
998 YOverlappingItemsShadow y_span_shadow = new YOverlappingItemsShadow(y_item_span_top_edge);
999 setYOverlappingItemsSpan(y,y_span_shadow);
1000 }
1001
1002
1003 // Step 3: Cast shadow
1004 castShadow(y_item_span_top_edge, yt+1, yb);
1005
1006 }
1007 else {
1008 // Top edge to our new item has hit a shadow entry (straight off)
1009 // => Look up what the shadow references, and then add in to that
1010
1011 // Effectively after the shadow reference lookup this is the same
1012 // as the above, without the need to worry about Step 2 (as no move is needed)
1013
1014 YOverlappingItemsShadow y_item_span_shadow = (YOverlappingItemsShadow)item_span;
1015 YOverlappingItemsTopEdge y_item_span_top_edge = y_item_span_shadow.getTopEdge();
1016
1017 XOrderedLine xitem_span = y_item_span_top_edge.getXOrderedLine();
1018
1019 // merge with this item list, preserving x ordering
1020 xitem_span.orderedMergeItem(xitem.getBoundingXLeft(),xitem);
1021
1022 // Now Cast shadow
1023 castShadow(y_item_span_top_edge, yt+1, yb);
1024 }
1025
1026 merged_item = true;
1027 break;
1028
1029 }
1030
1031 }
1032
1033 // Having checked all the y-location's ('yt' to 'yb') of this x-item, if all y-span entries were found to be null
1034 // => 'merged_item' is still false
1035
1036 if (!merged_item) {
1037 // xitem didn't intersect with any existing y-spans
1038 // => simple case for add (i.e. all entries affected by map are currently null)
1039
1040 // Start up a new x-ordered-line (consisting of only 'xitem'), add in top edge and cast shadow
1041
1042 XOrderedLine xitem_line = new XOrderedLine(xitem);
1043
1044 YOverlappingItemsTopEdge y_item_span_top_edge = new YOverlappingItemsTopEdge(xitem_line);
1045
1046 setYOverlappingItemsSpan(yt,y_item_span_top_edge);
1047
1048 castShadowIntoEmptySpace(y_item_span_top_edge, yt+1, yb);
1049 }
1050
1051
1052 }
1053
1054 private ArrayList<DimensionExtent> calcXGroupXGaps(XGroupItem xgroup_pivot_item, List<XGroupItem> xgroup_item_list)
1055 {
1056 // 'xgroup_pivot_item' current not used!!
1057
1058 int enclosing_xl = getBoundingXLeft();
1059 int enclosing_xr = getBoundingXRight();
1060
1061 int enclosing_x_dim = enclosing_xr - enclosing_xl +1;
1062 boolean is_x_shadow[] = new boolean[enclosing_x_dim]; // defaults all values to false
1063
1064 ArrayList<DimensionExtent> x_gap_list = new ArrayList<DimensionExtent>();
1065
1066 for (XGroupItem xgroup_item: xgroup_item_list) {
1067 int xl = xgroup_item.getBoundingXLeft();
1068 int xr = xgroup_item.getBoundingXRight();
1069
1070 for (int x=xl; x<=xr; x++) {
1071 int x_offset = x - enclosing_xl;
1072 is_x_shadow[x_offset] = true;
1073 }
1074 }
1075
1076 // New find where the contiguous runs of 'false' are, as they point to the gaps
1077
1078 int x = 1;
1079 int start_x_gap = enclosing_xl;
1080 boolean in_gap = true;
1081
1082 while (x < is_x_shadow.length) {
1083 boolean prev_is_shadow = is_x_shadow[x-1];
1084 boolean this_is_shadow = is_x_shadow[x];
1085
1086 if (prev_is_shadow && !this_is_shadow) {
1087 // reached end of shadow, record start of a gap
1088 start_x_gap = enclosing_xl + x;
1089 in_gap = true;
1090 }
1091 else if (!prev_is_shadow && this_is_shadow) {
1092 // reached the end of a gap, record it
1093 int end_x_gap = enclosing_xl + x -1;
1094 DimensionExtent de = new DimensionExtent(start_x_gap,end_x_gap);
1095 x_gap_list.add(de);
1096 in_gap = false;
1097 }
1098 x++;
1099 }
1100
1101 if (in_gap) {
1102 int end_x_gap = enclosing_xl + x -1;
1103 DimensionExtent de = new DimensionExtent(start_x_gap,end_x_gap);
1104 x_gap_list.add(de);
1105 }
1106
1107 return x_gap_list;
1108 }
1109
1110 protected void boxMultipleXRawItemsInGaps(XGroupItem xgroup_pivot_item, ArrayList<DimensionExtent> x_text_gap_list)
1111 {
1112 ArrayList<YOverlappingItemsTopEdge> y_span_overlap = calcYSpanOverlap(xgroup_pivot_item);
1113
1114 // work out where continuous runs of raw-text items intersect with the gaps occurring between boxed items
1115
1116 // foreach x-gap,
1117 // foreach y-span's list of x-sorted objects,
1118 // => see how many raw-text items fit into it
1119
1120
1121 ArrayList<ArrayList<XRawItem>> implicit_box_list = new ArrayList<ArrayList<XRawItem>>();
1122
1123 for (DimensionExtent de_gap: x_text_gap_list) {
1124
1125 int deg_xl = de_gap.min;
1126 int deg_xr = de_gap.max;
1127
1128 ArrayList<XRawItem> grouped_raw_text_list = new ArrayList<XRawItem>();
1129
1130 int y_span_line_count = 0;
1131
1132 for (YOverlappingItemsTopEdge y_top_edge: y_span_overlap) {
1133
1134 List<XItem> x_item_list = y_top_edge.x_items.getXItemList();
1135
1136 boolean used_x_raw_text = false;
1137
1138 for (XItem x_item: x_item_list) {
1139
1140 if (x_item instanceof XRawItem) {
1141 XRawItem x_raw_item = (XRawItem)x_item;
1142
1143 int xri_xl = x_raw_item.getBoundingXLeft();
1144 int xri_xr = x_raw_item.getBoundingXRight();
1145
1146 if ((xri_xl>=deg_xl) && (xri_xr<=deg_xr)) {
1147 grouped_raw_text_list.add(x_raw_item);
1148 used_x_raw_text = true;
1149 }
1150 }
1151 }
1152
1153 if (used_x_raw_text) {
1154 y_span_line_count++;
1155 }
1156 }
1157
1158 // Only interested in implicitly boxing if the formed group is used over 2 or more y-span lines
1159 if (y_span_line_count>=2) {
1160 implicit_box_list.add(grouped_raw_text_list);
1161 }
1162 }
1163
1164 //System.err.println("*** Number of implicit groups found: " + implicit_box_list.size());
1165
1166 for (ArrayList<XRawItem> implicit_x_item_list : implicit_box_list) {
1167
1168 for (YOverlappingItemsTopEdge y_top_edge: y_span_overlap) {
1169
1170 List<XItem> yspan_x_item_list = y_top_edge.x_items.getXItemList();
1171
1172 // Remove all the XRawItems from the current y-span
1173 yspan_x_item_list.removeAll(implicit_x_item_list);
1174
1175 }
1176
1177 // Create a list of original Text items
1178 // (OK that they are not y-ordered)
1179 ArrayList<Item> implicit_item_list= new ArrayList<Item>();
1180 for (XRawItem x_raw_item: implicit_x_item_list) {
1181 Item item = (Text) x_raw_item.item;
1182 implicit_item_list.add(item);
1183 }
1184
1185 // Now insert them as their own boxed up items
1186 XGroupItem implicit_xgroup = new XGroupItem(frame,implicit_item_list);
1187 this.mapInItem(implicit_xgroup);
1188 }
1189
1190 }
1191
1192 protected void implicitBoxing(XGroupItem xgroup_pivot_item,List<XGroupItem> xgroup_item_list) {
1193
1194 // Implicit boxing is needed if there are two or more raw-text items
1195 // that overlap in y-span-map of the given xgroup_item
1196
1197 // First establish if there is any kind of multiple overlap
1198 if (multipleYSpanOverlap(xgroup_pivot_item)) {
1199
1200 // Overlap could be with other boxed items, so need to investigate further
1201
1202 // Do this by working out if there are any raw-text items lurking between the pivot xgroup_item
1203 // and the list of other xgroup_items
1204
1205 // Step 1: Get list intersection (y-dim) of this group item, with any
1206 // other group items in xgroup_item_list
1207 ArrayList<XGroupItem> y_overlapping_xgroup_item_list = calcXGroupYExtentIntersection(xgroup_pivot_item,xgroup_item_list);
1208
1209 // Step 2: Work out where the gaps are between the y-overlapping boxes in the x-dimension
1210 ArrayList<DimensionExtent> x_text_gap_list = calcXGroupXGaps(xgroup_pivot_item,y_overlapping_xgroup_item_list);
1211
1212 // Step 3: Remove any sequences of raw-text items that fall in the gaps from YSpan, box them up, and reinsert
1213 boxMultipleXRawItemsInGaps(xgroup_pivot_item,x_text_gap_list);
1214
1215 }
1216 }
1217
1218
1219
1220 public void mapInXGroupItemsRecursive(List<XGroupItem> xgroup_item_list)
1221 {
1222
1223 // Map in all the items in the given list:
1224 for (XGroupItem xgroup_item: xgroup_item_list) {
1225 if (!xgroup_item.isOriginalOutOfFlowItem()) {
1226
1227 // See if any implicit boxing of raw-text items is needed
1228 if (doImplicitBoxing) {
1229 implicitBoxing(xgroup_item,xgroup_item_list);
1230 }
1231 mapInItem(xgroup_item); // Map in this x-group-item
1232 }
1233 }
1234
1235 // Now recursively work through each item's nested x-groups
1236 for (XGroupItem xgroup_item: xgroup_item_list) {
1237
1238 List<XGroupItem> nested_xgroup_item_list = xgroup_item.getGroupedItemList();
1239
1240 if (nested_xgroup_item_list.size() >0) {
1241 xgroup_item.mapInXGroupItemsRecursive(nested_xgroup_item_list);
1242 }
1243 }
1244 }
1245
1246 public List<Item[]> getYXOverlappingItemListLines() {
1247 final List<XRawItem> yxOverlappingXRawItemList = getYXOverlappingXRawItemList(true);
1248 final List<Item[]> lines = new ArrayList<Item[]>();
1249 final List<XRawItem> currentLineXItem = new ArrayList<XRawItem>();
1250 for(final XRawItem xitem : yxOverlappingXRawItemList) {
1251 if(xitem.getItem() == GROUPSEP_START) continue;
1252 else if(xitem.getItem() == GROUPSEP_END) {
1253 if(currentLineXItem.isEmpty()) continue;
1254 else {
1255 final List<Item> ln = new ArrayList<Item>();
1256 for(final XRawItem xrawitem : currentLineXItem) ln.add(xrawitem.getItem());
1257 lines.add(ln.toArray(new Item[]{}));
1258 currentLineXItem.clear();
1259 }
1260 } else {
1261 if(currentLineXItem.isEmpty()) currentLineXItem.add(xitem);
1262 else {
1263 final YOverlappingItemsSpan[] itemSpanArray = xitem.getGroup().yitems_span_array;
1264 final int index = xitem.getBoundingYTop() - xitem.getGroup().getBoundingYTop();
1265 final YOverlappingItemsSpan itemSpan = itemSpanArray[index];
1266 final List<XItem> xOrderedList = itemSpan instanceof YOverlappingItemsTopEdge ?
1267 ((YOverlappingItemsTopEdge)itemSpan).getXOrderedLine().getXItemList() :
1268 ((YOverlappingItemsShadow)itemSpan).getTopEdge().getXOrderedLine().getXItemList();
1269 if(!xOrderedList.contains(currentLineXItem.get(0))) {
1270 if(!currentLineXItem.isEmpty()) {
1271 final List<Item> ln = new ArrayList<Item>();
1272 for(final XRawItem xrawitem : currentLineXItem) ln.add(xrawitem.getItem());
1273 lines.add(ln.toArray(new Item[]{}));
1274 currentLineXItem.clear();
1275 }
1276 currentLineXItem.add(xitem);
1277 } else {
1278 currentLineXItem.add(xitem);
1279 }
1280 }
1281 }
1282 }
1283 if(!currentLineXItem.isEmpty()) {
1284 final List<Item> ln = new ArrayList<Item>();
1285 for(final XRawItem xrawitem : currentLineXItem) ln.add(xrawitem.getItem());
1286 lines.add(ln.toArray(new Item[]{}));
1287 currentLineXItem.clear();
1288 }
1289 return lines;
1290 }
1291
1292 public ArrayList<Item> getYXOverlappingItemList(boolean separateGroups) {
1293 final List<XRawItem> yxOverlappingXItemList = getYXOverlappingXRawItemList(separateGroups);
1294 final ArrayList<Item> yxOverlappingItemList = new ArrayList<Item>();
1295 for(final XRawItem xitem : yxOverlappingXItemList) yxOverlappingItemList.add(xitem.getItem());
1296 return yxOverlappingItemList;
1297 }
1298
1299 public List<XRawItem> getYXOverlappingXRawItemList(final boolean separateGroups) {
1300 ArrayList<XRawItem> overlapping_y_ordered_items = new ArrayList<XRawItem>();
1301
1302 for (int y = 0; y < y_span_height; y++) {
1303
1304 YOverlappingItemsSpan item_span = yitems_span_array[y];
1305
1306 if (item_span != null) {
1307
1308 if (item_span instanceof YOverlappingItemsTopEdge) {
1309
1310 YOverlappingItemsTopEdge item_span_top_edge = (YOverlappingItemsTopEdge) item_span;
1311 XOrderedLine xitem_line = item_span_top_edge
1312 .getXOrderedLine();
1313
1314 for (XItem xspan : xitem_line.getXItemList()) {
1315 if (xspan instanceof XRawItem) {
1316 XRawItem xitem_span = (XRawItem) xspan;
1317// Item item = xitem_span.getItem();
1318//
1319// overlapping_y_ordered_items.add(item);
1320 overlapping_y_ordered_items.add(xitem_span);
1321 } else {
1322 // Must be an XGroupItem => recursive call on xspan
1323 // item
1324
1325 XGroupItem nested_group_item = (XGroupItem) xspan;
1326 List<XRawItem> nested_overlapping_items = nested_group_item
1327 .getYXOverlappingXRawItemList(separateGroups);
1328 if (separateGroups) {
1329 overlapping_y_ordered_items.add(new XRawItem(GROUPSEP_START, this));
1330 }
1331 overlapping_y_ordered_items
1332 .addAll(nested_overlapping_items);
1333 if (separateGroups) {
1334 overlapping_y_ordered_items.add(new XRawItem(GROUPSEP_END, this));
1335 }
1336 }
1337 }
1338 }
1339 }
1340 }
1341
1342 return overlapping_y_ordered_items;
1343 }
1344
1345 public ArrayList<Item> getYXOverlappingItemList() {
1346 return getYXOverlappingItemList(false);
1347 }
1348
1349 public String toString() {
1350 return "XGroupItem";
1351 }
1352}
1353
Note: See TracBrowser for help on using the repository browser.