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