Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/HeuristicLab.Data-3.3.csproj
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/HeuristicLab.Data-3.3.csproj	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/HeuristicLab.Data-3.3.csproj	(revision 14650)
@@ -146,4 +146,7 @@
     <Compile Include="Interfaces\IStringConvertibleMatrix.cs" />
     <Compile Include="Interfaces\IStringConvertibleValue.cs" />
+    <Compile Include="PersistentDataStructures\Adaptations\HistoryArray.cs" />
+    <Compile Include="PersistentDataStructures\Adaptations\HistoryList.cs" />
+    <Compile Include="PersistentDataStructures\Implementations\ArrayMappedTrie.cs" />
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PercentArray.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PercentArray.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PercentArray.cs	(revision 14650)
@@ -45,8 +45,8 @@
       StringBuilder sb = new StringBuilder();
       sb.Append("[");
-      if (array.Length > 0) {
-        sb.Append(array[0].ToString("#0.#################### %"));  // percent format
-        for (int i = 1; i < array.Length; i++)
-          sb.Append(";").Append(array[i].ToString("#0.#################### %"));  // percent format
+      if (historyArray.Length > 0) {
+        sb.Append(historyArray[0].ToString("#0.#################### %"));  // percent format
+        for (int i = 1; i < historyArray.Length; i++)
+          sb.Append(";").Append(historyArray[i].ToString("#0.#################### %"));  // percent format
       }
       sb.Append("]");
Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryArray.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryArray.cs	(revision 14650)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryArray.cs	(revision 14650)
@@ -0,0 +1,140 @@
+﻿using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Data.PersistentDataStructures.Implementations;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Data.PersistentDataStructures.Adaptations {
+
+  [StorableClass]
+  public class HistoryArray<T> : ICloneable, IList<T>, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable {
+
+    [Storable]
+    private ArrayMappedTrie<T> amt;
+    [Storable]
+    public int Count { get; private set; }
+    public int Length { get { return Count; } }
+
+    [StorableConstructor]
+    protected HistoryArray(bool isDeserializing) { }
+
+    protected HistoryArray(HistoryArray<T> orig) {
+      amt = orig.amt.Clone();
+      Count = orig.Count;
+    }
+
+    public HistoryArray(int size) {
+      amt = new ArrayMappedTrie<T>();
+      Count = size;
+    }
+
+    public HistoryArray(IEnumerable<T> elements) {
+      amt = new ArrayMappedTrie<T>();
+      Count = 0;
+      foreach (var element in elements) {
+        Add(element);
+      }
+    }
+
+    public T this[int index] {
+      get {
+        if (index < 0 || index >= Count) throw new IndexOutOfRangeException();
+        return amt[(UInt32) index];
+      }
+      set {
+        if (index < 0 || index >= Count) throw new IndexOutOfRangeException();
+        amt[(UInt32) index] = value;
+      }
+    }
+
+    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
+
+    public IEnumerator<T> GetEnumerator() {
+      for (int i = 0; i < Count; i++) {
+        yield return this[i];
+      }
+    }
+
+    public object Clone() { return new HistoryArray<T>(this); }
+    public void Add(T item) { amt[(UInt32)Count] = item; Count++; }
+
+    public void Clear() {
+      var oldInterval = amt.SnapshotInterval;
+      amt.SnapshotInterval = 0;
+      for (int i = 0; i < Count; i++)
+        this[i] = default(T);
+      amt.SnapshotInterval = oldInterval;
+      if (oldInterval > 0)
+        amt.CreateSnapshot();
+    }
+    public bool Contains(T item) { return amt.Any(i => i.Equals(item)); }
+
+    public void CopyTo(T[] array, int arrayIndex) {
+      for (int i = 0; i < Count && i+arrayIndex < array.Length; i++) {
+        array[i + arrayIndex] = this[i];
+      }
+    }
+
+    public bool Remove(T item) { throw new NotSupportedException(); }
+    int ICollection<T>.Count { get { return Count;  } }
+
+    public bool IsReadOnly { get { return false;  } } 
+    public int IndexOf(T item) {
+      for (int i = 0; i < Count; i++) {
+        if (this[i].Equals(item)) return i;
+      }
+      return -1;
+    }
+    public void Insert(int index, T item) { throw new NotSupportedException(); }
+    public void RemoveAt(int index) { throw new NotSupportedException(); }
+
+    public void CopyTo(Array array, int index) {
+      for (int i = 0; i < Count && i < array.Length + index; i++) {
+        array.SetValue(this[i], i+index);
+      }
+    }
+    int ICollection.Count { get { return Count;  } }
+
+    public object SyncRoot { get { return this;  } }
+    public bool IsSynchronized { get { return true;  } }
+
+    public int CompareTo(object other, IComparer comparer) {
+      HistoryArray<T> o = other as HistoryArray<T>;
+      if (o == null) return 1;
+      for (int i = 0; i < Count && i < o.Count; i++) {
+        var result = comparer.Compare(this[i], o[i]);
+        if (result != 0)
+          return result;
+      }
+      return Count.CompareTo(o.Count);
+    }
+
+    public bool Equals(object other, IEqualityComparer comparer) {
+      HistoryArray<T> o = other as HistoryArray<T>;
+      if (o == null || o.Count != Count) return false;
+      for (int i = 0; i < Count; i++) {
+        if (!comparer.Equals(this[i], o[i]))
+          return false;
+      }
+      return true;
+    }
+
+    public int GetHashCode(IEqualityComparer comparer) {
+      unchecked { // overflow is fine
+        int hash = (int)2166136261;
+        for (int i = 0; i < Count; i++) {
+          hash = (hash * 16777619) ^ (this[i]?.GetHashCode() ?? 0);
+        }
+        return hash;
+      }
+    }
+
+    public void Resize(int newSize) {
+      for (int i = newSize; i < Count; i++) {
+        amt.Remove((UInt32)i);
+      }
+      Count = newSize;
+    }
+  }
+}
Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryList.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryList.cs	(revision 14650)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryList.cs	(revision 14650)
@@ -0,0 +1,117 @@
+﻿using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Data.PersistentDataStructures.Implementations;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Data.PersistentDataStructures.Adaptations {
+
+  [StorableClass]
+  public class HistoryList<T> : IList<T> {
+
+    [Storable]
+    private readonly ArrayMappedTrie<T> amt;
+
+    public int Count { get; private set; }
+
+    [StorableConstructor]
+    protected HistoryList(bool isDesierializing) { }
+
+    public HistoryList() {
+      amt = new ArrayMappedTrie<T>(true);
+      Count = 0;
+    }
+
+    public T this[int index] {
+      get {
+        if (index < 0 || index >= Count) throw new IndexOutOfRangeException();
+        return amt[(UInt32) index];
+      }
+      set {
+        if (index < 0 || index >= Count) throw new IndexOutOfRangeException();
+        amt[(UInt32) index] = value;
+      }
+    }
+
+    public IEnumerator<T> GetEnumerator() {
+      for (int i = 0; i < Count; i++)
+        yield return amt[(UInt32)i];
+    }
+
+    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
+
+    public void Add(T item) {
+      amt[(UInt32)Count] = item;
+      Count++;
+    }
+
+    public void Clear() { amt.Clear(); }
+
+    public bool Contains(T item) { return amt.Contains(item); }
+
+    public void CopyTo(T[] array, int arrayIndex) {
+      for (int i = 0; i < Count && i < array.Length + arrayIndex; i++) {
+        array[i + arrayIndex] = this[i];
+      }
+    }
+
+    public bool Remove(T item) {
+      var oldInternval = amt.SnapshotInterval;
+      amt.SnapshotInterval = 0;
+      bool found = false;
+      var wi = 0;
+      for (int i = 0; i < Count; i++) {
+        var value = amt[(UInt32) i];
+        if (!value.Equals(item)) {
+          if (wi < i) amt[(UInt32) wi] = value;
+          wi++;
+        }
+      }
+      found = wi < Count;
+      while (wi < Count) {
+        amt.Remove((UInt32) wi);
+        wi++;
+        Count--;
+      }
+      amt.SnapshotInterval = oldInternval;
+      if (oldInternval > 0)
+        amt.CreateSnapshot();
+      return found;
+    }
+
+    public bool IsReadOnly { get { return false; } }
+
+    public int IndexOf(T item) {
+      for (int i = 0; i < Count; i++) {
+        if (amt[(UInt32)i].Equals(item)) return i;
+      }
+      return -1;
+    }
+
+    public void Insert(int index, T item) {
+      var oldInterval = amt.SnapshotInterval;
+      amt.SnapshotInterval = 0;
+      for (int i = Count; i > index; i--) {
+        amt[(UInt32)i] = amt[(UInt32)i - 1];
+      }
+      amt[(UInt32) index] = item;
+      Count++;
+      amt.SnapshotInterval = oldInterval;
+      if (oldInterval > 0)
+        amt.CreateSnapshot();
+    }
+
+    public void RemoveAt(int index) {
+      var oldInterval = amt.SnapshotInterval;
+      amt.SnapshotInterval = 0;
+      for (int i = index; i < Count; i++) {
+        amt[(UInt32)i] = amt[(UInt32)i + 1];
+      }
+      amt.Remove((UInt32)Count-1);
+      amt.SnapshotInterval = oldInterval;
+      if (oldInterval > 0)
+        amt.CreateSnapshot();
+    }
+  }
+}
Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs	(revision 14650)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs	(revision 14650)
@@ -0,0 +1,310 @@
+﻿using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Collections.Specialized;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Data.PersistentDataStructures.Implementations {
+
+  [StorableClass]
+  public class ArrayMappedTrie<T> : IEnumerable<T> {
+
+    [StorableClass]
+    private class Node : IEnumerable {
+
+      [Storable]
+      private BitVector32 bitmap;
+      [Storable]
+      private readonly object[] values;
+
+      private static UInt16 CalculateLocalIndex(UInt16 subIndex, BitVector32 bitmap) {
+        UInt32 relevantBits = ((((uint)1)<<subIndex) - 1) & (uint) bitmap.Data;
+        return (UInt16) PopCount(relevantBits);
+      }
+
+      public bool Contains(UInt16 localIndex) { return bitmap[1 << localIndex]; }
+
+      [StorableConstructor]
+      protected Node(bool isDeserializing) { }
+
+      protected Node(BitVector32 bitmap, object[] values) {
+        this.bitmap = bitmap;
+        this.values = values;
+      }
+
+      public Node(UInt16 subIndex, object value) {
+        bitmap[1 << subIndex] = true;
+        values = new[] {value};
+      }
+
+      public object Get(UInt16 subIndex) {
+        return Contains(subIndex) ? values[CalculateLocalIndex(subIndex, bitmap)] : null;
+      }
+
+      public Node Set(UInt16 subIndex, object value) {
+        Debug.Assert(subIndex < 32);
+        if (Contains(subIndex)) {
+          var newValues = new object[values.Length];
+          Array.Copy(values, newValues, newValues.Length);
+          newValues[CalculateLocalIndex(subIndex, bitmap)] = value;
+          return new Node(bitmap, newValues);
+        } else {
+          var newValues = new object[values.Length + 1];
+          BitVector32 newBitmap = bitmap;
+          newBitmap[1 << subIndex] = true;
+          var localIndex = CalculateLocalIndex(subIndex, newBitmap);
+          if (localIndex > 0)
+            Array.ConstrainedCopy(values, 0, newValues, 0, localIndex);
+          newValues[localIndex] = value;
+          if (values.Length - localIndex > 0)
+            Array.ConstrainedCopy(values, localIndex, newValues, localIndex + 1, values.Length - localIndex);
+          return new Node(newBitmap, newValues);
+        }
+      }
+
+      public Node Remove(UInt16 subIndex) {
+        Debug.Assert(subIndex < 32);
+        if (!Contains(subIndex)) return this;
+        if (Length == 1) return null;
+        var newBitmap = bitmap;
+        var localIndex = CalculateLocalIndex(subIndex, bitmap);
+        newBitmap[1 << subIndex] = false;
+        var newValues = new object[values.Length - 1];
+        Array.ConstrainedCopy(values, 0, newValues, 0, localIndex);
+        Array.ConstrainedCopy(values, localIndex + 1, newValues, localIndex, newValues.Length - localIndex);
+        return new Node(newBitmap, newValues);
+      }
+
+      public UInt16 Length { get { return (UInt16) values.Length; } }
+
+      public IEnumerator GetEnumerator() {
+        return values.GetEnumerator();
+      }
+    }
+
+    [Storable]
+    private Node root;
+
+    [Storable]
+    private List<Node> oldRoots;
+
+    [Storable]
+    private UInt32 stepsSinceSnapshot = UInt32.MaxValue;
+
+    [Storable]
+    private readonly bool assumeFilledWithDefaultValue;
+
+    public ArrayMappedTrie(bool assumeFilledWithDefaultValue = true) {
+      this.assumeFilledWithDefaultValue = assumeFilledWithDefaultValue;
+      root = null;
+      ClonedFrom = null;
+      TrackClonedFrom = true;
+      SnapshotInterval = 1;
+    }
+
+    public T this[UInt32 index] {
+      get { return Get(root, index); }
+      set { Set(index, value); }
+    }
+
+    public UInt32 Count { get { return DoCount(root); } }
+
+    public UInt32 SnapshotInterval { get; set; }
+
+    public bool TrackClonedFrom { get; set; }
+
+    public ArrayMappedTrie<T> ClonedFrom { get; private set; }
+
+    public void CreateSnapshot() {
+      if (oldRoots == null) oldRoots = new List<Node>();
+      oldRoots.Add(root);
+      stepsSinceSnapshot = 0;
+    }
+
+    public void Remove(UInt32 index) {
+      CreateSnapshotIfNeccessary();
+      Remove(root, index, 6);
+      stepsSinceSnapshot++;
+    }
+
+    public void Clear() {
+      CreateSnapshotIfNeccessary();
+      root = null;
+      stepsSinceSnapshot++;
+    }
+
+    private void CreateSnapshotIfNeccessary() {
+      if (SnapshotInterval > 0 && stepsSinceSnapshot > SnapshotInterval)
+        CreateSnapshot();
+    }
+
+    private void Set(UInt32 index, T value) {
+      if (assumeFilledWithDefaultValue) {
+        T oldValue;
+        var containsIndex = Get(root, index, out oldValue);
+        if (containsIndex && oldValue.Equals(value) ||
+            !containsIndex && value.Equals(default(T))) return;
+      }
+      CreateSnapshotIfNeccessary();
+      root = assumeFilledWithDefaultValue && value.Equals(default(T)) ? Remove(root, index, 6) : Set(root, index, 6, value);
+      stepsSinceSnapshot++;
+    }
+
+    private static Node Set(Node n, UInt32 index, UInt16 level, T value) {
+      var subIndex = ExtractSubIndex(index, level);
+      if (level == 0)
+        return n == null ?
+           new Node(subIndex, value) :
+           n.Set(subIndex, value);
+      return n == null ?
+        new Node(subIndex, Set(null, index, (UInt16) (level - 1), value)) :
+        n.Set(subIndex, Set((Node)n.Get(subIndex), index, (UInt16)(level - 1), value));
+    }
+
+    private static Node Remove(Node n, UInt32 index, UInt16 level) {
+      if (n == null) return null;
+      var subIndex = ExtractSubIndex(index, level);
+      if (level == 0) return n.Remove(subIndex);
+      var newN = Remove((Node) n.Get(subIndex), index, (UInt16) (level - 1));
+      return newN == null ? n.Remove(subIndex) : n.Set(subIndex, newN);
+    }
+
+    private bool Get(Node n, UInt32 index, out T value) {
+      value = default(T);
+      var leafNode = Get(root, index, 6);
+      if (leafNode == null) return false;
+      var subIndex = ExtractSubIndex(index, 0);
+      if (!leafNode.Contains(subIndex)) return false;
+      value = (T)leafNode.Get(ExtractSubIndex(index, 0));
+      return true;
+    }
+
+    private T Get(Node n, UInt32 index) {
+      T value;
+      if (Get(n, index, out value) || assumeFilledWithDefaultValue)
+        return value;
+      throw new IndexOutOfRangeException();
+    }
+
+    private static Node Get(Node n, UInt32 index, UInt16 level) {
+      while (true) {
+        var subIndex = ExtractSubIndex(index, level);
+        if (level == 0) return n;
+        if (n == null) return null;
+        n = (Node) n.Get(subIndex);
+        level = (UInt16) (level - 1);
+      }
+    }
+
+    private UInt32 DoCount(Node n) { return DoCount(root, 6); }
+
+    private static UInt32 DoCount(Node n, UInt16 level) {
+      if (n == null) return 0;
+      return level == 0 ? n.Length :
+        n.Cast<Node>().Aggregate<Node, uint>(0,
+        (current, child) =>
+          current + DoCount(child, (UInt16) (level - 1)));
+    }
+
+    public UInt32 CountNodes() { return CountNodes(root, 6);  }
+
+    private static UInt32 CountNodes(Node n, UInt16 level) {
+      if (n == null) return 0;
+      if (level == 0) return 1;
+      return 1 + n.Cast<Node>().Aggregate<Node, uint>(0,
+        (current, child) =>
+          current + CountNodes(child, (UInt16) (level - 1)));
+    }
+
+    public UInt32 Overhead() { return Overhead(root, 6); }
+
+    private static UInt32 Overhead(Node n, UInt16 level) {
+      if (n == null) return 0;
+      if (level == 0) return 1 + 1; /* bitmap + child, leaf arrays are not overhead */
+      UInt32 total = 0;
+      foreach (Node child in n) {
+        total += Overhead(child, (UInt16)(level - 1));
+      }
+      return 1 + 1 + (UInt32)n.Length + total; /* node + bitmap + array + children */
+    }
+
+    public long SizeWithHistory() {
+      var nodes = new Dictionary<Node, UInt16>();
+      AddNodeSizeRecursively(root, nodes);
+      var size = nodes.Sum(kvp => (long) kvp.Value);
+      if (oldRoots != null) {
+        foreach (var node in oldRoots) {
+          AddNodeSizeRecursively(node, nodes);
+        }
+      }
+      var sizeWithHistory = nodes.Sum(kvp => (long)kvp.Value);
+      Console.WriteLine("size = {0}, size with history = {1}", size, sizeWithHistory);
+      return sizeWithHistory;
+    }
+
+    private static void AddNodeSizeRecursively(Node n, IDictionary<Node, UInt16> d) {
+      if (n == null) return;
+      if (d.ContainsKey(n)) return;
+      d[n] = (UInt16)(n.Length + 1 + 1);
+      foreach (var child in n) {
+        var childNode = child as Node;
+        if (child == null) break;
+        AddNodeSizeRecursively(childNode, d);
+      }
+    }
+
+    public ArrayMappedTrie<T> Clone() {
+      return new ArrayMappedTrie<T> {
+        TrackClonedFrom = this.TrackClonedFrom,
+        ClonedFrom = TrackClonedFrom ? this : null,
+        oldRoots = new List<Node> {root},
+        root = root
+      };
+    } 
+
+    public static UInt16 ExtractSubIndex(UInt32 index, int level) {
+      int offset = level*5;
+      const uint window = 0x1f;
+      UInt32 shiftedWindow = window << offset;
+      UInt32 maskedValue = index & shiftedWindow;
+      UInt32 subindex = maskedValue >> offset;
+      Debug.Assert(subindex < 32);
+      // Console.WriteLine("index {0} level {1} => {2} ({3})", index, level, subindex, subindex * Math.Pow(32, level));
+      return (UInt16)subindex;
+    }
+
+    private static IEnumerable<Node> GetChildrenRecursively(Node n, int level) {
+      if (level == 0) yield return n;
+      foreach (Node child in n) {
+        foreach (var grandchild in GetChildrenRecursively(child, level-1)) {
+          yield return grandchild;
+        }
+      }
+    }
+
+    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
+
+    public IEnumerator<T> GetEnumerator() {
+      foreach (var leaf in GetChildrenRecursively(root, 6)) {
+        foreach (var value in leaf)
+          yield return (T)value;
+      }
+    }
+
+    public const UInt32 SK5  = 0x55555555;
+    public const UInt32 SK3  = 0x33333333;
+    public const UInt32 SKF0 = 0x0f0f0f0f;
+    public const UInt32 SKFF = 0x00ff00ff;
+
+    public static UInt32 PopCount(UInt32 x) {
+      x -= (x>>1)&SK5;
+      x = (x & SK3) + ((x >> 2) & SK3);
+      x = (x & SKF0) + ((x >> 4) & SKF0);
+      x += x >> 8;
+      return (x + (x >> 16)) & 0x3F;
+    }
+
+  }
+}
Index: /branches/PersistentDataStructures/HeuristicLab.Data/3.3/ValueTypeArray.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Data/3.3/ValueTypeArray.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Data/3.3/ValueTypeArray.cs	(revision 14650)
@@ -28,4 +28,5 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data.PersistentDataStructures.Adaptations;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -40,6 +41,9 @@
     }
 
-    [Storable]
-    protected T[] array;
+    [Storable(AllowOneWay = true, Name = "array")]
+    protected T[] oldArrayValuePersistence { set { historyArray = new HistoryArray<T>(value); } }
+
+    [Storable]
+    protected HistoryArray<T> historyArray;
 
     [Storable]
@@ -60,5 +64,5 @@
 
     public virtual int Length {
-      get { return array.Length; }
+      get { return historyArray.Length; }
       #region Mono Compatibility
       // this setter should be protected, but the Mono compiler couldn't handle it
@@ -66,5 +70,5 @@
         if (ReadOnly) throw new NotSupportedException("Length cannot be set. ValueTypeArray is read-only.");
         if (value != Length) {
-          Array.Resize<T>(ref array, value);
+          historyArray.Resize(value);
           while (elementNames.Count > value)
             elementNames.RemoveAt(elementNames.Count - 1);
@@ -90,9 +94,9 @@
 
     public virtual T this[int index] {
-      get { return array[index]; }
+      get { return historyArray[index]; }
       set {
         if (ReadOnly) throw new NotSupportedException("Item cannot be set. ValueTypeArray is read-only.");
-        if (!value.Equals(array[index])) {
-          array[index] = value;
+        if (!value.Equals(historyArray[index])) {
+          historyArray[index] = value;
           OnItemChanged(index);
         }
@@ -115,5 +119,5 @@
     protected ValueTypeArray(ValueTypeArray<T> original, Cloner cloner)
       : base(original, cloner) {
-      this.array = (T[])original.array.Clone();
+      this.historyArray = (HistoryArray<T>)original.historyArray.Clone();
       this.readOnly = original.readOnly;
       this.resizable = original.resizable;
@@ -121,5 +125,5 @@
     }
     protected ValueTypeArray() {
-      array = new T[0];
+      historyArray = new HistoryArray<T>(0);
       readOnly = false;
       resizable = true;
@@ -127,5 +131,5 @@
     }
     protected ValueTypeArray(int length) {
-      array = new T[length];
+      historyArray = new HistoryArray<T>(length);
       readOnly = false;
       resizable = true;
@@ -134,5 +138,5 @@
     protected ValueTypeArray(T[] elements) {
       if (elements == null) throw new ArgumentNullException();
-      array = (T[])elements.Clone();
+      historyArray = new HistoryArray<T>(elements);
       readOnly = false;
       resizable = true;
@@ -147,16 +151,15 @@
 
     public T[] CloneAsArray() {
-      //mkommend: this works because T must be a value type (struct constraint);
-      return (T[])array.Clone();
+      return historyArray.ToArray();
     }
 
     public override string ToString() {
-      if (array.Length == 0) return "[]";
+      if (historyArray.Length == 0) return "[]";
 
       StringBuilder sb = new StringBuilder();
       sb.Append("[");
-      sb.Append(array[0].ToString());
-      for (int i = 1; i < array.Length; i++) {
-        sb.Append(";").Append(array[i].ToString());
+      sb.Append(historyArray[0].ToString());
+      for (int i = 1; i < historyArray.Length; i++) {
+        sb.Append(";").Append(historyArray[i].ToString());
         if (sb.Length > maximumToStringLength) {
           sb.Append("...");
@@ -169,5 +172,5 @@
 
     public virtual IEnumerator<T> GetEnumerator() {
-      return array.Cast<T>().GetEnumerator();
+      return historyArray.Cast<T>().GetEnumerator();
     }
 
Index: /branches/PersistentDataStructures/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVector.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVector.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVector.cs	(revision 14650)
@@ -41,6 +41,6 @@
     public BinaryVector(BoolArray elements)
       : this(elements.Length) {
-      for (int i = 0; i < array.Length; i++)
-        array[i] = elements[i];
+      for (int i = 0; i < historyArray.Length; i++)
+        historyArray[i] = elements[i];
     }
 
@@ -52,5 +52,5 @@
       if (length > 0) {
         for (int i = 0; i < length; i++)
-          array[startIndex + i] = random.Next(2) == 0;
+          historyArray[startIndex + i] = random.Next(2) == 0;
         OnReset();
       }
Index: /branches/PersistentDataStructures/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVector.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVector.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVector.cs	(revision 14650)
@@ -42,6 +42,6 @@
     public IntegerVector(IntArray elements)
       : this(elements.Length) {
-      for (int i = 0; i < array.Length; i++)
-        array[i] = elements[i];
+      for (int i = 0; i < historyArray.Length; i++)
+        historyArray[i] = elements[i];
     }
 
@@ -54,5 +54,5 @@
         int numbers = (int)Math.Floor((max - min) / (double)step);
         for (int i = startIndex; i < startIndex + length; i++) {
-          array[i] = random.Next(numbers) * step + min;
+          historyArray[i] = random.Next(numbers) * step + min;
         }
         OnReset();
@@ -65,5 +65,5 @@
           if (bounds.Columns > 2) step = bounds[i % bounds.Rows, 2];
           int numbers = (int)Math.Floor((max - min) / (double)step);
-          array[i] = random.Next(numbers) * step + min;
+          historyArray[i] = random.Next(numbers) * step + min;
         }
         OnReset();
Index: /branches/PersistentDataStructures/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs	(revision 14650)
@@ -54,5 +54,5 @@
     /// <returns>An enumeration of all groups.</returns>
     public IEnumerable<List<int>> GetGroups() {
-      var len = array.Length;
+      var len = historyArray.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
       // iterate from lowest to highest index
@@ -61,5 +61,5 @@
         var group = new List<int> { i };
         remaining.Remove(i);
-        var next = array[i];
+        var next = historyArray[i];
         if (next != i) {
           int prev;
@@ -69,5 +69,5 @@
               throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
             prev = next;
-            next = array[next];
+            next = historyArray[next];
           } while (next != prev);
         }
@@ -104,5 +104,5 @@
     public IEnumerable<int> GetGroupForward(int index) {
       yield return index;
-      var next = array[index];
+      var next = historyArray[index];
       if (next == index) yield break;
       int prev;
@@ -110,5 +110,5 @@
         yield return next;
         prev = next;
-        next = array[next];
+        next = historyArray[next];
       } while (next != prev);
     }
@@ -130,8 +130,8 @@
     public IEnumerable<int> GetGroupBackward(int index) {
       yield return index;
-      var next = array[index];
+      var next = historyArray[index];
       // return preceding elements in group
       for (var prev = index - 1; prev >= 0; prev--) {
-        if (array[prev] != next) continue;
+        if (historyArray[prev] != next) continue;
         next = prev;
         yield return next;
@@ -150,15 +150,15 @@
     /// be part of exactly one group.</param>
     public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
-      var len = array.Length;
+      var len = historyArray.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
       foreach (var group in grouping) {
         var prev = -1;
         foreach (var g in group.OrderBy(x => x)) {
-          if (prev >= 0) array[prev] = g;
+          if (prev >= 0) historyArray[prev] = g;
           prev = g;
           if (!remaining.Remove(prev))
             throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
         }
-        if (prev >= 0) array[prev] = prev;
+        if (prev >= 0) historyArray[prev] = prev;
       }
       if (remaining.Count > 0)
@@ -175,10 +175,10 @@
     /// <returns>True if the encoding is valid.</returns>
     public bool Validate() {
-      var len = array.Length;
+      var len = historyArray.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
       for (var i = 0; i < len; i++) {
         if (!remaining.Contains(i)) continue;
         remaining.Remove(i);
-        var next = array[i];
+        var next = historyArray[i];
         if (next == i) continue;
         int prev;
@@ -186,5 +186,5 @@
           if (!remaining.Remove(next)) return false;
           prev = next;
-          next = array[next];
+          next = historyArray[next];
         } while (next != prev);
       }
@@ -216,7 +216,7 @@
     public void LinearizeTreeStructures() {
       // Step 1: Convert the array into LLE-e
-      ToLLEeInplace(array);
+      ToLLEeInplace(historyArray.ToArray());
       // Step 2: For all groups linearize the links
-      FromLLEe(array);
+      FromLLEe(historyArray.ToArray());
     }
 
@@ -234,5 +234,5 @@
     /// <returns>An integer array in LLE-e representation</returns>
     public int[] ToLLEe() {
-      var result = (int[])array.Clone();
+      var result = (int[])historyArray.Clone();
       ToLLEeInplace(result);
       return result;
@@ -242,5 +242,5 @@
       var length = a.Length;
       for (var i = length - 1; i >= 0; i--) {
-        if (array[i] == i) a[i] = i;
+        if (historyArray[i] == i) a[i] = i;
         else a[i] = a[a[i]];
       }
@@ -257,13 +257,13 @@
     /// <param name="llee">The LLE-e representation</param>
     public void FromLLEe(int[] llee) {
-      var length = array.Length;
+      var length = historyArray.Length;
       var groups = new Dictionary<int, int>();
       for (var i = length - 1; i >= 0; i--) {
         if (llee[i] == i) {
-          array[i] = i;
+          historyArray[i] = i;
           groups[i] = i;
         } else {
           var g = llee[i];
-          array[i] = groups[g];
+          historyArray[i] = groups[g];
           groups[g] = i;
         }
Index: /branches/PersistentDataStructures/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs	(revision 14650)
@@ -71,6 +71,6 @@
     public Permutation(PermutationTypes type, IntArray elements)
       : this(type, elements.Length) {
-      for (int i = 0; i < array.Length; i++)
-        array[i] = elements[i];
+      for (int i = 0; i < historyArray.Length; i++)
+        historyArray[i] = elements[i];
     }
 
@@ -103,7 +103,7 @@
           index2 = startIndex + random.Next(i + 1);
           if (index1 != index2) {
-            val = array[index1];
-            array[index1] = array[index2];
-            array[index2] = val;
+            val = historyArray[index1];
+            historyArray[index1] = historyArray[index2];
+            historyArray[index2] = val;
           }
         }
Index: /branches/PersistentDataStructures/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVector.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVector.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVector.cs	(revision 14650)
@@ -41,6 +41,6 @@
     public RealVector(DoubleArray elements)
       : this(elements.Length) {
-      for (int i = 0; i < array.Length; i++)
-        array[i] = elements[i];
+      for (int i = 0; i < historyArray.Length; i++)
+        historyArray[i] = elements[i];
     }
 
@@ -53,5 +53,5 @@
       if (length > 0) {
         for (int i = 0; i < length; i++)
-          array[startIndex + i] = min + delta * random.NextDouble();
+          historyArray[startIndex + i] = min + delta * random.NextDouble();
         OnReset();
       }
@@ -63,5 +63,5 @@
           double min = bounds[i % bounds.Rows, 0];
           double max = bounds[i % bounds.Rows, 1];
-          array[i] = min + (max - min) * random.NextDouble();
+          historyArray[i] = min + (max - min) * random.NextDouble();
         }
         OnReset();
Index: /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs	(revision 14650)
@@ -40,6 +40,6 @@
 
       Tour tour = new Tour();
-      for (int i = 0; i < this.array.Length; i++) {
-        if (this.array[i] >= cities) {
+      for (int i = 0; i < this.historyArray.Length; i++) {
+        if (this.historyArray[i] >= cities) {
           if (tour.Stops.Count > 0) {
             result.Add(tour);
@@ -48,5 +48,5 @@
           }
         } else {
-          tour.Stops.Add(this.array[i] + 1);
+          tour.Stops.Add(this.historyArray[i] + 1);
         }
       }
@@ -72,6 +72,6 @@
 
         while (vehicleAssignment == -1) {
-          if (this.array[i] >= ProblemInstance.Cities.Value) {
-            vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
+          if (this.historyArray[i] >= ProblemInstance.Cities.Value) {
+            vehicleAssignment = this.historyArray[i] - ProblemInstance.Cities.Value;
           }
 
Index: /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs	(revision 14650)
@@ -24,4 +24,5 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data.PersistentDataStructures.Adaptations;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -69,7 +70,7 @@
     public PermutationEncoding(Permutation permutation, IVRPProblemInstance problemInstance)
       : base(PermutationTypes.RelativeUndirected) {
-      this.array = new int[permutation.Length];
-      for (int i = 0; i < array.Length; i++)
-        this.array[i] = permutation[i];
+      this.historyArray = new HistoryArray<int>(permutation.Length);
+      for (int i = 0; i < historyArray.Length; i++)
+        this.historyArray[i] = permutation[i];
 
       this.ProblemInstance = problemInstance;
@@ -82,5 +83,5 @@
 
     public int IndexOf(int city) {
-      return Array.IndexOf(this.array, city);
+      return historyArray.IndexOf(city);
     }
   }
Index: /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/PrinsEncoding.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/PrinsEncoding.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/PrinsEncoding.cs	(revision 14650)
@@ -102,5 +102,5 @@
 
         //find predecessor / successor in permutation
-        int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1;
+        int predecessorIndex = historyArray.IndexOf(tour.Stops[0] - 1) - 1;
         if (predecessorIndex >= 0) {
           int predecessor = this[predecessorIndex] + 1;
@@ -114,5 +114,5 @@
           }
         } else {
-          int successorIndex = Array.IndexOf(this.array,
+          int successorIndex = historyArray.IndexOf(
             tour.Stops[tour.Stops.Count - 1] - 1) + 1;
           int successor = this[successorIndex] + 1;
Index: /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/ZhuEncoding.cs
===================================================================
--- /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/ZhuEncoding.cs	(revision 14649)
+++ /branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/ZhuEncoding.cs	(revision 14650)
@@ -63,5 +63,5 @@
 
         //find predecessor / successor in permutation
-        int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1;
+        int predecessorIndex = historyArray.IndexOf(tour.Stops[0] - 1) - 1;
         if (predecessorIndex >= 0) {
           int predecessor = this[predecessorIndex] + 1;
@@ -75,5 +75,5 @@
           }
         } else {
-          int successorIndex = Array.IndexOf(this.array,
+          int successorIndex = historyArray.IndexOf(
             tour.Stops[tour.Stops.Count - 1] - 1) + 1;
           int successor = this[successorIndex] + 1;
