src/jalview/util/MapList.java

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