src/jalview/commands/EditCommand.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.commands;
  22
  23 import java.util.Locale;
  24
  25 import jalview.analysis.AlignSeq;
  26 import jalview.datamodel.AlignmentAnnotation;
  27 import jalview.datamodel.AlignmentI;
  28 import jalview.datamodel.Annotation;
  29 import jalview.datamodel.ContiguousI;
  30 import jalview.datamodel.Range;
  31 import jalview.datamodel.Sequence;
  32 import jalview.datamodel.SequenceFeature;
  33 import jalview.datamodel.SequenceI;
  34 import jalview.datamodel.features.SequenceFeaturesI;
  35 import jalview.util.Comparison;
  36 import jalview.util.ReverseListIterator;
  37 import jalview.util.StringUtils;
  38
  39 import java.util.ArrayList;
  40 import java.util.HashMap;
  41 import java.util.Hashtable;
  42 import java.util.Iterator;
  43 import java.util.List;
  44 import java.util.ListIterator;
  45 import java.util.Map;
  46
  47 /**
  48  *
  49  * <p>
  50  * Title: EditCommmand
  51  * </p>
  52  *
  53  * <p>
  54  * Description: Essential information for performing undo and redo for cut/paste
  55  * insert/delete gap which can be stored in the HistoryList
  56  * </p>
  57  *
  58  * <p>
  59  * Copyright: Copyright (c) 2006
  60  * </p>
  61  *
  62  * <p>
  63  * Company: Dundee University
  64  * </p>
  65  *
  66  * @author not attributable
  67  * @version 1.0
  68  */
  69 public class EditCommand implements CommandI
  70 {
  71   public enum Action
  72   {
  73     INSERT_GAP
  74     {
  75       @Override
  76       public Action getUndoAction()
  77       {
  78         return DELETE_GAP;
  79       }
  80     },
  81     DELETE_GAP
  82     {
  83       @Override
  84       public Action getUndoAction()
  85       {
  86         return INSERT_GAP;
  87       }
  88     },
  89     CUT
  90     {
  91       @Override
  92       public Action getUndoAction()
  93       {
  94         return PASTE;
  95       }
  96     },
  97     PASTE
  98     {
  99       @Override
 100       public Action getUndoAction()
 101       {
 102         return CUT;
 103       }
 104     },
 105     REPLACE
 106     {
 107       @Override
 108       public Action getUndoAction()
 109       {
 110         return REPLACE;
 111       }
 112     },
 113     INSERT_NUC
 114     {
 115       @Override
 116       public Action getUndoAction()
 117       {
 118         return null;
 119       }
 120     };
 121
 122     public abstract Action getUndoAction();
 123   };
 124
 125   private List<Edit> edits = new ArrayList<>();
 126
 127   String description;
 128
 129   public EditCommand()
 130   {
 131   }
 132
 133   public EditCommand(String desc)
 134   {
 135     this.description = desc;
 136   }
 137
 138   public EditCommand(String desc, Action command, SequenceI[] seqs,
 139           int position, int number, AlignmentI al)
 140   {
 141     this.description = desc;
 142     if (command == Action.CUT || command == Action.PASTE)
 143     {
 144       setEdit(new Edit(command, seqs, position, number, al));
 145     }
 146
 147     performEdit(0, null);
 148   }
 149
 150   public EditCommand(String desc, Action command, String replace,
 151           SequenceI[] seqs, int position, int number, AlignmentI al)
 152   {
 153     this.description = desc;
 154     if (command == Action.REPLACE)
 155     {
 156       setEdit(new Edit(command, seqs, position, number, al, replace));
 157     }
 158
 159     performEdit(0, null);
 160   }
 161
 162   /**
 163    * Set the list of edits to the specified item (only).
 164    *
 165    * @param e
 166    */
 167   protected void setEdit(Edit e)
 168   {
 169     edits.clear();
 170     edits.add(e);
 171   }
 172
 173   /**
 174    * Add the given edit command to the stored list of commands. If simply
 175    * expanding the range of the last command added, then modify it instead of
 176    * adding a new command.
 177    *
 178    * @param e
 179    */
 180   public void addEdit(Edit e)
 181   {
 182     if (!expandEdit(edits, e))
 183     {
 184       edits.add(e);
 185     }
 186   }
 187
 188   /**
 189    * Returns true if the new edit is incorporated by updating (expanding the
 190    * range of) the last edit on the list, else false. We can 'expand' the last
 191    * edit if the new one is the same action, on the same sequences, and acts on
 192    * a contiguous range. This is the case where a mouse drag generates a series
 193    * of contiguous gap insertions or deletions.
 194    *
 195    * @param edits
 196    * @param e
 197    * @return
 198    */
 199   protected static boolean expandEdit(List<Edit> edits, Edit e)
 200   {
 201     if (edits == null || edits.isEmpty())
 202     {
 203       return false;
 204     }
 205     Edit lastEdit = edits.get(edits.size() - 1);
 206     Action action = e.command;
 207     if (lastEdit.command != action)
 208     {
 209       return false;
 210     }
 211
 212     /*
 213      * Both commands must act on the same sequences - compare the underlying
 214      * dataset sequences, rather than the aligned sequences, which change as
 215      * they are edited.
 216      */
 217     if (lastEdit.seqs.length != e.seqs.length)
 218     {
 219       return false;
 220     }
 221     for (int i = 0; i < e.seqs.length; i++)
 222     {
 223       if (lastEdit.seqs[i].getDatasetSequence() != e.seqs[i]
 224               .getDatasetSequence())
 225       {
 226         return false;
 227       }
 228     }
 229
 230     /**
 231      * Check a contiguous edit; either
 232      * <ul>
 233      * <li>a new Insert <n> positions to the right of the last <insert n>,
 234      * or</li>
 235      * <li>a new Delete <n> gaps which is <n> positions to the left of the last
 236      * delete.</li>
 237      * </ul>
 238      */
 239     boolean contiguous = (action == Action.INSERT_GAP
 240             && e.position == lastEdit.position + lastEdit.number)
 241             || (action == Action.DELETE_GAP
 242                     && e.position + e.number == lastEdit.position);
 243     if (contiguous)
 244     {
 245       /*
 246        * We are just expanding the range of the last edit. For delete gap, also
 247        * moving the start position left.
 248        */
 249       lastEdit.number += e.number;
 250       lastEdit.seqs = e.seqs;
 251       if (action == Action.DELETE_GAP)
 252       {
 253         lastEdit.position--;
 254       }
 255       return true;
 256     }
 257     return false;
 258   }
 259
 260   /**
 261    * Clear the list of stored edit commands.
 262    *
 263    */
 264   protected void clearEdits()
 265   {
 266     edits.clear();
 267   }
 268
 269   /**
 270    * Returns the i'th stored Edit command.
 271    *
 272    * @param i
 273    * @return
 274    */
 275   protected Edit getEdit(int i)
 276   {
 277     if (i >= 0 && i < edits.size())
 278     {
 279       return edits.get(i);
 280     }
 281     return null;
 282   }
 283
 284   @Override
 285   final public String getDescription()
 286   {
 287     return description;
 288   }
 289
 290   @Override
 291   public int getSize()
 292   {
 293     return edits.size();
 294   }
 295
 296   /**
 297    * Return the alignment for the first edit (or null if no edit).
 298    *
 299    * @return
 300    */
 301   final public AlignmentI getAlignment()
 302   {
 303     return (edits.isEmpty() ? null : edits.get(0).al);
 304   }
 305
 306   /**
 307    * append a new editCommand Note. this shouldn't be called if the edit is an
 308    * operation affects more alignment objects than the one referenced in al (for
 309    * example, cut or pasting whole sequences). Use the form with an additional
 310    * AlignmentI[] views parameter.
 311    *
 312    * @param command
 313    * @param seqs
 314    * @param position
 315    * @param number
 316    * @param al
 317    * @param performEdit
 318    */
 319   final public void appendEdit(Action command, SequenceI[] seqs,
 320           int position, int number, AlignmentI al, boolean performEdit)
 321   {
 322     appendEdit(command, seqs, position, number, al, performEdit, null);
 323   }
 324
 325   /**
 326    * append a new edit command with a set of alignment views that may be
 327    * operated on
 328    *
 329    * @param command
 330    * @param seqs
 331    * @param position
 332    * @param number
 333    * @param al
 334    * @param performEdit
 335    * @param views
 336    */
 337   final public void appendEdit(Action command, SequenceI[] seqs,
 338           int position, int number, AlignmentI al, boolean performEdit,
 339           AlignmentI[] views)
 340   {
 341     Edit edit = new Edit(command, seqs, position, number, al);
 342     appendEdit(edit, al, performEdit, views);
 343   }
 344
 345   /**
 346    * Overloaded method that accepts an Edit object with additional parameters.
 347    *
 348    * @param edit
 349    * @param al
 350    * @param performEdit
 351    * @param views
 352    */
 353   final public void appendEdit(Edit edit, AlignmentI al,
 354           boolean performEdit, AlignmentI[] views)
 355   {
 356     if (al.getHeight() == edit.seqs.length)
 357     {
 358       edit.al = al;
 359       edit.fullAlignmentHeight = true;
 360     }
 361
 362     addEdit(edit);
 363
 364     if (performEdit)
 365     {
 366       performEdit(edit, views);
 367     }
 368   }
 369
 370   /**
 371    * Execute all the edit commands, starting at the given commandIndex
 372    *
 373    * @param commandIndex
 374    * @param views
 375    */
 376   public final void performEdit(int commandIndex, AlignmentI[] views)
 377   {
 378     ListIterator<Edit> iterator = edits.listIterator(commandIndex);
 379     while (iterator.hasNext())
 380     {
 381       Edit edit = iterator.next();
 382       performEdit(edit, views);
 383     }
 384   }
 385
 386   /**
 387    * Execute one edit command in all the specified alignment views
 388    *
 389    * @param edit
 390    * @param views
 391    */
 392   protected static void performEdit(Edit edit, AlignmentI[] views)
 393   {
 394     switch (edit.command)
 395     {
 396     case INSERT_GAP:
 397       insertGap(edit);
 398       break;
 399     case DELETE_GAP:
 400       deleteGap(edit);
 401       break;
 402     case CUT:
 403       cut(edit, views);
 404       break;
 405     case PASTE:
 406       paste(edit, views);
 407       break;
 408     case REPLACE:
 409       replace(edit);
 410       break;
 411     case INSERT_NUC:
 412       // TODO:add deleteNuc for UNDO
 413       // case INSERT_NUC:
 414       // insertNuc(edits[e]);
 415       break;
 416     default:
 417       break;
 418     }
 419   }
 420
 421   @Override
 422   final public void doCommand(AlignmentI[] views)
 423   {
 424     performEdit(0, views);
 425   }
 426
 427   /**
 428    * Undo the stored list of commands, in reverse order.
 429    */
 430   @Override
 431   final public void undoCommand(AlignmentI[] views)
 432   {
 433     ListIterator<Edit> iterator = edits.listIterator(edits.size());
 434     while (iterator.hasPrevious())
 435     {
 436       Edit e = iterator.previous();
 437       switch (e.command)
 438       {
 439       case INSERT_GAP:
 440         deleteGap(e);
 441         break;
 442       case DELETE_GAP:
 443         insertGap(e);
 444         break;
 445       case CUT:
 446         paste(e, views);
 447         break;
 448       case PASTE:
 449         cut(e, views);
 450         break;
 451       case REPLACE:
 452         replace(e);
 453         break;
 454       case INSERT_NUC:
 455         // not implemented
 456         break;
 457       default:
 458         break;
 459       }
 460     }
 461   }
 462
 463   /**
 464    * Insert gap(s) in sequences as specified by the command, and adjust
 465    * annotations.
 466    *
 467    * @param command
 468    */
 469   final private static void insertGap(Edit command)
 470   {
 471
 472     for (int s = 0; s < command.seqs.length; s++)
 473     {
 474       command.seqs[s].insertCharAt(command.position, command.number,
 475               command.gapChar);
 476       // System.out.println("pos: "+command.position+" number:
 477       // "+command.number);
 478     }
 479
 480     adjustAnnotations(command, true, false, null);
 481   }
 482
 483   //
 484   // final void insertNuc(Edit command)
 485   // {
 486   //
 487   // for (int s = 0; s < command.seqs.length; s++)
 488   // {
 489   // System.out.println("pos: "+command.position+" number: "+command.number);
 490   // command.seqs[s].insertCharAt(command.position, command.number,'A');
 491   // }
 492   //
 493   // adjustAnnotations(command, true, false, null);
 494   // }
 495
 496   /**
 497    * Delete gap(s) in sequences as specified by the command, and adjust
 498    * annotations.
 499    *
 500    * @param command
 501    */
 502   final static private void deleteGap(Edit command)
 503   {
 504     for (int s = 0; s < command.seqs.length; s++)
 505     {
 506       command.seqs[s].deleteChars(command.position,
 507               command.position + command.number);
 508     }
 509
 510     adjustAnnotations(command, false, false, null);
 511   }
 512
 513   /**
 514    * Carry out a Cut action. The cut characters are saved in case Undo is
 515    * requested.
 516    *
 517    * @param command
 518    * @param views
 519    */
 520   static void cut(Edit command, AlignmentI[] views)
 521   {
 522     boolean seqDeleted = false;
 523     command.string = new char[command.seqs.length][];
 524
 525     for (int i = 0; i < command.seqs.length; i++)
 526     {
 527       final SequenceI sequence = command.seqs[i];
 528       if (sequence.getLength() > command.position)
 529       {
 530         command.string[i] = sequence.getSequence(command.position,
 531                 command.position + command.number);
 532         SequenceI oldds = sequence.getDatasetSequence();
 533         ContiguousI cutPositions = sequence.findPositions(
 534                 command.position + 1, command.position + command.number);
 535         boolean cutIsInternal = cutPositions != null
 536                 && sequence.getStart() != cutPositions.getBegin()
 537                 && sequence.getEnd() != cutPositions.getEnd();
 538
 539         /*
 540          * perform the cut; if this results in a new dataset sequence, add
 541          * that to the alignment dataset
 542          */
 543         SequenceI ds = sequence.getDatasetSequence();
 544         sequence.deleteChars(command.position,
 545                 command.position + command.number);
 546
 547         if (command.oldds != null && command.oldds[i] != null)
 548         {
 549           /*
 550            * we are Redoing a Cut, or Undoing a Paste - so
 551            * oldds entry contains the cut dataset sequence,
 552            * with sequence features in expected place
 553            */
 554           sequence.setDatasetSequence(command.oldds[i]);
 555           command.oldds[i] = oldds;
 556         }
 557         else
 558         {
 559           /*
 560            * new cut operation: save the dataset sequence
 561            * so it can be restored in an Undo
 562            */
 563           if (command.oldds == null)
 564           {
 565             command.oldds = new SequenceI[command.seqs.length];
 566           }
 567           command.oldds[i] = oldds;// todo not if !cutIsInternal?
 568
 569           // do we need to edit sequence features for new sequence ?
 570           if (oldds != sequence.getDatasetSequence() || (cutIsInternal
 571                   && sequence.getFeatures().hasFeatures()))
 572           // todo or just test cutIsInternal && cutPositions != null ?
 573           {
 574             if (cutPositions != null)
 575             {
 576               cutFeatures(command, sequence, cutPositions.getBegin(),
 577                       cutPositions.getEnd(), cutIsInternal);
 578             }
 579           }
 580         }
 581         SequenceI newDs = sequence.getDatasetSequence();
 582         if (newDs != ds && command.al != null
 583                 && command.al.getDataset() != null
 584                 && !command.al.getDataset().getSequences().contains(newDs))
 585         {
 586           command.al.getDataset().addSequence(newDs);
 587         }
 588       }
 589
 590       if (sequence.getLength() < 1)
 591       {
 592         command.al.deleteSequence(sequence);
 593         seqDeleted = true;
 594       }
 595     }
 596
 597     adjustAnnotations(command, false, seqDeleted, views);
 598   }
 599
 600   /**
 601    * Perform the given Paste command. This may be to add cut or copied sequences
 602    * to an alignment, or to undo a 'Cut' action on a region of the alignment.
 603    *
 604    * @param command
 605    * @param views
 606    */
 607   static void paste(Edit command, AlignmentI[] views)
 608   {
 609     boolean seqWasDeleted = false;
 610
 611     for (int i = 0; i < command.seqs.length; i++)
 612     {
 613       boolean newDSNeeded = false;
 614       boolean newDSWasNeeded = command.oldds != null
 615               && command.oldds[i] != null;
 616       SequenceI sequence = command.seqs[i];
 617       if (sequence.getLength() < 1)
 618       {
 619         /*
 620          * sequence was deleted; re-add it to the alignment
 621          */
 622         if (command.alIndex[i] < command.al.getHeight())
 623         {
 624           List<SequenceI> sequences = command.al.getSequences();
 625           synchronized (sequences)
 626           {
 627             if (!(command.alIndex[i] < 0))
 628             {
 629               sequences.add(command.alIndex[i], sequence);
 630             }
 631           }
 632         }
 633         else
 634         {
 635           command.al.addSequence(sequence);
 636         }
 637         seqWasDeleted = true;
 638       }
 639       int newStart = sequence.getStart();
 640       int newEnd = sequence.getEnd();
 641
 642       StringBuilder tmp = new StringBuilder();
 643       tmp.append(sequence.getSequence());
 644       // Undo of a delete does not replace original dataset sequence on to
 645       // alignment sequence.
 646
 647       int start = 0;
 648       int length = 0;
 649
 650       if (command.string != null && command.string[i] != null)
 651       {
 652         if (command.position >= tmp.length())
 653         {
 654           // This occurs if padding is on, and residues
 655           // are removed from end of alignment
 656           int len = command.position - tmp.length();
 657           while (len > 0)
 658           {
 659             tmp.append(command.gapChar);
 660             len--;
 661           }
 662         }
 663         tmp.insert(command.position, command.string[i]);
 664         for (int s = 0; s < command.string[i].length; s++)
 665         {
 666           if (!Comparison.isGap(command.string[i][s]))
 667           {
 668             length++;
 669             if (!newDSNeeded)
 670             {
 671               newDSNeeded = true;
 672               start = sequence.findPosition(command.position);
 673               // end = sequence
 674               // .findPosition(command.position + command.number);
 675             }
 676             if (sequence.getStart() == start)
 677             {
 678               newStart--;
 679             }
 680             else
 681             {
 682               newEnd++;
 683             }
 684           }
 685         }
 686         command.string[i] = null;
 687       }
 688
 689       sequence.setSequence(tmp.toString());
 690       sequence.setStart(newStart);
 691       sequence.setEnd(newEnd);
 692
 693       /*
 694        * command and Undo share the same dataset sequence if cut was
 695        * at start or end of sequence
 696        */
 697       boolean sameDatasetSequence = false;
 698       if (newDSNeeded)
 699       {
 700         if (sequence.getDatasetSequence() != null)
 701         {
 702           SequenceI ds;
 703           if (newDSWasNeeded)
 704           {
 705             ds = command.oldds[i];
 706           }
 707           else
 708           {
 709             // make a new DS sequence
 710             // use new ds mechanism here
 711             String ungapped = AlignSeq.extractGaps(Comparison.GapChars,
 712                     sequence.getSequenceAsString());
 713             ds = new Sequence(sequence.getName(), ungapped,
 714                     sequence.getStart(), sequence.getEnd());
 715             ds.setDescription(sequence.getDescription());
 716           }
 717           if (command.oldds == null)
 718           {
 719             command.oldds = new SequenceI[command.seqs.length];
 720           }
 721           command.oldds[i] = sequence.getDatasetSequence();
 722           sameDatasetSequence = ds == sequence.getDatasetSequence();
 723           ds.setSequenceFeatures(sequence.getSequenceFeatures());
 724           if (!sameDatasetSequence && command.al.getDataset() != null)
 725           {
 726             // delete 'undone' sequence from alignment dataset
 727             command.al.getDataset()
 728                     .deleteSequence(sequence.getDatasetSequence());
 729           }
 730           sequence.setDatasetSequence(ds);
 731         }
 732         undoCutFeatures(command, command.seqs[i], start, length,
 733                 sameDatasetSequence);
 734       }
 735     }
 736     adjustAnnotations(command, true, seqWasDeleted, views);
 737
 738     command.string = null;
 739   }
 740
 741   static void replace(Edit command)
 742   {
 743     StringBuilder tmp;
 744     String oldstring;
 745     int start = command.position;
 746     int end = command.number;
 747     // TODO TUTORIAL - Fix for replacement with different length of sequence (or
 748     // whole sequence)
 749     // TODO Jalview 2.4 bugfix change to an aggregate command - original
 750     // sequence string is cut, new string is pasted in.
 751     command.number = start + command.string[0].length;
 752     for (int i = 0; i < command.seqs.length; i++)
 753     {
 754       boolean newDSWasNeeded = command.oldds != null
 755               && command.oldds[i] != null;
 756       boolean newStartEndWasNeeded = command.oldStartEnd != null
 757               && command.oldStartEnd[i] != null;
 758
 759       /**
 760        * cut addHistoryItem(new EditCommand("Cut Sequences", EditCommand.CUT,
 761        * cut, sg.getStartRes(), sg.getEndRes()-sg.getStartRes()+1,
 762        * viewport.alignment));
 763        *
 764        */
 765       /**
 766        * then addHistoryItem(new EditCommand( "Add sequences",
 767        * EditCommand.PASTE, sequences, 0, alignment.getWidth(), alignment) );
 768        *
 769        */
 770       ContiguousI beforeEditedPositions = command.seqs[i].findPositions(1,
 771               start);
 772       ContiguousI afterEditedPositions = command.seqs[i]
 773               .findPositions(end + 1, command.seqs[i].getLength());
 774
 775       oldstring = command.seqs[i].getSequenceAsString();
 776       tmp = new StringBuilder(oldstring.substring(0, start));
 777       tmp.append(command.string[i]);
 778       String nogaprep = AlignSeq.extractGaps(Comparison.GapChars,
 779               new String(command.string[i]));
 780       if (end < oldstring.length())
 781       {
 782         tmp.append(oldstring.substring(end));
 783       }
 784       // stash end prior to updating the sequence object so we can save it if
 785       // need be.
 786       Range oldstartend = new Range(command.seqs[i].getStart(),
 787               command.seqs[i].getEnd());
 788       command.seqs[i].setSequence(tmp.toString());
 789       command.string[i] = oldstring
 790               .substring(start, Math.min(end, oldstring.length()))
 791               .toCharArray();
 792       String nogapold = AlignSeq.extractGaps(Comparison.GapChars,
 793               new String(command.string[i]));
 794
 795       if (!nogaprep.toLowerCase(Locale.ROOT)
 796               .equals(nogapold.toLowerCase(Locale.ROOT)))
 797       {
 798         // we may already have dataset and limits stashed...
 799         if (newDSWasNeeded || newStartEndWasNeeded)
 800         {
 801           if (newDSWasNeeded)
 802           {
 803             // then just switch the dataset sequence
 804             SequenceI oldds = command.seqs[i].getDatasetSequence();
 805             command.seqs[i].setDatasetSequence(command.oldds[i]);
 806             command.oldds[i] = oldds;
 807           }
 808           if (newStartEndWasNeeded)
 809           {
 810             Range newStart = command.oldStartEnd[i];
 811             command.oldStartEnd[i] = oldstartend;
 812             command.seqs[i].setStart(newStart.getBegin());
 813             command.seqs[i].setEnd(newStart.getEnd());
 814           }
 815         }
 816         else
 817         {
 818           // decide if we need a new dataset sequence or modify start/end
 819           // first edit the original dataset sequence string
 820           SequenceI oldds = command.seqs[i].getDatasetSequence();
 821           String osp = oldds.getSequenceAsString();
 822           int beforeStartOfEdit = -oldds.getStart() + 1
 823                   + (beforeEditedPositions == null
 824                           ? ((afterEditedPositions != null)
 825                                   ? afterEditedPositions.getBegin() - 1
 826                                   : oldstartend.getBegin()
 827                                           + nogapold.length())
 828                           : beforeEditedPositions.getEnd());
 829           int afterEndOfEdit = -oldds.getStart() + 1
 830                   + ((afterEditedPositions == null) ? oldstartend.getEnd()
 831                           : afterEditedPositions.getBegin() - 1);
 832           String fullseq = osp.substring(0, beforeStartOfEdit) + nogaprep
 833                   + osp.substring(afterEndOfEdit);
 834
 835           // and check if new sequence data is different..
 836           if (!fullseq.equalsIgnoreCase(osp))
 837           {
 838             // old ds and edited ds are different, so
 839             // create the new dataset sequence
 840             SequenceI newds = new Sequence(oldds);
 841             newds.setSequence(fullseq.toUpperCase(Locale.ROOT));
 842
 843             if (command.oldds == null)
 844             {
 845               command.oldds = new SequenceI[command.seqs.length];
 846             }
 847             command.oldds[i] = command.seqs[i].getDatasetSequence();
 848
 849             // And preserve start/end for good-measure
 850
 851             if (command.oldStartEnd == null)
 852             {
 853               command.oldStartEnd = new Range[command.seqs.length];
 854             }
 855             command.oldStartEnd[i] = oldstartend;
 856             // TODO: JAL-1131 ensure newly created dataset sequence is added to
 857             // the set of
 858             // dataset sequences associated with the alignment.
 859             // TODO: JAL-1131 fix up any annotation associated with new dataset
 860             // sequence to ensure that original sequence/annotation
 861             // relationships
 862             // are preserved.
 863             command.seqs[i].setDatasetSequence(newds);
 864           }
 865           else
 866           {
 867             if (command.oldStartEnd == null)
 868             {
 869               command.oldStartEnd = new Range[command.seqs.length];
 870             }
 871             command.oldStartEnd[i] = new Range(command.seqs[i].getStart(),
 872                     command.seqs[i].getEnd());
 873             if (beforeEditedPositions != null
 874                     && afterEditedPositions == null)
 875             {
 876               // modification at end
 877               command.seqs[i].setEnd(beforeEditedPositions.getEnd()
 878                       + nogaprep.length() - nogapold.length());
 879             }
 880             else if (afterEditedPositions != null
 881                     && beforeEditedPositions == null)
 882             {
 883               // modification at start
 884               command.seqs[i].setStart(
 885                       afterEditedPositions.getBegin() - nogaprep.length());
 886             }
 887             else
 888             {
 889               // edit covered both start and end. Here we can only guess the
 890               // new
 891               // start/end
 892               String nogapalseq = AlignSeq.extractGaps(Comparison.GapChars,
 893                       command.seqs[i].getSequenceAsString()
 894                               .toUpperCase(Locale.ROOT));
 895               int newStart = command.seqs[i].getDatasetSequence()
 896                       .getSequenceAsString().indexOf(nogapalseq);
 897               if (newStart == -1)
 898               {
 899                 throw new Error(
 900                         "Implementation Error: could not locate start/end "
 901                                 + "in dataset sequence after an edit of the sequence string");
 902               }
 903               int newEnd = newStart + nogapalseq.length() - 1;
 904               command.seqs[i].setStart(newStart);
 905               command.seqs[i].setEnd(newEnd);
 906             }
 907           }
 908         }
 909       }
 910       tmp = null;
 911       oldstring = null;
 912     }
 913   }
 914
 915   final static void adjustAnnotations(Edit command, boolean insert,
 916           boolean modifyVisibility, AlignmentI[] views)
 917   {
 918     AlignmentAnnotation[] annotations = null;
 919
 920     if (modifyVisibility && !insert)
 921     {
 922       // only occurs if a sequence was added or deleted.
 923       command.deletedAnnotationRows = new Hashtable<>();
 924     }
 925     if (command.fullAlignmentHeight)
 926     {
 927       annotations = command.al.getAlignmentAnnotation();
 928     }
 929     else
 930     {
 931       int aSize = 0;
 932       AlignmentAnnotation[] tmp;
 933       for (int s = 0; s < command.seqs.length; s++)
 934       {
 935         command.seqs[s].sequenceChanged();
 936
 937         if (modifyVisibility)
 938         {
 939           // Rows are only removed or added to sequence object.
 940           if (!insert)
 941           {
 942             // remove rows
 943             tmp = command.seqs[s].getAnnotation();
 944             if (tmp != null)
 945             {
 946               int alen = tmp.length;
 947               for (int aa = 0; aa < tmp.length; aa++)
 948               {
 949                 if (!command.al.deleteAnnotation(tmp[aa]))
 950                 {
 951                   // strip out annotation not in the current al (will be put
 952                   // back on insert in all views)
 953                   tmp[aa] = null;
 954                   alen--;
 955                 }
 956               }
 957               command.seqs[s].setAlignmentAnnotation(null);
 958               if (alen != tmp.length)
 959               {
 960                 // save the non-null annotation references only
 961                 AlignmentAnnotation[] saved = new AlignmentAnnotation[alen];
 962                 for (int aa = 0, aapos = 0; aa < tmp.length; aa++)
 963                 {
 964                   if (tmp[aa] != null)
 965                   {
 966                     saved[aapos++] = tmp[aa];
 967                     tmp[aa] = null;
 968                   }
 969                 }
 970                 tmp = saved;
 971                 command.deletedAnnotationRows.put(command.seqs[s], saved);
 972                 // and then remove any annotation in the other views
 973                 for (int alview = 0; views != null
 974                         && alview < views.length; alview++)
 975                 {
 976                   if (views[alview] != command.al)
 977                   {
 978                     AlignmentAnnotation[] toremove = views[alview]
 979                             .getAlignmentAnnotation();
 980                     if (toremove == null || toremove.length == 0)
 981                     {
 982                       continue;
 983                     }
 984                     // remove any alignment annotation on this sequence that's
 985                     // on that alignment view.
 986                     for (int aa = 0; aa < toremove.length; aa++)
 987                     {
 988                       if (toremove[aa].sequenceRef == command.seqs[s])
 989                       {
 990                         views[alview].deleteAnnotation(toremove[aa]);
 991                       }
 992                     }
 993                   }
 994                 }
 995               }
 996               else
 997               {
 998                 // save all the annotation
 999                 command.deletedAnnotationRows.put(command.seqs[s], tmp);
1000               }
1001             }
1002           }
1003           else
1004           {
1005             // recover rows
1006             if (command.deletedAnnotationRows != null
1007                     && command.deletedAnnotationRows
1008                             .containsKey(command.seqs[s]))
1009             {
1010               AlignmentAnnotation[] revealed = command.deletedAnnotationRows
1011                       .get(command.seqs[s]);
1012               command.seqs[s].setAlignmentAnnotation(revealed);
1013               if (revealed != null)
1014               {
1015                 for (int aa = 0; aa < revealed.length; aa++)
1016                 {
1017                   // iterate through al adding original annotation
1018                   command.al.addAnnotation(revealed[aa]);
1019                 }
1020                 for (int aa = 0; aa < revealed.length; aa++)
1021                 {
1022                   command.al.setAnnotationIndex(revealed[aa], aa);
1023                 }
1024                 // and then duplicate added annotation on every other alignment
1025                 // view
1026                 for (int vnum = 0; views != null
1027                         && vnum < views.length; vnum++)
1028                 {
1029                   if (views[vnum] != command.al)
1030                   {
1031                     int avwidth = views[vnum].getWidth() + 1;
1032                     // duplicate in this view
1033                     for (int a = 0; a < revealed.length; a++)
1034                     {
1035                       AlignmentAnnotation newann = new AlignmentAnnotation(
1036                               revealed[a]);
1037                       command.seqs[s].addAlignmentAnnotation(newann);
1038                       newann.padAnnotation(avwidth);
1039                       views[vnum].addAnnotation(newann);
1040                       views[vnum].setAnnotationIndex(newann, a);
1041                     }
1042                   }
1043                 }
1044               }
1045             }
1046           }
1047           continue;
1048         }
1049
1050         if (command.seqs[s].getAnnotation() == null)
1051         {
1052           continue;
1053         }
1054
1055         if (aSize == 0)
1056         {
1057           annotations = command.seqs[s].getAnnotation();
1058         }
1059         else
1060         {
1061           tmp = new AlignmentAnnotation[aSize
1062                   + command.seqs[s].getAnnotation().length];
1063
1064           System.arraycopy(annotations, 0, tmp, 0, aSize);
1065
1066           System.arraycopy(command.seqs[s].getAnnotation(), 0, tmp, aSize,
1067                   command.seqs[s].getAnnotation().length);
1068
1069           annotations = tmp;
1070         }
1071         aSize = annotations.length;
1072       }
1073     }
1074
1075     if (annotations == null)
1076     {
1077       return;
1078     }
1079
1080     if (!insert)
1081     {
1082       command.deletedAnnotations = new Hashtable<>();
1083     }
1084
1085     int aSize;
1086     Annotation[] temp;
1087     for (int a = 0; a < annotations.length; a++)
1088     {
1089       if (annotations[a].autoCalculated
1090               || annotations[a].annotations == null)
1091       {
1092         continue;
1093       }
1094
1095       int tSize = 0;
1096
1097       aSize = annotations[a].annotations.length;
1098       if (insert)
1099       {
1100         temp = new Annotation[aSize + command.number];
1101         if (annotations[a].padGaps)
1102         {
1103           for (int aa = 0; aa < temp.length; aa++)
1104           {
1105             temp[aa] = new Annotation(command.gapChar + "", null, ' ', 0);
1106           }
1107         }
1108       }
1109       else
1110       {
1111         if (command.position < aSize)
1112         {
1113           if (command.position + command.number >= aSize)
1114           {
1115             tSize = aSize;
1116           }
1117           else
1118           {
1119             tSize = aSize - command.number;
1120           }
1121         }
1122         else
1123         {
1124           tSize = aSize;
1125         }
1126
1127         if (tSize < 0)
1128         {
1129           tSize = aSize;
1130         }
1131         temp = new Annotation[tSize];
1132       }
1133
1134       if (insert)
1135       {
1136         if (command.position < annotations[a].annotations.length)
1137         {
1138           System.arraycopy(annotations[a].annotations, 0, temp, 0,
1139                   command.position);
1140
1141           if (command.deletedAnnotations != null
1142                   && command.deletedAnnotations
1143                           .containsKey(annotations[a].annotationId))
1144           {
1145             Annotation[] restore = command.deletedAnnotations
1146                     .get(annotations[a].annotationId);
1147
1148             System.arraycopy(restore, 0, temp, command.position,
1149                     command.number);
1150
1151           }
1152
1153           System.arraycopy(annotations[a].annotations, command.position,
1154                   temp, command.position + command.number,
1155                   aSize - command.position);
1156         }
1157         else
1158         {
1159           if (command.deletedAnnotations != null
1160                   && command.deletedAnnotations
1161                           .containsKey(annotations[a].annotationId))
1162           {
1163             Annotation[] restore = command.deletedAnnotations
1164                     .get(annotations[a].annotationId);
1165
1166             temp = new Annotation[annotations[a].annotations.length
1167                     + restore.length];
1168             System.arraycopy(annotations[a].annotations, 0, temp, 0,
1169                     annotations[a].annotations.length);
1170             System.arraycopy(restore, 0, temp,
1171                     annotations[a].annotations.length, restore.length);
1172           }
1173           else
1174           {
1175             temp = annotations[a].annotations;
1176           }
1177         }
1178       }
1179       else
1180       {
1181         if (tSize != aSize || command.position < 2)
1182         {
1183           int copylen = Math.min(command.position,
1184                   annotations[a].annotations.length);
1185           if (copylen > 0)
1186           {
1187             System.arraycopy(annotations[a].annotations, 0, temp, 0,
1188                     copylen); // command.position);
1189           }
1190
1191           Annotation[] deleted = new Annotation[command.number];
1192           if (copylen >= command.position)
1193           {
1194             copylen = Math.min(command.number,
1195                     annotations[a].annotations.length - command.position);
1196             if (copylen > 0)
1197             {
1198               System.arraycopy(annotations[a].annotations, command.position,
1199                       deleted, 0, copylen); // command.number);
1200             }
1201           }
1202
1203           command.deletedAnnotations.put(annotations[a].annotationId,
1204                   deleted);
1205           if (annotations[a].annotations.length > command.position
1206                   + command.number)
1207           {
1208             System.arraycopy(annotations[a].annotations,
1209                     command.position + command.number, temp,
1210                     command.position, annotations[a].annotations.length
1211                             - command.position - command.number); // aSize
1212           }
1213         }
1214         else
1215         {
1216           int dSize = aSize - command.position;
1217
1218           if (dSize > 0)
1219           {
1220             Annotation[] deleted = new Annotation[command.number];
1221             System.arraycopy(annotations[a].annotations, command.position,
1222                     deleted, 0, dSize);
1223
1224             command.deletedAnnotations.put(annotations[a].annotationId,
1225                     deleted);
1226
1227             tSize = Math.min(annotations[a].annotations.length,
1228                     command.position);
1229             temp = new Annotation[tSize];
1230             System.arraycopy(annotations[a].annotations, 0, temp, 0, tSize);
1231           }
1232           else
1233           {
1234             temp = annotations[a].annotations;
1235           }
1236         }
1237       }
1238
1239       annotations[a].annotations = temp;
1240     }
1241   }
1242
1243   /**
1244    * Restores features to the state before a Cut.
1245    * <ul>
1246    * <li>re-add any features deleted by the cut</li>
1247    * <li>remove any truncated features created by the cut</li>
1248    * <li>shift right any features to the right of the cut</li>
1249    * </ul>
1250    *
1251    * @param command
1252    *          the Cut command
1253    * @param seq
1254    *          the sequence the Cut applied to
1255    * @param start
1256    *          the start residue position of the cut
1257    * @param length
1258    *          the number of residues cut
1259    * @param sameDatasetSequence
1260    *          true if dataset sequence and frame of reference were left
1261    *          unchanged by the Cut
1262    */
1263   final static void undoCutFeatures(Edit command, SequenceI seq,
1264           final int start, final int length, boolean sameDatasetSequence)
1265   {
1266     SequenceI sequence = seq.getDatasetSequence();
1267     if (sequence == null)
1268     {
1269       sequence = seq;
1270     }
1271
1272     /*
1273      * shift right features that lie to the right of the restored cut (but not
1274      * if dataset sequence unchanged - so coordinates were changed by Cut)
1275      */
1276     if (!sameDatasetSequence)
1277     {
1278       /*
1279        * shift right all features right of and not
1280        * contiguous with the cut position
1281        */
1282       seq.getFeatures().shiftFeatures(start + 1, length);
1283
1284       /*
1285        * shift right any features that start at the cut position,
1286        * unless they were truncated
1287        */
1288       List<SequenceFeature> sfs = seq.getFeatures().findFeatures(start,
1289               start);
1290       for (SequenceFeature sf : sfs)
1291       {
1292         if (sf.getBegin() == start)
1293         {
1294           if (!command.truncatedFeatures.containsKey(seq)
1295                   || !command.truncatedFeatures.get(seq).contains(sf))
1296           {
1297             /*
1298              * feature was shifted left to cut position (not truncated),
1299              * so shift it back right
1300              */
1301             SequenceFeature shifted = new SequenceFeature(sf,
1302                     sf.getBegin() + length, sf.getEnd() + length,
1303                     sf.getFeatureGroup(), sf.getScore());
1304             seq.addSequenceFeature(shifted);
1305             seq.deleteFeature(sf);
1306           }
1307         }
1308       }
1309     }
1310
1311     /*
1312      * restore any features that were deleted or truncated
1313      */
1314     if (command.deletedFeatures != null
1315             && command.deletedFeatures.containsKey(seq))
1316     {
1317       for (SequenceFeature deleted : command.deletedFeatures.get(seq))
1318       {
1319         sequence.addSequenceFeature(deleted);
1320       }
1321     }
1322
1323     /*
1324      * delete any truncated features
1325      */
1326     if (command.truncatedFeatures != null
1327             && command.truncatedFeatures.containsKey(seq))
1328     {
1329       for (SequenceFeature amended : command.truncatedFeatures.get(seq))
1330       {
1331         sequence.deleteFeature(amended);
1332       }
1333     }
1334   }
1335
1336   /**
1337    * Returns the list of edit commands wrapped by this object.
1338    *
1339    * @return
1340    */
1341   public List<Edit> getEdits()
1342   {
1343     return this.edits;
1344   }
1345
1346   /**
1347    * Returns a map whose keys are the dataset sequences, and values their
1348    * aligned sequences before the command edit list was applied. The aligned
1349    * sequences are copies, which may be updated without affecting the originals.
1350    *
1351    * The command holds references to the aligned sequences (after editing). If
1352    * the command is an 'undo',then the prior state is simply the aligned state.
1353    * Otherwise, we have to derive the prior state by working backwards through
1354    * the edit list to infer the aligned sequences before editing.
1355    *
1356    * Note: an alternative solution would be to cache the 'before' state of each
1357    * edit, but this would be expensive in space in the common case that the
1358    * original is never needed (edits are not mirrored).
1359    *
1360    * @return
1361    * @throws IllegalStateException
1362    *           on detecting an edit command of a type that can't be unwound
1363    */
1364   public Map<SequenceI, SequenceI> priorState(boolean forUndo)
1365   {
1366     Map<SequenceI, SequenceI> result = new HashMap<>();
1367     if (getEdits() == null)
1368     {
1369       return result;
1370     }
1371     if (forUndo)
1372     {
1373       for (Edit e : getEdits())
1374       {
1375         for (SequenceI seq : e.getSequences())
1376         {
1377           SequenceI ds = seq.getDatasetSequence();
1378           // SequenceI preEdit = result.get(ds);
1379           if (!result.containsKey(ds))
1380           {
1381             /*
1382              * copy sequence including start/end (but don't use copy constructor
1383              * as we don't need annotations)
1384              */
1385             SequenceI preEdit = new Sequence("", seq.getSequenceAsString(),
1386                     seq.getStart(), seq.getEnd());
1387             preEdit.setDatasetSequence(ds);
1388             result.put(ds, preEdit);
1389           }
1390         }
1391       }
1392       return result;
1393     }
1394
1395     /*
1396      * Work backwards through the edit list, deriving the sequences before each
1397      * was applied. The final result is the sequence set before any edits.
1398      */
1399     Iterator<Edit> editList = new ReverseListIterator<>(getEdits());
1400     while (editList.hasNext())
1401     {
1402       Edit oldEdit = editList.next();
1403       Action action = oldEdit.getAction();
1404       int position = oldEdit.getPosition();
1405       int number = oldEdit.getNumber();
1406       final char gap = oldEdit.getGapCharacter();
1407       for (SequenceI seq : oldEdit.getSequences())
1408       {
1409         SequenceI ds = seq.getDatasetSequence();
1410         SequenceI preEdit = result.get(ds);
1411         if (preEdit == null)
1412         {
1413           preEdit = new Sequence("", seq.getSequenceAsString(),
1414                   seq.getStart(), seq.getEnd());
1415           preEdit.setDatasetSequence(ds);
1416           result.put(ds, preEdit);
1417         }
1418         /*
1419          * 'Undo' this edit action on the sequence (updating the value in the
1420          * map).
1421          */
1422         if (ds != null)
1423         {
1424           if (action == Action.DELETE_GAP)
1425           {
1426             preEdit.setSequence(new String(StringUtils.insertCharAt(
1427                     preEdit.getSequence(), position, number, gap)));
1428           }
1429           else if (action == Action.INSERT_GAP)
1430           {
1431             preEdit.setSequence(new String(StringUtils.deleteChars(
1432                     preEdit.getSequence(), position, position + number)));
1433           }
1434           else
1435           {
1436             System.err.println("Can't undo edit action " + action);
1437             // throw new IllegalStateException("Can't undo edit action " +
1438             // action);
1439           }
1440         }
1441       }
1442     }
1443     return result;
1444   }
1445
1446   public class Edit
1447   {
1448     SequenceI[] oldds;
1449
1450     /**
1451      * start and end of sequence prior to edit
1452      */
1453     Range[] oldStartEnd;
1454
1455     boolean fullAlignmentHeight = false;
1456
1457     Map<SequenceI, AlignmentAnnotation[]> deletedAnnotationRows;
1458
1459     Map<String, Annotation[]> deletedAnnotations;
1460
1461     /*
1462      * features deleted by the cut (re-add on Undo)
1463      * (including the original of any shortened features)
1464      */
1465     Map<SequenceI, List<SequenceFeature>> deletedFeatures;
1466
1467     /*
1468      * shortened features added by the cut (delete on Undo)
1469      */
1470     Map<SequenceI, List<SequenceFeature>> truncatedFeatures;
1471
1472     AlignmentI al;
1473
1474     final Action command;
1475
1476     char[][] string;
1477
1478     SequenceI[] seqs;
1479
1480     int[] alIndex;
1481
1482     int position;
1483
1484     int number;
1485
1486     char gapChar;
1487
1488     /*
1489      * flag that identifies edits inserted to balance
1490      * user edits in a 'locked editing' region
1491      */
1492     private boolean systemGenerated;
1493
1494     public Edit(Action cmd, SequenceI[] sqs, int pos, int count, char gap)
1495     {
1496       this.command = cmd;
1497       this.seqs = sqs;
1498       this.position = pos;
1499       this.number = count;
1500       this.gapChar = gap;
1501     }
1502
1503     Edit(Action cmd, SequenceI[] sqs, int pos, int count, AlignmentI align)
1504     {
1505       this(cmd, sqs, pos, count, align.getGapCharacter());
1506
1507       this.al = align;
1508
1509       alIndex = new int[sqs.length];
1510       for (int i = 0; i < sqs.length; i++)
1511       {
1512         alIndex[i] = align.findIndex(sqs[i]);
1513       }
1514
1515       fullAlignmentHeight = (align.getHeight() == sqs.length);
1516     }
1517
1518     /**
1519      * Constructor given a REPLACE command and the replacement string
1520      *
1521      * @param cmd
1522      * @param sqs
1523      * @param pos
1524      * @param count
1525      * @param align
1526      * @param replace
1527      */
1528     Edit(Action cmd, SequenceI[] sqs, int pos, int count, AlignmentI align,
1529             String replace)
1530     {
1531       this(cmd, sqs, pos, count, align);
1532
1533       string = new char[sqs.length][];
1534       for (int i = 0; i < sqs.length; i++)
1535       {
1536         string[i] = replace.toCharArray();
1537       }
1538     }
1539
1540     public SequenceI[] getSequences()
1541     {
1542       return seqs;
1543     }
1544
1545     public int getPosition()
1546     {
1547       return position;
1548     }
1549
1550     public Action getAction()
1551     {
1552       return command;
1553     }
1554
1555     public int getNumber()
1556     {
1557       return number;
1558     }
1559
1560     public char getGapCharacter()
1561     {
1562       return gapChar;
1563     }
1564
1565     public void setSystemGenerated(boolean b)
1566     {
1567       systemGenerated = b;
1568     }
1569
1570     public boolean isSystemGenerated()
1571     {
1572       return systemGenerated;
1573     }
1574   }
1575
1576   /**
1577    * Returns an iterator over the list of edit commands which traverses the list
1578    * either forwards or backwards.
1579    *
1580    * @param forwards
1581    * @return
1582    */
1583   public Iterator<Edit> getEditIterator(boolean forwards)
1584   {
1585     if (forwards)
1586     {
1587       return getEdits().iterator();
1588     }
1589     else
1590     {
1591       return new ReverseListIterator<>(getEdits());
1592     }
1593   }
1594
1595   /**
1596    * Adjusts features for Cut, and saves details of changes made to allow Undo
1597    * <ul>
1598    * <li>features left of the cut are unchanged</li>
1599    * <li>features right of the cut are shifted left</li>
1600    * <li>features internal to the cut region are deleted</li>
1601    * <li>features that overlap or span the cut are shortened</li>
1602    * <li>the originals of any deleted or shortened features are saved, to re-add
1603    * on Undo</li>
1604    * <li>any added (shortened) features are saved, to delete on Undo</li>
1605    * </ul>
1606    *
1607    * @param command
1608    * @param seq
1609    * @param fromPosition
1610    * @param toPosition
1611    * @param cutIsInternal
1612    */
1613   protected static void cutFeatures(Edit command, SequenceI seq,
1614           int fromPosition, int toPosition, boolean cutIsInternal)
1615   {
1616     /*
1617      * if the cut is at start or end of sequence
1618      * then we don't modify the sequence feature store
1619      */
1620     if (!cutIsInternal)
1621     {
1622       return;
1623     }
1624     List<SequenceFeature> added = new ArrayList<>();
1625     List<SequenceFeature> removed = new ArrayList<>();
1626
1627     SequenceFeaturesI featureStore = seq.getFeatures();
1628     if (toPosition < fromPosition || featureStore == null)
1629     {
1630       return;
1631     }
1632
1633     int cutStartPos = fromPosition;
1634     int cutEndPos = toPosition;
1635     int cutWidth = cutEndPos - cutStartPos + 1;
1636
1637     synchronized (featureStore)
1638     {
1639       /*
1640        * get features that overlap the cut region
1641        */
1642       List<SequenceFeature> toAmend = featureStore.findFeatures(cutStartPos,
1643               cutEndPos);
1644
1645       /*
1646        * add any contact features that span the cut region
1647        * (not returned by findFeatures)
1648        */
1649       for (SequenceFeature contact : featureStore.getContactFeatures())
1650       {
1651         if (contact.getBegin() < cutStartPos
1652                 && contact.getEnd() > cutEndPos)
1653         {
1654           toAmend.add(contact);
1655         }
1656       }
1657
1658       /*
1659        * adjust start-end of overlapping features;
1660        * delete features enclosed by the cut;
1661        * delete partially overlapping contact features
1662        */
1663       for (SequenceFeature sf : toAmend)
1664       {
1665         int sfBegin = sf.getBegin();
1666         int sfEnd = sf.getEnd();
1667         int newBegin = sfBegin;
1668         int newEnd = sfEnd;
1669         boolean toDelete = false;
1670         boolean follows = false;
1671
1672         if (sfBegin >= cutStartPos && sfEnd <= cutEndPos)
1673         {
1674           /*
1675            * feature lies within cut region - delete it
1676            */
1677           toDelete = true;
1678         }
1679         else if (sfBegin < cutStartPos && sfEnd > cutEndPos)
1680         {
1681           /*
1682            * feature spans cut region - left-shift the end
1683            */
1684           newEnd -= cutWidth;
1685         }
1686         else if (sfEnd <= cutEndPos)
1687         {
1688           /*
1689            * feature overlaps left of cut region - truncate right
1690            */
1691           newEnd = cutStartPos - 1;
1692           if (sf.isContactFeature())
1693           {
1694             toDelete = true;
1695           }
1696         }
1697         else if (sfBegin >= cutStartPos)
1698         {
1699           /*
1700            * remaining case - feature overlaps right
1701            * truncate left, adjust end of feature
1702            */
1703           newBegin = cutIsInternal ? cutStartPos : cutEndPos + 1;
1704           newEnd = newBegin + sfEnd - cutEndPos - 1;
1705           if (sf.isContactFeature())
1706           {
1707             toDelete = true;
1708           }
1709         }
1710
1711         seq.deleteFeature(sf);
1712         if (!follows)
1713         {
1714           removed.add(sf);
1715         }
1716         if (!toDelete)
1717         {
1718           SequenceFeature copy = new SequenceFeature(sf, newBegin, newEnd,
1719                   sf.getFeatureGroup(), sf.getScore());
1720           seq.addSequenceFeature(copy);
1721           if (!follows)
1722           {
1723             added.add(copy);
1724           }
1725         }
1726       }
1727
1728       /*
1729        * and left shift any features lying to the right of the cut region
1730        */
1731
1732       featureStore.shiftFeatures(cutEndPos + 1, -cutWidth);
1733     }
1734
1735     /*
1736      * save deleted and amended features, so that Undo can
1737      * re-add or delete them respectively
1738      */
1739     if (command.deletedFeatures == null)
1740     {
1741       command.deletedFeatures = new HashMap<>();
1742     }
1743     if (command.truncatedFeatures == null)
1744     {
1745       command.truncatedFeatures = new HashMap<>();
1746     }
1747     command.deletedFeatures.put(seq, removed);
1748     command.truncatedFeatures.put(seq, added);
1749   }
1750 }