C# – Programming Tutorials

How to use Native Code in Unity

You can use native code in Unity by importing Native Plugins.
Native Plugins are basically libraries of native code written in C/C++. You can import them in C# and make function calls to native code. This way you can gain performance, or use them for whatever reasons you have. I want to note that this isn’t Unity specific thing, I am just using Unity as an example.

How To Create a Native Library

I am working with Visual Studio, so I will show you how to do it in Visual Studio.

You need to create a C++ Dynamic-Link Library (DLL) project. After you write your native code there, you need to build the project and a .dll will be generated. Later you will need to import this .dll in Unity.

Let’s write a simple function so that I can show you how to import it in Unity.

#define DllExport __declspec(dllexport)

extern "C" {
	DllExport float GetFloat() { return 1.0f; }
}

How To Import It In Unity

First you have to place the .dll somewhere in the Assets folder. You can create a sub-folder specifically fot the native libraries if you want, it doesn’t matter. Let’s say the name of the library is MyLib.dll. This is how you import it.

public class TestBehaviour : MonoBehaviour
{
    [DllImport("MyLib")]
    private static extern float GetFloat();

    private void Awake()
    {
        Debug.Log(GetFloat());
    }
}

How To Import a Class

Lets say you don’t want to import static functions, but an entire class with instance methods instead.

The concept of “instance” method is actually just some sugar that the compiler/framework provides. Actually all methods are static. Instance methods just have an additional hidden parameter “this” that is a reference to the object instance.
If you want to call a native method for a certain native object, you would need to pass the native object reference along to the method call. Usually, you would create a wrapper class in .NET/C# that holds that native pointer (IntPtr) and provides the required methods for the C# environment. Those calls are then forwarded to the native interface. You just have to pass the object along.

Here is an example

// Header
class Person
{
public:
	Person(const char* name);
	~Person();

	const char* GetName() const;

private:
	char* _name;
};

// Source
Person::Person(const char* name)
{
	size_t nameLength = strlen(name);
	_name = new char[nameLength + 1];

	for (int i = 0; i < nameLength; i++)
	{
		_name[i] = name[i];
	}

	_name[nameLength] = '\0';
}

Person::~Person()
{
	delete _name;
	_name = nullptr;
}

const char* Person::GetName() const
{
	return _name;
}

// Export Interface
extern "C" {
	DllExport Person* CreatePerson(const char* name)
	{
		return new Person(name);
	}

	DllExport void DestroyPerson(Person* person)
	{
		delete person;
	}

	DllExport const char* GetPersonName(Person* person)
	{
		return person->GetName();
	}
}

// C# Wrapper Class
public class Person
{
    private IntPtr _personPtr = IntPtr.Zero;

    public Person(string name)
    {
        IntPtr namePtr = Marshal.StringToHGlobalAnsi(name);
        _personPtr = CreatePerson(namePtr);
        Marshal.FreeHGlobal(namePtr);
    }

    ~Person()
    {
        if (_personPtr != IntPtr.Zero)
        {
            DestroyPerson(_personPtr);
            _personPtr = IntPtr.Zero;
        }
    }

    public string GetName()
    {
        IntPtr namePtr = GetPersonName(_personPtr);
        string name = Marshal.PtrToStringAnsi(namePtr);

        return name;
    }

    [DllImport("MyLib")]
    private static extern IntPtr CreatePerson(IntPtr name);

    [DllImport("MyLib")]
    private static extern void DestroyPerson(IntPtr person);

    [DllImport("MyLib")]
    private static extern IntPtr GetPersonName(IntPtr person);
}

Bezier Curves

Bezier Curves are very useful and have many applications, but what do we need to know to implement one ourselves? Well, you can keep reading, or you can just download the unity package that I made.

Lerp (Linear Interpolation)

Before we start we need to know what Lerp is. If you want to understand it more mathematically you can check the description in wikipedia. It’s very simple. Lerp is a function which takes three parameters – a, b and t, where a is start value, b is end value, and t is time (between 0 and 1). The function is defined like this

Lerp

In code it looks like this

float Lerp(float a, float b, float t)
{
    return (1f - t) * a + t * b;
}

Note that we can use the same logic if we want to lerp vectors

Vector3 Lerp(Vector3 a, Vector3 b, float t)
{
    return (1f - t) * a + t * b;
}

Bezier Curves

Now that we know what lerp is we can start.
A bezier curve is also defined by a function, but a function of higher degree (cubic to be precise). For a cubic curve we need 4 points (control points). These 4 points control the shape of the curve. Lets call the points p0, p1, p2 and p3. p0 is called start point, p1 – start tangent, p2 – end tangent, and p3 – end point. Lets imagine that the points are positioned like this:

Control Points

The slider at the bottom represents the t value.
In order to construct the function we are going to go through some steps. In each step we are going to make some lerps, and at the end we will combine these lerps.

Step One

We are going to make 3 lerps – between p0 and p1, between p1 and p2, and between p2 and p3.

Vector3 a = Lerp(p0, p1, t);
Vector3 b = Lerp(p1, p2, t);
Vector3 c = Lerp(p2, p3, t);

It looks like this

Lerp One

Now lets draw lines between a and b, and between b and c

Lerp One Plus Lines

Step Two

Again we are going to make some lerps – this time between a and b, and between b and c

Vector3 d = Lerp(a, b, t);
Vector3 e = Lerp(b, c, t);

Lerp Two

Now lets draw a line between d and e

Lerp Two Plus Lines

Step Three

Now all we need to do is to make one last lerp between d and e, so we can find the point on the curve at any given time t.

Vector3 pointOnCurve = Lerp(d, e, t);

Lets draw the point

Lerp Three

And now let’s draw the bezier curve

Draw Curve

The Function

Now if we combine all these lerps, we get the final function that defines any bezier curve by 4 points and a t value

Vector3 GetPointOnBezierCurve(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t)
{
    Vector3 a = Lerp(p0, p1, t);
    Vector3 b = Lerp(p1, p2, t);
    Vector3 c = Lerp(p2, p3, t);
    Vector3 d = Lerp(a, b, t);
    Vector3 e = Lerp(b, c, t);
    Vector3 pointOnCurve = Lerp(d, e, t);

    return pointOnCurve;
}

However this function is not very cheap. With a little math we can simplify the function and thus improve the performance.

Optimizations

Mathematically the function looks like this

Point On Curve

With a little calculations on paper we can simplify it to this

Optimized

So the final function in code can be written like this

Vector3 GetPointOnBezierCurve(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t)
{
    float u = 1f - t;
    float t2 = t * t;
    float u2 = u * u;
    float u3 = u2 * u;
    float t3 = t2 * t;

    Vector3 result =
        (u3) * p0 +
        (3f * u2 * t) * p1 +
        (3f * u * t2) * p2 +
        (t3) * p3;

    return result;
}

Bezier Splines (Bezier Paths)

What if we want to create a more complex curve?
There are two options:

Use a higher degree function
Combine (chain) cubic bezier curves

The first option is not very good, because every time we increase the degree of the function, we create more job for the CPU (we increase the number of calculations).
The second one is more widely used, and it can be explained like this:

Bezier Spline

p3 is the end of the first bezier curve and the start of the second one, and so on.

Abstract Input System in Unity

Right now I am creating a game. For this game I wanted to create a good input system. The thing is I didn’t know where to start. I am a big fan of Ori and the Blind Forest, so I decided to decompile the game and see how the big guys did it. As expected, their code was huge, but I took only the parts for my needs.

Interfaces

There are 2 basic interfaces for taking raw input: IAxisInput and IButtonInput.

public interface IAxisInput
{
    float GetAxis();
}

public interface IButtonInput
{
    bool GetButton(); // When the button is held down
    bool GetButtonDown(); // Executed once on button down
    bool GetButtonUp(); // Executed once on button up
}

For the next interface you need to know exactly what the character can do. In my case the character can only move horizontally and jump, so the interface looks like this.

public interface IInputProvider
{
    IAxisInput HorizontalAxisInput { get; }
    IButtonInput JumpButtonInput { get; }
}

This interface provides us with input from different sources. For example, we can create a KeyboardAndMouseInputProvider, or a MobileInputProvider. Lets actually implement those two.

KeyboardAndMouseInputProvider

public class KeyboardAndMouseInputProvider : IInputProvider
{
    private IAxisInput horizontalAxisInput;
    private IButtonInput jumpButtonInput;

    public KeyboardAndMouseInputProvider()
    {
        this.horizontalAxisInput = new CHorizontalAxisInput();
        this.jumpButtonInput = new CJumpButtonInput();
    }

    public virtual IAxisInput HorizontalAxisInput
    {
        get
        {
            return this.horizontalAxisInput;
        }
    }

    public virtual IButtonInput JumpButtonInput
    {
        get
        {
            return this.jumpButtonInput;
        }
    }

    private class CHorizontalAxisInput : IAxisInput
    {
        public float GetAxis()
        {
            return Input.GetAxis("Horizontal");
        }
    }

    private class CJumpButtonInput : IButtonInput
    {
        public bool GetButton()
        {
            return Input.GetButton("Jump");
        }

        public bool GetButtonDown()
        {
            return Input.GetButtonDown("Jump");
        }

        public bool GetButtonUp()
        {
            return Input.GetButtonUp("Jump");
        }
    }
}

MobileInputProvider

public class MobileInputProvider : MonoBehaviour, IInputProvider
{
    [SerializeField]
    private VirtualJoystick leftJoystick = null;

    private IAxisInput horizontalAxisInput;
    private IButtonInput jumpButtonInput;

    public virtual IAxisInput HorizontalAxisInput
    {
        get
        {
            return this.horizontalAxisInput;
        }
    }

    public virtual IButtonInput JumpButtonInput
    {
        get
        {
            return this.jumpButtonInput;
        }
    }

    public void Init()
    {
        this.horizontalAxisInput = new CHorizontalAxisInput(this.leftJoystick);
        this.jumpButtonInput = new CJumpButtonInput();
    }

    private class CHorizontalAxisInput : IAxisInput
    {
        private VirtualJoystick leftJoystick;

        public CHorizontalAxisInput(VirtualJoystick leftJoystick)
        {
            this.leftJoystick = leftJoystick;
        }

        public float GetAxis()
        {
            return this.leftJoystick.GetAxes().x;
        }
    }

    private class CJumpButtonInput : IButtonInput
    {
        private int lastJumpTouchId;

        public bool GetButton()
        {
            if (Input.touchCount > 0)
            {
                foreach (var touch in Input.touches)
                {
                    if ((touch.phase == TouchPhase.Stationary || touch.phase == TouchPhase.Moved) &&
                        (touch.position.x > Screen.width / 2f) &&
                        (touch.fingerId == this.lastJumpTouchId))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public bool GetButtonDown()
        {
            if (Input.touchCount > 0)
            {
                foreach (var touch in Input.touches)
                {
                    if (touch.phase == TouchPhase.Began &&
                        touch.position.x > Screen.width / 2f)
                    {
                        this.lastJumpTouchId = touch.fingerId;
                        return true;
                    }
                }
            }

            return false;
        }

        public bool GetButtonUp()
        {
            if (Input.touchCount > 0)
            {
                foreach (var touch in Input.touches)
                {
                    if (touch.phase == TouchPhase.Ended &&
                        touch.position.x > Screen.width / 2f &&
                        touch.fingerId == this.lastJumpTouchId)
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    }
}

Another layer of abstraction

In Unity if we want to get an axis we just do it like this.

float horizontalAxis = Input.GetAxis("Horizontal");

But we can’t get the the horizontal axis like that if we are on a mobile device. We have a MobileInputProvider, we just need a class that uses it.

public static class PlayerInput
{
    public static IInputProvider InputProvider { get; set; }

    public static IAxisInput HorizontalAxisInput
    {
        get
        {
            return InputProvider.HorizontalAxisInput;
        }
    }

    public static IButtonInput JumpButtonInput
    {
        get
        {
            return InputProvider.JumpButtonInput;
        }
    }
}

Now we can get the horizontal axis from a mobile device like this.

PlayerInput.InputProvider = mobileInputProvider;
float horizontalAxis = PlayerInput.HorizontalAxisInput.GetAxis();

Compound Input Provider

But what if we want to be able to get input both from a keyboard and from a mobile device. Well we need a provider that gets input from both, but that will be kinda stupid, because we have them in separate, why create a third provider that is copy-paste from the first two? We just need to think of a smart way to combine both input providers. That is how we do it.

First we create an axis input that can get axes from many sources. We will call this one CompoundAxisInput. Here is the implementation.

public class CompoundAxisInput : IAxisInput
{
    private const float AXIS_DEAD_ZONE = 0.2f;

    private IAxisInput[] axisInputs;
    private int lastPressedIndex;

    public CompoundAxisInput() { }

    public CompoundAxisInput(params IAxisInput[] axisInputs)
    {
        this.axisInputs = axisInputs;
    }

    public virtual float GetAxis()
    {
        float positiveAxis = 0f;
        float negativeAxis = 0f;
        if (this.axisInputs != null)
        {
            for (int i = 0; i < this.axisInputs.Length; i++)
            {
                float value = this.axisInputs[i].GetAxis();
                if (Mathf.Abs(value) > AXIS_DEAD_ZONE)
                {
                    this.lastPressedIndex = i;
                }
                else
                {
                    continue;
                }

                if (value < 0f)
                {
                    negativeAxis = Mathf.Min(negativeAxis, value);
                }
                else
                {
                    positiveAxis = Mathf.Max(positiveAxis, value);
                }
            }
        }

        return positiveAxis + negativeAxis;
    }

    public IAxisInput GetLastPressed()
    {
        return this.axisInputs[this.lastPressedIndex];
    }

    public void AddAxisInput(IAxisInput axisInput)
    {
        if (this.axisInputs == null)
        {
            this.axisInputs = new IAxisInput[1];
            this.axisInputs[0] = axisInput;
        }
        else
        {
            Array.Resize(ref this.axisInputs, this.axisInputs.Length + 1);
            this.axisInputs[this.axisInputs.Length - 1] = axisInput;
        }
    }

    public void ClearAxisInputs()
    {
        this.axisInputs = null;
    }
}

It’s an axis input that internally has an array of axis inputs. When we call the GetAxis() method, we find the most negative one and most positive one from all of the axis inputs and return the sum of them. That way if we press left on a keyboard and right on a joystick for example, the character will stay in one place, because the horizontal axis will be zero.

Now we have to do the same for the button input. Lets call the class CompoundButtonInput.

public class CompoundButtonInput : IButtonInput
{
    private IButtonInput[] buttonInputs;
    private int lastPressedIndex;

    public CompoundButtonInput() { }

    public CompoundButtonInput(params IButtonInput[] buttonInputs)
    {
        this.buttonInputs = buttonInputs;
    }

    public virtual bool GetButton()
    {
        if (this.buttonInputs != null)
        {
            for (int i = 0; i < this.buttonInputs.Length; i++)
            {
                if (this.buttonInputs[i].GetButton())
                {
                    this.lastPressedIndex = i;
                    return true;
                }
            }
        }

        return false;
    }

    public virtual bool GetButtonDown()
    {
        if (this.buttonInputs != null)
        {
            for (int i = 0; i < this.buttonInputs.Length; i++)
            {
                if (this.buttonInputs[i].GetButtonDown())
                {
                    this.lastPressedIndex = i;
                    return true;
                }
            }
        }

        return false;
    }

    public virtual bool GetButtonUp()
    {
        if (this.buttonInputs != null)
        {
            for (int i = 0; i < this.buttonInputs.Length; i++)
            {
                if (this.buttonInputs[i].GetButtonUp())
                {
                    this.lastPressedIndex = i;
                    return true;
                }
            }
        }

        return false;
    }

    public IButtonInput GetLastPressed()
    {
        return this.buttonInputs[this.lastPressedIndex];
    }

    public void AddButtonInput(IButtonInput buttonInput)
    {
        if (this.buttonInputs == null)
        {
            this.buttonInputs = new IButtonInput[1];
            this.buttonInputs[0] = buttonInput;
        }
        else
        {
            Array.Resize(ref this.buttonInputs, this.buttonInputs.Length + 1);
            this.buttonInputs[this.buttonInputs.Length - 1] = buttonInput;
        }
    }

    public void ClearButtonInputs()
    {
        this.buttonInputs = null;
    }
}

Finally we create a CompoundInputProvider

public class CompoundInputProvider : IInputProvider
{
    private IInputProvider[] inputProviders;
    private CompoundAxisInput horizontalAxisInput;
    private CompoundButtonInput jumpButtonInput;

    public CompoundInputProvider()
        : this(null)
    { }

    public CompoundInputProvider(params IInputProvider[] inputProviders)
    {
        this.horizontalAxisInput = new CompoundAxisInput();
        this.jumpButtonInput = new CompoundButtonInput();

        if (inputProviders != null)
        {
            for (int i = 0; i < inputProviders.Length; i++)
            {
                this.AddInputProvider(inputProviders[i]);
            }
        }
    }

    public virtual IAxisInput HorizontalAxisInput
    {
        get
        {
            return this.horizontalAxisInput;
        }
    }

    public virtual IButtonInput JumpButtonInput
    {
        get
        {
            return this.jumpButtonInput;
        }
    }

    public void AddInputProvider(IInputProvider inputProvider)
    {
        if (this.inputProviders == null)
        {
            this.inputProviders = new IInputProvider[1];
            this.inputProviders[0] = inputProvider;
        }
        else
        {
            Array.Resize(ref this.inputProviders, this.inputProviders.Length + 1);
            this.inputProviders[this.inputProviders.Length - 1] = inputProvider;
        }

        this.horizontalAxisInput.AddAxisInput(inputProvider.HorizontalAxisInput);
        this.jumpButtonInput.AddButtonInput(inputProvider.JumpButtonInput);
    }

    public void ClearInputProviders()
    {
        this.inputProviders = null;
        this.horizontalAxisInput.ClearAxisInputs();
        this.jumpButtonInput.ClearButtonInputs();
    }
}

All that’s left is to provide our PlayerInput class with the right CompoundInputProvider. I do this in an InputManager script.

public class InputManager : MonoBehaviour
{
    [SerializeField]
    private MobileInputProvider mobileInputProvider = null;

    protected virtual void Awake()
    {
        this.InitInputProvider();
    }

    private void InitInputProvider()
    {
        CompoundInputProvider compoundInputProvider = new CompoundInputProvider();
        if (this.mobileInputProvider != null)
        {
            this.mobileInputProvider.Init();
            compoundInputProvider.AddInputProvider(this.mobileInputProvider);
        }

#if UNITY_EDITOR
        compoundInputProvider.AddInputProvider(new KeyboardAndMouseInputProvider());
#endif

        PlayerInput.InputProvider = compoundInputProvider;
    }
}

Now we are ready to use our PlayerInput class instead of the Input class that Unity gives us.

Dynamic Queue Implementation – C#

A dynamic queue is a queue that is implemented with nodes. Nodes consist of two things: value and link to another node.

The following image illustrates the implementation:

dynamic-queue

The most left node is the front of the queue, and the most right one is the back of the queue. Every node is connected to the one right of it. The back of the queue points to null.

You can see the implementation of the queue here.
Lets jump to the explanation.

First lets see how the Node is implemented.

private class Node
{
	public T Item { get; set; }
	public Node Next { get; set; }

	public Node(T item)
	{
		this.Item = item;
		this.Next = null;
	}

	public Node(T item, Node previous)
	{
		this.Item = item;
		this.Next = null;
		previous.Next = this;
	}
}

We have an Item which represents the value of the node. The link is a simple reference to a node and is called Next. We also have two constructors. One that creates a node with some item and has a pointer to null. The other one creates the same node, but the difference is that a previous node is linked to the one that was just created. The Node class is a private class in the Queue class which I called CustomQueue.

Now lets jump to the CustomQueue.
Lets see what fields, constructors and properties we have.

private Node front;
private Node back;
private int count;

public CustomQueue()
{
	this.front = null;
	this.back = null;
	this.count = 0;
}

public int Count
{
	get
	{
		return this.count;
	}
}

We have references(pointers) to the front and the back of the queue. There is a count field that has a Count property with getter only (we don’t want to mess up the count from the outside). We also have only a single default constructor that makes an empty queue by initializing the front and the back with null and count with 0.

Now lets see the basic methods.

public void Enqueue(T item)
{
	if (this.front == null)
	{
		// We have empty queue
		this.front = new Node(item);
		this.back = this.front;
	}
	else
	{
		Node newNode = new Node(item, this.back);
		this.back = newNode;
	}

	this.count++;
}

The “Enqueue” method adds a new element to the front of the queue. First we check if the queue is empty (if so we make a queue with only one node that points to null). If the queue is not empty, we create a new node and tell the back of the queue to start pointing at the node we’ve just created. This is accomplished with the second constructor. We have to tell that the new back of the queue is the new node. Last we increment the count.

Consider the following code:

CustomQueue<int> queue = new CustomQueue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

In the memory that looks much like this:

enqueue

public T Dequeue()
{
	if (this.count == 0)
	{
		// We have empty queue
		throw new InvalidOperationException("The queue is empty");
	}

	T result = this.front.Item;
	this.front = this.front.Next;
	this.count--;

	return result;
}

The “Dequeue” method removes the front of the queue and returns the value of it. We first make a check if the queue is empty (if so we throw an InvalidOperationExceltion). If the queue is not empty, then we remove the front. It’s simple, we just initialize the front with it’s link. The garbage collector will take care of the node that is discarded from the queue. We also have to decrement the count and return the result (the value of the removed element).

Consider the following code:

CustomQueue<int> queue = new CustomQueue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

queue.Dequeue();
queue.Dequeue();
queue.Dequeue();

The dequeue process should look something like this:

dequeue

public T Peek()
{
	if (this.count == 0)
	{
		// We have empty queue
		throw new InvalidOperationException("The queue is empty");
	}

	return this.front.Item;
}

The “Peek” method gets the value of the front of the queue. Again there is a check for empty queue and an exception throw if it’s empty.

public void Clear()
{
	this.front = null;
	this.back = null;
	this.count = 0;
}

The “Clear” method clears the queue (makes it empty). It’s just like the constructor. We initialize the front and the back with null and the count with 0.

CustomQueue implements the ICloneable interface. It’s useful to clone the queue sometimes.

public object Clone()
{
	CustomQueue<T> clone = new CustomQueue<T>();

	Node currentNode = this.front;
	while (currentNode != null)
	{
		// We have non-empty queue
		clone.Enqueue(currentNode.Item);
		currentNode = currentNode.Next;
	}

	return clone;
}

The “Clone” method creates a deep copy of the queue. How do we do that? We create an empty queue named “clone”. If the original queue is empty we just return the empty clone queue. If it is not empty however, we have to make the deep copy. It’s very simple. We have a reference(node) called “currentNode” that first points to the front of the original queue. This node helps us to walk through the original queue from the front to the back. We say this: “while currentNode != null (we haven’t reached the end of the queue) – enqueue the value of the current node we’ve reached into the clone queue and go to the next node of the original queue”. Then we return the clone.

It looks like this:

queue-clone-process

I’ve also added some extension methods in the CustomQueue class. They are helpful, plus helped me for the unit tests.

public override string ToString()
{
	StringBuilder result = new StringBuilder();

	Node currentNode = this.front;
	while (currentNode != null)
	{
		result.Append(currentNode.Item);
		currentNode = currentNode.Next;
	}

	return result.ToString();
}

public T[] ToArray()
{
	T[] result = new T[this.count];

	Node currentNode = this.front;
	for (int i = 0; i < result.Length; i++)
	{
		result[i] = currentNode.Item;
		currentNode = currentNode.Next;
	}

	return result;
}

“ToString” and “ToArray” are much like the clone method. We are walking through the original queue and the value of the current node we’ve reached is appended in a StringBuilder in the first case, and put in an array in the second case.

The CustomQueue also implements the IEnumerable<T> interface so that the queue can be walked with a foreach loop.

public IEnumerator<T> GetEnumerator()
{
	Node currentNode = this.front;
	while (currentNode != null)
	{
		T result = currentNode.Item;
		currentNode = currentNode.Next;

		yield return result;
	}
}

IEnumerator IEnumerable.GetEnumerator()
{
	return this.GetEnumerator();
}

The IEnumerable and IEnumerator interfaces are hard to explain and this post does not concern them, so I will stop here. Maybe I will make a post on how to implement these interfaces the hard way and the easy way (here I’ve used the easy way). That’s all. Hope it was useful.

Dynamic Stack Implementation – C#

A dynamic stack is a stack that is implemented not with an array but with nodes. A node consists of two things (a value and a link to another node).

The next image illustrates the stack.

dynamic-stack

You can find the full source here.

Lets see how the Node is implemented.

private class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
    {
        this.Item = item;
        this.Next = null;
    }

    public Node(T item, Node next)
    {
        this.Item = item;
        this.Next = next;
    }
}

In my implementation the value is called Item and the link to the next node is a Node reference called Next. We also have two constructors. One that creates a node with a given item and a link that points to null, and one that creates a node with a given item and a link that points to a node different than null.

What do we have?

private Node top;
private int count;

public CustomStack()
{
    this.top = null;
    this.count = 0;
}

public int Count
{
    get
    {
        return this.count;
    }
}

We have a node that points to the top of the stack. The count is optional but it’s always better to know how many items we have in a stack. We have only a simple default constructor that initializes our stack. The top is null and the count is zero when the stack is created. We also have a property for the count with getter only.

Not lets see how the basic methods are implemented.

public void Push(T item)
{
    if (this.top == null)
    {
        // We have empty stack
        this.top = new Node(item);
    }
    else
    {
        Node newNode = new Node(item, this.top);
        this.top = newNode;
    }

    this.count++;
}

The “Push” method adds a new node to the stack. If the stack is empty, then we create a new node that points to null. This new node is the only element in the stack (the stack top). If the stack is not empty however, a new node is created. This node has to be the top of the stack so we point it’s link to the stack top. Then the top node starts to point the new node (the new node becomes the top of the stack).

Lets see it with our eyes.
Consider the following code:

CustomStack<int> stack = new CustomStack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

In the memory it should look something like this:

stack-push

public T Peek()
{
    if (this.count == 0)
    {
        // We have empty stack
        throw new InvalidOperationException("The stack is empty");
    }

    return this.top.Item;
}

The “Peek” method gets the value of the top without removing the top from the stack. If the stack is empty however, an InvalidOperationException is thrown.

public T Pop()
{
    if (this.count == 0)
    {
        // We have empty stack
        throw new InvalidOperationException("The stack is empty");
    }

    T result = this.top.Item;
    this.top = this.top.Next;
    this.count--;

    return result;
}

The “Pop” is almost the same as “Peek”. The difference is that it not only gets the value of the top but it also removes the top from the stack. The value is taken and the top is assigned to it’s link (next node). The count is decremented. Finally the value is returned.

Consider the following code:

CustomStack<int> stack = new CustomStack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

stack.Pop();
stack.Pop();
stack.Pop();

The popping process looks like this:

stack-pop

public void Clear()
{
    this.top = null;
    this.count = 0;
}

“Clear” clears the stack. It’s just like the constructor. We initialize the top with null and the count with 0.

public object Clone()
{
    CustomStack clone = new CustomStack();

    if (this.count != 0)
    {
        // We have non-empty stack
        clone.top = new Node(this.top.Item);
        Node currentNode = this.top.Next;
        Node cloneLastNode = clone.top;

        while (currentNode != null)
        {
            Node newNode = new Node(currentNode.Item);
            cloneLastNode.Next = newNode;
            cloneLastNode = newNode;
            currentNode = currentNode.Next;
        }

        cloneLastNode.Next = null;
        clone.count = this.count;
    }

    return clone;
}

This is maybe the most complex method of all. If the stack is empty the job is easy. We just make an empty stack and returned it. If it is not, then we have to make the actual copy. This method makes a deep copy. That means that the two stacks don’t depend on each other. They are equal, but not the same (don’t share the same reference). How do we do that? First we make the clone a copy of the top. The “currentNode” is a helper node that will walk through the original stack from the top to the end. The “cloneLastNode” is the last node of the clone stack at any state of the copying progress. At first the “cloneLastNode” is the top of the clone stack. While “currentNode” is not null (we haven’t reached the original stack’s end) we make a new node exactly the same as the current node we’ve reached. Then the last node of the clone stack is linked to the new node and then is assigned to it. That way in the next iteration this can be repeated. The “currentNode” is also assigned to it’s link. Last we link the last node of the clone stack to null and copy the count of the original stack. I can say it like that: “while we haven’t reached the end of the stack, create a new node with value equal to the value of the current node we’ve reached, link the last node of the clone stack with the new node and make the last node of the clone to be the new node, then go to the next node of the original stack. Last the link of the last node of the clone stack is initialized with null”.

You just have to think it through and try to write it in a paper.
It’s very hard to be explained, maybe a picture will help:

stack-clone

The next methods are not basic for Stack implementation but are helpful sometimes. You can consider them as extensions.

public override string ToString()
{
    StringBuilder result = new StringBuilder();

    Node currentNode = this.top;
    while (currentNode != null)
    {
        result.Append(currentNode.Item.ToString());
        currentNode = currentNode.Next;
    }

    return result.ToString();
}

I’ve overrided the ToString method. It’s very simple. The stack is walked through from the top to the end and the values of the nodes are appended to a StringBuilder.

public T[] ToArray()
{
    T[] result = new T[this.count];

    Node currentNode = this.top;
    for (int i = 0; i < this.count; i++)
    {
        result[i] = currentNode.Item;
        currentNode = currentNode.Next;
    }

    return result;
}

Exactly the same as ToString. The difference is that the values of the nodes are put into an array.

public IEnumerator GetEnumerator()
{
    Node currentNode = this.top;
    while (currentNode != null)
    {
        T result = currentNode.Item;
        currentNode = currentNode.Next;

        yield return result;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return this.GetEnumerator();
}

This one is hard to be explained. My stack implements IEnumerable<T>. That way it can be walked through with a foreach loop. If you want to learn about it you can find a lot of information in MSDN or other resources. Maybe I will make a different post to explain how to implement this interface the hard way and the easy way.