001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.euclidean.oned;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Iterator;
022import java.util.List;
023import java.util.NoSuchElementException;
024
025import org.apache.commons.math3.geometry.Point;
026import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
027import org.apache.commons.math3.geometry.partitioning.BSPTree;
028import org.apache.commons.math3.geometry.partitioning.BoundaryProjection;
029import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
030import org.apache.commons.math3.util.Precision;
031
032/** This class represents a 1D region: a set of intervals.
033 * @since 3.0
034 */
035public class IntervalsSet extends AbstractRegion<Euclidean1D, Euclidean1D> implements Iterable<double[]> {
036
037    /** Default value for tolerance. */
038    private static final double DEFAULT_TOLERANCE = 1.0e-10;
039
040    /** Build an intervals set representing the whole real line.
041     * @param tolerance tolerance below which points are considered identical.
042     * @since 3.3
043     */
044    public IntervalsSet(final double tolerance) {
045        super(tolerance);
046    }
047
048    /** Build an intervals set corresponding to a single interval.
049     * @param lower lower bound of the interval, must be lesser or equal
050     * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY})
051     * @param upper upper bound of the interval, must be greater or equal
052     * to {@code lower} (may be {@code Double.POSITIVE_INFINITY})
053     * @param tolerance tolerance below which points are considered identical.
054     * @since 3.3
055     */
056    public IntervalsSet(final double lower, final double upper, final double tolerance) {
057        super(buildTree(lower, upper, tolerance), tolerance);
058    }
059
060    /** Build an intervals set from an inside/outside BSP tree.
061     * <p>The leaf nodes of the BSP tree <em>must</em> have a
062     * {@code Boolean} attribute representing the inside status of
063     * the corresponding cell (true for inside cells, false for outside
064     * cells). In order to avoid building too many small objects, it is
065     * recommended to use the predefined constants
066     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
067     * @param tree inside/outside BSP tree representing the intervals set
068     * @param tolerance tolerance below which points are considered identical.
069     * @since 3.3
070     */
071    public IntervalsSet(final BSPTree<Euclidean1D> tree, final double tolerance) {
072        super(tree, tolerance);
073    }
074
075    /** Build an intervals set from a Boundary REPresentation (B-rep).
076     * <p>The boundary is provided as a collection of {@link
077     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
078     * interior part of the region on its minus side and the exterior on
079     * its plus side.</p>
080     * <p>The boundary elements can be in any order, and can form
081     * several non-connected sets (like for example polygons with holes
082     * or a set of disjoints polyhedrons considered as a whole). In
083     * fact, the elements do not even need to be connected together
084     * (their topological connections are not used here). However, if the
085     * boundary does not really separate an inside open from an outside
086     * open (open having here its topological meaning), then subsequent
087     * calls to the {@link
088     * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Point)
089     * checkPoint} method will not be meaningful anymore.</p>
090     * <p>If the boundary is empty, the region will represent the whole
091     * space.</p>
092     * @param boundary collection of boundary elements
093     * @param tolerance tolerance below which points are considered identical.
094     * @since 3.3
095     */
096    public IntervalsSet(final Collection<SubHyperplane<Euclidean1D>> boundary,
097                        final double tolerance) {
098        super(boundary, tolerance);
099    }
100
101    /** Build an intervals set representing the whole real line.
102     * @deprecated as of 3.1 replaced with {@link #IntervalsSet(double)}
103     */
104    @Deprecated
105    public IntervalsSet() {
106        this(DEFAULT_TOLERANCE);
107    }
108
109    /** Build an intervals set corresponding to a single interval.
110     * @param lower lower bound of the interval, must be lesser or equal
111     * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY})
112     * @param upper upper bound of the interval, must be greater or equal
113     * to {@code lower} (may be {@code Double.POSITIVE_INFINITY})
114     * @deprecated as of 3.3 replaced with {@link #IntervalsSet(double, double, double)}
115     */
116    @Deprecated
117    public IntervalsSet(final double lower, final double upper) {
118        this(lower, upper, DEFAULT_TOLERANCE);
119    }
120
121    /** Build an intervals set from an inside/outside BSP tree.
122     * <p>The leaf nodes of the BSP tree <em>must</em> have a
123     * {@code Boolean} attribute representing the inside status of
124     * the corresponding cell (true for inside cells, false for outside
125     * cells). In order to avoid building too many small objects, it is
126     * recommended to use the predefined constants
127     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
128     * @param tree inside/outside BSP tree representing the intervals set
129     * @deprecated as of 3.3, replaced with {@link #IntervalsSet(BSPTree, double)}
130     */
131    @Deprecated
132    public IntervalsSet(final BSPTree<Euclidean1D> tree) {
133        this(tree, DEFAULT_TOLERANCE);
134    }
135
136    /** Build an intervals set from a Boundary REPresentation (B-rep).
137     * <p>The boundary is provided as a collection of {@link
138     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
139     * interior part of the region on its minus side and the exterior on
140     * its plus side.</p>
141     * <p>The boundary elements can be in any order, and can form
142     * several non-connected sets (like for example polygons with holes
143     * or a set of disjoints polyhedrons considered as a whole). In
144     * fact, the elements do not even need to be connected together
145     * (their topological connections are not used here). However, if the
146     * boundary does not really separate an inside open from an outside
147     * open (open having here its topological meaning), then subsequent
148     * calls to the {@link
149     * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Point)
150     * checkPoint} method will not be meaningful anymore.</p>
151     * <p>If the boundary is empty, the region will represent the whole
152     * space.</p>
153     * @param boundary collection of boundary elements
154     * @deprecated as of 3.3, replaced with {@link #IntervalsSet(Collection, double)}
155     */
156    @Deprecated
157    public IntervalsSet(final Collection<SubHyperplane<Euclidean1D>> boundary) {
158        this(boundary, DEFAULT_TOLERANCE);
159    }
160
161    /** Build an inside/outside tree representing a single interval.
162     * @param lower lower bound of the interval, must be lesser or equal
163     * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY})
164     * @param upper upper bound of the interval, must be greater or equal
165     * to {@code lower} (may be {@code Double.POSITIVE_INFINITY})
166     * @param tolerance tolerance below which points are considered identical.
167     * @return the built tree
168     */
169    private static BSPTree<Euclidean1D> buildTree(final double lower, final double upper,
170                                                  final double tolerance) {
171        if (Double.isInfinite(lower) && (lower < 0)) {
172            if (Double.isInfinite(upper) && (upper > 0)) {
173                // the tree must cover the whole real line
174                return new BSPTree<Euclidean1D>(Boolean.TRUE);
175            }
176            // the tree must be open on the negative infinity side
177            final SubHyperplane<Euclidean1D> upperCut =
178                new OrientedPoint(new Vector1D(upper), true, tolerance).wholeHyperplane();
179            return new BSPTree<Euclidean1D>(upperCut,
180                               new BSPTree<Euclidean1D>(Boolean.FALSE),
181                               new BSPTree<Euclidean1D>(Boolean.TRUE),
182                               null);
183        }
184        final SubHyperplane<Euclidean1D> lowerCut =
185            new OrientedPoint(new Vector1D(lower), false, tolerance).wholeHyperplane();
186        if (Double.isInfinite(upper) && (upper > 0)) {
187            // the tree must be open on the positive infinity side
188            return new BSPTree<Euclidean1D>(lowerCut,
189                                            new BSPTree<Euclidean1D>(Boolean.FALSE),
190                                            new BSPTree<Euclidean1D>(Boolean.TRUE),
191                                            null);
192        }
193
194        // the tree must be bounded on the two sides
195        final SubHyperplane<Euclidean1D> upperCut =
196            new OrientedPoint(new Vector1D(upper), true, tolerance).wholeHyperplane();
197        return new BSPTree<Euclidean1D>(lowerCut,
198                                        new BSPTree<Euclidean1D>(Boolean.FALSE),
199                                        new BSPTree<Euclidean1D>(upperCut,
200                                                                 new BSPTree<Euclidean1D>(Boolean.FALSE),
201                                                                 new BSPTree<Euclidean1D>(Boolean.TRUE),
202                                                                 null),
203                                        null);
204
205    }
206
207    /** {@inheritDoc} */
208    @Override
209    public IntervalsSet buildNew(final BSPTree<Euclidean1D> tree) {
210        return new IntervalsSet(tree, getTolerance());
211    }
212
213    /** {@inheritDoc} */
214    @Override
215    protected void computeGeometricalProperties() {
216        if (getTree(false).getCut() == null) {
217            setBarycenter((Point<Euclidean1D>) Vector1D.NaN);
218            setSize(((Boolean) getTree(false).getAttribute()) ? Double.POSITIVE_INFINITY : 0);
219        } else {
220            double size = 0.0;
221            double sum = 0.0;
222            for (final Interval interval : asList()) {
223                size += interval.getSize();
224                sum  += interval.getSize() * interval.getBarycenter();
225            }
226            setSize(size);
227            if (Double.isInfinite(size)) {
228                setBarycenter((Point<Euclidean1D>) Vector1D.NaN);
229            } else if (size >= Precision.SAFE_MIN) {
230                setBarycenter((Point<Euclidean1D>) new Vector1D(sum / size));
231            } else {
232                setBarycenter((Point<Euclidean1D>) ((OrientedPoint) getTree(false).getCut().getHyperplane()).getLocation());
233            }
234        }
235    }
236
237    /** Get the lowest value belonging to the instance.
238     * @return lowest value belonging to the instance
239     * ({@code Double.NEGATIVE_INFINITY} if the instance doesn't
240     * have any low bound, {@code Double.POSITIVE_INFINITY} if the
241     * instance is empty)
242     */
243    public double getInf() {
244        BSPTree<Euclidean1D> node = getTree(false);
245        double  inf  = Double.POSITIVE_INFINITY;
246        while (node.getCut() != null) {
247            final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane();
248            inf  = op.getLocation().getX();
249            node = op.isDirect() ? node.getMinus() : node.getPlus();
250        }
251        return ((Boolean) node.getAttribute()) ? Double.NEGATIVE_INFINITY : inf;
252    }
253
254    /** Get the highest value belonging to the instance.
255     * @return highest value belonging to the instance
256     * ({@code Double.POSITIVE_INFINITY} if the instance doesn't
257     * have any high bound, {@code Double.NEGATIVE_INFINITY} if the
258     * instance is empty)
259     */
260    public double getSup() {
261        BSPTree<Euclidean1D> node = getTree(false);
262        double  sup  = Double.NEGATIVE_INFINITY;
263        while (node.getCut() != null) {
264            final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane();
265            sup  = op.getLocation().getX();
266            node = op.isDirect() ? node.getPlus() : node.getMinus();
267        }
268        return ((Boolean) node.getAttribute()) ? Double.POSITIVE_INFINITY : sup;
269    }
270
271    /** {@inheritDoc}
272     * @since 3.3
273     */
274    @Override
275    public BoundaryProjection<Euclidean1D> projectToBoundary(final Point<Euclidean1D> point) {
276
277        // get position of test point
278        final double x = ((Vector1D) point).getX();
279
280        double previous = Double.NEGATIVE_INFINITY;
281        for (final double[] a : this) {
282            if (x < a[0]) {
283                // the test point lies between the previous and the current intervals
284                // offset will be positive
285                final double previousOffset = x - previous;
286                final double currentOffset  = a[0] - x;
287                if (previousOffset < currentOffset) {
288                    return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(previous), previousOffset);
289                } else {
290                    return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[0]), currentOffset);
291                }
292            } else if (x <= a[1]) {
293                // the test point lies within the current interval
294                // offset will be negative
295                final double offset0 = a[0] - x;
296                final double offset1 = x - a[1];
297                if (offset0 < offset1) {
298                    return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[1]), offset1);
299                } else {
300                    return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(a[0]), offset0);
301                }
302            }
303            previous = a[1];
304        }
305
306        // the test point if past the last sub-interval
307        return new BoundaryProjection<Euclidean1D>(point, finiteOrNullPoint(previous), x - previous);
308
309    }
310
311    /** Build a finite point.
312     * @param x abscissa of the point
313     * @return a new point for finite abscissa, null otherwise
314     */
315    private Vector1D finiteOrNullPoint(final double x) {
316        return Double.isInfinite(x) ? null : new Vector1D(x);
317    }
318
319    /** Build an ordered list of intervals representing the instance.
320     * <p>This method builds this intervals set as an ordered list of
321     * {@link Interval Interval} elements. If the intervals set has no
322     * lower limit, the first interval will have its low bound equal to
323     * {@code Double.NEGATIVE_INFINITY}. If the intervals set has
324     * no upper limit, the last interval will have its upper bound equal
325     * to {@code Double.POSITIVE_INFINITY}. An empty tree will
326     * build an empty list while a tree representing the whole real line
327     * will build a one element list with both bounds being
328     * infinite.</p>
329     * @return a new ordered list containing {@link Interval Interval}
330     * elements
331     */
332    public List<Interval> asList() {
333        final List<Interval> list = new ArrayList<Interval>();
334        for (final double[] a : this) {
335            list.add(new Interval(a[0], a[1]));
336        }
337        return list;
338    }
339
340    /** Get the first leaf node of a tree.
341     * @param root tree root
342     * @return first leaf node
343     */
344    private BSPTree<Euclidean1D> getFirstLeaf(final BSPTree<Euclidean1D> root) {
345
346        if (root.getCut() == null) {
347            return root;
348        }
349
350        // find the smallest internal node
351        BSPTree<Euclidean1D> smallest = null;
352        for (BSPTree<Euclidean1D> n = root; n != null; n = previousInternalNode(n)) {
353            smallest = n;
354        }
355
356        return leafBefore(smallest);
357
358    }
359
360    /** Get the node corresponding to the first interval boundary.
361     * @return smallest internal node,
362     * or null if there are no internal nodes (i.e. the set is either empty or covers the real line)
363     */
364    private BSPTree<Euclidean1D> getFirstIntervalBoundary() {
365
366        // start search at the tree root
367        BSPTree<Euclidean1D> node = getTree(false);
368        if (node.getCut() == null) {
369            return null;
370        }
371
372        // walk tree until we find the smallest internal node
373        node = getFirstLeaf(node).getParent();
374
375        // walk tree until we find an interval boundary
376        while (node != null && !(isIntervalStart(node) || isIntervalEnd(node))) {
377            node = nextInternalNode(node);
378        }
379
380        return node;
381
382    }
383
384    /** Check if an internal node corresponds to the start abscissa of an interval.
385     * @param node internal node to check
386     * @return true if the node corresponds to the start abscissa of an interval
387     */
388    private boolean isIntervalStart(final BSPTree<Euclidean1D> node) {
389
390        if ((Boolean) leafBefore(node).getAttribute()) {
391            // it has an inside cell before it, it may end an interval but not start it
392            return false;
393        }
394
395        if (!(Boolean) leafAfter(node).getAttribute()) {
396            // it has an outside cell after it, it is a dummy cut away from real intervals
397            return false;
398        }
399
400        // the cell has an outside before and an inside after it
401        // it is the start of an interval
402        return true;
403
404    }
405
406    /** Check if an internal node corresponds to the end abscissa of an interval.
407     * @param node internal node to check
408     * @return true if the node corresponds to the end abscissa of an interval
409     */
410    private boolean isIntervalEnd(final BSPTree<Euclidean1D> node) {
411
412        if (!(Boolean) leafBefore(node).getAttribute()) {
413            // it has an outside cell before it, it may start an interval but not end it
414            return false;
415        }
416
417        if ((Boolean) leafAfter(node).getAttribute()) {
418            // it has an inside cell after it, it is a dummy cut in the middle of an interval
419            return false;
420        }
421
422        // the cell has an inside before and an outside after it
423        // it is the end of an interval
424        return true;
425
426    }
427
428    /** Get the next internal node.
429     * @param node current internal node
430     * @return next internal node in ascending order, or null
431     * if this is the last internal node
432     */
433    private BSPTree<Euclidean1D> nextInternalNode(BSPTree<Euclidean1D> node) {
434
435        if (childAfter(node).getCut() != null) {
436            // the next node is in the sub-tree
437            return leafAfter(node).getParent();
438        }
439
440        // there is nothing left deeper in the tree, we backtrack
441        while (isAfterParent(node)) {
442            node = node.getParent();
443        }
444        return node.getParent();
445
446    }
447
448    /** Get the previous internal node.
449     * @param node current internal node
450     * @return previous internal node in ascending order, or null
451     * if this is the first internal node
452     */
453    private BSPTree<Euclidean1D> previousInternalNode(BSPTree<Euclidean1D> node) {
454
455        if (childBefore(node).getCut() != null) {
456            // the next node is in the sub-tree
457            return leafBefore(node).getParent();
458        }
459
460        // there is nothing left deeper in the tree, we backtrack
461        while (isBeforeParent(node)) {
462            node = node.getParent();
463        }
464        return node.getParent();
465
466    }
467
468    /** Find the leaf node just before an internal node.
469     * @param node internal node at which the sub-tree starts
470     * @return leaf node just before the internal node
471     */
472    private BSPTree<Euclidean1D> leafBefore(BSPTree<Euclidean1D> node) {
473
474        node = childBefore(node);
475        while (node.getCut() != null) {
476            node = childAfter(node);
477        }
478
479        return node;
480
481    }
482
483    /** Find the leaf node just after an internal node.
484     * @param node internal node at which the sub-tree starts
485     * @return leaf node just after the internal node
486     */
487    private BSPTree<Euclidean1D> leafAfter(BSPTree<Euclidean1D> node) {
488
489        node = childAfter(node);
490        while (node.getCut() != null) {
491            node = childBefore(node);
492        }
493
494        return node;
495
496    }
497
498    /** Check if a node is the child before its parent in ascending order.
499     * @param node child node considered
500     * @return true is the node has a parent end is before it in ascending order
501     */
502    private boolean isBeforeParent(final BSPTree<Euclidean1D> node) {
503        final BSPTree<Euclidean1D> parent = node.getParent();
504        if (parent == null) {
505            return false;
506        } else {
507            return node == childBefore(parent);
508        }
509    }
510
511    /** Check if a node is the child after its parent in ascending order.
512     * @param node child node considered
513     * @return true is the node has a parent end is after it in ascending order
514     */
515    private boolean isAfterParent(final BSPTree<Euclidean1D> node) {
516        final BSPTree<Euclidean1D> parent = node.getParent();
517        if (parent == null) {
518            return false;
519        } else {
520            return node == childAfter(parent);
521        }
522    }
523
524    /** Find the child node just before an internal node.
525     * @param node internal node at which the sub-tree starts
526     * @return child node just before the internal node
527     */
528    private BSPTree<Euclidean1D> childBefore(BSPTree<Euclidean1D> node) {
529        if (isDirect(node)) {
530            // smaller abscissas are on minus side, larger abscissas are on plus side
531            return node.getMinus();
532        } else {
533            // smaller abscissas are on plus side, larger abscissas are on minus side
534            return node.getPlus();
535        }
536    }
537
538    /** Find the child node just after an internal node.
539     * @param node internal node at which the sub-tree starts
540     * @return child node just after the internal node
541     */
542    private BSPTree<Euclidean1D> childAfter(BSPTree<Euclidean1D> node) {
543        if (isDirect(node)) {
544            // smaller abscissas are on minus side, larger abscissas are on plus side
545            return node.getPlus();
546        } else {
547            // smaller abscissas are on plus side, larger abscissas are on minus side
548            return node.getMinus();
549        }
550    }
551
552    /** Check if an internal node has a direct oriented point.
553     * @param node internal node to check
554     * @return true if the oriented point is direct
555     */
556    private boolean isDirect(final BSPTree<Euclidean1D> node) {
557        return ((OrientedPoint) node.getCut().getHyperplane()).isDirect();
558    }
559
560    /** Get the abscissa of an internal node.
561     * @param node internal node to check
562     * @return abscissa
563     */
564    private double getAngle(final BSPTree<Euclidean1D> node) {
565        return ((OrientedPoint) node.getCut().getHyperplane()).getLocation().getX();
566    }
567
568    /** {@inheritDoc}
569     * <p>
570     * The iterator returns the limit values of sub-intervals in ascending order.
571     * </p>
572     * <p>
573     * The iterator does <em>not</em> support the optional {@code remove} operation.
574     * </p>
575     * @since 3.3
576     */
577    public Iterator<double[]> iterator() {
578        return new SubIntervalsIterator();
579    }
580
581    /** Local iterator for sub-intervals. */
582    private class SubIntervalsIterator implements Iterator<double[]> {
583
584        /** Current node. */
585        private BSPTree<Euclidean1D> current;
586
587        /** Sub-interval no yet returned. */
588        private double[] pending;
589
590        /** Simple constructor.
591         */
592        SubIntervalsIterator() {
593
594            current = getFirstIntervalBoundary();
595
596            if (current == null) {
597                // all the leaf tree nodes share the same inside/outside status
598                if ((Boolean) getFirstLeaf(getTree(false)).getAttribute()) {
599                    // it is an inside node, it represents the full real line
600                    pending = new double[] {
601                        Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY
602                    };
603                } else {
604                    pending = null;
605                }
606            } else if (isIntervalEnd(current)) {
607                // the first boundary is an interval end,
608                // so the first interval starts at infinity
609                pending = new double[] {
610                    Double.NEGATIVE_INFINITY, getAngle(current)
611                };
612            } else {
613                selectPending();
614            }
615        }
616
617        /** Walk the tree to select the pending sub-interval.
618         */
619        private void selectPending() {
620
621            // look for the start of the interval
622            BSPTree<Euclidean1D> start = current;
623            while (start != null && !isIntervalStart(start)) {
624                start = nextInternalNode(start);
625            }
626
627            if (start == null) {
628                // we have exhausted the iterator
629                current = null;
630                pending = null;
631                return;
632            }
633
634            // look for the end of the interval
635            BSPTree<Euclidean1D> end = start;
636            while (end != null && !isIntervalEnd(end)) {
637                end = nextInternalNode(end);
638            }
639
640            if (end != null) {
641
642                // we have identified the interval
643                pending = new double[] {
644                    getAngle(start), getAngle(end)
645                };
646
647                // prepare search for next interval
648                current = end;
649
650            } else {
651
652                // the final interval is open toward infinity
653                pending = new double[] {
654                    getAngle(start), Double.POSITIVE_INFINITY
655                };
656
657                // there won't be any other intervals
658                current = null;
659
660            }
661
662        }
663
664        /** {@inheritDoc} */
665        public boolean hasNext() {
666            return pending != null;
667        }
668
669        /** {@inheritDoc} */
670        public double[] next() {
671            if (pending == null) {
672                throw new NoSuchElementException();
673            }
674            final double[] next = pending;
675            selectPending();
676            return next;
677        }
678
679        /** {@inheritDoc} */
680        public void remove() {
681            throw new UnsupportedOperationException();
682        }
683
684    }
685
686}