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