過去の状態のスナップショットを取れるMap

時間を指定して、その時点での状態を取れるようなMapを作ってみた。
何に使うかとかは考えてない。

こういった、データの世代別管理をして過去のある時点をスナップショットとして取得できるようなデータ構造は、扱うデータが巨大になってバックアップのためにシステムを止めれないというときに重要になったりしますね。
あと、データを変更せず追記する一方なので、ストレージの仕組みとして使うと、変更回数の制限があるSSDと相性がいいとか。

使うとこんな感じ。

    public static void main(String[] args) throws InterruptedException{
        VersionedMap<String, Integer> vm =
            new VersionedMap<String, Integer>();
        vm.put("abc", 3);
        vm.put("aaa", 6);
        vm.put("hoge", 10);
        System.out.println("--t1--");
        print(vm);
        sleep(100);
        Date t1 = new Date();
        sleep(100);

        vm.put("abc", 12);
        vm.put("bbb", 33);
        vm.remove("hoge");
        System.out.println("--t2--");
        print(vm);

        System.out.println("--t1--");
        print(vm.getSnapShot(t1));
    }

    static void print(Map<String, Integer> m){
        for(Map.Entry<String, Integer> me : m.entrySet()){
            System.out.printf("%s - %d%n", me.getKey(), me.getValue());
        }
    }

動かすとこう。

--t1--
abc - 3
aaa - 6
hoge - 10
--t2--
aaa - 6
bbb - 33
abc - 12
--t1--
abc - 3
aaa - 6
hoge - 10

本体は、これ。
実際に使うには、entrySet()とかkeySet()をちゃんと実装しないといけないけど。
あと、スナップショットとるときにちゃんと2分探索にするとか、データの有効期限を決めるとか。

import java.util.*;

public class VersionedMap<K, V> implements Map<K, V>{
    static class Data<V>{
        V data;
        long time = new Date().getTime();
        boolean exist = true;
        Data(){
            exist = false;
        }
        Data(V d){
            data = d;
        }
    }
    private Map<K, ArrayList<Data<V>>> repos = new HashMap<K, ArrayList<Data<V>>>();
    private int currentCount = 0;
    @Override
    public int size() {
        return currentCount;
    }

    @Override
    public boolean isEmpty() {
        return currentCount == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        ArrayList<Data<V>> list = repos.get(key);
        if(list == null) return false;
        return list.get(list.size() - 1).exist;
    }

    @Override
    public boolean containsValue(Object value) {
        for(ArrayList<Data<V>> dt : repos.values()){
            Data<V> d = dt.get(dt.size() - 1);
            if(!d.exist) continue;
            if(d.data == null){
                if(value == null) return true;
            }else{
                if(d.data.equals(value)) return true;
            }
        }
        return false;
    }

    @Override
    public V get(Object key) {
        ArrayList<Data<V>> d = repos.get(key);
        if(d == null) return null;
        return d.get(d.size() - 1).data;
    }

    @Override
    public V put(K key, V value) {
        if(repos.containsKey(key)){
            ArrayList<Data<V>> d = repos.get(key);
            Data<V> dt = d.get(d.size() - 1);
            d.add(new Data(value));
            if(!dt.exist) currentCount++;
            return dt.data;
        }else{
            ArrayList<Data<V>> d = new ArrayList<Data<V>>();
            d.add(new Data<V>(value));
            repos.put(key, d);
            currentCount++;
            return null;
        }
    }

    @Override
    public V remove(Object key) {
        if(repos.containsKey(key)){
            ArrayList<Data<V>> d = repos.get(key);
            Data<V> dt = d.get(d.size() - 1);
            if(!dt.exist) return null;
            d.add(new Data<V>());
            currentCount--;
            return dt.data;
        }else{
            return null;
        }
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for(Map.Entry<? extends K, ? extends V> me : m.entrySet()){
            put(me.getKey(), me.getValue());
        }
    }

    @Override
    public void clear() {
        for(ArrayList<Data<V>> list : repos.values()){
            Data<V> dt = list.get(list.size() - 1);
            if(dt.exist){
                list.add(new Data<V>());
            }
        }
        currentCount = 0;
    }

    @Override
    public Set<K> keySet() {
        Set<K> ret = new HashSet<K>();
        for(Map.Entry<K, ArrayList<Data<V>>> me : repos.entrySet()){
            Data<V> last = me.getValue().get(me.getValue().size() - 1);
            if(last.exist) ret.add(me.getKey());
        }
        return ret;
    }

    @Override
    public Collection<V> values() {
        Set<V> ret = new HashSet<V>();
        for(Map.Entry<K, ArrayList<Data<V>>> me : repos.entrySet()){
            Data<V> last = me.getValue().get(me.getValue().size() - 1);
            if(last.exist) ret.add(last.data);
        }
        return ret;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> ret = new HashSet<Map.Entry<K, V>>();
        for(Map.Entry<K, ArrayList<Data<V>>> me : repos.entrySet()){
            Data<V> last = me.getValue().get(me.getValue().size() - 1);
            if(last.exist) ret.add(new AbstractMap.SimpleEntry<K, V>(me.getKey(), last.data));
        }
        return ret;
    }

    public Map<K, V> getSnapShot(Date d){
        Map<K, V> ret = new HashMap<K, V>();
        long time = d.getTime();
        for(Map.Entry<K, ArrayList<Data<V>>> me : repos.entrySet()){
            ArrayList<Data<V>> data = me.getValue();
            
            Data<V> result = null;
            for(Data<V> dt: data){
                if(dt.time > time){
                    break;
                }
                result = dt;
            }
            if(result != null && result.exist){
                ret.put(me.getKey(), result.data);
            }
             
        }

        return ret;
    }
}