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