Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15454)
@@ -27,4 +27,5 @@
 using HeuristicLab.Common;
 using HeuristicLab.Problems.BinPacking;
+using HeuristicLab.Problems.BinPacking3D.Geometry;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -38,5 +39,5 @@
     public BinPacking3D(PackingShape binShape)
       : base(binShape) {
-      ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
+      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
       AddExtremePoint(binShape.Origin);
       InitializeOccupationLayers();
@@ -63,4 +64,237 @@
       #endregion
     }
+
+    #region New methods for bin packer class
+
+    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
+      Items[itemID] = item;
+      Positions[itemID] = position;
+      ExtremePoints.Remove(position);
+      ResidualSpace.Remove(position);
+    }
+
+    public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
+      /*if (stackingConstraints) {
+        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
+        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
+        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
+      } else {*/
+      GenerateNewExtremePointsForNewItem(item, position);
+
+      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
+      foreach (var above in GetItemsAbove(position)) {
+        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
+      }
+      foreach (var front in GetItemsInfront(position)) {
+        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
+      }
+      foreach (var right in GetItemsOnRight(position)) {
+        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
+      }
+      //}
+    }
+
+
+
+    /// <summary>
+    /// In this case feasability is defined as following: 
+    /// 1. the item fits into the bin-borders; 
+    /// 2. the point is supported by something; 
+    /// 3. the item does not collide with another already packed item
+    /// 
+    /// Unfortunatelly this method does not support item rotation
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <returns></returns>
+    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
+      var b1 = CheckItemDimensions(item);
+      var b2 = ItemCanBePlaced(item, position);
+      var b3 = CheckStackingConstraints(item, position, stackingConstraints);
+
+      return b1 && b2 && b3;
+    }
+
+    /// <summary>
+    /// Compares the dimensions of a given item and the current bin. 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
+    private bool CheckItemDimensions(PackingItem item) {
+      return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
+    }
+
+    /// <summary>
+    /// Returns true if a given item can be placed in the current bin
+    /// </summary>
+    /// <param name="givenItem"></param>
+    /// <param name="givenItemPosition"></param>
+    /// <returns></returns>
+    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
+      // Check if the boundings of the bin would injured
+      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
+          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
+          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
+        return false;
+      }
+
+      //if the given item collides with any other item, it can not be placed
+      foreach (var item in Items) {
+        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
+                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
+          return false;
+        }
+      }
+      return true;     
+    }
+
+    /// <summary>
+    /// Checks if two given items in a space collides
+    /// </summary>
+    /// <param name="t1"></param>
+    /// <param name="t2"></param>
+    /// <returns></returns>
+    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
+      var position1 = t1.Item1;
+      var item1 = t1.Item2;
+      var position2 = t2.Item1;
+      var item2 = t2.Item2;
+      var cx = (position2.X == position1.X) || (position2.X < position1.X && position2.X + item2.Width > position1.X) || (position2.X > position1.X && position1.X + item1.Width > position2.X);
+      var cy = (position2.Y == position1.Y) || (position2.Y < position1.Y && position2.Y + item2.Height > position1.Y) || (position2.Y > position1.Y && position1.Y + item1.Height > position2.Y);
+      var cz = (position2.Z == position1.Z) || (position2.Z < position1.Z && position2.Z + item2.Depth > position1.Z) || (position2.Z > position1.Z && position1.Z + item1.Depth > position2.Z);
+      return cx && cy && cz;
+    }
+
+    /// <summary>
+    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <returns></returns>
+    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
+      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
+        return true;
+      }
+
+      return IsStaticStable(item, position) && IsWeightSupported(item, position);
+    }
+
+
+    /// <summary>
+    /// Checks if a given item has any point lieing on another item.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
+      bool p1, p2, p3, p4;
+      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+
+      return p1 || p2 || p3 || p4;
+    }
+
+    /// <summary>
+    /// Checks if a given item is static stable.
+    /// A item is static stable if all edges have an object below.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
+      bool p1, p2, p3, p4;
+      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+      return p1 && p2 && p3 && p4;
+    }
+
+    /// <summary>
+    /// This method sets the out parameters p1 ... p3 if the point lies on another item.
+    /// p1 ... p3 represents one point on the bottom side of an given item.
+    /// +---------+
+    /// |p1     p2|
+    /// |         |
+    /// |p4     p3|
+    /// +---------+
+    /// </summary>
+    /// <param name="item">Given item</param>
+    /// <param name="position">Given item position</param>
+    /// <param name="p1"></param>
+    /// <param name="p2"></param>
+    /// <param name="p3"></param>
+    /// <param name="p4"></param>
+    public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
+
+      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
+
+      p1 = itemsP1.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
+      p2 = itemsP2.Where(x => position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
+      p3 = itemsP3.Where(x => position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
+      p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
+    }
+
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="itemsP1"></param>
+    /// <param name="itemsP2"></param>
+    /// <param name="itemsP3"></param>
+    /// <param name="itemsP4"></param>
+    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
+      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
+      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
+      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
+      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
+
+    }
+
+    /// <summary>
+    /// Returns a collection of items which are below a given point. 
+    /// The top side of every item is at the same level as the Y-coordinate of the given position.
+    /// </summary>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
+      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
+    }
+
+
+    /// <summary>
+    /// Checks if a given the weight of an given item is supportet by the items below.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
+      if (position.Y == 0) {
+        return true;
+      }
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
+
+      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
+
+      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
+    }
+
+
+
+    #endregion
 
     public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
@@ -83,4 +317,6 @@
     }
 
+
+
     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
@@ -168,4 +404,5 @@
     }
 
+
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
       var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
@@ -204,5 +441,5 @@
 
     #region Projections
-        
+
     private Vector3D ProjectBackward(Vector3D pos) {
       var line = new Line3D(pos, new Vector3D(0, 0, -1));
@@ -268,5 +505,9 @@
     #region Get items
 
-    
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="pos"></param>
+    /// <returns></returns>
     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
       var line = new Line3D(pos, new Vector3D(0, 1, 0));
@@ -298,5 +539,38 @@
         .Select(x => Tuple.Create(x.Position, x.Item));
     }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 1, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
+      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 0, 1));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(1, 0, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
     #endregion
+
+
 
     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
@@ -316,10 +590,5 @@
     }
 
-    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
-      var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
-      return feasible
-        && IsSupportedByAtLeastOnePoint(item, position)
-        && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
-    }
+  
 
     #region Sliding based packing    
@@ -425,42 +694,5 @@
       return shortestSide;
     }
-    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
-      //Static stability is given, if item is placed on the ground
-      if (position.Y == 0)
-        return true;
-
-      if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
-        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
-        && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
-        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
-        return true;
-
-      return false;
-    }
-
-    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
-      if (position.Y == 0)
-        return true;
-
-      int y = position.Y - 1;
-      for (int x = position.X; x < position.X + item.Width; x++)
-        for (int z = position.Z; z < position.Z + item.Depth; z++)
-          if (IsPointOccupied(new PackingPosition(0, x, y, z)))
-            return true;
-
-      return false;
-    }
-    public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
-      if (ep.Y == 0)
-        return true;
-
-      if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
-        return true;
-
-      return false;
-    }
+    
 
     protected override void InitializeOccupationLayers() {
@@ -488,5 +720,5 @@
       return result;
     }
-    
+
     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
       foreach (var ep in ExtremePoints.ToList()) {
@@ -509,5 +741,6 @@
           }
         }
-        if (ep.Z <= pos.Z && 
+
+        if (ep.Z <= pos.Z &&
             ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
             ep.X >= pos.X && ep.X < pos.X + width) {
@@ -517,4 +750,5 @@
           changed = true;
         }
+
         if (changed) {
           if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
@@ -529,245 +763,5 @@
     }
 
-    #region Helper classes for vector math
-    private class Vector3D {
-      public int X;
-      public int Y;
-      public int Z;
-      public Vector3D() { }
-      public Vector3D(int x, int y, int z) {
-        X = x;
-        Y = y;
-        Z = z;
-      }
-      public Vector3D(PackingPosition pos) {
-        X = pos.X;
-        Y = pos.Y;
-        Z = pos.Z;
-      }
-      public static Vector3D AlongX(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X + item.Width,
-          pos.Y,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongY(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y + item.Height,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y,
-          pos.Z + item.Depth
-        );
-      }
-      public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X + item.Width,
-          pos.Y,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y + item.Height,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y,
-          pos.Z + item.Depth
-        );
-      }
-
-      public Vector3D Cross(Vector3D b) {
-        return new Vector3D(
-          Y * b.Z - Z * b.Y,
-          -X * b.Z + Z * b.X,
-          X * b.Y - Y * b.X
-        );
-      }
-
-      public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
-        return X >= pos.X && X < pos.X + rs.Item1
-          && Y >= pos.Y && Y < pos.Y + rs.Item2
-          && Z >= pos.Z && Z < pos.Z + rs.Item3;
-      }
-
-      public static int operator *(Vector3D a, Vector3D b) {
-        return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
-      }
-      public static Vector3D operator *(int a, Vector3D b) {
-        return new Vector3D(a * b.X, a * b.Y, a * b.Z);
-      }
-      public static Vector3D operator *(Vector3D a, int b) {
-        return new Vector3D(a.X * b, a.Y * b, a.Z * b);
-      }
-      public static Vector3D operator +(Vector3D a, Vector3D b) {
-        return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
-      }
-      public static Vector3D operator -(Vector3D a, Vector3D b) {
-        return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
-      }
-
-      public override bool Equals(object obj) {
-        var packPos = obj as PackingPosition;
-        if (packPos != null) {
-          return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
-        }
-        var vec = obj as Vector3D;
-        if (vec != null) {
-          return X == vec.X && Y == vec.Y && Z == vec.Z;
-        }
-        return false;
-      }
-    }
-
-    // A line is given as a point and a directing vector
-    private class Line3D {
-      public Vector3D Point;
-      public Vector3D Direction;
-
-      public Line3D(Vector3D point, Vector3D direction) {
-        Point = point;
-        Direction = direction;
-      }
-      public Line3D(PackingPosition position, Vector3D direction) {
-        Point = new Vector3D(position);
-        Direction = direction;
-      }
-
-      public bool Intersects(Plane3D plane) {
-        return plane.Intersects(this);
-      }
-
-      public Vector3D Intersect(Plane3D plane) {
-        return plane.Intersect(this);
-      }
-    }
-
-    private enum Side { Top, Left, Bottom, Right, Front, Back }
-    // A plane is given as a point and two directing vectors
-    private class Plane3D {
-      public Vector3D Point { get; private set; }
-      public Vector3D Direction1 { get; private set; }
-      public Vector3D Direction2 { get; private set; }
-      public Vector3D Normal { get; private set; }
-      private int rhs;
-
-      public Plane3D(PackingShape bin, Side side) {
-        switch (side) {
-          case Side.Top: // ZX plane
-            Point = new Vector3D(0, bin.Height, 0);
-            Direction1 = new Vector3D(0, 0, bin.Depth);
-            Direction2 = new Vector3D(bin.Width, 0, 0);
-            break;
-          case Side.Left: // ZY plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(0, 0, bin.Depth);
-            Direction2 = new Vector3D(0, bin.Height, 0);
-            break;
-          case Side.Bottom: // XZ plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(bin.Width, 0, 0);
-            Direction2 = new Vector3D(0, 0, bin.Depth);
-            break;
-          case Side.Right: // YZ plane
-            Point = new Vector3D(bin.Width, 0, 0);
-            Direction1 = new Vector3D(0, bin.Height, 0);
-            Direction2 = new Vector3D(0, 0, bin.Depth);
-            break;
-          case Side.Front: // XY plane
-            Point = new Vector3D(0, 0, bin.Depth);
-            Direction1 = new Vector3D(bin.Width, 0, 0);
-            Direction2 = new Vector3D(0, bin.Height, 0);
-            break;
-          case Side.Back: // YX plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(0, bin.Height, 0);
-            Direction2 = new Vector3D(bin.Width, 0, 0);
-            break;
-        }
-        Normal = Direction1.Cross(Direction2);
-        rhs = 0;
-      }
-
-      public Plane3D(PackingPosition pos, PackingItem item, Side side) {
-        // the directing vectors are chosen such that normal always points outside the packing item
-        switch (side) {
-          case Side.Top: // ZX plane
-            Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
-            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            break;
-          case Side.Left: // ZY plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            Direction2 = new Vector3D(0, item.Height, 0);
-            break;
-          case Side.Bottom: // XZ plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            break;
-          case Side.Right: // YZ plane
-            Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, item.Height, 0);
-            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            break;
-          case Side.Front: // XY plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
-            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            Direction2 = new Vector3D(0, item.Height, 0);
-            break;
-          case Side.Back: // YX plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, item.Height, 0);
-            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            break;
-        }
-        Normal = Direction1.Cross(Direction2);
-        rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
-      }
-
-      public bool IsElementOf(Vector3D point) {
-        return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
-      }
-
-      public bool Intersects(Line3D line) {
-        return Intersect(line) != null;
-      }
-
-      public Vector3D Intersect(Line3D line) {
-        var denom = Normal * line.Direction;
-        if (denom == 0) {
-          // dir is perpendicular to the normal vector of the plane
-          // this means they intersect if p1 is element of the plane
-          // also the plane does not stretch infinitely, but is bound
-          // to the parallelogram spanned by the point and the two
-          // directing vectors
-          if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
-            return line.Point;
-          else return null;
-        }
-        var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
-        if (IsWithinDirectionalVectors(intersect)) return intersect;
-        return null;
-      }
-
-      public bool IsWithinDirectionalVectors(Vector3D point) {
-        return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
-            && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
-            && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
-      }
-    }
-    #endregion
+
   }
 }
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs	(revision 15454)
@@ -0,0 +1,59 @@
+﻿using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.BinPacking3D.Packer;
+
+namespace HeuristicLab.Problems.BinPacking3D.Decoder {
+
+  /// <summary>
+  /// This class creates a solution
+  /// </summary>
+  [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
+  [StorableClass]
+  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> {
+
+    [StorableConstructor]
+    protected ExtremePointPermutationDecoder(bool deserializing) : base(deserializing) { }
+    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoderBase original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    /// <summary>
+    /// Creates an extrem point based permutation decoder
+    /// </summary>
+    /// <param name="binPacker">Contains the packing algorithm for packing the items</param>
+    public ExtremePointPermutationDecoder(BinPacker binPacker) : base() {
+      _binPacker = binPacker;
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      throw new NotImplementedException();
+    }
+
+    BinPacker _binPacker;
+
+    /// <summary>
+    /// Creates a solution for displaying it on the HEAL gui
+    /// </summary>
+    /// <param name="permutation">Permutation of items sorted by a sorting method. The value of each permutation index references to the index of the items list</param>
+    /// <param name="binShape">Bin for storing the items</param>
+    /// <param name="items">A list of packing items which should be assigned to a bin</param>
+    /// <param name="useStackingConstraints"></param>
+    /// <returns></returns>
+    public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
+      
+      foreach (var packedBin in _binPacker.PackItems()) {
+        solution.Bins.Add(packedBin);
+      }
+      return solution;
+    }
+  }
+}
+
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs	(revision 15454)
@@ -0,0 +1,32 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Geometry {
+  /// <summary>
+  /// A line is given as a point and a directing vector
+  /// </summary>
+  internal class Line3D {
+    public Vector3D Point;
+    public Vector3D Direction;
+
+    public Line3D(Vector3D point, Vector3D direction) {
+      Point = point;
+      Direction = direction;
+    }
+    public Line3D(PackingPosition position, Vector3D direction) {
+      Point = new Vector3D(position);
+      Direction = direction;
+    }
+
+    public bool Intersects(Plane3D plane) {
+      return plane.Intersects(this);
+    }
+
+    public Vector3D Intersect(Plane3D plane) {
+      return plane.Intersect(this);
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Plane3D.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Plane3D.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Plane3D.cs	(revision 15454)
@@ -0,0 +1,128 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Geometry {
+  internal enum Side { Top, Left, Bottom, Right, Front, Back }
+
+  /// <summary>
+  /// A plane is given as a point and two directing vectors
+  /// </summary>
+  internal class Plane3D {
+    public Vector3D Point { get; private set; }
+    public Vector3D Direction1 { get; private set; }
+    public Vector3D Direction2 { get; private set; }
+    public Vector3D Normal { get; private set; }
+    private int rhs;
+
+    public Plane3D(PackingShape bin, Side side) {
+      switch (side) {
+        case Side.Top: // ZX plane
+          Point = new Vector3D(0, bin.Height, 0);
+          Direction1 = new Vector3D(0, 0, bin.Depth);
+          Direction2 = new Vector3D(bin.Width, 0, 0);
+          break;
+        case Side.Left: // ZY plane
+          Point = new Vector3D(0, 0, 0);
+          Direction1 = new Vector3D(0, 0, bin.Depth);
+          Direction2 = new Vector3D(0, bin.Height, 0);
+          break;
+        case Side.Bottom: // XZ plane
+          Point = new Vector3D(0, 0, 0);
+          Direction1 = new Vector3D(bin.Width, 0, 0);
+          Direction2 = new Vector3D(0, 0, bin.Depth);
+          break;
+        case Side.Right: // YZ plane
+          Point = new Vector3D(bin.Width, 0, 0);
+          Direction1 = new Vector3D(0, bin.Height, 0);
+          Direction2 = new Vector3D(0, 0, bin.Depth);
+          break;
+        case Side.Front: // XY plane
+          Point = new Vector3D(0, 0, bin.Depth);
+          Direction1 = new Vector3D(bin.Width, 0, 0);
+          Direction2 = new Vector3D(0, bin.Height, 0);
+          break;
+        case Side.Back: // YX plane
+          Point = new Vector3D(0, 0, 0);
+          Direction1 = new Vector3D(0, bin.Height, 0);
+          Direction2 = new Vector3D(bin.Width, 0, 0);
+          break;
+      }
+      Normal = Direction1.Cross(Direction2);
+      rhs = 0;
+    }
+
+    public Plane3D(PackingPosition pos, PackingItem item, Side side) {
+      // the directing vectors are chosen such that normal always points outside the packing item
+      switch (side) {
+        case Side.Top: // ZX plane
+          Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
+          Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
+          Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
+          break;
+        case Side.Left: // ZY plane
+          Point = new Vector3D(pos.X, pos.Y, pos.Z);
+          Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
+          Direction2 = new Vector3D(0, item.Height, 0);
+          break;
+        case Side.Bottom: // XZ plane
+          Point = new Vector3D(pos.X, pos.Y, pos.Z);
+          Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
+          Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
+          break;
+        case Side.Right: // YZ plane
+          Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
+          Direction1 = new Vector3D(0, item.Height, 0);
+          Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
+          break;
+        case Side.Front: // XY plane
+          Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
+          Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
+          Direction2 = new Vector3D(0, item.Height, 0);
+          break;
+        case Side.Back: // YX plane
+          Point = new Vector3D(pos.X, pos.Y, pos.Z);
+          Direction1 = new Vector3D(0, item.Height, 0);
+          Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
+          break;
+      }
+      Normal = Direction1.Cross(Direction2);
+      rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
+    }
+
+    public bool IsElementOf(Vector3D point) {
+      return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
+    }
+
+    public bool Intersects(Line3D line) {
+      return Intersect(line) != null;
+    }
+
+    public Vector3D Intersect(Line3D line) {
+      var denom = Normal * line.Direction;
+      if (denom == 0) {
+        // dir is perpendicular to the normal vector of the plane
+        // this means they intersect if p1 is element of the plane
+        // also the plane does not stretch infinitely, but is bound
+        // to the parallelogram spanned by the point and the two
+        // directing vectors
+        if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
+          return line.Point;
+        else
+          return null;
+      }
+      var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
+      if (IsWithinDirectionalVectors(intersect))
+        return intersect;
+      return null;
+    }
+
+    public bool IsWithinDirectionalVectors(Vector3D point) {
+      return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
+          && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
+          && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs	(revision 15454)
@@ -0,0 +1,110 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Geometry {
+  internal class Vector3D {
+
+    public int X { get; set; }
+    public int Y { get; set; }
+    public int Z { get; set; }
+
+    public Vector3D() { }
+    public Vector3D(int x, int y, int z) {
+      X = x;
+      Y = y;
+      Z = z;
+    }
+    public Vector3D(PackingPosition pos) {
+      X = pos.X;
+      Y = pos.Y;
+      Z = pos.Z;
+    }
+    public static Vector3D AlongX(Vector3D pos, PackingItem item) {
+      return new Vector3D(
+        pos.X + item.Width,
+        pos.Y,
+        pos.Z
+      );
+    }
+    public static Vector3D AlongY(Vector3D pos, PackingItem item) {
+      return new Vector3D(
+        pos.X,
+        pos.Y + item.Height,
+        pos.Z
+      );
+    }
+    public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
+      return new Vector3D(
+        pos.X,
+        pos.Y,
+        pos.Z + item.Depth
+      );
+    }
+    public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
+      return new Vector3D(
+        pos.X + item.Width,
+        pos.Y,
+        pos.Z
+      );
+    }
+    public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
+      return new Vector3D(
+        pos.X,
+        pos.Y + item.Height,
+        pos.Z
+      );
+    }
+    public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
+      return new Vector3D(
+        pos.X,
+        pos.Y,
+        pos.Z + item.Depth
+      );
+    }
+
+    public Vector3D Cross(Vector3D b) {
+      return new Vector3D(
+        Y * b.Z - Z * b.Y,
+        -X * b.Z + Z * b.X,
+        X * b.Y - Y * b.X
+      );
+    }
+
+    public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
+      return X >= pos.X && X < pos.X + rs.Item1
+        && Y >= pos.Y && Y < pos.Y + rs.Item2
+        && Z >= pos.Z && Z < pos.Z + rs.Item3;
+    }
+
+    public static int operator *(Vector3D a, Vector3D b) {
+      return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
+    }
+    public static Vector3D operator *(int a, Vector3D b) {
+      return new Vector3D(a * b.X, a * b.Y, a * b.Z);
+    }
+    public static Vector3D operator *(Vector3D a, int b) {
+      return new Vector3D(a.X * b, a.Y * b, a.Z * b);
+    }
+    public static Vector3D operator +(Vector3D a, Vector3D b) {
+      return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
+    }
+    public static Vector3D operator -(Vector3D a, Vector3D b) {
+      return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
+    }
+
+    public override bool Equals(object obj) {
+      var packPos = obj as PackingPosition;
+      if (packPos != null) {
+        return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
+      }
+      var vec = obj as Vector3D;
+      if (vec != null) {
+        return X == vec.X && Y == vec.Y && Z == vec.Z;
+      }
+      return false;
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs	(revision 15454)
@@ -26,58 +26,67 @@
 using System.IO;
 using System.Linq;
+using System.Reflection;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Problems.Instances;
 using HeuristicLab.Random;
-
-namespace HeuristicLab.Problems.BinPacking3D {
+using HeuristicLab.Problems.BinPacking.Random;
+
+namespace HeuristicLab.Problems.BinPacking3D.Instances {
   // make sure that for each class we have a separate entry in the problem instance providers
+
   public class RandomInstanceClass1Provider : RandomInstanceProvider {
-    public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
-  }
+    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
+
+  }
+
   public class RandomInstanceClass2Provider : RandomInstanceProvider {
-    public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass3Provider : RandomInstanceProvider {
-    public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass4Provider : RandomInstanceProvider {
-    public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass5Provider : RandomInstanceProvider {
-    public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
+
   }
 
   public class RandomInstanceClass6Provider : RandomInstanceProvider {
-    public RandomInstanceClass6Provider() : base() {
+    public RandomInstanceClass6Provider() : base(new SRand48()) {
       @class = 6;
       binWidth = binHeight = binDepth = 10;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 11);
-      h = rand.Next(1, 11);
-      d = rand.Next(1, 11);
+      w = rand.Next(1, 10);
+      h = rand.Next(1, 10);
+      d = rand.Next(1, 10);
     }
   }
   public class RandomInstanceClass7Provider : RandomInstanceProvider {
-    public RandomInstanceClass7Provider() : base() {
+    public RandomInstanceClass7Provider() : base(new SRand48()) {
       @class = 7;
       binWidth = binHeight = binDepth = 40;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 36);
-      h = rand.Next(1, 36);
-      d = rand.Next(1, 36);
+      w = rand.Next(1, 35);
+      h = rand.Next(1, 35);
+      d = rand.Next(1, 35);
     }
   }
   public class RandomInstanceClass8Provider : RandomInstanceProvider {
-    public RandomInstanceClass8Provider() : base() {
+    public RandomInstanceClass8Provider() : base(new SRand48()) {
       @class = 8;
       binWidth = binHeight = binDepth = 100;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 101);
-      h = rand.Next(1, 101);
-      d = rand.Next(1, 101);
+      w = rand.Next(1, 100);
+      h = rand.Next(1, 100);
+      d = rand.Next(1, 100);
     }
   }
@@ -88,4 +97,18 @@
   public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
 
+    /// <summary>
+    /// Number of created test items. This items are used for packing them into the bin
+    /// </summary>
+    private readonly int[] _numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
+
+    /// <summary>
+    /// Number of instance for which should be created for each instance
+    /// </summary>
+    private readonly int _numberOfGeneratedInstances;
+
+    /// <summary>
+    /// Random generator for creating random packing items.
+    /// </summary>
+    private readonly IRandom _randomGenerator;
 
 
@@ -93,4 +116,6 @@
     protected int binWidth, binHeight, binDepth;
 
+    #region Common information for displaying on the ui
+
     public override string Name {
       get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
@@ -109,24 +134,40 @@
     }
 
-    public RandomInstanceProvider() : base() { }
-
+    #endregion
+
+
+    public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() {
+      _numberOfGeneratedInstances = numberOfGeneratedInstances;
+      if (numberOfGeneratedTestItems != null) {
+        _numberOfGeneratedTestItems = numberOfGeneratedTestItems;
+      }
+      _randomGenerator = randomGenerator;
+    }
+
+
+    /// <summary>
+    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
+    /// </summary>
+    /// <returns></returns>
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
       // 10 classes
-      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
-      foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
-        // get class parameters
-        // generate 30 different instances for each class
-        foreach (int instance in Enumerable.Range(1, 30)) {
+      foreach (int numItems in _numberOfGeneratedTestItems) {
+        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
           string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
-          var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
-          yield return dd;
+          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given, 
+           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
+           * This guarantees that the instances will always be the same
+           */
+          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
         }
       }
     }
+
 
     public override BPPData LoadData(IDataDescriptor dd) {
       var randDd = dd as RandomDataDescriptor;
-      if (randDd == null)
+      if (randDd == null) {
         throw new NotSupportedException("Cannot load data descriptor " + dd);
+      }
 
       var data = new BPPData() {
@@ -134,8 +175,8 @@
         Items = new PackingItem[randDd.NumItems]
       };
-      var instanceRand = new MersenneTwister((uint)randDd.Seed);
+      _randomGenerator.Reset(randDd.Seed);
       for (int i = 0; i < randDd.NumItems; i++) {
         int w, h, d;
-        SampleItemParameters(instanceRand, out w, out h, out d);
+        SampleItemParameters(_randomGenerator, out w, out h, out d);
         data.Items[i] = new PackingItem(w, h, d, data.BinShape);
       }
@@ -143,77 +184,82 @@
     }
 
-    // default implementation for class 1 .. 5
+
+    /// <summary>
+    /// Generates the dimensions for a item by using the given random generator
+    /// </summary>
+    /// <param name="rand">Given random generator</param>
+    /// <param name="w">Calculated width of the item</param>
+    /// <param name="h">Calculated height of the item</param>
+    /// <param name="d">Calculated depth of the item</param>
     protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      // for classes 1 - 5
       Contract.Assert(@class >= 1 && @class <= 5);
-      var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
+      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
       weights[@class - 1] = 0.6;
       var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
-
-      int minW, maxW;
-      int minH, maxH;
-      int minD, maxD;
-      GetItemParameters(type, rand, binWidth, binHeight, binDepth,
-        out minW, out maxW, out minH, out maxH, out minD, out maxD);
-
-      w = rand.Next(minW, maxW + 1);
-      h = rand.Next(minH, maxH + 1);
-      d = rand.Next(minD, maxD + 1);
-    }
-
-    private void GetItemParameters(int type, IRandom rand,
-      int w, int h, int d,
-      out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
+      */
+
+      // as by Martello and Vigo
+      int type = @class;
+      if (type <= 5) {
+        var t = rand.Next(1, 10);
+        if (t <= 5) {
+          type = t;
+        }
+      }
+
       switch (type) {
-        case 1: {
-            minW = 1;
-            maxW = w / 2; // integer division on purpose (see paper)
-            minH = h * 2 / 3;
-            maxH = h;
-            minD = d * 2 / 3;
-            maxD = d;
-            break;
-          }
-        case 2: {
-            minW = w * 2 / 3;
-            maxW = w;
-            minH = 1;
-            maxH = h / 2;
-            minD = d * 2 / 3;
-            maxD = d;
-            break;
-          }
-        case 3: {
-            minW = w * 2 / 3;
-            maxW = w;
-            minH = h * 2 / 3;
-            maxH = h;
-            minD = 1;
-            maxD = d / 2;
-            break;
-          }
-        case 4: {
-            minW = w / 2;
-            maxW = w;
-            minH = h / 2;
-            maxH = h;
-            minD = d / 2;
-            maxD = d;
-            break;
-          }
-        case 5: {
-            minW = 1;
-            maxW = w / 2;
-            minH = 1;
-            maxH = h / 2;
-            minD = 1;
-            maxD = d / 2;
-            break;
-          }
-        default: {
-            throw new InvalidProgramException();
-          }
-      }
-    }
+        case 1:
+          CreateInstanceDimensionsType1(rand, out w, out h, out d);
+          break;
+        case 2:
+          CreateInstanceDimensionsType2(rand, out w, out h, out d);
+          break;
+        case 3:
+          CreateInstanceDimensionsType3(rand, out w, out h, out d);
+          break;
+        case 4:
+          CreateInstanceDimensionsType4(rand, out w, out h, out d);
+          break;
+        case 5:
+          CreateInstanceDimensionsType5(rand, out w, out h, out d);
+          break;
+        default:
+          throw new InvalidProgramException();
+      }
+    }
+
+
+    #region Instance dimensions generators for type 1 - 5
+    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(1, binWidth / 2);
+      h = rand.Next((binHeight * 2) / 3, binHeight);
+      d = rand.Next((binDepth * 2) / 3, binDepth);
+    }
+
+    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(((binWidth * 2) / 3), binWidth);
+      h = rand.Next(1, binHeight / 2);
+      d = rand.Next(((binDepth * 2) / 3), binDepth);
+    }
+
+    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(((binWidth * 2) / 3), binWidth);
+      h = rand.Next(((binHeight * 2) / 3), binHeight);
+      d = rand.Next(1, binDepth / 2);
+    }
+    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(binWidth / 2, binWidth);
+      h = rand.Next(binHeight / 2, binHeight);
+      d = rand.Next(binDepth / 2, binDepth);
+    }
+    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(1, binWidth / 2);
+      h = rand.Next(1, binHeight / 2);
+      d = rand.Next(1, binDepth / 2);
+    }
+
+    #endregion
+
+
 
     public override bool CanImportData {
@@ -242,10 +288,8 @@
           else
             writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
-
         }
         writer.Flush();
       }
     }
-
   }
 }
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProviderWithSRand.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProviderWithSRand.cs	(revision 15424)
+++ 	(revision )
@@ -1,363 +1,0 @@
-﻿#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
- */
-#endregion
-
-
-using System;
-using System.Collections.Generic;
-using System.Diagnostics.Contracts;
-using System.IO;
-using System.Linq;
-using System.Reflection;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Problems.Instances;
-using HeuristicLab.Random;
-
-namespace HeuristicLab.Problems.BinPacking3D {
-  // make sure that for each class we have a separate entry in the problem instance providers
-  
-  public class RandomInstanceClass1ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass1ProviderWithSRand() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
-    
-  }
-
-  public class RandomInstanceClass2ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass2ProviderWithSRand() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
-    
-  }
-  public class RandomInstanceClass3ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass3ProviderWithSRand() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
-    
-  }
-  public class RandomInstanceClass4ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass4ProviderWithSRand() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
-    
-  }
-  public class RandomInstanceClass5ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass5ProviderWithSRand() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
-    
-  }
-
-  public class RandomInstanceClass6ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass6ProviderWithSRand() : base() {
-      @class = 6;
-      binWidth = binHeight = binDepth = 10;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 10);
-      h = rand.Next(1, 10);
-      d = rand.Next(1, 10);
-    }
-  }
-  public class RandomInstanceClass7ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass7ProviderWithSRand() : base() {
-      @class = 7;
-      binWidth = binHeight = binDepth = 40;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 35);
-      h = rand.Next(1, 35);
-      d = rand.Next(1, 35);
-    }
-  }
-  public class RandomInstanceClass8ProviderWithSRand : RandomInstanceProviderWithSRand {
-    public RandomInstanceClass8ProviderWithSRand() : base() {
-      @class = 8;
-      binWidth = binHeight = binDepth = 100;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 100);
-      h = rand.Next(1, 100);
-      d = rand.Next(1, 100);
-    }
-  }
-
-  // class 9 from the paper (all-fill) is not implemented 
-
-
-  public abstract class RandomInstanceProviderWithSRand : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
-
-    /// <summary>
-    /// Number of created test items. This items are used for packing them into the bin
-    /// </summary>
-    //private static readonly int[] numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
-    private static readonly int[] numberOfGeneratedTestItems = new int[] { 50, 100, 150, 200 };
-
-    /// <summary>
-    /// Number of instance for which should be created for each instance
-    /// </summary>
-    private static readonly int numberOfGeneratedInstances = 10;
-
-    #region Random Generator srand48
-    protected class SRand48 : Item, IRandom {
-      private object locker = new object();
-
-      private bool init = false;
-
-      private uint _h48;
-      private uint _l48;
-
-      public SRand48() {
-        if (!init) {
-          Seed((uint)DateTime.Now.Ticks);
-          init = true;
-        }
-      }
-      public SRand48(uint seed) {
-        if (!init) {
-          Seed(seed);
-          init = true;
-        }
-      }
-
-      public override IDeepCloneable Clone(Cloner cloner) {
-        throw new NotImplementedException();
-      }
-
-      public int Next() {
-        lock (locker) {
-          return (int)LRand48x();
-        }
-      }
-
-      public int Next(int maxVal) {
-        lock (locker) {
-          if (maxVal <= 0)
-            throw new ArgumentException("The interval [0, " + maxVal + ") is empty");
-          return (int)(LRand48x() % maxVal);
-        }
-      }
-
-      public int Next(int minVal, int maxVal) {
-        lock (locker) {
-          if (maxVal <= minVal)
-            throw new ArgumentException("The interval [" + minVal + ", " + maxVal + ") is empty");
-          return Next(maxVal - minVal + 1) + minVal;
-        }
-      }
-
-      public double NextDouble() {
-        lock (locker) {
-          return ((double)Next()) * (1.0 / 4294967296.0);
-        }
-      }
-
-      public void Reset() {
-        lock (locker) {
-          Seed((uint)DateTime.Now.Ticks);
-        }
-      }
-
-      public void Reset(int seed) {
-        lock (locker) {
-          Seed((uint)seed);
-        }
-      }
-
-      private void Seed(uint seed) {
-        _h48 = seed;
-        _l48 = 0x330E;
-      }
-
-      private int LRand48x() {
-        _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC);
-        _l48 = _l48 * 0xE66D + 0xB;
-        _h48 = _h48 + (_l48 >> 16);
-        _l48 = _l48 & 0xFFFF;
-        return (int)(_h48 >> 1);
-      }
-
-    }
-
-    #endregion
-
-    protected int @class;
-    protected int binWidth, binHeight, binDepth;
-
-    #region Common information for displaying it on the ui
-    
-    public override string Name {
-      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
-    }
-
-    public override string Description {
-      get { return "Randomly generated 3d bin packing problems as described in Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
-    }
-
-    public override Uri WebLink {
-      get { return null; }
-    }
-
-    public override string ReferencePublication {
-      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
-    }
-
-    #endregion
-    public RandomInstanceProviderWithSRand() : base() { }
-
-    
-    /// <summary>
-    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
-    /// </summary>
-    /// <returns></returns>
-    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
-      // 10 classes
-      foreach (int numItems in numberOfGeneratedTestItems) {
-        for (int instance = 1; instance <= numberOfGeneratedInstances; instance++) {
-          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
-          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given, 
-           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
-           * This guarantees that the instances will always be the same
-           */
-          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
-        }
-      }
-    }
-
-    
-    public override BPPData LoadData(IDataDescriptor dd) {
-      var randDd = dd as RandomDataDescriptor;
-      if (randDd == null)
-        throw new NotSupportedException("Cannot load data descriptor " + dd);
-
-      var data = new BPPData() {
-        BinShape = new PackingShape(binWidth, binHeight, binDepth),
-        Items = new PackingItem[randDd.NumItems]
-      };
-      var instanceRand = new SRand48((uint)randDd.Seed);
-      for (int i = 0; i < randDd.NumItems; i++) {
-        int w, h, d;
-        SampleItemParameters(instanceRand, out w, out h, out d);
-        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
-      }
-      return data;
-    }
-
-    
-    /// <summary>
-    /// Generates the dimensions for a item by using the given random generator
-    /// </summary>
-    /// <param name="rand">Given random generator</param>
-    /// <param name="w">Calculated width of the item</param>
-    /// <param name="h">Calculated height of the item</param>
-    /// <param name="d">Calculated depth of the item</param>
-    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      Contract.Assert(@class >= 1 && @class <= 5);
-      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
-      weights[@class - 1] = 0.6;
-      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
-      */
-
-      // as by Martello and Vigo
-      int type = @class;
-      if (type <= 5) {
-        var t = rand.Next(1, 10);
-        if (t <= 5) {
-          type = t;
-        }
-      }
-
-      switch (type) {
-        case 1:
-          CreateInstanceDimensionsType1(rand, out w, out h, out d);
-          break;
-        case 2:
-          CreateInstanceDimensionsType2(rand, out w, out h, out d);
-          break;
-        case 3:
-          CreateInstanceDimensionsType3(rand, out w, out h, out d);
-          break;
-        case 4:
-          CreateInstanceDimensionsType4(rand, out w, out h, out d);
-          break;
-        case 5:
-          CreateInstanceDimensionsType5(rand, out w, out h, out d);
-          break;
-        default: 
-            throw new InvalidProgramException();
-      }
-    }
-
-    
-    #region Instance dimensions generators for type 1 - 5
-    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, binWidth / 2);
-      h = rand.Next((binHeight * 2) / 3, binHeight);
-      d = rand.Next((binDepth * 2) / 3, binDepth);
-    }
-
-    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(((binWidth * 2) / 3), binWidth);
-      h = rand.Next(1, binHeight / 2);
-      d = rand.Next(((binDepth * 2) / 3), binDepth);
-    }
-
-    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(((binWidth * 2) / 3), binWidth);
-      h = rand.Next(((binHeight * 2) / 3), binHeight);
-      d = rand.Next(1, binDepth / 2);
-    }
-    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(binWidth / 2, binWidth);
-      h = rand.Next(binHeight / 2, binHeight);
-      d = rand.Next(binDepth / 2, binDepth);
-    }
-    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, binWidth / 2);
-      h = rand.Next(1, binHeight / 2);
-      d = rand.Next(1, binDepth / 2);
-    }
-   
-    #endregion
-
-
-
-    public override bool CanImportData {
-      get { return false; }
-    }
-    public override BPPData ImportData(string path) {
-      throw new NotSupportedException();
-    }
-
-    public override bool CanExportData {
-      get { return true; }
-    }
-
-    public override void ExportData(BPPData instance, string file) {
-      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
-        Export(instance, stream);
-      }
-    }
-    public static void Export(BPPData instance, Stream stream) {
-
-      using (var writer = new StreamWriter(stream)) {
-        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
-        for (int i = 0; i < instance.NumItems; i++) {
-          if (i == 0)
-            writer.WriteLine("{0,-5} {1,-5} {2,-5}   W(I),H(I),D(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
-          else
-            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
-        }
-        writer.Flush();
-      }
-    }
-  }
-}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15454)
@@ -0,0 +1,79 @@
+﻿using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Packer {
+  [Item("BinPacker", "A class for packing bins for the 3D bin-packer problem.")]
+  [StorableClass]
+  public abstract class BinPacker {
+    protected Permutation _permutation;
+    protected PackingShape _binShape;
+    protected IList<PackingItem> _items;
+    protected bool _useStackingConstraints;
+
+    /// <summary>
+    /// Packs all items of the bin packer and returns a collection of BinPacking3D objects
+    /// </summary>
+    /// <returns></returns>
+    public abstract IList<BinPacking3D> PackItems();
+
+    /// <summary>
+    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
+    /// </summary>
+    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
+    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
+    /// <param name="packingBin">This object will be filled with some of the given items</param>
+    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
+
+      foreach (var itemId in new List<int>(remainingIds)) {
+        bool rotated = rotationArray == null ? false : rotationArray[itemId];
+        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
+        // if a valid packing position could be found, the current item can be added to the given bin
+        if (position != null) {
+          PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
+          remainingIds.Remove(itemId);
+        }
+      }
+    }
+
+    /// <summary>
+    /// Pack a given item into a given bin and updates the residual space and the extreme points
+    /// </summary>
+    /// <param name="packingBin"></param>
+    /// <param name="itemId"></param>
+    /// <param name="packingItem"></param>
+    /// <param name="position"></param>
+    protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
+
+      packingBin.AddItem(itemId, packingItem, position);
+      packingBin.UpdateResidualSpace(packingItem, position);
+      packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);
+    }
+
+    /// <summary>
+    /// This method tries to find a valid packing position for an given item in a given packing bin
+    /// </summary>
+    /// <param name="packingBin"></param>
+    /// <param name="packingItem"></param>
+    /// <param name="useStackingConstraints"></param>
+    /// <param name="rotated"></param>
+    /// <returns>Returns the packing position for an given item. If there could not be found a valid position it returns null</returns>
+    protected PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints, bool rotated) {
+      PackingItem newItem = new PackingItem(
+        rotated ? packingItem.Depth : packingItem.Width,
+        packingItem.Height,
+        rotated ? packingItem.Width : packingItem.Depth,
+        packingItem.TargetBin, packingItem.Weight, packingItem.Material);
+
+      // The extremepoints are sortet by Z, X, Y
+
+      return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs	(revision 15454)
@@ -0,0 +1,41 @@
+﻿using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Packer {
+
+  [Item("BinPackerFirstFit", "A class for packing bins for the 3D bin-packer problem. It uses a first fit algorithm")]
+  [StorableClass]
+  public class BinPackerFirstFit : BinPacker {
+
+    public BinPackerFirstFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      _permutation = permutation;
+      _binShape = binShape;
+      _items = items;
+      _useStackingConstraints = useStackingConstraints;
+    }
+
+
+    /// <summary>
+    /// Packs the items of the object by using a first fit algorithm into an amount of bins and returns them
+    /// </summary>
+    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
+    public override IList<BinPacking3D> PackItems() {
+      IList<BinPacking3D> packingList = new List<BinPacking3D>();
+      IList<int> remainingIds = new List<int>(_permutation);
+
+      while (remainingIds.Count > 0) {
+        BinPacking3D packingBin = new BinPacking3D(_binShape);
+        PackRemainingItems(ref remainingIds, ref packingBin, _items, _useStackingConstraints, null);
+        packingList.Add(packingBin);
+      }
+
+      return packingList;
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs	(revision 15454)
@@ -0,0 +1,56 @@
+﻿using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Packer {
+  [Item("BinPackerFreeVolumeBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the free volume.")]
+  [StorableClass]
+  public class BinPackerFreeVolumeBestFit : BinPacker {
+    public BinPackerFreeVolumeBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      _permutation = permutation;
+      _binShape = binShape;
+      _items = items;
+      _useStackingConstraints = useStackingConstraints;
+    }
+
+    public override IList<BinPacking3D> PackItems() {
+      IList<BinPacking3D> packingList = new List<BinPacking3D>();
+      IList<int> remainingIds = new List<int>(_permutation);
+      
+
+      foreach (int remainingId in remainingIds) {
+        var sortedBins = packingList.OrderBy(x => x.FreeVolume);
+        PackingItem item = _items[remainingId];
+        bool positionFound = false;
+
+        foreach (var packingBin in sortedBins) {
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+          positionFound = position != null;
+          var bin = packingBin;
+          if (positionFound) {
+            PackItem(ref bin, remainingId, item, position, _useStackingConstraints);
+            break;
+          }            
+        }
+
+        if (!positionFound) {
+          BinPacking3D packingBin = new BinPacking3D(_binShape);
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+
+          if (position == null) {
+            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in empty bin.");
+          }
+
+          PackItem(ref packingBin, remainingId, item, position, _useStackingConstraints);
+          packingList.Add(packingBin);
+        }
+      }
+      return packingList.ToList();
+    }
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs	(revision 15454)
@@ -0,0 +1,97 @@
+﻿using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Packer {
+  [Item("BinPackerResidualSpaceBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the residual space.")]
+  [StorableClass]
+  public class BinPackerResidualSpaceBestFit : BinPacker {
+    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      _permutation = permutation;
+      _binShape = binShape;
+      _items = items;
+      _useStackingConstraints = useStackingConstraints;
+    }
+
+    /// <summary>
+    /// Packs the items into the bins by using a best fit residual space algorithm.
+    /// The order of the chosen items depends on the merit function. 
+    /// Each residual space belongs to an extreme point.
+    /// </summary>
+    /// <returns></returns>
+    public override IList<BinPacking3D> PackItems() {
+      IList<BinPacking3D> packingList = new List<BinPacking3D>();
+      IList<int> remainingIds = new List<int>(_permutation);
+      bool rotated = false;
+
+      foreach (var remainingId in remainingIds) {
+        PackingItem item = _items[remainingId];
+        var residualSpacePoints = GetResidualSpaceForAllPoints(packingList, item);
+        var sortedPoints = residualSpacePoints.OrderBy(x => x.Item3);
+        var packed = false;
+
+        foreach (var point in sortedPoints) {
+          if (point.Item1.IsPositionFeasible(item, point.Item2, _useStackingConstraints)) {
+            var binPacking = point.Item1;
+            PackItem(ref binPacking, remainingId, item, point.Item2, _useStackingConstraints);
+            packed = true;
+            break;
+          }
+        }
+
+        if (!packed) {
+          BinPacking3D binPacking = new BinPacking3D(_binShape);
+          var position = FindPackingPositionForItem(binPacking, item, _useStackingConstraints, rotated);
+          if (position != null) {
+            PackItem(ref binPacking, remainingId, item, position, _useStackingConstraints);
+          } else {
+            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
+          }
+          packingList.Add(binPacking);
+        }
+      }
+
+      return packingList;
+    }
+
+    /// <summary>
+    /// This method returns a list with all bins and their residual space where a given item can be placed.
+    /// It is nessecary to get all bins and their residaul space because this list will be sortet later.
+    /// </summary>
+    /// <param name="packingList"></param>
+    /// <param name="item"></param>
+    /// <returns></returns>
+    public static IList<Tuple<BinPacking3D, PackingPosition, int>> GetResidualSpaceForAllPoints(IList<BinPacking3D> packingList, PackingItem item) {
+      var residualSpacePoints = new List<Tuple<BinPacking3D, PackingPosition, int>>();
+      foreach (BinPacking3D bp in packingList) {
+        foreach (var ep in bp.ExtremePoints) {
+          var rs = bp.ResidualSpace[ep];
+          if (rs.Item1 < item.Width || rs.Item2 < item.Height || rs.Item3 < item.Depth) {
+            continue;
+          }
+          residualSpacePoints.Add(Tuple.Create(bp, ep, CalculateResidualMerit(rs, item, ep)));
+        }
+      }
+      return residualSpacePoints;
+    }
+
+    /// <summary>
+    /// The merit function puts an item on the EP that minimizes the difference between its residual space an the item dimension
+    /// </summary>
+    /// <param name="rs"></param>
+    /// <param name="item"></param>
+    /// <param name="ep"></param>
+    /// <returns></returns>
+    private static int CalculateResidualMerit(Tuple<int, int, int> rs, PackingItem item, PackingPosition ep) {
+      return ((rs.Item1 - item.Width) +
+          (rs.Item2 - item.Height) +
+          (rs.Item3 - item.Depth));
+    }
+
+  }
+}
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs	(revision 15454)
@@ -103,4 +103,10 @@
     #region IComparable<PackingPosition> Members
 
+    /// <summary>
+    /// Compares two packing positions by their coordinates. 
+    /// The order of comparing is z -> x -> y.
+    /// </summary>
+    /// <param name="other"></param>
+    /// <returns></returns>
     public int CompareTo(PackingPosition other) {
       int result = Z.CompareTo(other.Z);
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs	(revision 15454)
@@ -32,7 +32,8 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.Packer;
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  
+
   public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
   public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
@@ -86,5 +87,5 @@
       Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
       Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
-      
+
       Problem = new PermutationProblem();
     }
@@ -93,9 +94,13 @@
       return new ExtremePointAlgorithm(this, cloner);
     }
-    
+
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
     }
 
+    /// <summary>
+    /// Runs the extreme point algorithm and adds the results to the property <see cref="Result"/>
+    /// </summary>
+    /// <param name="token"></param>
     protected override void Run(CancellationToken token) {
       var items = Problem.Items;
@@ -109,13 +114,13 @@
         fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
       }
+
+      //
       var result = GetBest(bin, items, sorting, fitting, token);
-      if (result == null) throw new InvalidOperationException("No result obtained!");
-
-      Results.Add(new Result("Best Solution",
-        "The best found solution",
-        result.Item1));
-      Results.Add(new Result("Best Solution Quality",
-        "The quality of the best found solution according to the evaluator",
-        new DoubleValue(result.Item2)));
+      if (result == null) {
+        throw new InvalidOperationException("No result obtained!");
+      }
+
+      Results.Add(new Result("Best Solution", "The best found solution", result.Item1));
+      Results.Add(new Result("Best Solution Quality", "The quality of the best found solution according to the evaluator", new DoubleValue(result.Item2)));
 
       var binUtil = new BinUtilizationEvaluator();
@@ -128,12 +133,15 @@
         new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
 
-      if (result.Item3.HasValue && sorting.Length > 1)
+      if (result.Item3.HasValue && sorting.Length > 1) {
         Results.Add(new Result("Best Sorting Method",
           "The sorting method that found the best solution",
           new EnumValue<SortingMethod>(result.Item3.Value)));
-      if (result.Item4.HasValue && fitting.Length > 1)
+      }
+
+      if (result.Item4.HasValue && fitting.Length > 1) {
         Results.Add(new Result("Best Fitting Method",
           "The fitting method that found the best solution",
           new EnumValue<FittingMethod>(result.Item4.Value)));
+      }
     }
 
@@ -146,8 +154,9 @@
         foreach (var sort in sortings) {
           var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
-          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
-          if (double.IsNaN(best)
-            || Problem.Maximization && result.Item2 > best
-            || !Problem.Maximization && result.Item2 < best) {
+          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
+            continue;
+          }
+
+          if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
             bestSolution = result.Item1;
             best = result.Item2;
@@ -155,14 +164,68 @@
             bestFitting = fit;
           }
-          if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+          if (token.IsCancellationRequested) {
+            return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+          }
         }
       }
-      if (double.IsNaN(best)) return null;
+      if (double.IsNaN(best)) {
+        return null;
+      }
       return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     }
 
     private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
+      Permutation sortedItems = SortItemsBySortingMethod(bin, items, sorting, delta);
+
+      if (false) {// alt
+        ExtremePointPermutationDecoderBase decoder = GetDecoderByFittingMethod(fitting);
+        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
+        var fit = evaluator.Evaluate(sol);
+
+        return Tuple.Create(sol, fit);
+      } else {
+        Decoder.ExtremePointPermutationDecoder decoder = new Decoder.ExtremePointPermutationDecoder(GetBinPackerByFittingMethod(fitting, sortedItems, bin, items, stackingConstraints));
+
+        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
+        var fit = evaluator.Evaluate(sol);
+
+        return Tuple.Create(sol, fit);
+      }
+      
+
+      
+    }
+
+
+
+    private static BinPacker GetBinPackerByFittingMethod(FittingMethod fittingMethod, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      BinPacker binPacker = null;
+      switch (fittingMethod) {
+        case FittingMethod.FirstFit:
+          binPacker = new BinPackerFirstFit(sortedItems, binShape, items, useStackingConstraints);
+          break;
+        case FittingMethod.FreeVolumeBestFit:
+          binPacker = new BinPackerFreeVolumeBestFit(sortedItems, binShape, items, useStackingConstraints);
+          break;
+        case FittingMethod.ResidualSpaceBestFit:
+          binPacker = new BinPackerResidualSpaceBestFit(sortedItems, binShape, items, useStackingConstraints);
+          break;
+        default:
+          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
+      }
+      return binPacker;
+    }
+
+    /// <summary>
+    /// Returns a new permutation of the given items depending on the sorting method
+    /// </summary>
+    /// <param name="bin"></param>
+    /// <param name="items"></param>
+    /// <param name="sortingMethod"></param>
+    /// <param name="delta"></param>
+    /// <returns></returns>
+    private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
       Permutation sorted = null;
-      switch (sorting) {
+      switch (sortingMethod) {
         case SortingMethod.Given:
           sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
@@ -216,9 +279,18 @@
                         .Select(x => x.Index).ToArray());
           break;
-        default: throw new ArgumentException("Unknown sorting method: " + sorting);
-      }
-      
+        default:
+          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
+      }
+      return sorted;
+    }
+
+    /// <summary>
+    /// Returns a decoder depending on the given fitting method
+    /// </summary>
+    /// <param name="fittingMethod"></param>
+    /// <returns></returns>
+    private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
       ExtremePointPermutationDecoderBase decoder = null;
-      switch (fitting) {
+      switch (fittingMethod) {
         case FittingMethod.FirstFit:
           decoder = new ExtremePointPermutationDecoder();
@@ -230,11 +302,8 @@
           decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
           break;
-        default: throw new ArgumentException("Unknown fitting method: " + fitting);
-      }
-
-      var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
-      var fit = evaluator.Evaluate(sol);
-
-      return Tuple.Create(sol, fit);
+        default:
+          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
+      }
+      return decoder;
     }
   }
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs	(revision 15454)
@@ -37,7 +37,10 @@
     #region Properties
     [Storable]
+
+    //key = item id
     public ObservableDictionary<int, TPos> Positions { get; private set; }
 
     [Storable]
+    //key = item id
     public ObservableDictionary<int, TItem> Items { get; private set; }
 
@@ -138,6 +141,17 @@
       return false;
     }
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <returns></returns>
     public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
-      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
+      //In this case feasability is defined as following: 
+      //1. the item fits into the bin-borders; 
+      //2. the point is supported by something; 
+      //3. the item does not collide with another already packed item
       if (!BinShape.Encloses(position, item))
         return false;
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15424)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15454)
@@ -103,8 +103,16 @@
     <Compile Include="2D\ProblemBase.cs" />
     <Compile Include="2D\Solution.cs" />
+    <Compile Include="3D\Packer\BinPacker.cs" />
+    <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
     <Compile Include="3D\BinPacking3D.cs" />
+    <Compile Include="3D\Decoder\ExtremePointPermutationDecoder.cs" />
     <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
     <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
-    <Compile Include="3D\Instances\RandomInstanceProviderWithSRand.cs" />
+    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
+    <Compile Include="3D\Geometry\Line3D.cs" />
+    <Compile Include="3D\Geometry\Plane3D.cs" />
+    <Compile Include="3D\Geometry\Vector3D.cs" />
+    <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
+    <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
     <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
@@ -112,5 +120,4 @@
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
     <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
-    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
@@ -150,4 +157,5 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="Random\SRand48.cs" />
   </ItemGroup>
   <ItemGroup>
Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Random/SRand48.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Random/SRand48.cs	(revision 15454)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Random/SRand48.cs	(revision 15454)
@@ -0,0 +1,163 @@
+﻿/* 
+ * C# port of the implementation of the srand48 random generator.
+ * First implemented in test3dbpp.c by S. Martello, D. Pisinger, D. Vigo, E. den Boef, J. Korst (2003) 
+ */
+using HeuristicLab.Core;
+using System;
+using HeuristicLab.Common;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.BinPacking.Random {
+
+  [Item("SRand", "A pseudo random number generator which creates uniformly distributed random numbers.")]
+  [StorableClass]
+  public sealed class SRand48 : Item, IRandom {
+    private object locker = new object();
+
+    [Storable]
+    private bool init = false;
+    [Storable]
+    private uint _h48;
+    [Storable]
+    private uint _l48;
+    
+
+    /// <summary>
+    /// Used by HeuristicLab.Persistence to initialize new instances during deserialization.
+    /// </summary>
+    /// <param name="deserializing">true, if the constructor is called during deserialization.</param>
+    [StorableConstructor]
+    private SRand48(bool deserializing) : base(deserializing) { }
+
+    /// <summary>
+    /// Initializes a new instance from an existing one (copy constructor).
+    /// </summary>
+    /// <param name="original">The original <see cref="SRand48"/> instance which is used to initialize the new instance.</param>
+    /// <param name="cloner">A <see cref="Cloner"/> which is used to track all already cloned objects in order to avoid cycles.</param>
+    private SRand48(SRand48 original, Cloner cloner)
+      : base(original, cloner) {
+      _h48 = original._h48;
+      _l48 = original._l48;
+      init = original.init;
+    }
+
+
+    /// <summary>
+    /// Initializes a new instance of <see cref="SRand48"/>.
+    /// </summary>
+    public SRand48() {
+      if (!init) {
+        Seed((uint)DateTime.Now.Ticks);
+        init = true;
+      }
+    }
+
+    /// <summary>
+    /// Initializes a new instance of <see cref="SRand48"/> 
+    /// with the given seed <paramref name="seed"/>.
+    /// </summary>
+    /// <param name="seed">The seed with which to initialize the random number generator.</param>
+    public SRand48(uint seed) {
+      if (!init) {
+        Seed(seed);
+        init = true;
+      }
+    }
+
+    /// <summary>
+    /// Clones the current instance (deep clone).
+    /// </summary>
+    /// <param name="cloner">Dictionary of all already cloned objects. (Needed to avoid cycles.)</param>
+    /// <returns>The cloned object as <see cref="SRand48"/>.</returns>
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new SRand48(this, cloner);
+    }
+
+    /// <summary>
+    /// Gets a new random number.
+    /// </summary>
+    /// <returns>A new int random number.</returns>
+    public int Next() {
+      lock (locker) {
+        return (int)LRand48x();
+      }
+    }
+
+    /// <summary>
+    /// Gets a new random number being smaller than the given <paramref name="maxVal"/>.
+    /// </summary>
+    /// <exception cref="ArgumentException">Thrown when the given maximum value is 
+    /// smaller or equal to zero.</exception>
+    /// <param name="maxVal">The maximum value of the generated random number.</param>
+    /// <returns>A new int random number.</returns>
+    public int Next(int maxVal) {
+      lock (locker) {
+        if (maxVal <= 0)
+          throw new ArgumentException("The interval [0, " + maxVal + ") is empty");
+        return (int)(LRand48x() % maxVal);
+      }
+    }
+
+    /// <summary>
+    /// Gets a new random number being in the given interval <paramref name="minVal"/> and 
+    /// <paramref name="maxVal"/>.
+    /// </summary>
+    /// <param name="minVal">The minimum value of the generated random number.</param>
+    /// <param name="maxVal">The maximum value of the generated random number.</param>
+    /// <returns>A new int random number.</returns>
+    public int Next(int minVal, int maxVal) {
+      lock (locker) {
+        if (maxVal <= minVal)
+          throw new ArgumentException("The interval [" + minVal + ", " + maxVal + ") is empty");
+        return Next(maxVal - minVal + 1) + minVal;
+      }
+    }
+
+    /// <summary>
+    /// Gets a new double random variable.
+    /// </summary>
+    /// <returns></returns>
+    public double NextDouble() {
+      lock (locker) {
+        return ((double)Next()) * (1.0 / 4294967296.0);
+      }
+    }
+
+    /// <summary>
+    /// Resets the current random number generator.
+    /// </summary>
+    public void Reset() {
+      lock (locker) {
+        Seed((uint)DateTime.Now.Ticks);
+      }
+    }
+
+    /// <summary>
+    /// Resets the current random number generator with the given seed <paramref name="s"/>.
+    /// </summary>
+    /// <param name="seed">The seed with which to reset the current instance.</param>
+    public void Reset(int seed) {
+      lock (locker) {
+        Seed((uint)seed);
+      }
+    }
+
+    /// <summary>
+    /// Initializes current instance with random seed.
+    /// </summary>
+    /// <param name="seed">A starting seed.</param>
+    private void Seed(uint seed) {
+      _h48 = seed;
+      _l48 = 0x330E;
+    }
+
+    private int LRand48x() {
+      _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC);
+      _l48 = _l48 * 0xE66D + 0xB;
+      _h48 = _h48 + (_l48 >> 16);
+      _l48 = _l48 & 0xFFFF;
+      return (int)(_h48 >> 1);
+    }
+    
+  }
+}
