Click here to Skip to main content
15,122,559 members
Please Sign up or sign in to vote.
5.00/5 (3 votes)
See more:
I've looked over several examples for this but can't seem to implement it properly. I'm writing a game and want to make a backup of the game pieces so the player can 'undo' a move, phase, or turn. All my copies seem to be shallow copies, and I'd like to implement a deep copy with ICloneable instead of using ConvertAll, but after several days of not getting anything to work, I'm ready to try anything. I'd like a simple, straight forward, solution though. Here's a sample of what I've got:

C#
using System;
using System.Configuration;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace CiG
{
    public partial class CiG : Form
    {	
		public List<UnitsInPlayData> UiP = new List<UnitsInPlayData>();

		public class UnitsInPlayData
		{
			public int Item1 { get; set; }
			public string Item2 { get; set; }
			public bool Item3 { get; set; }
			public int[] Item4 { get; set; }
		}
	}
}


Can someone please get me moving forward again? Thanks!
Posted
Comments
Sergey Alexandrovich Kryukov 16-Sep-13 17:14pm
   
And where is the IClonable in your code? How it is even relevant to the question.
—SA
Member 10040991 16-Sep-13 17:28pm
   
I took all my botched attempts out and provided the code I started with.
Sergey Alexandrovich Kryukov 16-Sep-13 18:12pm
   
It's quite far from you are talking about.
Okay, please see my answer, ask your follow up questions, if any.
—SA
BillWoodruff 16-Sep-13 23:26pm
   
I think this is an excellent question, and the responses of Sergey are worthy of careful study. I seem to remember seeing an article here on CP about implementing an 'undo facility.

I assume that your "real" Class, that you mention has "40 attributes," you have some very complex nested Types, yes ?

I don't have total confidence, yet, that my experiments with deep cloning WinForms Controls are "robust," so I won't answer here, but here are some links I found very valuable:

// Cloning Events
// Alex Aza http://stackoverflow.com/a/6055422

// Generic Cloning
// Marcel Roma http://stackoverflow.com/a/10267292
// also see Stuart Helwig http://stackoverflow.com/a/3473722/133321

The place I "ground to a halt" in my experiments was in trying to understand and use BindingFlags.FlattenHierarchy http://msdn.microsoft.com/EN-US/library/cexkb29a(v=VS.110,d=hv.2).aspx

About which MSDN comments: "Specifies that public and protected static members up the hierarchy should be returned. Private static members in inherited classes are not returned. Static members include fields, methods, events, and properties. Nested types are not returned."

I'll leave you with a "wild thought:" how about a List that contains 40 stacks, queues, or other appropriate data structures :)

good luck, Bill
BillWoodruff 17-Sep-13 4:01am
   
An afterthought: it would be of interest to me if you would clarify exactly what you mean by "forty attributes." In .NET "attributes" has a special meaning, and I would be interested to know specifically the range of fields, or whatever, you need to save, in order to have a usable undo facility.
Member 10040991 17-Sep-13 6:42am
   
Like the example I provided above, just 40+ items. No nested classes, just basic variables. I suppose I could try the serializable approach, but wasn't sure the int[] array and bool would translate easily.
BillWoodruff 17-Sep-13 13:37pm
   
You certainly won't have any problem serializing fields like int, string, or arrays of ints.

Depending on the number of "undo levels" you wish to support, my guess is you can handle this in memory. Have you thought about using a Stack ?

Of course, everything depends on what kind of game this is, if it uses a "grid" so there are #nx#n locations which "pieces" can occupy, whether it is single-player, multi-player on one machine, or multi- on several machines via a network, or via internet, or whatever.

And, the "sophistication" of the type of undo facility you want to implement will determine many things, as well as the required speed of response of the game.
BillWoodruff 18-Sep-13 9:20am
   
I'm curious: do you feel you are "on track" now, or would you like some additional feedback ?

If you think a bit, you will probably be able to see, that IClonable won't help you to implement deep cloning, because the library type implementing this interface implement, well, just the shallow cloning.

The problem is the recursion assumed by the idea of shallow cloning. Ideally, you would need to clone all objects according to the interface implementation and try to clone all references instead of copying them, but how? A reference of some other object may implement IClonable, but that implementation may or may not be deep. Actually, the interface implies that the implementation is shallow.

How can you work around this problem? One of approaches could be this: implement the parallel mechanism. Let's say, you want to introduce another interface assuming that the objects implementing it would implement the deep cloning:
C#
    public interface IDeepCloneable {
        IDeepCloneable DeepClone();
    } //interface IDeepCloneable
}

Still, you cannot guarantee that the types implementing this interface will actually implement deep cloning, but you can require that they do it and assume that they actually do. Under this assumption, you can even implement "universal" deep cloning algorithm which you can pass to the derived classes of some base "deep clonable" class and use the required recursion. Then it could look like this:
C#
using System.Reflection;

//...

    public class DeepClonable : IDeepCloneable {
        IDeepCloneable IDeepCloneable.DeepClone() {
            Type deepClonableType = typeof(IDeepCloneable);
            FieldInfo[] fields = this.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance);
            IDeepCloneable clone = new DeepClonable();
            foreach (FieldInfo field in fields) {
                Type fieldType = field.FieldType;
                object fieldValue = field.GetValue(this);
                if (fieldValue == null) {
                    field.SetValue(clone, fieldValue);
                    continue;
                } //if 
                if (deepClonableType.IsAssignableFrom(fieldType)) { // deep:
                    IDeepCloneable fieldClone = ((IDeepCloneable)fieldValue).DeepClone();
                    field.SetValue(clone, fieldClone);
                } else // shallow:
                    field.SetValue(clone, fieldValue);
            } //loop
            return clone;            
        } //IDeepCloneable.DeepClone
    } //class DeepClonable


[EDIT #1]

Alternatively/additionally, you can use ICloneable in combination with the above, to provide a fall-back mechanism using ICloneable objects not implementing ICloneable for shallow cloning:
C#
public class DeepClonable : IDeepCloneable {
    IDeepCloneable IDeepCloneable.DeepClone() {
        Type deepClonableType = typeof(IDeepCloneable);
        Type clonableType = typeof(ICloneable);
        FieldInfo[] fields = this.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance);
        IDeepCloneable clone = new DeepClonable();
        foreach (FieldInfo field in fields) {
            Type fieldType = field.FieldType;
            object fieldValue = field.GetValue(this);
            if (fieldValue == null) {
                field.SetValue(clone, fieldValue);
                continue;
            } //if
            if (deepClonableType.IsAssignableFrom(fieldType)) { // deep:
                IDeepCloneable fieldClone = ((IDeepCloneable)fieldValue).DeepClone();
                field.SetValue(clone, fieldClone);
            } else if (clonableType.IsAssignableFrom(fieldType)) { // shallow, based in ICloneable
                object fieldClone = ((ICloneable)fieldValue).Clone();
                field.SetValue(clone, fieldClone);
            } else // shallowest :-) :
                field.SetValue(clone, fieldValue);
        } //loop
        return clone;
    } //IDeepCloneable.DeepClone
} //class DeepClonable


[END EDIT #1]

Note that in this "universal" implementation, we need to assume that that the type implementing the interface also support the constructor of some "universal" signature, say, parameterless constructor, as shown in the code. However, we don't need to assume it's the case for other IDeepCloneable implementations we may face during recursion, because other implementations can be different, we only use the fact that the interface is implemented. Also note that reflection used in the code above is inherently slow, so you may want to create faster ad-hoc implementation. Also note that you can implement any interface not only by classes by also by structures (struct). For example:
C#
public struct Child {
    public int IntegerValue;
    public string Name;
    public Child(int integerValue, string name) { IntegerValue = integerValue; Name = name; }
    //...
} //struct Child

public struct Parent : IDeepCloneable {
    public Parent(bool dummy) {
        childNodes = new System.Collections.Generic.List<IDeepCloneable>();
        children = new System.Collections.Generic.List<Child>();
    } //Parent
    public System.Collections.Generic.List<IDeepCloneable> ChildNodes { get { return this.childNodes; } }
    public System.Collections.Generic.List<Child> Children { get { return this.children; } }
    System.Collections.Generic.List<IDeepCloneable> childNodes;
    System.Collections.Generic.List<Child> children;
    IDeepCloneable IDeepCloneable.DeepClone() {
        Parent clone = new Parent(false);
        foreach (Child child in this.children)
            clone.children.Add(new Child(child.IntegerValue, child.Name)); // implicit clone
        foreach (IDeepCloneable childNode in this.childNodes) {
            IDeepCloneable childClone = childNode.DeepClone(); // all recursion is here
            clone.ChildNodes.Add(childClone);
        } //loop
        return clone;
    } //IDeepCloneable.DeepClone
    //...
} //struct Parent
I have intentionally more difficult case of struct which does not allow parameterless constructor, so I introduce a constructor with a dummy parameter, just for illustration. I also demonstrated "logical" implicit shallow clone for the struct Child.

One more delicate detail: you need to understand that the class System.String, even though it is a reference object, actually does not require cloning at all. It logically behaves like a value type, due to its "interning" feature and the use of "intern pool". Please see:
http://msdn.microsoft.com/en-us/library/system.string.intern.aspx[^],
http://msdn.microsoft.com/en-us/library/system.string.isinterned.aspx[^] (no need to actually use any of these properties).

Explanation of intern pool: http://broadcast.oreilly.com/2010/08/understanding-c-stringintern-m.html[^].

See also:
http://en.wikipedia.org/wiki/Recursion[^],
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29[^].

[EDIT #2]

I forgot to explain that you really need to implement cloning of the list in a specialized way, because lists don't implement ICloneable. As it have been your major concern, it will take a separate answer.

[END EDIT #2]

—SA
   
v4
Comments
Member 10040991 16-Sep-13 19:46pm
   
This is way more complicated and generic than I was looking for. I only have two lists I want to make clones of. It is also hard for me to see how to implement this with my list class, which is the problem I've had with ALL the other examples I've looked at. I'm looking for something concise like: MoveUiP = UiP.Clone(); but I don't see how I can get to that using the code you have provided. Your implicit clone requires that I enumerate all 40+ of my classes attributes, which isn't an option I'm looking for. Is there an easier way?
Sergey Alexandrovich Kryukov 16-Sep-13 20:13pm
   
I explained the case of lists in the second example. But you should make yourself determined: you either go agree to use "easier" ad-hoc way, easier for understanding, and do a monkey business to "I enumerate all 40+ of my classes attributes" (only members (fields, properties, even though just fields would be enough)), or you make and effort and understand "more complicated" way, which however does not require but allows ad-hoc approach. Come to thing about, the problem is simple enough, but you should better understand what you want and what amount of practical work it may require.

It's only natural that deep understanding entails less of manual, repeatable and mechanical work...
Besides, I already put all the solution, you only need to use this code...

—SA
Member 10040991 16-Sep-13 20:25pm
   
I was hoping that this little code bit would do the job:

MoveUiP.Clear();
UiP.ForEach(i => MoveUiP.Add(i));

But, unfortunately, it doesn't work. Both contain the same data when I debug.
Making a copy of an object shouldn't be this difficult.

I will have to study your code more, its not obvious to me how to make it work with my list classes. I don't get the Parent Child section of your code, I don't think I have a child in mine.
Sergey Alexandrovich Kryukov 16-Sep-13 20:35pm
   
Of course. You clear MoveUiP (why?!) and try to add elements of cleared list to some other list. How could it possibly work? Just think a bit...
—SA
Sergey Alexandrovich Kryukov 16-Sep-13 20:39pm
   
Parent/Children/ChildNodes objects are only for an example, to make deep cloning non-trivial. You can show when deep cloning is different from shallow only if you have some use case of recursion. I artificially added two different child-like members, to create two such cases. Otherwise, how could I explain the difference?

Are you getting the picture?

—SA
Member 10040991 16-Sep-13 20:58pm
   
I reuse MoveUiP and have to clear it out. Did I get the example backwards? As I understand it it cycles thru each element of UiP and adds i to MoveUiP?

I just found this code:

var source = new List<string>();

// populate...

var copy = source.Select(x=>string.Copy(x));

But I need to replace the string.Copy with UnitsInPlayData.Copy and I have nothing written in the UnitsInPlayData for a Copy method. Might I add Icloneable to the class and have a Copy method that returns a memberwise clone?

I'll look at this again tomorrow, its getting late. You have been a lot of help so far, I just don't understand it yet. Thanks for sticking with me.
Sergey Alexandrovich Kryukov 16-Sep-13 22:27pm
   
Hold on, I'll give you some more solutions...
It looks like you mixing up source and destination. How could be source = new List()?
You need to clone source onto destination...
—SA
Sergey Alexandrovich Kryukov 16-Sep-13 23:01pm
   
Please see Solution 2 for now.
—SA
BillWoodruff 16-Sep-13 22:58pm
   
***** One of your best, Sergey, fascinating !
Sergey Alexandrovich Kryukov 16-Sep-13 23:00pm
   
Thank you, Bill, but I put one more solution (Solution 2, after OP's clarifications) and plan to put one more, more universal one, which should be more interesting.
It is supposed to be Solution 3, to be ready soon.
—SA
Sergey Alexandrovich Kryukov 16-Sep-13 23:38pm
   
Bill, please see Solution 3. This is really interesting, you will see.

And this is my fresh idea. This is where we gain from answering question. Sometimes, helping others with some particular problem, you can get a new productive look at old or new problems of the technology...

—SA
After your clarifications, I think I got your problem: you really didn't hope to get deep cloning. Rather, you wanted to get ad-hoc specific clone, "one-level-deeper" clone, to cover your list elements, cloned, not referenced. And you are lost.

Here is how you could do it:
C#
public partial class CiG : Form, ICloneable { // inheriting from Form is bad! I just follow your decision here

    public List<UnitsInPlayData> UiP = new List<UnitsInPlayData>();

    public class UnitsInPlayData : ICloneable {
        public int Item1 { get; set; }
        public string Item2 { get; set; }
        public bool Item3 { get; set; }
        public int[] Item4 { get; set; }
        object ICloneable.Clone() {
            UnitsInPlayData clone = new UnitsInPlayData();
            clone.Item1 = this.Item1;
            clone.Item2 = this.Item2;
            clone.Item3 = this.Item3;
            clone.Item4 = new int[this.Item4.Length];
            for (int index = 0; index < this.Item4.Length; ++index)
                clone.Item4[index] = this.Item4[index];
            return clone;
        } //ICloneable.Clone
    } //class UnitsInPlayData

    object ICloneable.Clone() {
        CiG clone = new CiG();
        foreach (UnitsInPlayData item in this.UiP)
            // untyped character of ICloneable
            // leads to ugly type casts:
            clone.UiP.Add((UnitsInPlayData)((ICloneable)item).Clone());
        return clone;
    } //ICloneable.Clone()

} //CiG


Note: your biggest strategic mistake was not cloning (I hope now you got it), but mixing up Form type and data type in your type CiG. This is really bad to mix up UI and data layer, but this is a subject of a separate big talk.

I demonstrated the 2-level hierarchy of ad-hoc cloning, to cover both the array and list. You really need to do it on a custom level, because arrays and collections don't implement ICloneable. I already mentioned in Solution 1 that ICloneable would not help you too much…

Still, I would recommend to find a more universal solution. It would take loading brain rather than hands. However, there is one, easier but more universal approach…
   
v2
I found another approach to deep cloning, which does not require any interfaces at all and is based on Data Conract and may seem quite weird, but it is really the most universal. It may seep not efficient at first glance, but this is not really true. We will discuss it later. First, I want to show this universal solution:
C#
using System.Runtime.Serialization;
using System.IO;

//...

        static object DeepClone(object source) { // only one universal method for all cases
            if (source == null) return null;
            DataContractSerializer serializer = new DataContractSerializer(
                    source.GetType(),
                    null,
                    int.MaxValue,
                    true,
                    true, // not only trees, any arbitrary graphs
                    null);
            MemoryStream stream = new MemoryStream();
            serializer.WriteObject(stream, source);
            stream.Seek(0, SeekOrigin.Begin);
            return serializer.ReadObject(stream);
        } //DeepClone


That's all. Now, let's discuss it. First of all, it won't clone everything. But this is good. Most types have some redundancies used for, usually, better performance, but redundancy is bad for cloning. Universal cloning method should only clone non-redundant data. So, the code shown will clone only the data mentioned in the data contract. This is absolutely non-intrusive method, so the contract is defined by adding [DataContract] attributes for types and [DataMember] attributes for member, all we need to include in the contract. Adding this attributes cannot affect the behavior of types making in contract, it only affect persistent and cloning behavior.

This is how it works: http://msdn.microsoft.com/en-us/library/ms733127.aspx[^].

Actually, in terms of usage, this is the easiest to use, most robust, reliable and universal approach. Only one universal method. Not only we enable universal cloning, but it gives us XML persistence for free. Besides, we can clone not just some hierarchy of objects (a tree), but any arbitrary graph of objects (please see my comment in the code above, "// not only trees, any arbitrary graphs"). But how about performance? This is XML, a big string with data. Won't it be too slow?

Actually, it depends, but it is actually amazingly fast. For really big object graphs, the limitation would be having in the memory 3 copies of data at the same time: source, stream (the biggest part, because of XML textual redundancy) and the clone. However, for vast majority of data sets, it won't be a problem. After going out of the context of DeepClone, the stream memory will eventually be reclaimed by the Garbage Collector.

As to the performance, things are really interesting. The code is usually much faster then the code I've shown in my Solution 1. Why? This is how serialization works: the slow part, reflection, happens mostly only for the first time. Later on, a serialization assembly is created and reused each time you clone the objects of the same types again. Performance gain, due to this intricate trick, is amazing. The generation of the serialization assemblies is based on System.Reflection.Emit. To get some idea, please see, for example:
http://stackoverflow.com/questions/3185121/assembly-serialization-why[^],
http://msdn.microsoft.com/en-us/library/bk3w6240.aspx[^].

See also:
http://msdn.microsoft.com/en-us/library/system.runtime.serialization.datacontractserializer.aspx[^],
http://msdn.microsoft.com/en-us/library/system.io.memorystream.aspx[^].

—SA
   
v3
Comments
BillWoodruff 17-Sep-13 1:01am
   
Fascinating, upvoted. I wonder how this might compare to using Mehdi Gholam's fastBinaryJSON, as an alternative in terms of performance. So far I've only found one type of object that his JSON serializers can emit, but nor de-serialized, that the built-in Windows binary serializer can handle.
   
Thank you, Bill.
I cannot evaluate Mehdi's work at this moment, need to look at it more thoroughly. I only can tell that I used System.Reflection.Emit for serialization (my own alternative to Microsoft Data Contract; using Emit is very labor-taking) and can tell that saving on relatively slow reflection has much stronger impact than saving on stream content. Would be interesting to compare performance for some typical cases...
—SA
BillWoodruff 17-Sep-13 3:39am
   
I think your technique here would be great as an article on CP. I've often wondered why WinForms didn't have a built-in method to deep-clone its own Controls at run-time, since there are many cases where you'd like to take an existing Control, that was extensively styled, and duplicate it at run-time. I've answered that question in my own head by thinking that since the built-in Controls are often .NET wrappers around fossil-shells of COM and ActiveX there was some constraint in doing that wasn't worth dealing with for MS.

And, the second reason, I assumed, was that, after all, you can make a UserControl/Component that inherits from the built-in Controls, style that all you want, and, at run-time, create new ones.

Of course, talking about deep-copying Controls, is not really the issue at hand on this thread, which, as I read it, is creating an 'Undo facility that is efficient.

yours, Bill
   
Your idea of using deep cloning of controls is valuable, as you can use yet another form creation technique: if you have an array of groups of controls, extensively styled, you can use the designer and create just one group, for a sample. The code called from a constructor (or, anyway, before the form is first shown) can create the rest of the array by deep cloning of the whole group, which of course should be places on a single parent, like a panel, otherwise it would defeat the purpose: you need also to shift it, for alignment purpose.

Generally, using the designer for making a whole thing would be a dumb manual work, best avoided. (The designer is generally heavily abused by many who thus earn such dump manual work for them and produce ugly non-supportable forms.) At the same time, if you use the code for all the controls depicted above, cloning is not needed, because you just repeat the same group in the loop. So, deep cloning would make limited use here.

Anyway, thank you for the interesting note.

—SA
BillWoodruff 18-Sep-13 9:00am
   
The built-in WindowsForms controls are not clonable, or serializable.
   
I know. Both aspects are irrelevant to the method of cloning/serialization based on Data Contract. You just add attributes to types and members to become a part of contract.
However, what we discussed about cloning of forms is still questionable. You would need to add side-effect methods (Data Contract has them), to do pre-/post-serialization processing, etc. It would limit the value of this approach...
—SA
Member 10040991 17-Sep-13 6:57am
   
I'm liking this deep clone serializer, but what is the correct syntax to call it? I'm guessing it would be simply MoveUiP = DeepClone(UiP); ?? I'm assuming I have permission to use it? I've been working with C# for about 6 months now on a full time basis and there is a lot to learn and understand. You guys have been a great help, even though most of this is way over my head. Thanks.
   
Correct. This is a static method, so you can put it any class, static or not. Yes, please use it freely.

I hope this method is not over your head. It is based on the technology extremely hard for understanding (or if you wanted to reimplement Data Contract as I currently do), because such extremely advanced technique as generation of assemblies on the fly (using System.Reflection.Emit) is involved, which is pretty hard to write, as it needs good understanding of CIL and very hard to debug, telling you on my own experience. At the same time, the usage is much simpler than in other techniques.

You are very welcome.
Good luck, call again.

—SA
Member 10040991 17-Sep-13 7:11am
   
OK - I had to add using System.Xml; and a dll reference to the project for System.Runtime.Serialization. Now the compiler error says that serializer.PreserveObjectReferences is read-only and can't be assigned to true. I'm assuming I can remark that line out?
   
Sorry, my fault, and thank you for spotting my bug, I now fixed it.

Yes, it is read-only. This is done in a different way. I removed this line but changed to following text:

Besides, we can clone not just some hierarchy of objects (a tree), but any arbitrary graph of objects (you would need to use the constructor parameter bool preserveObjectReferences in a different DataContractSerializer constructor).

Now, you need it only in more complex cases, when you data graph is not a tree, that is, when there the circular references between objects in the contract are allowed to be circular. Without this parameters, the store method of the serializer would go into the infinite circle. The preserveObjectReferences parameter tells the serializer to give unique IDs to all references in the XML file, so they are re-used. When some object appears second time (due to the circle in the data graph), it is found as already serialized and marked with a reference to already created unique ID.

You don't need it if your data is simpler. In your case, your data is purely hierarchical (a tree, which means "no cycles").

—SA
Sergey Alexandrovich Kryukov 17-Sep-13 14:22pm
   
I added another update to the code, related to the problem you found. Please see the constructor call in this code, comment after the second "true" parameter and the note on this in the text below.
I tried to write this constructor the way compatible with v.3.5, the lowest version having Data Contract, and of course all later versions. With later versions, there is the DataContractSerializerSettings:
http://msdn.microsoft.com/en-us/library/hh194533.aspx.

Okay, this aspect is cleared.

People push me to right an article on the topic (see below). Maybe this would be a good idea, but I know that this solution won't be optimal in performance and memory consumption (albeit temporary). The ideal solution can highly optimize it by using System.Reflection.Emit directly, but writing it would take a lot more time. By the way, I'll up-vote your question, just for starting this interesting topic. Thank you.

—SA
Member 10040991 17-Sep-13 7:28am
   
The correct call to the method is:
MoveUiP = (List < unitsinplaydata > )DeepClone(UiP);

I was missing a cast. This works perfectly. There is a split second delay in moving units on the map, but I think it is acceptable.
   
Great. I hope the universal character of the technique and ease of use worth it. Thank you for testing and your feedback.
—SA
Nitin Singh India 17-Sep-13 13:33pm
   
Can we have full article extracted from this question as it went too deep to be simply a question :) Lots of technology compared to each other
Sergey Alexandrovich Kryukov 17-Sep-13 13:50pm
   
Thank you.
I'm thinking about it. BillWoodruff gave me this idea, as you can see above. I already have some improvements, so it would be an article from scratch...
—SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900