001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.gui.dialogs.relation;
003    
004    import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.BACKWARD;
005    import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.FORWARD;
006    import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.NONE;
007    import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.ROUNDABOUT_LEFT;
008    import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.ROUNDABOUT_RIGHT;
009    
010    import java.util.ArrayList;
011    import java.util.Arrays;
012    import java.util.Collection;
013    import java.util.Collections;
014    import java.util.Comparator;
015    import java.util.HashMap;
016    import java.util.HashSet;
017    import java.util.Iterator;
018    import java.util.LinkedList;
019    import java.util.List;
020    import java.util.Map;
021    import java.util.Set;
022    import java.util.concurrent.CopyOnWriteArrayList;
023    
024    import javax.swing.DefaultListSelectionModel;
025    import javax.swing.ListSelectionModel;
026    import javax.swing.event.TableModelEvent;
027    import javax.swing.event.TableModelListener;
028    import javax.swing.table.AbstractTableModel;
029    
030    import org.openstreetmap.josm.Main;
031    import org.openstreetmap.josm.data.SelectionChangedListener;
032    import org.openstreetmap.josm.data.coor.EastNorth;
033    import org.openstreetmap.josm.data.osm.DataSet;
034    import org.openstreetmap.josm.data.osm.Node;
035    import org.openstreetmap.josm.data.osm.OsmPrimitive;
036    import org.openstreetmap.josm.data.osm.Relation;
037    import org.openstreetmap.josm.data.osm.RelationMember;
038    import org.openstreetmap.josm.data.osm.Way;
039    import org.openstreetmap.josm.data.osm.event.AbstractDatasetChangedEvent;
040    import org.openstreetmap.josm.data.osm.event.DataChangedEvent;
041    import org.openstreetmap.josm.data.osm.event.DataSetListener;
042    import org.openstreetmap.josm.data.osm.event.NodeMovedEvent;
043    import org.openstreetmap.josm.data.osm.event.PrimitivesAddedEvent;
044    import org.openstreetmap.josm.data.osm.event.PrimitivesRemovedEvent;
045    import org.openstreetmap.josm.data.osm.event.RelationMembersChangedEvent;
046    import org.openstreetmap.josm.data.osm.event.TagsChangedEvent;
047    import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
048    import org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction;
049    import org.openstreetmap.josm.gui.layer.OsmDataLayer;
050    import org.openstreetmap.josm.gui.widgets.OsmPrimitivesTableModel;
051    
052    public class MemberTableModel extends AbstractTableModel implements TableModelListener, SelectionChangedListener, DataSetListener, OsmPrimitivesTableModel {
053    
054        /**
055         * data of the table model: The list of members and the cached WayConnectionType of each member.
056         **/
057        private List<RelationMember> members;
058        private List<WayConnectionType> connectionType = null;
059    
060        private DefaultListSelectionModel listSelectionModel;
061        private CopyOnWriteArrayList<IMemberModelListener> listeners;
062        private OsmDataLayer layer;
063    
064        private final int UNCONNECTED = Integer.MIN_VALUE;
065        
066        private static final Collection<AdditionalSorter> additionalSorters = new ArrayList<AdditionalSorter>();
067        
068        static {
069            additionalSorters.add(new AssociatedStreetSorter());
070        }
071    
072        /**
073         * constructor
074         */
075        public MemberTableModel(OsmDataLayer layer) {
076            members = new ArrayList<RelationMember>();
077            listeners = new CopyOnWriteArrayList<IMemberModelListener>();
078            this.layer = layer;
079            addTableModelListener(this);
080        }
081    
082        public OsmDataLayer getLayer() {
083            return layer;
084        }
085    
086        public void register() {
087            DataSet.addSelectionListener(this);
088            getLayer().data.addDataSetListener(this);
089        }
090    
091        public void unregister() {
092            DataSet.removeSelectionListener(this);
093            getLayer().data.removeDataSetListener(this);
094        }
095    
096        /* --------------------------------------------------------------------------- */
097        /* Interface SelectionChangedListener                                          */
098        /* --------------------------------------------------------------------------- */
099        public void selectionChanged(Collection<? extends OsmPrimitive> newSelection) {
100            if (Main.main.getEditLayer() != this.layer) return;
101            // just trigger a repaint
102            Collection<RelationMember> sel = getSelectedMembers();
103            fireTableDataChanged();
104            setSelectedMembers(sel);
105        }
106    
107        /* --------------------------------------------------------------------------- */
108        /* Interface DataSetListener                                                   */
109        /* --------------------------------------------------------------------------- */
110        public void dataChanged(DataChangedEvent event) {
111            // just trigger a repaint - the display name of the relation members may
112            // have changed
113            Collection<RelationMember> sel = getSelectedMembers();
114            fireTableDataChanged();
115            setSelectedMembers(sel);
116        }
117    
118        public void nodeMoved(NodeMovedEvent event) {/* ignore */}
119        public void primitivesAdded(PrimitivesAddedEvent event) {/* ignore */}
120    
121        public void primitivesRemoved(PrimitivesRemovedEvent event) {
122            // ignore - the relation in the editor might become out of sync with the relation
123            // in the dataset. We will deal with it when the relation editor is closed or
124            // when the changes in the editor are applied.
125        }
126    
127        public void relationMembersChanged(RelationMembersChangedEvent event) {
128            // ignore - the relation in the editor might become out of sync with the relation
129            // in the dataset. We will deal with it when the relation editor is closed or
130            // when the changes in the editor are applied.
131        }
132    
133        public void tagsChanged(TagsChangedEvent event) {
134            // just refresh the respective table cells
135            //
136            Collection<RelationMember> sel = getSelectedMembers();
137            for (int i=0; i < members.size();i++) {
138                if (members.get(i).getMember() == event.getPrimitive()) {
139                    fireTableCellUpdated(i, 1 /* the column with the primitive name */);
140                }
141            }
142            setSelectedMembers(sel);
143        }
144    
145        public void wayNodesChanged(WayNodesChangedEvent event) {/* ignore */}
146    
147        public void otherDatasetChange(AbstractDatasetChangedEvent event) {/* ignore */}
148        /* --------------------------------------------------------------------------- */
149    
150        public void addMemberModelListener(IMemberModelListener listener) {
151            if (listener != null) {
152                listeners.addIfAbsent(listener);
153            }
154        }
155    
156        public void removeMemberModelListener(IMemberModelListener listener) {
157            listeners.remove(listener);
158        }
159    
160        protected void fireMakeMemberVisible(int index) {
161            for (IMemberModelListener listener : listeners) {
162                listener.makeMemberVisible(index);
163            }
164        }
165    
166        public void populate(Relation relation) {
167            members.clear();
168            if (relation != null) {
169                // make sure we work with clones of the relation members
170                // in the model.
171                members.addAll(new Relation(relation).getMembers());
172            }
173            fireTableDataChanged();
174        }
175    
176        public int getColumnCount() {
177            return 3;
178        }
179    
180        public int getRowCount() {
181            return members.size();
182        }
183    
184        public Object getValueAt(int rowIndex, int columnIndex) {
185            switch (columnIndex) {
186            case 0:
187                return members.get(rowIndex).getRole();
188            case 1:
189                return members.get(rowIndex).getMember();
190            case 2:
191                return getWayConnection(rowIndex);
192            }
193            // should not happen
194            return null;
195        }
196    
197        @Override
198        public boolean isCellEditable(int rowIndex, int columnIndex) {
199            return columnIndex == 0;
200        }
201    
202        @Override
203        public void setValueAt(Object value, int rowIndex, int columnIndex) {
204            RelationMember member = members.get(rowIndex);
205            RelationMember newMember = new RelationMember(value.toString(), member.getMember());
206            members.remove(rowIndex);
207            members.add(rowIndex, newMember);
208        }
209    
210        @Override
211        public OsmPrimitive getReferredPrimitive(int idx) {
212            return members.get(idx).getMember();
213        }
214    
215        public void moveUp(int[] selectedRows) {
216            if (!canMoveUp(selectedRows))
217                return;
218    
219            for (int row : selectedRows) {
220                RelationMember member1 = members.get(row);
221                RelationMember member2 = members.get(row - 1);
222                members.set(row, member2);
223                members.set(row - 1, member1);
224            }
225            fireTableDataChanged();
226            getSelectionModel().setValueIsAdjusting(true);
227            getSelectionModel().clearSelection();
228            for (int row : selectedRows) {
229                row--;
230                getSelectionModel().addSelectionInterval(row, row);
231            }
232            getSelectionModel().setValueIsAdjusting(false);
233            fireMakeMemberVisible(selectedRows[0] - 1);
234        }
235    
236        public void moveDown(int[] selectedRows) {
237            if (!canMoveDown(selectedRows))
238                return;
239    
240            for (int i = selectedRows.length - 1; i >= 0; i--) {
241                int row = selectedRows[i];
242                RelationMember member1 = members.get(row);
243                RelationMember member2 = members.get(row + 1);
244                members.set(row, member2);
245                members.set(row + 1, member1);
246            }
247            fireTableDataChanged();
248            getSelectionModel();
249            getSelectionModel().setValueIsAdjusting(true);
250            getSelectionModel().clearSelection();
251            for (int row : selectedRows) {
252                row++;
253                getSelectionModel().addSelectionInterval(row, row);
254            }
255            getSelectionModel().setValueIsAdjusting(false);
256            fireMakeMemberVisible(selectedRows[0] + 1);
257        }
258    
259        public void remove(int[] selectedRows) {
260            if (!canRemove(selectedRows))
261                return;
262            int offset = 0;
263            for (int row : selectedRows) {
264                row -= offset;
265                if (members.size() > row) {
266                    members.remove(row);
267                    offset++;
268                }
269            }
270            fireTableDataChanged();
271        }
272    
273        public boolean canMoveUp(int[] rows) {
274            if (rows == null || rows.length == 0)
275                return false;
276            Arrays.sort(rows);
277            return rows[0] > 0 && members.size() > 0;
278        }
279    
280        public boolean canMoveDown(int[] rows) {
281            if (rows == null || rows.length == 0)
282                return false;
283            Arrays.sort(rows);
284            return members.size() > 0 && rows[rows.length - 1] < members.size() - 1;
285        }
286    
287        public boolean canRemove(int[] rows) {
288            if (rows == null || rows.length == 0)
289                return false;
290            return true;
291        }
292    
293        public DefaultListSelectionModel getSelectionModel() {
294            if (listSelectionModel == null) {
295                listSelectionModel = new DefaultListSelectionModel();
296                listSelectionModel.setSelectionMode(ListSelectionModel.MULTIPLE_INTERVAL_SELECTION);
297            }
298            return listSelectionModel;
299        }
300    
301        public void removeMembersReferringTo(List<? extends OsmPrimitive> primitives) {
302            if (primitives == null)
303                return;
304            Iterator<RelationMember> it = members.iterator();
305            while (it.hasNext()) {
306                RelationMember member = it.next();
307                if (primitives.contains(member.getMember())) {
308                    it.remove();
309                }
310            }
311            fireTableDataChanged();
312        }
313    
314        public void applyToRelation(Relation relation) {
315            relation.setMembers(members);
316        }
317    
318        public boolean hasSameMembersAs(Relation relation) {
319            if (relation == null)
320                return false;
321            if (relation.getMembersCount() != members.size())
322                return false;
323            for (int i = 0; i < relation.getMembersCount(); i++) {
324                if (!relation.getMember(i).equals(members.get(i)))
325                    return false;
326            }
327            return true;
328        }
329    
330        /**
331         * Replies the set of incomplete primitives
332         *
333         * @return the set of incomplete primitives
334         */
335        public Set<OsmPrimitive> getIncompleteMemberPrimitives() {
336            Set<OsmPrimitive> ret = new HashSet<OsmPrimitive>();
337            for (RelationMember member : members) {
338                if (member.getMember().isIncomplete()) {
339                    ret.add(member.getMember());
340                }
341            }
342            return ret;
343        }
344    
345        /**
346         * Replies the set of selected incomplete primitives
347         *
348         * @return the set of selected incomplete primitives
349         */
350        public Set<OsmPrimitive> getSelectedIncompleteMemberPrimitives() {
351            Set<OsmPrimitive> ret = new HashSet<OsmPrimitive>();
352            for (RelationMember member : getSelectedMembers()) {
353                if (member.getMember().isIncomplete()) {
354                    ret.add(member.getMember());
355                }
356            }
357            return ret;
358        }
359    
360        /**
361         * Replies true if at least one the relation members is incomplete
362         *
363         * @return true if at least one the relation members is incomplete
364         */
365        public boolean hasIncompleteMembers() {
366            for (RelationMember member : members) {
367                if (member.getMember().isIncomplete())
368                    return true;
369            }
370            return false;
371        }
372    
373        /**
374         * Replies true if at least one of the selected members is incomplete
375         *
376         * @return true if at least one of the selected members is incomplete
377         */
378        public boolean hasIncompleteSelectedMembers() {
379            for (RelationMember member : getSelectedMembers()) {
380                if (member.getMember().isIncomplete())
381                    return true;
382            }
383            return false;
384        }
385    
386        protected List<Integer> getSelectedIndices() {
387            ArrayList<Integer> selectedIndices = new ArrayList<Integer>();
388            for (int i = 0; i < members.size(); i++) {
389                if (getSelectionModel().isSelectedIndex(i)) {
390                    selectedIndices.add(i);
391                }
392            }
393            return selectedIndices;
394        }
395    
396        private void addMembersAtIndex(List<? extends OsmPrimitive> primitives, int index) {
397            if (primitives == null)
398                return;
399            int idx = index;
400            for (OsmPrimitive primitive : primitives) {
401                RelationMember member = new RelationMember("", primitive);
402                members.add(idx++, member);
403            }
404            fireTableDataChanged();
405            getSelectionModel().clearSelection();
406            getSelectionModel().addSelectionInterval(index, index + primitives.size() - 1);
407            fireMakeMemberVisible(index);
408        }
409    
410        public void addMembersAtBeginning(List<? extends OsmPrimitive> primitives) {
411            addMembersAtIndex(primitives, 0);
412        }
413    
414        public void addMembersAtEnd(List<? extends OsmPrimitive> primitives) {
415            addMembersAtIndex(primitives, members.size());
416        }
417    
418        public void addMembersBeforeIdx(List<? extends OsmPrimitive> primitives, int idx) {
419            addMembersAtIndex(primitives, idx);
420        }
421    
422        public void addMembersAfterIdx(List<? extends OsmPrimitive> primitives, int idx) {
423            addMembersAtIndex(primitives, idx + 1);
424        }
425    
426        /**
427         * Replies the number of members which refer to a particular primitive
428         *
429         * @param primitive the primitive
430         * @return the number of members which refer to a particular primitive
431         */
432        public int getNumMembersWithPrimitive(OsmPrimitive primitive) {
433            int count = 0;
434            for (RelationMember member : members) {
435                if (member.getMember().equals(primitive)) {
436                    count++;
437                }
438            }
439            return count;
440        }
441    
442        /**
443         * updates the role of the members given by the indices in <code>idx</code>
444         *
445         * @param idx the array of indices
446         * @param role the new role
447         */
448        public void updateRole(int[] idx, String role) {
449            if (idx == null || idx.length == 0)
450                return;
451            for (int row : idx) {
452                RelationMember oldMember = members.get(row);
453                RelationMember newMember = new RelationMember(role, oldMember.getMember());
454                members.remove(row);
455                members.add(row, newMember);
456            }
457            fireTableDataChanged();
458            for (int row : idx) {
459                getSelectionModel().addSelectionInterval(row, row);
460            }
461        }
462    
463        /**
464         * Get the currently selected relation members
465         *
466         * @return a collection with the currently selected relation members
467         */
468        public Collection<RelationMember> getSelectedMembers() {
469            ArrayList<RelationMember> selectedMembers = new ArrayList<RelationMember>();
470            for (int i : getSelectedIndices()) {
471                selectedMembers.add(members.get(i));
472            }
473            return selectedMembers;
474        }
475    
476        /**
477         * Replies the set of selected referers. Never null, but may be empty.
478         *
479         * @return the set of selected referers
480         */
481        public Collection<OsmPrimitive> getSelectedChildPrimitives() {
482            Collection<OsmPrimitive> ret = new ArrayList<OsmPrimitive>();
483            for (RelationMember m: getSelectedMembers()) {
484                ret.add(m.getMember());
485            }
486            return ret;
487        }
488    
489        /**
490         * Replies the set of selected referers. Never null, but may be empty.
491         *
492         * @return the set of selected referers
493         */
494        public Set<OsmPrimitive> getChildPrimitives(Collection<? extends OsmPrimitive> referenceSet) {
495            HashSet<OsmPrimitive> ret = new HashSet<OsmPrimitive>();
496            if (referenceSet == null) return null;
497            for (RelationMember m: members) {
498                if (referenceSet.contains(m.getMember())) {
499                    ret.add(m.getMember());
500                }
501            }
502            return ret;
503        }
504    
505        /**
506         * Selects the members in the collection selectedMembers
507         *
508         * @param selectedMembers the collection of selected members
509         */
510        public void setSelectedMembers(Collection<RelationMember> selectedMembers) {
511            if (selectedMembers == null || selectedMembers.isEmpty()) {
512                getSelectionModel().clearSelection();
513                return;
514            }
515    
516            // lookup the indices for the respective members
517            //
518            Set<Integer> selectedIndices = new HashSet<Integer>();
519            for (RelationMember member : selectedMembers) {
520                for (int idx = 0; idx < members.size(); ++idx) {
521                    if (member.equals(members.get(idx))) {
522                        selectedIndices.add(idx);
523                    }
524                }
525            }
526            setSelectedMembersIdx(selectedIndices);
527        }
528    
529        /**
530         * Selects the members in the collection selectedIndices
531         *
532         * @param selectedIndices the collection of selected member indices
533         */
534        public void setSelectedMembersIdx(Collection<Integer> selectedIndices) {
535            if (selectedIndices == null || selectedIndices.isEmpty()) {
536                getSelectionModel().clearSelection();
537                return;
538            }
539            // select the members
540            //
541            getSelectionModel().setValueIsAdjusting(true);
542            getSelectionModel().clearSelection();
543            for (int row : selectedIndices) {
544                getSelectionModel().addSelectionInterval(row, row);
545            }
546            getSelectionModel().setValueIsAdjusting(false);
547            // make the first selected member visible
548            //
549            if (selectedIndices.size() > 0) {
550                fireMakeMemberVisible(Collections.min(selectedIndices));
551            }
552        }
553    
554        /**
555         * Replies true if the index-th relation members referrs
556         * to an editable relation, i.e. a relation which is not
557         * incomplete.
558         *
559         * @param index the index
560         * @return true, if the index-th relation members referrs
561         * to an editable relation, i.e. a relation which is not
562         * incomplete
563         */
564        public boolean isEditableRelation(int index) {
565            if (index < 0 || index >= members.size())
566                return false;
567            RelationMember member = members.get(index);
568            if (!member.isRelation())
569                return false;
570            Relation r = member.getRelation();
571            return !r.isIncomplete();
572        }
573    
574        /**
575         * Replies true if there is at least one relation member given as {@code members}
576         * which refers to at least on the primitives in {@code primitives}.
577         *
578         * @param members the members
579         * @param primitives the collection of primitives
580         * @return true if there is at least one relation member in this model
581         * which refers to at least on the primitives in <code>primitives</code>; false
582         * otherwise
583         */
584        public static boolean hasMembersReferringTo(Collection<RelationMember> members, Collection<OsmPrimitive> primitives) {
585            if (primitives == null || primitives.isEmpty()) {
586                return false;
587            }
588            HashSet<OsmPrimitive> referrers = new HashSet<OsmPrimitive>();
589            for (RelationMember member : members) {
590                referrers.add(member.getMember());
591            }
592            for (OsmPrimitive referred : primitives) {
593                if (referrers.contains(referred)) {
594                    return true;
595                }
596            }
597            return false;
598        }
599    
600        /**
601         * Replies true if there is at least one relation member in this model
602         * which refers to at least on the primitives in <code>primitives</code>.
603         *
604         * @param primitives the collection of primitives
605         * @return true if there is at least one relation member in this model
606         * which refers to at least on the primitives in <code>primitives</code>; false
607         * otherwise
608         */
609        public boolean hasMembersReferringTo(Collection<OsmPrimitive> primitives) {
610            return hasMembersReferringTo(members, primitives);
611        }
612    
613        /**
614         * Selects all mebers which refer to {@link OsmPrimitive}s in the collections
615         * <code>primitmives</code>. Does nothing is primitives is null.
616         *
617         * @param primitives the collection of primitives
618         */
619        public void selectMembersReferringTo(Collection<? extends OsmPrimitive> primitives) {
620            if (primitives == null) return;
621            getSelectionModel().setValueIsAdjusting(true);
622            getSelectionModel().clearSelection();
623            for (int i=0; i< members.size();i++) {
624                RelationMember m = members.get(i);
625                if (primitives.contains(m.getMember())) {
626                    this.getSelectionModel().addSelectionInterval(i,i);
627                }
628            }
629            getSelectionModel().setValueIsAdjusting(false);
630            if (getSelectedIndices().size() > 0) {
631                fireMakeMemberVisible(getSelectedIndices().get(0));
632            }
633        }
634    
635        /**
636         * Replies true if <code>primitive</code> is currently selected in the layer this
637         * model is attached to
638         *
639         * @param primitive the primitive
640         * @return true if <code>primitive</code> is currently selected in the layer this
641         * model is attached to, false otherwise
642         */
643        public boolean isInJosmSelection(OsmPrimitive primitive) {
644            return layer.data.isSelected(primitive);
645        }
646    
647        /**
648         * Replies true if the layer this model belongs to is equal to the active
649         * layer
650         *
651         * @return true if the layer this model belongs to is equal to the active
652         * layer
653         */
654        protected boolean isActiveLayer() {
655            if (Main.map == null || Main.map.mapView == null) return false;
656            return Main.map.mapView.getActiveLayer() == layer;
657        }
658    
659        /**
660         * get a node we can link against when sorting members
661         * @param element the element we want to link against
662         * @param linked_element already linked against element
663         * @return the unlinked node if element is a way, the node itself if element is a node, null otherwise
664         */
665        /*private static Node getUnusedNode(RelationMember element, RelationMember linked_element)
666        {
667            Node result = null;
668    
669            if (element.isWay()) {
670                Way w = element.getWay();
671                if (linked_element.isWay()) {
672                    Way x = linked_element.getWay();
673                    if ((w.firstNode() == x.firstNode()) || (w.firstNode() == x.lastNode())) {
674                        result = w.lastNode();
675                    } else {
676                        result = w.firstNode();
677                    }
678                } else if (linked_element.isNode()) {
679                    Node m = linked_element.getNode();
680                    if (w.firstNode() == m) {
681                        result = w.lastNode();
682                    } else {
683                        result = w.firstNode();
684                    }
685                }
686            } else if (element.isNode()) {
687                Node n = element.getNode();
688                result = n;
689            }
690    
691            return result;
692        }*/
693    
694        /*
695         * Sort a collection of relation members by the way they are linked.
696         *
697         * @param relationMembers collection of relation members
698         * @return sorted collection of relation members
699         */
700        private List<RelationMember> sortMembers(List<RelationMember> relationMembers) {
701            RelationNodeMap map = new RelationNodeMap(relationMembers);
702            // List of groups of linked members
703            //
704            ArrayList<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>();
705    
706            // current group of members that are linked among each other
707            // Two successive members are always linked i.e. have a common node.
708            //
709            LinkedList<Integer> group;
710    
711            Integer first;
712            while ((first = map.pop()) != null) {
713                group = new LinkedList<Integer>();
714                group.add(first);
715    
716                allGroups.add(group);
717    
718                Integer next = first;
719                while ((next = map.popAdjacent(next)) != null) {
720                    group.addLast(next);
721                }
722    
723                // The first element need not be in front of the list.
724                // So the search goes in both directions
725                //
726                next = first;
727                while ((next = map.popAdjacent(next)) != null) {
728                    group.addFirst(next);
729                }
730            }
731    
732            ArrayList<RelationMember> newMembers = new ArrayList<RelationMember>();
733            for (LinkedList<Integer> tmpGroup : allGroups) {
734                for (Integer p : tmpGroup) {
735                    newMembers.add(relationMembers.get(p));
736                }
737            }
738    
739            // Try to sort remaining members with custom mechanisms (relation-dependent)
740            List<RelationMember> notSortableMembers = new LinkedList<RelationMember>();
741            Map<AdditionalSorter, List<RelationMember>> additionalMap = new HashMap<AdditionalSorter, List<RelationMember>>();
742    
743            // Dispatch members to correct sorters
744            for (Integer i : map.getNotSortableMembers()) {
745                RelationMember m = relationMembers.get(i);
746                for (AdditionalSorter sorter : additionalSorters) {
747                    List<RelationMember> list = notSortableMembers;
748                    if (sorter.acceptsMember(m)) {
749                        list = additionalMap.get(sorter);
750                        if (list == null) {
751                            additionalMap.put(sorter, list = new LinkedList<RelationMember>()); 
752                        }
753                    }
754                    list.add(m);
755                }
756            }
757            
758            // Sort members and add them to result
759            for (AdditionalSorter s : additionalMap.keySet()) {
760                newMembers.addAll(s.sortMembers(additionalMap.get(s)));
761            }
762            
763            // Finally, add members that have not been sorted at all
764            newMembers.addAll(notSortableMembers);
765            
766            return newMembers;
767        }
768    
769        /**
770         * Sort the selected relation members by the way they are linked.
771         */
772        void sort() {
773            List<RelationMember> selectedMembers = new ArrayList<RelationMember>(getSelectedMembers());
774            List<RelationMember> sortedMembers = null;
775            List<RelationMember> newMembers;
776            if (selectedMembers.size() <= 1) {
777                newMembers = sortMembers(members);
778                sortedMembers = newMembers;
779            } else {
780                sortedMembers = sortMembers(selectedMembers);
781                List<Integer> selectedIndices = getSelectedIndices();
782                newMembers = new ArrayList<RelationMember>();
783                boolean inserted = false;
784                for (int i=0; i < members.size(); i++) {
785                    if (selectedIndices.contains(i)) {
786                        if (!inserted) {
787                            newMembers.addAll(sortedMembers);
788                            inserted = true;
789                        }
790                    } else {
791                        newMembers.add(members.get(i));
792                    }
793                }
794            }
795    
796            if (members.size() != newMembers.size()) throw new AssertionError();
797    
798            members.clear();
799            members.addAll(newMembers);
800            fireTableDataChanged();
801            setSelectedMembers(sortedMembers);
802        }
803    
804        private Direction determineDirection(int ref_i, Direction ref_direction, int k) {
805            return determineDirection(ref_i, ref_direction, k, false);
806        }
807        /**
808         * Determines the direction of way k with respect to the way ref_i.
809         * The way ref_i is assumed to have the direction ref_direction and
810         * to be the predecessor of k.
811         *
812         * If both ways are not linked in any way, NONE is returned.
813         *
814         * Else the direction is given as follows:
815         * Let the relation be a route of oneway streets, and someone travels them in the given order.
816         * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way.
817         *
818         **/
819        private Direction determineDirection(int ref_i, final Direction ref_direction, int k, boolean reversed) {
820            if (ref_i < 0 || k < 0 || ref_i >= members.size() || k >= members.size())
821                return NONE;
822            if (ref_direction == NONE)
823                return NONE;
824    
825            final RelationMember m_ref = members.get(ref_i);
826            final RelationMember m = members.get(k);
827            Way way_ref = null;
828            Way way = null;
829    
830            if (m_ref.isWay()) {
831                way_ref = m_ref.getWay();
832            }
833            if (m.isWay()) {
834                way = m.getWay();
835            }
836    
837            if (way_ref == null || way == null)
838                return NONE;
839    
840            /** the list of nodes the way k can dock to */
841            List<Node> refNodes= new ArrayList<Node>();
842    
843            switch (ref_direction) {
844            case FORWARD:
845                refNodes.add(way_ref.lastNode());
846                break;
847            case BACKWARD:
848                refNodes.add(way_ref.firstNode());
849                break;
850            case ROUNDABOUT_LEFT:
851            case ROUNDABOUT_RIGHT:
852                refNodes = way_ref.getNodes();
853                break;
854            }
855    
856            if (refNodes == null)
857                return NONE;
858    
859            for (Node n : refNodes) {
860                if (n == null) {
861                    continue;
862                }
863                if (roundaboutType(k) != NONE) {
864                    for (Node nn : way.getNodes()) {
865                        if (n == nn)
866                            return roundaboutType(k);
867                    }
868                } else if(isOneway(m)) {
869                    if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
870                        if(isBackward(m))
871                            return BACKWARD;
872                        else
873                            return FORWARD;
874                    }
875                    if (n == RelationNodeMap.lastOnewayNode(m) && reversed) {
876                        if(isBackward(m))
877                            return FORWARD;
878                        else
879                            return BACKWARD;
880                    }
881                } else {
882                    if (n == way.firstNode())
883                        return FORWARD;
884                    if (n == way.lastNode())
885                        return BACKWARD;
886                }
887            }
888            return NONE;
889        }
890    
891        /**
892         * determine, if the way i is a roundabout and if yes, what type of roundabout
893         */
894        private Direction roundaboutType(int i) {
895            RelationMember m = members.get(i);
896            if (m == null || !m.isWay()) return NONE;
897            Way w = m.getWay();
898            return roundaboutType(w);
899        }
900        static Direction roundaboutType(Way w) {
901            if (w != null &&
902                    "roundabout".equals(w.get("junction")) &&
903                    w.getNodesCount() < 200 &&
904                    w.getNodesCount() > 2 &&
905                    w.getNode(0) != null &&
906                    w.getNode(1) != null &&
907                    w.getNode(2) != null &&
908                    w.firstNode() == w.lastNode()) {
909                /** do some simple determinant / cross pruduct test on the first 3 nodes
910                    to see, if the roundabout goes clock wise or ccw */
911                EastNorth en1 = w.getNode(0).getEastNorth();
912                EastNorth en2 = w.getNode(1).getEastNorth();
913                EastNorth en3 = w.getNode(2).getEastNorth();
914                if (en1 != null && en2 != null && en3 != null) {
915                    en1 = en1.sub(en2);
916                    en2 = en2.sub(en3);
917                    return en1.north() * en2.east() - en2.north() * en1.east() > 0 ? ROUNDABOUT_LEFT : ROUNDABOUT_RIGHT;
918                }
919            }
920            return NONE;
921        }
922    
923        WayConnectionType getWayConnection(int i) {
924            if (connectionType == null) {
925                updateLinks();
926            }
927            return connectionType.get(i);
928        }
929    
930        public void tableChanged(TableModelEvent e) {
931            connectionType = null;
932        }
933    
934        /**
935         * Reverse the relation members.
936         */
937        void reverse() {
938            List<Integer> selectedIndices = getSelectedIndices();
939            List<Integer> selectedIndicesReversed = getSelectedIndices();
940    
941            if (selectedIndices.size() <= 1) {
942                Collections.reverse(members);
943                fireTableDataChanged();
944                setSelectedMembers(members);
945            } else {
946                Collections.reverse(selectedIndicesReversed);
947    
948                ArrayList<RelationMember> newMembers = new ArrayList<RelationMember>(members);
949    
950                for (int i=0; i < selectedIndices.size(); i++) {
951                    newMembers.set(selectedIndices.get(i), members.get(selectedIndicesReversed.get(i)));
952                }
953    
954                if (members.size() != newMembers.size()) throw new AssertionError();
955                members.clear();
956                members.addAll(newMembers);
957                fireTableDataChanged();
958                setSelectedMembersIdx(selectedIndices);
959            }
960        }
961    
962        /**
963         * refresh the cache of member WayConnectionTypes
964         */
965        public void updateLinks() {
966            connectionType = null;
967            final List<WayConnectionType> con = new ArrayList<WayConnectionType>();
968    
969            for (int i=0; i<members.size(); ++i) {
970                con.add(null);
971            }
972    
973            firstGroupIdx=0;
974    
975            lastForwardWay = UNCONNECTED;
976            lastBackwardWay = UNCONNECTED;
977            onewayBeginning = false;
978            WayConnectionType lastWct = null;
979    
980            for (int i=0; i<members.size(); ++i) {
981                final RelationMember m = members.get(i);
982                if (!m.isWay() || m.getWay() == null || m.getWay().isIncomplete()) {
983                    if(i > 0) {
984                        makeLoopIfNeeded(con, i-1);
985                    }
986                    con.set(i, new WayConnectionType());
987                    firstGroupIdx = i;
988                    continue;
989                }
990    
991                WayConnectionType wct = new WayConnectionType(false);
992                wct.linkPrev = i>0 && con.get(i-1) != null && con.get(i-1).isValid();
993                wct.direction = NONE;
994    
995                if(isOneway(m)){
996                    if(lastWct != null && lastWct.isOnewayTail) {
997                        wct.isOnewayHead = true;
998                    }
999                    if(lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED){ //Beginning of new oneway
1000                        wct.isOnewayHead = true;
1001                        lastForwardWay = i-1;
1002                        lastBackwardWay = i-1;
1003                        onewayBeginning = true;
1004                    }
1005                }
1006    
1007                if (wct.linkPrev) {
1008                    if(lastBackwardWay != UNCONNECTED && lastForwardWay != UNCONNECTED) {
1009                        wct = determineOnewayConnectionType(con, m, i, wct);
1010                        if(!wct.linkPrev) {
1011                            firstGroupIdx = i;
1012                        }
1013                    }
1014    
1015                    if(!isOneway(m)) {
1016                        wct.direction = determineDirection(i-1, lastWct.direction, i);
1017                        wct.linkPrev = (wct.direction != NONE);
1018                    }
1019                }
1020    
1021                if (!wct.linkPrev) {
1022                    wct.direction = determineDirectionOfFirst(i, m);
1023                    if(isOneway(m)){
1024                        wct.isOnewayLoopForwardPart = true;
1025                        lastForwardWay = i;
1026                    }
1027                }
1028    
1029                wct.linkNext = false;
1030                if(lastWct != null) {
1031                    lastWct.linkNext = wct.linkPrev;
1032                }
1033                con.set(i, wct);
1034                lastWct = wct;
1035    
1036                if(!wct.linkPrev) {
1037                    if(i > 0) {
1038                        makeLoopIfNeeded(con, i-1);
1039                    }
1040                    firstGroupIdx = i;
1041                }
1042            }
1043            makeLoopIfNeeded(con, members.size()-1);
1044            connectionType = con;
1045        }
1046    
1047        //    private static void unconnectPreviousLink(List<WayConnectionType> con, int beg, boolean backward){
1048        //        int i = beg;
1049        //        while(true){
1050        //            WayConnectionType t = con.get(i--);
1051        //            t.isOnewayOppositeConnected = false;
1052        //            if(backward && t.isOnewayLoopBackwardPart) break;
1053        //            if(!backward && t.isOnewayLoopForwardPart) break;
1054        //        }
1055        //    }
1056    
1057        private static Direction reverse(final Direction dir){
1058            if(dir == FORWARD) return BACKWARD;
1059            if(dir == BACKWARD) return FORWARD;
1060            return dir;
1061        }
1062    
1063        private static boolean isBackward(final RelationMember member){
1064            return member.getRole().equals("backward");
1065        }
1066    
1067        private static boolean isForward(final RelationMember member){
1068            return member.getRole().equals("forward");
1069        }
1070    
1071        public static boolean isOneway(final RelationMember member){
1072            return isForward(member) || isBackward(member);
1073        }
1074    
1075        int firstGroupIdx;
1076        private void makeLoopIfNeeded(final List<WayConnectionType> con, final int i) {
1077            boolean loop;
1078            if (i == firstGroupIdx) { //is primitive loop
1079                loop = determineDirection(i, FORWARD, i) == FORWARD;
1080            } else {
1081                loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction;
1082            }
1083            if (loop) {
1084                for (int j=firstGroupIdx; j <= i; ++j) {
1085                    con.get(j).isLoop = true;
1086                }
1087            }
1088        }
1089    
1090        private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
1091            if (roundaboutType(i) != NONE)
1092                return roundaboutType(i);
1093    
1094            if (isOneway(m)){
1095                if(isBackward(m)) return BACKWARD;
1096                else return FORWARD;
1097            } else { /** guess the direction and see if it fits with the next member */
1098                if(determineDirection(i, FORWARD, i+1) != NONE) return FORWARD;
1099                if(determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD;
1100            }
1101            return NONE;
1102        }
1103    
1104        int lastForwardWay, lastBackwardWay;
1105        boolean onewayBeginning;
1106        private WayConnectionType determineOnewayConnectionType(final List<WayConnectionType> con,
1107                RelationMember m, int i, final WayConnectionType wct) {
1108            Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
1109            Direction dirBW = NONE;
1110            if(onewayBeginning) {
1111                if(lastBackwardWay < 0) {
1112                    dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
1113                } else {
1114                    dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
1115                }
1116    
1117                if(dirBW != NONE) {
1118                    onewayBeginning = false;
1119                }
1120            } else {
1121                dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
1122            }
1123    
1124            if(isOneway(m)) {
1125                if(dirBW != NONE){
1126                    wct.direction = dirBW;
1127                    lastBackwardWay = i;
1128                    wct.isOnewayLoopBackwardPart = true;
1129                }
1130                if(dirFW != NONE){
1131                    wct.direction = dirFW;
1132                    lastForwardWay = i;
1133                    wct.isOnewayLoopForwardPart = true;
1134                }
1135                if(dirFW == NONE && dirBW == NONE) { //Not connected to previous
1136                    //                        unconnectPreviousLink(con, i, true);
1137                    //                        unconnectPreviousLink(con, i, false);
1138                    wct.linkPrev = false;
1139                    if(isOneway(m)){
1140                        wct.isOnewayHead = true;
1141                        lastForwardWay = i-1;
1142                        lastBackwardWay = i-1;
1143                    } else {
1144                        lastForwardWay = UNCONNECTED;
1145                        lastBackwardWay = UNCONNECTED;
1146                    }
1147                    onewayBeginning = true;
1148                }
1149    
1150                if(dirFW != NONE && dirBW != NONE) { //End of oneway loop
1151                    if(i+1<members.size() && determineDirection(i, dirFW, i+1) != NONE) {
1152                        wct.isOnewayLoopBackwardPart = false;
1153                        dirBW = NONE;
1154                        wct.direction = dirFW;
1155                    } else {
1156                        wct.isOnewayLoopForwardPart = false;
1157                        dirFW = NONE;
1158                        wct.direction = dirBW;
1159                    }
1160    
1161                    wct.isOnewayTail = true;
1162                }
1163    
1164            } else {
1165                lastForwardWay = UNCONNECTED;
1166                lastBackwardWay = UNCONNECTED;
1167                if(dirFW == NONE || dirBW == NONE) {
1168                    wct.linkPrev = false;
1169                }
1170            }
1171            return wct;
1172        }
1173        
1174        private static interface AdditionalSorter {
1175            public boolean acceptsMember(RelationMember m);
1176            public List<RelationMember> sortMembers(List<RelationMember> list);
1177        }
1178        
1179        /**
1180         * Class that sorts type=associatedStreet relation's houses.
1181         */
1182        private static class AssociatedStreetSorter implements AdditionalSorter {
1183    
1184            @Override
1185            public boolean acceptsMember(RelationMember m) {
1186                return m != null 
1187                        && m.getRole() != null && m.getRole().equals("house") 
1188                        && m.getMember() != null && m.getMember().get("addr:housenumber") != null;
1189            }
1190    
1191            @Override
1192            public List<RelationMember> sortMembers(List<RelationMember> list) {
1193                Collections.sort(list, new Comparator<RelationMember>() {
1194                    @Override
1195                    public int compare(RelationMember a, RelationMember b) {
1196                        if (a == b || a.getMember() == b.getMember()) return 0;
1197                        String addrA = a.getMember().get("addr:housenumber").trim();
1198                        String addrB = b.getMember().get("addr:housenumber").trim();
1199                        if (addrA.equals(addrB)) return 0;
1200                        // Strip non-digits (from "1B" addresses for example)
1201                        String addrAnum = addrA.replaceAll("\\D+", "");
1202                        String addrBnum = addrB.replaceAll("\\D+", "");
1203                        // Compare only numbers
1204                        try {
1205                            Integer res = Integer.parseInt(addrAnum) - Integer.parseInt(addrBnum);
1206                            if (res != 0) return res;
1207                        } catch (NumberFormatException e) {
1208                            // Ignore NumberFormatException. If the number is not composed of digits, strings are compared next
1209                        }
1210                        // Same number ? Compare full strings
1211                        return addrA.compareTo(addrB);
1212                    }
1213                });
1214                return list;
1215            }
1216        }
1217    }