プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

プログラムで履歴の実装のひな形

たぶん、これ以上履歴の構成が変更されることはないと思うのでこんな物を用意しておけば履歴は簡単に作成できるぞー、というのを載せてみる。
 
 
単に履歴は一つ一つ行き来するだけでなく、ある程度のまとまりで実行することがあるので、基本的には直接履歴を作成するのではなく、クッションとして履歴を作成する為のイベントをかませておくと作りやすい。
 
そのイベントの例。
toHistory関数でこのイベントを実際の履歴クラスに変換する。
そこは各々のイベントに応じて実装する。
 
linkedEventはひとまとまりにされた履歴に属するイベントを保存する。
可視性について無修飾子になっているのは同じhisotryパッケージ以外から弄らせない為だ。よってプログラムする上で気にする必要はない。
isGroupは他のイベントのlinkedEventに含まれているかどうかだが、これも気にしなくて良い。
 
HistoryContainerはHistoryクラス(後述)を返す関数を定義したインターフェース。
(以下ソースではimport文を省略)
 

package history;

public abstract class HistoryEvent{
    static private long nextid=0;

    public final long when;
    public final long id;
    public final HistoryContainer source;
    
    boolean isGroup=false;
    //行われた逆順に入れること。
    final LinkedList<HistoryEvent> linkedEvent = new LinkedList<HistoryEvent>();
  
    public HistoryEvent(HistoryContainer source) {
        this.source = source;
        when = System.currentTimeMillis();
        id = nextid++;
    }
    
    final public HistoryContainer getSource() {
        return source;
    }

    public String toString(){return "History Event";}

    abstract public HistoryBase toHistory();
}
package history;

public interface HistoryContainer {
    public History getHistory();
}

 
これらのイベントを保存しておくスタックを用意する。
例のenumを使ったシングルトンパターンを利用してみた。
ここのtoHistoryGroupでさっきのlinkedEventに追加操作を行ってる。
markGroupStart()関数を呼び出した後から、toHistoryGroupを呼び出したところまでの一連の履歴を一つの履歴として扱う。

package history;

public enum EventPool{
    EventPool(1000);

    //ヒープ領域を超えるほどイベントを保持する状態の方が異常なので
    //領域の拡張は許可しない。
    private final HistoryEvent heap;
    private int size=0;
    
    private EventPool(int length) {
        heap  = new HistoryEvent[length];
    }
    

    public int size(){return size;}
    
    public HistoryEvent pop(){
        if(size==0)throw new Error("buffer is empty!");
        HistoryEvent ret = heap[--size];
        heap[size]=null;
        return ret;
    }

    public void push(HistoryEvent e){
        if(size == heap.length)throw new Error("can't push! out of EventPool's heapmemory. HeapSize:"+heap.length);
        heap[size++] = e;
    }

    public void clear(){
        size = 0;
        Arrays.fill(heap, null);
    }
    
    public void markGroupStart(){push(new GroupStartFlag());}
    
    public void toHistoryGroup(){
        HistoryEvent e = pop();
        HistoryEvent ee = pop();
        if(ee==null)throw new Error("Mark is not found");
        while(!(ee instanceof GroupStartFlag)){
            e.linkedEvent.add(ee);
            ee.isGroup = true;
            if(size==0)throw new Error("Mark is not found");            
            ee=pop();
        }
        e.toHistory();
        //デバッグ    showRest();
    }
    
    public void toHistory(){
        pop().toHistory();
        //デバッグ    showRest();
    }
    

    //フラグ用のイベントクラス
    private static class GroupStartFlag extends HistoryEvent{
         private static HistoryContainer hc = new HistoryContainer() {
            @Override
            public History getHistory() {return null;}
        };
        public GroupStartFlag() {
            super(hc);
        }
        public HistoryBase toHistory() {throw new Error("can't make History");}
    }
    
    //デバッグ用関数
    public void showRest(){
        if(size==0)return;
        System.out.println("残ってる物:");
        for(HistoryEvent a:heap){
            if(a==null)break;
            System.out.println(a.getClass().getName());
        }
    }

}
 
さて、次に履歴の実装に移る。
実際に機能を実装する前にインターフェースを作成する。
以下で登場するListObject,StackObjectは私が使い回しているsetBeforeとかのリンク構造を持つことを宣言するインターフェースなんだけど、なんでこういうインターフェースが標準でないかね?
private package history;

interface HistoryFace extends ListObject<HistoryFace>,StackObject<HistoryFace>{
    public String getHistoryName();
    public long memorySize();
    public void clear();
    /**
     * 履歴を進みます。<br>
     * 履歴復成功時にtrueが返ります
     * @return 成功したか否か
     */

    public  boolean redo();
    /**
     * 履歴を戻ります<br>
     * 履歴復元成功時にtrueが返ります
     * @return 成功したか否か
     */

    public boolean undo();

    /**
     * ヒストリーが正しく使えるかどうか
     * @return falseの時、何らかのエラーがあります。
     */

    public boolean correct();
}

interface ListObject<T> {
    public T next();
    public boolean hasNext();
    public void setNext(T obj);
}

interface StackObject<T> {
    public boolean hasBefore();
    public T before();
    public void setBefore(T obj);
}
 
で、これを実際に実装する。
まずは、履歴の大本、管理、開始点とも言える根幹クラスHisotryを実装する。
 
maxMemorySizeが履歴が保持するメモリの最大量。
これを超えたメモリーを保持する場合は、古い履歴から消されていく。
その計算はかなりおおざっぱだけどね。
履歴に登録する為の関数はpushだけど、これもまた可視性がついていないのでhisotryパッケージ内からしか呼び出せない。(setNext等は呼び出し禁止)
pushの引数HistoryBaseクラスは後述するが、全ての履歴の元となるクラスだ。

package history;

final public class History implements Iterable<HistoryFace>,HistoryFace{

    private long maxMemorySize = 1048576L*20;
    public void setMaxMemorySize(int megabyte){if(megabyte > 5){maxMemorySize = 1048576L*megabyte;}}
    public int getMaxMemorySize(){return (int)(maxMemorySize>>20);}

    private HistoryFace first = null;
    private HistoryFace last = null;
    private int currentNumber = -1;

    @Override
    public long memorySize() {
        long m = 0;
        for(HistoryFace o :this){
            m += o.memorySize();
        }
        return m;
    }

    void push(HistoryBase obj){
        if(first != null){
            int i=0,sum=length();
            for(HistoryFace o:this){
                if(i == currentNumber){
                    first = o;
                    break;
                }
                o.clear();
                i++;
            }
            if(currentNumber !=i || currentNumber==sum){
                first = null;
                last = obj;
                currentNumber=-1;
            }else currentNumber =0;

            try{
                while(memorySize() >= maxMemorySize){
                    removeLast();
                }
            }catch(Exception e){
                clear();
                i=0;
            }
        }else last = obj;
        HistoryFace i = first;
        first = obj;
        currentNumber = 0;
        obj.setNext(i);
        obj.setBefore(null);
        if(i != null)
            i.setBefore(first);
    }

    @Override
    public void clear() {
        last =  null;
        for(HistoryFace o:this){
            o.clear();
        }
        first = null;
        currentNumber = -1;
    }

    @Override
    public boolean redo() {
        HistoryFace current = getCurrent(-1);
        if(current == null)return false;
        if(current.redo()){
            currentNumber--;
            return true;
        }else{
            removeAll();
            return false;
        }
    }

    @Override
    public boolean undo() {
        HistoryFace current = getCurrent(0);
        if(current == null)    return false;
        if(current.undo()){
            currentNumber++;
            return true;
        }else{
            if(!current.correct()){
                removeAll();
            }
            return false;
        }
    }

    public int length(){
        int i = 0;
        Iterator<HistoryFace> it = iterator();
        while(it.hasNext()){
            it.next();
            i++;
        }
        return i;
    }

    private HistoryFace getCurrent(int n){
        if(currentNumber+n < 0)return null;
        int i=0;
        for(HistoryFace o:this){
            if(i == currentNumber+n){
                return o;
            }
            i++;
        }
        return null;
    }


    @Override
    public Iterator<HistoryFace> iterator() {
        return new Iterator<HistoryFace>() {
            HistoryFace now = History.this;
            @Override
            public void remove() throws UnsupportedOperationException{
                throw new UnsupportedOperationException();
            }

            @Override
            public boolean hasNext() {
                return now.hasNext();
            }

            @Override
            public HistoryFace next() {
                return now=now.next();
            }
        };
    }

    //呼び出すときは必ずfirst==currentが成立していること
    private void removeLast() throws Exception{
        if(first==null ||  currentNumber != 0)throw new Exception("can't remove");
        HistoryFace i = last;
        last = last.before();
        i.clear();
        if(last == null){
            first = null;
            currentNumber = -1;
        }
    }

    private void removeAll(){
        for(HistoryFace h:this){
            h.clear();
        }
        first = null;
        last = null;
        currentNumber = -1;
    }

    //--------------------------
    //HistoryFace Override
    //--------------------------
    @Override
    public boolean hasNext() {return first!=null?true:false;}
    @Override
    public HistoryFace next() {return first;}
    
    @Override
    public String getHistoryName() {return "History";}

    @Override
    public boolean correct() {return true;}

    @Override @Deprecated public void setNext(HistoryFace obj) {}
    
    @Override @Deprecated public HistoryFace before() {return null;}

    @Override @Deprecated public void setBefore(HistoryFace a) {}

    @Override @Deprecated public boolean hasBefore() {return false;}

}
 
では、HistoryBaseクラスについて。
実際にredo,undoの処理はこのクラスを拡張したクラスのredo_,undo_関数で行う。
getMemorySizeはインスタンスが保持するメモリ量をざっくばらんに自分で計算して返す。
clear_関数はデストラクターの代わり。削除時にすぐに呼び出される。
消される前に何かやっておかないといけない処理があればここでおこなう。
package history;

public abstract class HistoryBase implements HistoryFace{
    private static final HistoryBase NULL = new HistoryBase[0];
    protected CanvasData canvas = CONTAINER.getCanvas();
    
    private HistoryFace next=null;
    private HistoryFace before = null;
    private HistoryBase[] linkedhistory=NULL;

    public HistoryBase(HistoryEvent e) {
        if(!e.isGroup){
            e.getSource().getHistory().push(this);
            if(!e.linkedEvent.isEmpty()){
                int i=0;
                LinkedList<HistoryBase> list = new LinkedList<HistoryBase>();
                for(HistoryEvent ee:e.linkedEvent){
                    if(ee==null)continue;
                    HistoryBase h = ee.toHistory();
                    if(h==null)continue;
                    list.add(h);
                    i++;
                }
                linkedhistory = new HistoryBase[i];
                list.toArray(linkedhistory);
            }
        }
    }
    
    ///HistoryFaceの実装////////////////////////////////////
    
    @Override
    final public long memorySize() {
        long l = getMemorySize();
        for(HistoryBase h:linkedhistory)l+=h.memorySize();
        return l;
    }

    abstract public long getMemorySize();
    
    @Override
    public final boolean undo() {
        if(!correct() || !undo_()){
            new Exception("undo error! "+getHistoryName()).printStackTrace();
            return false;
        }
        for(HistoryBase a:linkedhistory)if(!a.undo()){
            new Exception("undo error! "+a.getHistoryName()).printStackTrace();
            return false;
        }
        return true;
    }

    @Override
    public final boolean redo() {
        for(int i=linkedhistory.length-1;i>=0;i--){
            if(!linkedhistory[i].redo()){
                new Exception("redo error! "+linkedhistory[i].getHistoryName()).printStackTrace();
                return false;
            }
        }
        if(!correct() || !redo_()){
            new Exception("redo error! "+getHistoryName()).printStackTrace();
            return false;
        }
        return true;
    }

    abstract boolean redo_();
    abstract boolean undo_();
    

    public final void clear(){
        if(before != null){
            before.setNext(null);
        }
        before = null;
        for(HistoryBase h:linkedhistory)h.clear();
        linkedhistory = null;
        clear_();
    }
    protected abstract void clear_();

    
    ///ListObjectの実装////////////////////////////////////
    @Override
    public final boolean hasNext(){return next!=null;}
    @Override
    public final void setNext(HistoryFace obj) {next = obj;}
    @Override
    public final HistoryFace next() {return next;}
    
    ///StackObjectの実装////////////////////////////////////
    @Override
    public final HistoryFace before(){return before;}
    @Override
    public final void setBefore(HistoryFace obj) {before = obj;}
    @Override
    public final boolean hasBefore(){return before!=null;}
    
}
まとめてjarファイル化した物
history.jar