src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.2)
   3  * Copyright (C) 2014 The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.util;
  22
  23 import java.util.ArrayList;
  24 import java.util.Arrays;
  25 import java.util.List;
  26
  27 /**
  28  * A simple way of bijectively mapping a non-contiguous linear range to another
  29  * non-contiguous linear range.
  30  *
  31  * Use at your own risk!
  32  *
  33  * TODO: efficient implementation of private posMap method
  34  *
  35  * TODO: test/ensure that sense of from and to ratio start position is conserved
  36  * (codon start position recovery)
  37  */
  38 public class MapList
  39 {
  40
  41   /*
  42    * Subregions (base 1) described as { [start1, end1], [start2, end2], ...}
  43    */
  44   private List<int[]> fromShifts = new ArrayList<int[]>();
  45
  46   /*
  47    * Same format as fromShifts, for the 'mapped to' sequence
  48    */
  49   private List<int[]> toShifts = new ArrayList<int[]>();
  50
  51   /*
  52    * number of steps in fromShifts to one toRatio unit
  53    */
  54   private int fromRatio;
  55
  56   /*
  57    * number of steps in toShifts to one fromRatio
  58    */
  59   private int toRatio;
  60
  61   /*
  62    * lowest and highest value in the from Map
  63    */
  64   private int fromLowest;
  65
  66   private int fromHighest;
  67
  68   /*
  69    * lowest and highest value in the to Map
  70    */
  71   private int toLowest;
  72
  73   private int toHighest;
  74
  75   /**
  76    * Two MapList objects are equal if they are the same object, or they both
  77    * have populated shift ranges and all values are the same.
  78    */
  79   @Override
  80   public boolean equals(Object o)
  81   {
  82     if (o == null || !(o instanceof MapList))
  83     {
  84       return false;
  85     }
  86
  87     MapList obj = (MapList) o;
  88     if (obj == this)
  89     {
  90       return true;
  91     }
  92     if (obj.fromRatio != fromRatio || obj.toRatio != toRatio
  93             || obj.fromShifts == null || obj.toShifts == null)
  94     {
  95       return false;
  96     }
  97     return Arrays
  98             .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray())
  99             && Arrays
 100                     .deepEquals(toShifts.toArray(), obj.toShifts.toArray());
 101   }
 102
 103   /**
 104    * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...}
 105    *
 106    * @return
 107    */
 108   public List<int[]> getFromRanges()
 109   {
 110     return fromShifts;
 111   }
 112
 113   /**
 114    * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...}
 115    *
 116    * @return
 117    */
 118   public List<int[]> getToRanges()
 119   {
 120     return toShifts;
 121   }
 122
 123   /**
 124    * Flattens a list of [start, end] into a single [start1, end1, start2,
 125    * end2,...] array.
 126    *
 127    * @param shifts
 128    * @return
 129    */
 130   protected static int[] getRanges(List<int[]> shifts)
 131   {
 132     int[] rnges = new int[2 * shifts.size()];
 133     int i = 0;
 134     for (int[] r : shifts)
 135     {
 136       rnges[i++] = r[0];
 137       rnges[i++] = r[1];
 138     }
 139     return rnges;
 140   }
 141
 142   /**
 143    *
 144    * @return length of mapped phrase in from
 145    */
 146   public int getFromRatio()
 147   {
 148     return fromRatio;
 149   }
 150
 151   /**
 152    *
 153    * @return length of mapped phrase in to
 154    */
 155   public int getToRatio()
 156   {
 157     return toRatio;
 158   }
 159
 160   public int getFromLowest()
 161   {
 162     return fromLowest;
 163   }
 164
 165   public int getFromHighest()
 166   {
 167     return fromHighest;
 168   }
 169
 170   public int getToLowest()
 171   {
 172     return toLowest;
 173   }
 174
 175   public int getToHighest()
 176   {
 177     return toHighest;
 178   }
 179
 180   /**
 181    * Constructor.
 182    *
 183    * @param from
 184    *          contiguous regions as [start1, end1, start2, end2, ...]
 185    * @param to
 186    *          same format as 'from'
 187    * @param fromRatio
 188    *          phrase length in 'from' (e.g. 3 for dna)
 189    * @param toRatio
 190    *          phrase length in 'to' (e.g. 1 for protein)
 191    */
 192   public MapList(int from[], int to[], int fromRatio, int toRatio)
 193   {
 194     this.fromRatio = fromRatio;
 195     this.toRatio = toRatio;
 196     fromLowest = from[0];
 197     fromHighest = from[1];
 198     for (int i = 0; i < from.length; i += 2)
 199     {
 200       fromLowest = Math.min(fromLowest, from[i]);
 201       fromHighest = Math.max(fromHighest, from[i + 1]);
 202
 203       fromShifts.add(new int[]
 204       { from[i], from[i + 1] });
 205     }
 206
 207     toLowest = to[0];
 208     toHighest = to[1];
 209     for (int i = 0; i < to.length; i += 2)
 210     {
 211       toLowest = Math.min(toLowest, to[i]);
 212       toHighest = Math.max(toHighest, to[i + 1]);
 213       toShifts.add(new int[]
 214       { to[i], to[i + 1] });
 215     }
 216   }
 217
 218   /**
 219    * Copy constructor. Creates an identical mapping.
 220    *
 221    * @param map
 222    */
 223   public MapList(MapList map)
 224   {
 225     // TODO not used - remove?
 226     this.fromLowest = map.fromLowest;
 227     this.fromHighest = map.fromHighest;
 228     this.toLowest = map.toLowest;
 229     this.toHighest = map.toHighest;
 230
 231     this.fromRatio = map.fromRatio;
 232     this.toRatio = map.toRatio;
 233     if (map.fromShifts != null)
 234     {
 235       for (int[] r : map.fromShifts)
 236       {
 237         fromShifts.add(new int[]
 238         { r[0], r[1] });
 239       }
 240     }
 241     if (map.toShifts != null)
 242     {
 243       for (int[] r : map.toShifts)
 244       {
 245         toShifts.add(new int[]
 246         { r[0], r[1] });
 247       }
 248     }
 249   }
 250
 251   /**
 252    * Constructor given ranges as lists of [start, end] positions
 253    *
 254    * @param fromRange
 255    * @param toRange
 256    * @param fromRatio
 257    * @param toRatio
 258    */
 259   public MapList(List<int[]> fromRange, List<int[]> toRange,
 260           int fromRatio, int toRatio)
 261   {
 262     this.fromShifts = fromRange;
 263     this.toShifts = toRange;
 264     this.fromRatio = fromRatio;
 265     this.toRatio = toRatio;
 266
 267     fromLowest = Integer.MAX_VALUE;
 268     fromHighest = 0;
 269     for (int[] range : fromRange) {
 270       fromLowest = Math.min(fromLowest, range[0]);
 271       fromHighest = Math.max(fromHighest, range[1]);
 272     }
 273
 274     toLowest = Integer.MAX_VALUE;
 275     toHighest = 0;
 276     for (int[] range : toRange)
 277     {
 278       toLowest = Math.min(toLowest, range[0]);
 279       toHighest = Math.max(toHighest, range[1]);
 280     }
 281   }
 282
 283   /**
 284    * get all mapped positions from 'from' to 'to'
 285    *
 286    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 287    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 288    */
 289   protected int[][] makeFromMap()
 290   {
 291     // TODO not used - remove??
 292     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 293   }
 294
 295   /**
 296    * get all mapped positions from 'to' to 'from'
 297    *
 298    * @return int[to position]=position mapped in from
 299    */
 300   protected int[][] makeToMap()
 301   {
 302     // TODO not used - remove??
 303     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 304   }
 305
 306   /**
 307    * construct an int map for intervals in intVals
 308    *
 309    * @param shiftTo
 310    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 311    *         returning mapped position
 312    */
 313   private int[][] posMap(List<int[]> shiftTo, int ratio,
 314           List<int[]> shiftFrom,
 315           int toRatio)
 316   {
 317     // TODO not used - remove??
 318     int iv = 0, ivSize = shiftTo.size();
 319     if (iv >= ivSize)
 320     {
 321       return null;
 322     }
 323     int[] intv = shiftTo.get(iv++);
 324     int from = intv[0], to = intv[1];
 325     if (from > to)
 326     {
 327       from = intv[1];
 328       to = intv[0];
 329     }
 330     while (iv < ivSize)
 331     {
 332       intv = shiftTo.get(iv++);
 333       if (intv[0] < from)
 334       {
 335         from = intv[0];
 336       }
 337       if (intv[1] < from)
 338       {
 339         from = intv[1];
 340       }
 341       if (intv[0] > to)
 342       {
 343         to = intv[0];
 344       }
 345       if (intv[1] > to)
 346       {
 347         to = intv[1];
 348       }
 349     }
 350     int tF = 0, tT = 0;
 351     int mp[][] = new int[to - from + 2][];
 352     for (int i = 0; i < mp.length; i++)
 353     {
 354       int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
 355       if (m != null)
 356       {
 357         if (i == 0)
 358         {
 359           tF = tT = m[0];
 360         }
 361         else
 362         {
 363           if (m[0] < tF)
 364           {
 365             tF = m[0];
 366           }
 367           if (m[0] > tT)
 368           {
 369             tT = m[0];
 370           }
 371         }
 372       }
 373       mp[i] = m;
 374     }
 375     int[][] map = new int[][]
 376     { new int[]
 377     { from, to, tF, tT }, new int[to - from + 2] };
 378
 379     map[0][2] = tF;
 380     map[0][3] = tT;
 381
 382     for (int i = 0; i < mp.length; i++)
 383     {
 384       if (mp[i] != null)
 385       {
 386         map[1][i] = mp[i][0] - tF;
 387       }
 388       else
 389       {
 390         map[1][i] = -1; // indicates an out of range mapping
 391       }
 392     }
 393     return map;
 394   }
 395
 396   /**
 397    * addShift
 398    *
 399    * @param pos
 400    *          start position for shift (in original reference frame)
 401    * @param shift
 402    *          length of shift
 403    *
 404    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 405    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 406    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 407    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 408    *          rshift[1]+=shift; }
 409    */
 410
 411   /**
 412    * shift from pos to To(pos)
 413    *
 414    * @param pos
 415    *          int
 416    * @return int shifted position in To, frameshift in From, direction of mapped
 417    *         symbol in To
 418    */
 419   public int[] shiftFrom(int pos)
 420   {
 421     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 422   }
 423
 424   /**
 425    * inverse of shiftFrom - maps pos in To to a position in From
 426    *
 427    * @param pos
 428    *          (in To)
 429    * @return shifted position in From, frameshift in To, direction of mapped
 430    *         symbol in From
 431    */
 432   public int[] shiftTo(int pos)
 433   {
 434     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 435   }
 436
 437   /**
 438    *
 439    * @param shiftTo
 440    * @param fromRatio
 441    * @param shiftFrom
 442    * @param toRatio
 443    * @return
 444    */
 445   protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
 446           List<int[]> shiftFrom, int toRatio)
 447   {
 448     // TODO: javadoc; tests
 449     int[] fromCount = countPos(shiftTo, pos);
 450     if (fromCount == null)
 451     {
 452       return null;
 453     }
 454     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 455     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 456     int[] toPos = countToPos(shiftFrom, toCount);
 457     if (toPos == null)
 458     {
 459       return null; // throw new Error("Bad Mapping!");
 460     }
 461     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 462     return new int[]
 463     { toPos[0], fromRemainder, toPos[1] };
 464   }
 465
 466   /**
 467    * count how many positions pos is along the series of intervals.
 468    *
 469    * @param shiftTo
 470    * @param pos
 471    * @return number of positions or null if pos is not within intervals
 472    */
 473   protected static int[] countPos(List<int[]> shiftTo, int pos)
 474   {
 475     int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
 476     while (iv < ivSize)
 477     {
 478       intv = shiftTo.get(iv++);
 479       if (intv[0] <= intv[1])
 480       {
 481         if (pos >= intv[0] && pos <= intv[1])
 482         {
 483           return new int[]
 484           { count + pos - intv[0] + 1, +1 };
 485         }
 486         else
 487         {
 488           count += intv[1] - intv[0] + 1;
 489         }
 490       }
 491       else
 492       {
 493         if (pos >= intv[1] && pos <= intv[0])
 494         {
 495           return new int[]
 496           { count + intv[0] - pos + 1, -1 };
 497         }
 498         else
 499         {
 500           count += intv[0] - intv[1] + 1;
 501         }
 502       }
 503     }
 504     return null;
 505   }
 506
 507   /**
 508    * count out pos positions into a series of intervals and return the position
 509    *
 510    * @param shiftFrom
 511    * @param pos
 512    * @return position pos in interval set
 513    */
 514   protected static int[] countToPos(List<int[]> shiftFrom, int pos)
 515   {
 516     int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
 517     int[] intv =
 518     { 0, 0 };
 519     while (iv < ivSize)
 520     {
 521       intv = shiftFrom.get(iv++);
 522       diff = intv[1] - intv[0];
 523       if (diff >= 0)
 524       {
 525         if (pos <= count + 1 + diff)
 526         {
 527           return new int[]
 528           { pos - count - 1 + intv[0], +1 };
 529         }
 530         else
 531         {
 532           count += 1 + diff;
 533         }
 534       }
 535       else
 536       {
 537         if (pos <= count + 1 - diff)
 538         {
 539           return new int[]
 540           { intv[0] - (pos - count - 1), -1 };
 541         }
 542         else
 543         {
 544           count += 1 - diff;
 545         }
 546       }
 547     }
 548     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 549   }
 550
 551   /**
 552    * find series of intervals mapping from start-end in the From map.
 553    *
 554    * @param start
 555    *          position mapped 'to'
 556    * @param end
 557    *          position mapped 'to'
 558    * @return series of [start, end] ranges in sequence mapped 'from'
 559    */
 560   public int[] locateInFrom(int start, int end)
 561   {
 562     // inefficient implementation
 563     int fromStart[] = shiftTo(start);
 564     // needs to be inclusive of end of symbol position
 565     int fromEnd[] = shiftTo(end);
 566
 567     return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 568   }
 569
 570   /**
 571    * find series of intervals mapping from start-end in the to map.
 572    *
 573    * @param start
 574    *          position mapped 'from'
 575    * @param end
 576    *          position mapped 'from'
 577    * @return series of [start, end] ranges in sequence mapped 'to'
 578    */
 579   public int[] locateInTo(int start, int end)
 580   {
 581     int toStart[] = shiftFrom(start);
 582     int toEnd[] = shiftFrom(end);
 583     return getIntervals(toShifts, toStart, toEnd, toRatio);
 584   }
 585
 586   /**
 587    * like shift - except returns the intervals in the given vector of shifts
 588    * which were spanned in traversing fromStart to fromEnd
 589    *
 590    * @param shiftFrom
 591    * @param fromStart
 592    * @param fromEnd
 593    * @param fromRatio2
 594    * @return series of from,to intervals from from first position of starting
 595    *         region to final position of ending region inclusive
 596    */
 597   protected static int[] getIntervals(List<int[]> shiftFrom,
 598           int[] fromStart,
 599           int[] fromEnd, int fromRatio2)
 600   {
 601     if (fromStart == null || fromEnd == null)
 602     {
 603       return null;
 604     }
 605     int startpos, endpos;
 606     startpos = fromStart[0]; // first position in fromStart
 607     endpos = fromEnd[0]; // last position in fromEnd
 608     int endindx = (fromRatio2 - 1); // additional positions to get to last
 609     // position from endpos
 610     int intv = 0, intvSize = shiftFrom.size();
 611     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 612     // search intervals to locate ones containing startpos and count endindx
 613     // positions on from endpos
 614     while (intv < intvSize && (fs == -1 || fe == -1))
 615     {
 616       iv = shiftFrom.get(intv++);
 617       if (fe_s > -1)
 618       {
 619         endpos = iv[0]; // start counting from beginning of interval
 620         endindx--; // inclusive of endpos
 621       }
 622       if (iv[0] <= iv[1])
 623       {
 624         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 625         {
 626           fs = i;
 627         }
 628         if (endpos >= iv[0] && endpos <= iv[1])
 629         {
 630           if (fe_s == -1)
 631           {
 632             fe_s = i;
 633           }
 634           if (fe_s != -1)
 635           {
 636             if (endpos + endindx <= iv[1])
 637             {
 638               fe = i;
 639               endpos = endpos + endindx; // end of end token is within this
 640               // interval
 641             }
 642             else
 643             {
 644               endindx -= iv[1] - endpos; // skip all this interval too
 645             }
 646           }
 647         }
 648       }
 649       else
 650       {
 651         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 652         {
 653           fs = i;
 654         }
 655         if (endpos <= iv[0] && endpos >= iv[1])
 656         {
 657           if (fe_s == -1)
 658           {
 659             fe_s = i;
 660           }
 661           if (fe_s != -1)
 662           {
 663             if (endpos - endindx >= iv[1])
 664             {
 665               fe = i;
 666               endpos = endpos - endindx; // end of end token is within this
 667               // interval
 668             }
 669             else
 670             {
 671               endindx -= endpos - iv[1]; // skip all this interval too
 672             }
 673           }
 674         }
 675       }
 676       i++;
 677     }
 678     if (fs == fe && fe == -1)
 679     {
 680       return null;
 681     }
 682     List<int[]> ranges = new ArrayList<int[]>();
 683     if (fs <= fe)
 684     {
 685       intv = fs;
 686       i = fs;
 687       // truncate initial interval
 688       iv = shiftFrom.get(intv++);
 689       iv = new int[]
 690       { iv[0], iv[1] };// clone
 691       if (i == fs)
 692       {
 693         iv[0] = startpos;
 694       }
 695       while (i != fe)
 696       {
 697         ranges.add(iv); // add initial range
 698         iv = shiftFrom.get(intv++); // get next interval
 699         iv = new int[]
 700         { iv[0], iv[1] };// clone
 701         i++;
 702       }
 703       if (i == fe)
 704       {
 705         iv[1] = endpos;
 706       }
 707       ranges.add(iv); // add only - or final range
 708     }
 709     else
 710     {
 711       // walk from end of interval.
 712       i = shiftFrom.size() - 1;
 713       while (i > fs)
 714       {
 715         i--;
 716       }
 717       iv = shiftFrom.get(i);
 718       iv = new int[]
 719       { iv[1], iv[0] };// reverse and clone
 720       // truncate initial interval
 721       if (i == fs)
 722       {
 723         iv[0] = startpos;
 724       }
 725       while (--i != fe)
 726       { // fix apparent logic bug when fe==-1
 727         ranges.add(iv); // add (truncated) reversed interval
 728         iv = shiftFrom.get(i);
 729         iv = new int[]
 730         { iv[1], iv[0] }; // reverse and clone
 731       }
 732       if (i == fe)
 733       {
 734         // interval is already reversed
 735         iv[1] = endpos;
 736       }
 737       ranges.add(iv); // add only - or final range
 738     }
 739     // create array of start end intervals.
 740     int[] range = null;
 741     if (ranges != null && ranges.size() > 0)
 742     {
 743       range = new int[ranges.size() * 2];
 744       intv = 0;
 745       intvSize = ranges.size();
 746       i = 0;
 747       while (intv < intvSize)
 748       {
 749         iv = ranges.get(intv);
 750         range[i++] = iv[0];
 751         range[i++] = iv[1];
 752         ranges.set(intv++, null); // remove
 753       }
 754     }
 755     return range;
 756   }
 757
 758   /**
 759    * get the 'initial' position of mpos in To
 760    *
 761    * @param mpos
 762    *          position in from
 763    * @return position of first word in to reference frame
 764    */
 765   public int getToPosition(int mpos)
 766   {
 767     // TODO not used - remove??
 768     int[] mp = shiftTo(mpos);
 769     if (mp != null)
 770     {
 771       return mp[0];
 772     }
 773     return mpos;
 774   }
 775
 776   /**
 777    * get range of positions in To frame for the mpos word in From
 778    *
 779    * @param mpos
 780    *          position in From
 781    * @return null or int[] first position in To for mpos, last position in to
 782    *         for Mpos
 783    */
 784   public int[] getToWord(int mpos)
 785   {
 786     int[] mp = shiftTo(mpos);
 787     if (mp != null)
 788     {
 789       return new int[]
 790       { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 791     }
 792     return null;
 793   }
 794
 795   /**
 796    * get From position in the associated reference frame for position pos in the
 797    * associated sequence.
 798    *
 799    * @param pos
 800    * @return
 801    */
 802   public int getMappedPosition(int pos)
 803   {
 804     // TODO not used - remove??
 805     int[] mp = shiftFrom(pos);
 806     if (mp != null)
 807     {
 808       return mp[0];
 809     }
 810     return pos;
 811   }
 812
 813   public int[] getMappedWord(int pos)
 814   {
 815     // TODO not used - remove??
 816     int[] mp = shiftFrom(pos);
 817     if (mp != null)
 818     {
 819       return new int[]
 820       { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 821     }
 822     return null;
 823   }
 824
 825   /**
 826    *
 827    * @return a MapList whose From range is this maplist's To Range, and vice
 828    *         versa
 829    */
 830   public MapList getInverse()
 831   {
 832     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 833             getFromRatio());
 834   }
 835
 836   /**
 837    * test for containment rather than equivalence to another mapping
 838    *
 839    * @param map
 840    *          to be tested for containment
 841    * @return true if local or mapped range map contains or is contained by this
 842    *         mapping
 843    */
 844   public boolean containsEither(boolean local, MapList map)
 845   {
 846     // TODO not used - remove?
 847     if (local)
 848     {
 849       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 850               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 851               .getFromHighest()));
 852     }
 853     else
 854     {
 855       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 856               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 857               .getToHighest()));
 858     }
 859   }
 860 }