Feb 072010
 

Binary Trees are tree type data structures that contain two child nodes. They can be used to implement Binary Search trees, structures where the left child has a value lesser than the node and the right child has a greater value. Usually Linear collection objects require iteration linearly over the list. In the worst case scenario that the element to be searched is at the end of the list this can take a really really long time. For Binary Trees the search time is cut by half. Since every node tells the search which direction to go and search.

I implemented a basic Binary Tree in .NET for adding custom types. The Tree is generic and can be used to add any type objects. Also the object must implement the generic versions of IComparable and IEquitable for their types and object types. This leaves the search logic’s implementation to the type rather than the data structure. The complete solution can be downloaded here.

Lets see the declaration of the Binary Tree along with the private members.

class BinaryTree<T> where
    T:IComparable<T>,
    IEquatable<T>,
    IEquatable<object>,
    IComparable<object>
{
    BinaryTree<T> _parentNode;
    BinaryTree<T> _leftNode;
    BinaryTree<T> _rightNode;
    public T Value { get; set; }

Each BinaryTree object must be aware of its parent node and its left and right children, and the value it holds. Lets see the logic for adding the node. The adding logic is recursive. If it finds a null value, then the value is substituted. If not, then the node to be added is compared. If the value is lesser than the same method is called on the leftnode. This happens recursively till we get the node where the value is to be added.

public void AddNode(T _nodeTobeAdded)
{
    if (null==Value)
        //We found the value. Yay!!
        this.Value = _nodeTobeAdded;
    else
    {
        //Compare the node to be added. Here the
        //type's IComparable is called.
        if (_nodeTobeAdded.CompareTo(Value) < 0)
        {
            //Go down the left node. If the left node is null,
            //then create a new object, else return the existing object.
            _leftNode = null==_leftNode ?new BinaryTree<T>(this):_leftNode;
            _leftNode.AddNode(_nodeTobeAdded);
        }
        else
        {
            //Go Down the right node.
            _rightNode = null==_rightNode?new BinaryTree<T>(this):_rightNode;
            _rightNode.AddNode(_nodeTobeAdded);
        }
    }
}

The GetNode method follows a similar logic, with recursive searching of the tree till a match is found, if no match is found then a null value is returned. Note that only around half of the tree is searched, rather than all of the nodes, as would be the case with a linkedList. GetNode is implemented both for the type and an object. In both cases the Equals method’s implementation is called, giving the generic type the ability to decide on its own equality logic.

public T GetNode(T _nodeToBeGotten)
{
   if(_nodeToBeGotten.Equals(Value))
       return Value;
   else if(_nodeToBeGotten.CompareTo(Value)<0)
       return null==_leftNode? default(T): _leftNode.GetNode(_nodeToBeGotten);
   else
       return null==_rightNode?default(T): _rightNode.GetNode(_nodeToBeGotten);
}

public T GetNode(object o)
{
    if (Value.Equals(o))
        return Value;
    else if (Value.CompareTo(o)>0)
        return (null == _leftNode) ?
            default(T) : _leftNode.GetNode(o);
    else
        return null == _rightNode ?
            default(T) : _rightNode.GetNode(o);
}

Deleting is a bit tricky business. We have four scenarios here:-

  1. Its a leaf node, i.e. both the left and right children are null. This is the simplest scenario. Simply set the node itself to null
  2. The LeftNode is null but the right node is not, in this scenario – the node’s right node is set to the parent node’s right node, and the node is set to null.
  3. The Right node is null but left node is not. It is handled similar to the previous scenario.
  4. Both leftNode and rightNode is not null. In this scenarios we need to go down the leftnode, and iterate to its right most non empty node. This node is to be replaced with the node to be deleted. Just the value needs to be replaced and the right most node should be orphaned.
public void DeleteNode(object o)
{
    BinaryTree<T> _tempNode1 = this.GetTreeNode(o);
    DeleteNode(_tempNode1);
}

public void DeleteNode(T _nodeTobeDeleted)
{
    BinaryTree<T> _tempNode1 = this.GetTreeNode(_nodeTobeDeleted);
    DeleteNode(_tempNode1);
}

private void DeleteNode(BinaryTree<T> _tempNode1)
{
    BinaryTree<T> _tempNode2 = _tempNode1;
    if ((null == _tempNode1._leftNode) && (null == _tempNode1._rightNode))
        _tempNode1._parentNode = null;
    else if (null == _tempNode1._leftNode)
        _tempNode1._parentNode._rightNode = _tempNode1._rightNode;
    else if (null == _tempNode1._rightNode)
        _tempNode1._parentNode._leftNode = _tempNode1._leftNode;
    else
    {
        bool _goingRight = false;
        _tempNode1 = _tempNode1._leftNode;
        while (_tempNode1._rightNode != null)
        {
            _tempNode1 = _tempNode1._rightNode;
            _goingRight = true;
        }
        _tempNode2.Value = _tempNode1.Value;
        if (_goingRight) _tempNode1._parentNode._rightNode = null;
        else _tempNode1._parentNode._leftNode = null;
        _tempNode1 = null;
    }
}

//Private methods to get the nodes to be deleted
private BinaryTree<T> GetTreeNode(T _nodeToBeGotten)
{
    if (_nodeToBeGotten.Equals(Value))
        return this;
    else if (_nodeToBeGotten.CompareTo(Value) < 0)
        return null == _leftNode ? default(BinaryTree<T>) : _leftNode.GetTreeNode(_nodeToBeGotten);
    else
        return null == _rightNode ? default(BinaryTree<T>) : _rightNode.GetTreeNode(_nodeToBeGotten);
}

private BinaryTree<T> GetTreeNode(object o)
{
    if (Value.Equals(o))
        return this;
    else if (Value.CompareTo(o) > 0)
        return (null == _leftNode) ?
            default(BinaryTree<T>) : _leftNode.GetTreeNode(o);
    else
        return null == _rightNode ?
            default(BinaryTree<T>) : _rightNode.GetTreeNode(o);
}

The class which could be added to the tree needs to implement the four interfaces i mentioned. I implemented an Employee class which has just two fields Name and age and the comparison is done based on the age.

class Employee : IComparable<Employee>,IEquatable<Employee>,IEquatable<object>,IComparable<object>
    {
        private string _name;
        private int _age;

        public int Age{get{return _age;}}

        public Employee(string _name, int _age)
        {
            this._name = _name;
            this._age = _age;
        }

        #region IComparable<Employee> Members

        public int CompareTo(Employee other)
        {
            if (this._age < other._age)
                return -1;
            else
                return 1;
        }

        #endregion

        public bool Equals(Employee other)
        {
            if (this._age == other._age)
                return true;
            else
                return false;
        }

        #region IEquatable<object> Members

        public override bool Equals(object other)
        {
            int _age=0;
            if (int.TryParse(other.ToString(), out _age))
            {
                return this._age == _age ? true : false;
            }
            else return false;
        }

        #endregion

        #region IComparable<object> Members

        public int CompareTo(object other)
        {
            int _age = 0;
            if (int.TryParse(other.ToString(), out _age))
                return this._age < _age ? -1 : 1;
            else return 1;
        }

        #endregion

    }

This is the main method which adds a few objects to the tree collection.

static void Main(string[] args)
{
    BinaryTree<Employee> _btree = new BinaryTree<Employee>(new Employee("RootValue",40));
    _btree.AddNode(new Employee("Test1", 34));
    _btree.AddNode(new Employee("Test2", 26));
    _btree.AddNode(new Employee("Test3", 65));
}
Jan 092010
 

Though MVC is an age old architectural style that has existed since the 70s, its a relatively new entrant in the .NET world. I had written a general introduction about MVC earlier. That post is available here. While Java, Ruby, Python all had their MVC frameworks for quite some time, ASP.NET was quite comfortable with the Webform based architecture till recently. And Webforms arent really a bad way to code at all, you work with almost a Windows style of programming, dragging dropping controls. Double clicking them to code their event handlers. In fact due to this Rapid application development, ASP.NET was amazingly simple to work with. However, like with all other simple ways, ASP.NET webforms also take a lot of control away from the developer.

MVC seeks to give developers an alternative, where they have complete control over the application including the viewstate of the controls. My first look was at ASP.NET MVC was a training session given by an architect from Microsoft, and I absolutely didn’t like the complexity it brought to a simple demo application that was showed. I found that we were writing too much code, again bringing back spaghetti code that died with ASP. But over time, after digging into MVC, I found that it made a lot of sense. If my need is just to display a set of data, why should I sacrifice performance over all of the gridview’s bulky viewstate. Rather, it makes sense to use a HTML table and apply CSS to style it.  That is exactly the flexibility that MVC gives you, instead of relying on built in abstraction done by Webform architecture, you get to control every detail of your application.

WebForms

ASP.NET Webforms are radically different from any other server side scripting technology. For one, its event driven. Just like Windows programming, you assign an event handler to an element, like a button and it calls the handler when the button is clicked. No longer, do you have to keep on submitting the form to handle click events and write bulky code to do simple stuff. ASP.NET made the server side code clean – in fact a helluva lot cleaner than ASP.

But all this ignores the age old truth about the web/HTTP – that it is stateless. The server forgets about the page the minute its sent to the client and thats the end of it. So how is context maintained in WebForms? The answer is Viewstate. All of the control states are Base64 encoded and recreated on the server again where the request is executed. There is a lot of built-in plumbing to achieve this level of abstraction.

The main problem with webforms is that though it cleans up your code and markup and seperates them neatly in your Visual studio solution, it horribly clutters the rendered markup to the browser. Every control takes up more and more viewstate and the nested control names which are really long, make the markup bulky, and since this does a round trip on every request, it starts impacting performance and eventually scalability.

One more concern is the Testability, due to the event driven approach, the GUI is tighly coupled with your business layer and there isnt any effective way to test your web page. Automating such testing could be an tedious effort and you would most probably end up doing manual testing.

Despite all of these problems, Webforms are not a bad architecture. It is extremely mature and extensible. A lot of good documentation exists for it and it still makes sense for quite a few scenarios.

MVC

With MVC, it was love at first byte. In fact I never realized how inefficient webforms were, until i worked with MVC. Instead of a page receiving the request, its the Controller which lives at the heart of MVC. Once it gets the request, it decides which view to render and may use models.

One great thing about MVC is the clean Seperation of Concerns (SoC ) which you are able to achieve out of the box. Both the Controllers and the Views can be tested separately using testing tools like NUnit or MBUnit. So that means no longer. Manual testing doesn’t really make any sense for most scenarios, because the effort is not repeatable and when you want to try with a different input, you would need to start all over again.

Also, you have complete control over the HTML that your controls generate. No more grappling with heavy Viewstate and decreased performance. Also there is no concept of a postback in MVC. Hence although, we can make use of ASP.NET server controls, we cant use either ViewState or Postback in them. Microsoft is working to create a library of MVC aware server controls that would be more suitable for this architectural style. Also, you have complete control over the HTML that your controls generate. No more grappling with heavy Viewstate and decreased performance. Also there is no concept of a postback in MVC. Hence although, we can make use of ASP.NET server controls, we cant use either ViewState or Postback in them. Microsoft is working to create a library of MVC aware server controls that would be more suitable for this architectural style.

One major point that is oft repeated is that we shouldn’t jump the gun to convert every existing webforms applications into MVC just because its the in thing. You would have to rewrite your application completely, and the benefit derived would often not be worth the effort. But I would certainly  recommend that  you use MVC for any new applications you create. Its certainly the smarter way.

Jan 032010
 

In continuation to my earlier post about multithreading in .NET, I am writing about the ReaderWriterLock class which is one more method of thread synchronization.

The ReaderWriterLock is based on the fact that the Monitor locking (lock keyword in C#) doesnt really make any distinction whether the thread accessing the variable is reading it or writing to it. If its only reading it, then we should not need an exclusive lock. So If we allow multiple threads to read the value, it would be much faster than having mutually exclusive locks, which means a more scalable application? On paper, yes – but not in reality.

The problem with ReaderWriterLock is with its implementation. Several experts have slammed this technique and found that outside of limited scenarios, it is actually far slower than the Monitor.Enter method used to get an exclusive lock. ReaderWriterLock gives higher priority to reader threads then writers. This makes sense if you have many readers and only a few writers. So a lot of readers are able to read the resource while the writer has to wait longer to get the lock. But what If you have equal or more writers. The process of favoring readers make writer threads queued up and take a very long time to complete.

Jeffrey Richter says that this performance loss is due to support for Recursion in the ReaderWriterLock class. Due to this, the class needs to maintain a record of the number of times each thread acquires the lock and increment and decrement the counter. When multiple reader threads acquire the same lock (remember ReaderWriterLock class allows simultaneous reads), a counter is maintained for each thread. This overhead is what causes the ReaderWriterLock to pale in comparison to the Monitor class. It is approximately 6 times slower.

Here is a code sample. The Threads 1 and 3 are reader threads while the Thread 2 is a writer one. When you take a look at the output, its clear that the readers are granted simultaneous access to the _value variable, but when the writer thread is writing to it, all the readers wait in queue patiently for it to finish executing. I have made the DoWorkRead method parametrized in order to identify the thread on which the method is being executed.

class Program
{
    int _value = 0;
    ReaderWriterLock _rwLock = new ReaderWriterLock();
 
    static void Main(string[] args)
    {
        Program _prgm = new Program();
        for (int i = 0; i &lt; 20; i++)
        {
            Thread _t1Obj = new Thread(_prgm.DoWorkRead); //Reader Thread
            //Writer Thread
            Thread _t2Obj = new Thread(new ThreadStart(_prgm.DoWorkWrite));
            //Reader Again
            Thread _t3Obj = new Thread(_prgm.DoWorkRead); 
 
            //Start all threads
            _t1Obj.Start("Thread 1");
            _t2Obj.Start();
            _t3Obj.Start("Thread 3");
 
            //Wait for them to finish execution
            _t1Obj.Join();
            _t2Obj.Join();
            _t3Obj.Join();
        }
 
    }
 
    public void DoWorkRead(object threadName)
    {
        //Accquire Reader Lock.
        _rwLock.AcquireReaderLock(Timeout.Infinite);
        Console.WriteLine("Read start: Thread: " + threadName + " " + _value);
        if (threadName.ToString() == "Thread 1")
            //Irregular sleeps makes more chances of
            //Multiple threads trying to access it
            //at same time
            Thread.Sleep(10);
        else
            Thread.Sleep(250);
        Console.WriteLine("Read end  : Thread: " + threadName + " " + _value);
        _rwLock.ReleaseReaderLock();
        //Release Lock
    }
 
    public void DoWorkWrite()
    {
        _rwLock.AcquireWriterLock(Timeout.Infinite);
        Console.WriteLine("\nWriter start: " + _value);
        _value++; //Writing
        Console.WriteLine("Writer End: " + _value);
        _rwLock.ReleaseWriterLock();
        Console.WriteLine();
    }
 
}

A look at the output shows the once the writer acquires a lock, it is mutually exclusive, but both the reader threads are able to access the variable _value.

One more problem with the ReaderWriterLock class is that it allows Reader threads to acquire writer locks. If you set an infinite timeout, it will create a deadlock situation, where the thread just waits to get the Writer lock but cant because the very same thread holds on to the Reader lock and is yet to release it. So the application just waits and waits.

        public void DoWorkRead(object threadName)
        {
            //Accquire Reader Lock.
            _rwLock.AcquireReaderLock(Timeout.Infinite);
            Console.WriteLine("Read start: Thread: " + threadName + " " + _value);
            //NEVER EVER DO THE BELOW. IT WILL CREATE A DEADLOCK
            _rwLock.AcquireWriterLock(Timeout.Infinite);
            Thread.Sleep(10);
            Console.WriteLine("Read start: Thread: " + threadName + " " + _value);
            _rwLock.ReleaseReaderLock();
            //Release Lock
        }

Keeping all these issues in mind, Microsoft introduced a new class – the ReaderWriterLockSlim class from .NET 3.0 onwards, while leaving the old one in there as well, for backwards compatibility. This class placed Lock recursion in the hands of the developers by giving an enum that could be set during object recursion. With recursion out of the way, performance is dramatically better and comparable to the Monitor class. It also took care of the deadlock situation above. As a conclusion, it is always better to avoid the ReaderWriterLock class and use the slim implementation instead. If you are on .NET 2.0, then since that option is not open to you, its better to look at some other synchronization technique.

Dec 302009
 

I got an interesting problem by email recently where someone had asked me to solve the given below problem:-

A squad of robotic rovers are to be landed by NASA on a plateau on Mars.This plateau, which is curiously rectangular, must be navigated by therovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.

A rover’s position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom
left corner and facing North.

In order to control a rover, NASA sends a simple string of letters. The possible letters are ‘L’, ‘R’ and ‘M’. ‘L’ and ‘R’ makes the rover spin 90 degrees left or right respectively, without moving from its current spot. ‘M’ means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

INPUT:
The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover’s position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and  co-ordinates and the rover’s orientation.

Each rover will be finished sequentially, which means that the second rover won’t start to move until the first one has finished moving.

OUTPUT
The output for each rover should be its final co-ordinates and heading.

I worked out a simple solution for this problem. Of course there is a lot of room for improvement as this solution is the bare minimum one. The rover parses the instructions one at a time. Here are improvements I have planned to be implemented in later versions

  • Understand multiple instruction and process them at once to improve performance
  • Identify cyclic instructions that have no net effect on coordinates and ignore them
  • Move multiple rover objects at same time.
  • Prevent two rovers from taking at same positions at the same time.

Heres what I have for now.

The Rover class stores the state of each Rover on the grid.

 ///
    /// This class is responsible for maintaining the state of each Rover
    /// and processing the instructions given to it.
    ///
    class Rover
    {
        //private objects : Coordinates, Direction, Instruction Array
        private Coordinates _rovCor;
        private Direction _rovDir;
        private string _instructionArray;
 
        //readonly properties for above objects
        public int X { get { return _rovCor.X; } }
        public int Y { get { return _rovCor.Y; } }
        public Direction RoverDirection { get { return _rovDir; } }
 
        ///
        /// Constructor. Passes to Struct coorinates for getting coordinate object
        ///
        public Rover(int _xCor, int _yCor, char _startDir, string _instructionArray)
        {
            this._rovCor = new Coordinates(_xCor, _yCor);
            this._rovDir = GetDirection(_startDir);
            this._instructionArray = _instructionArray;
        }
 
        //Parses The Start Position into Direction Enum
        private Direction GetDirection(char _startDir)
        {
            switch (_startDir)
            {
                case 'N':
                    return Direction.North;
                case 'S':
                    return Direction.South;
                case 'E':
                    return Direction.East;
                case 'W':
                    return Direction.West;
                default:
                    throw new Exception("Unknown Direction Supplied. Accepted values are N,S,E,W");
            }
        }
 
        //Processes the Instruction Array
        public void ProcessInstructionArray()
        {
            foreach (char _instruction in _instructionArray)
            {
                ProcessInstruction(_instruction);
            }
        }
 
        //Processes individual instructions. delegates tasks to other methods
        //after checking instruction type.
        private void ProcessInstruction(char _instruction)
        {
            if ((_instruction == 'L') || (_instruction == 'R'))
            {
                ProcessDirectionInstruction(_instruction);
            }
            else if (_instruction == 'M')
                ProcessMoveInstruction();
            else
                throw new Exception("Invalid Instruction Processed. Please supply only L,R and M");
        }
 
        //Move Instruction is processed by the Coordinate Object
        private void ProcessMoveInstruction()
        {
            this._rovCor.UpdateCoordinates(_rovDir);
        }
 
        //This Processes the direction of the Rover. Instructions L and R
        //are processed by this method.
        private void ProcessDirectionInstruction(char _instruction)
        {
            int _rovDirInt = (int)this._rovDir;
 
            if (_instruction == 'L')
            {
                if (_rovDirInt == 0)
                    _rovDirInt = 4;
                this._rovDir = (Direction)(_rovDirInt - 1);
            }
            else
            {
                if (_rovDirInt == 3)
                    _rovDirInt = -1;
                this._rovDir = (Direction)(_rovDirInt + 1);
            }
 
        }
    }

The Rover class stores its coordinates and Directions as a struct and an enum. Here is the code for them.

    ///
    /// This enumeration is for the Direction the Rover is currently facing in.
    ///
    enum Direction { North, East, South, West, };
 
    ///
    /// This is Stuct which holds the current coordinates of the Rover.
    /// It is also used to hold the max coordinates of the Grid.
    ///
    struct Coordinates
    {
        private int _xCor;
        private int _yCor;
 
        public int X { get { return _xCor; } }
 
        public int Y { get { return _yCor; } }
 
        public Coordinates(int _xCor, int _yCor)
        {
            this._xCor = _xCor;
            this._yCor = _yCor;
        }
 
        public void UpdateCoordinates(Direction _dirObj)
        {
            switch (_dirObj)
            {
                case Direction.North:
                    this._yCor++;
                    break;
                case Direction.South:
                    this._yCor--;
                    break;
                case Direction.East:
                    this._xCor++;
                    break;
                case Direction.West:
                    this._xCor--;
                    break;
            }
        }
    }

The Grid class contains a generic list of all the rovers on the grid. It moves each rover in the list and makes sure the rover doesn’t cross the boundaries. If it does then an exception is thrown.

    ///
    /// This class is responsible for holding all the Rovers
    /// and also making sure no rovers cross the grid boundaries.
    /// The ToString() method is overridden to get the state of
    /// all rovers on the grid in an easy to read string format
    ///
    class Grid
    {
        //Maximum coordinates for the grid
        private Coordinates _maxCoordinates;
 
        //Collection Object to hold all rovers on grid
        private List _allRoversOnGrid;
 
        //Constructor to intialize Rover collection and max coordinates
        public Grid(Coordinates _maxCor)
        {
            this._maxCoordinates = _maxCor;
            _allRoversOnGrid = new List();
        }
 
        //Rovers can only be added to the collection. Nothing else
        //is exposed outside
        public void AddToRoverCollection(Rover _roverObj)
        {
            _allRoversOnGrid.Add(_roverObj);
        }
 
        //This method processes all the rovers on the grid and their instruction arrays
        public void MoveAllRoversOnGrid()
        {
            foreach (Rover _tempRov in _allRoversOnGrid)
            {
                _tempRov.ProcessInstructionArray();
                this.DoIntegrityCheck(_tempRov);
            }
        }
 
        //Making sure the Rover object stays within the grid.
        private void DoIntegrityCheck(Rover _tempRov)
        {
            if ((_tempRov.X &gt; _maxCoordinates.X) || (_tempRov.Y &gt; _maxCoordinates.Y))
            {
                throw new Exception("Rover Failed Grid Integrity. Moved out of Grid Boundaries");
            }
        }
 
        //Overriding the ToString method to get all rovers states
        public override string ToString()
        {
            StringBuilder _AllRoversState = new StringBuilder();
            _AllRoversState.Append("**********************************");
            _AllRoversState.Append(Environment.NewLine);
            _AllRoversState.Append("Number of Rovers currently on Grid: " + this._allRoversOnGrid.Count);
            _AllRoversState.Append(Environment.NewLine);
            _AllRoversState.Append(String.Format("Max Coordinates: X: {0},Y: {1}", _maxCoordinates.X, _maxCoordinates.Y));
            _AllRoversState.Append(Environment.NewLine);
            _AllRoversState.Append("Each Rover state as below: ");
            _AllRoversState.Append(Environment.NewLine);
            foreach (Rover _tempRov in _allRoversOnGrid)
            {
                _AllRoversState.Append(String.Format("Rover Details -- X:{0},Y:{1},Direction:{2}", _tempRov.X, _tempRov.Y, _tempRov.RoverDirection));
                _AllRoversState.Append(Environment.NewLine);
            }
            _AllRoversState.Append("**********************************");
            return _AllRoversState.ToString();
        }
 
    }

Finally, the code to call the Grid class:-

    class Program
    {
        static void Main(string[] args)
        {
 
            //Creating Grid Object
            Grid _testGrid = new Grid(new Coordinates(5,5));
            //Adding two rovers as per sample input
            _testGrid.AddToRoverCollection(new Rover(1, 2, 'N', "LMLMLMLMM"));
            _testGrid.AddToRoverCollection(new Rover(3, 3, 'E', "MMRMMRMRRM"));
            //move all rovers
            _testGrid.MoveAllRoversOnGrid();
            //Get Rover Final state using Grids ToString() method.
            Console.WriteLine(_testGrid.ToString());
        }
    }

To download the solution click here.

Dec 282009
 

How often have you faced  the irritating not responding screen while the application waits for the data that you requested for. The problem is not with bad code or a slow database, the problem with conventional applications is that all the code is executed on a single thread. i.e. whenever an operation is performed the calling function must wait for it to complete in order to resume execution.

Since the main thread is also the UI thread, the UI stops responding whenever its waiting for the function to return, making the user experience very bad. To avoid this, any time consuming operation should be executed on its own thread rather than the main thread. Lets see a simple example of a method created on another thread.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
        static void Main(string[] args){
            ThreadingApp _testObj = new ThreadingApp();
 
            //Declaring Two Objects for calling the parameterless and parametrized method
            Thread _tObj1 = new Thread(new ParameterizedThreadStart(_testObj.DoSomeWork));
            Thread _tObj2 = new Thread(new ThreadStart(_testObj.DoWork));
 
            //Calling the overloaded method
            _tObj1.Start("CustomParameter");
            //Calling the parameterless method
            _tObj2.Start();
 
        }
 
    class ThreadingApp{
        // Parameterless method executed on anothed
        public void DoWork(){
            Console.WriteLine("Executed On another thread");
        }
 
        public void DoSomeWork(object _name){
            Console.WriteLine("Executed on another thread. Paramter: " + _name);
        }
    }

The ability to pass parameters to methods on other threads is new in .NET 2.0. The delegate introduced for this is the ParametrizedThreadStart delegate which takes in an object parameter. Since its an object type, pretty much anything can be passed to the method. So creating new threads is pretty simple. But a word of caution here – Threading unless used carefully can introduce very hard to detect bugs in your system.

Multiple threads don’t cause any problem till the time each thread runs its own context not depending on shared resources or variables. The issues start when threads start to modify each others variables and access each others resources. Lets see a small example where multiple threads accessing the same variable can lead to unpredictable scenarios. In the below code two variables increment a class level variable and print the values before and after the incrementing. As you can see in the output below, it leads to a chaotic scenario where threads are misreading values and coming in each others way to access the variable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    class Program
    {
    int _value = 0;
    static void Main(string[] args){
        Program _prgm = new Program();
        for (int i = 0; i > 5; i++)
        {
            Thread _t1Obj = new Thread(new ThreadStart(_prgm.DoWork1));
            Thread _t2Obj = new Thread(new ThreadStart(_prgm.DoWork2));
 
            _t1Obj.Start();
            _t2Obj.Start();
        }
 
    }
 
    public void DoWork1()
    {
        Console.WriteLine("Thread1 start: " + _value);
        _value++;
        //Introduced a small sleep to bring some entropy in the system
        Thread.Sleep(10);
        Console.WriteLine("Thread1 End: " + _value);
    }
 
    public void DoWork2()
    {
        Console.WriteLine("Thread2 start: " + _value);
        _value++;
        Console.WriteLine("Thread2 End: " + _value);
    }
 
    }

When we see the output, it looks pretty haphazard. Its easy to see the threads are confused about execution and misreading the value of the variable.

The Monitor class can be used to synchronize threads in .NET. How it works is that it puts a lock on the currently executing code making all other threads wait before they can access the variables that current method has locked. The Monitor has two main static methods Monitor.Enter and Monitor.Exit for entering the lock and exiting from it. Apart from this there is also the Monitor.TryEnter which tries to gain ownership of the code block. If its not able to it returns false. This is very important since calling the Monitor.Exit for a block you dont have ownership of, would raise a SynchronizationLockException. However making sure to call Enter and Exit every time would get cumbersome for a developer and there are chances it might be forgotten. Here is where C# comes into rescue with the lock keyword. Enclosing the code within the lock block automatically does all the steps which are mentioned above.

1
2
3
4
5
6
7
8
9
10
11
12
    static readonly object _lockObj = new object();
    public void DoWork1()
    {
        lock (_lockObj)
        {
            Console.WriteLine("Thread1 start: " + _value);
            _value++;
            //Introduced a small sleep to bring some entropy in the system
            Thread.Sleep(10);
            Console.WriteLine("Thread1 End: " + _value);
        }
    }

Enclosing the code within the lock block brings order back to the method execution and we can observe that that each thread waits for the other to complete before attempting to modify the variable. Here is the IL for the above method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.method public hidebysig instance void  DoWork1() cil managed
{
 
  IL_0000:  ldsfld     object ThreadingApp.Program::_lockObj
  IL_0005:  dup
  IL_0007:  call       void [mscorlib]System.Threading.Monitor::Enter(object)
  .try
  {
    //Our method logic removed for brevity
  }  // end .try
  finally
  {
    IL_0057:  ldloc.0
    IL_0058:  call       void [mscorlib]System.Threading.Monitor::Exit(object)
    IL_005d:  endfinally
  }  // end handler
  IL_005e:  ret
} // end of method Program::DoWork1

A very important point stressed time and again would be to make sure not to expose the locking object outside the class. If this is done, anyone can use the object to lock your methods and not release them while your application threads remain indefinitely waiting for the lock to be freed.

There are many other techniques for thread synchronization in .NET. I will be covering them in upcoming posts.

Dec 262009
 

Events and Delegates are quite tied together in .NET, but there are differences in terms of usage. Events are implemented through delegates, but they are not quite interchangeable. The event keyword is an access modifier on the delegate which restricts its usage outside the class which it belongs to.

First the similarities. See the below code, which declares a delegate and creates objects for it with and without the event modifier. Then uses both of them, without any difference whatsoever.

    class Test
    {
        public delegate void MyDelegate(string _someRandomMessage);
 
        //One is a delegate while other is an event.
        public MyDelegate _mydelObj;
        public event MyDelegate _myeventObj;
 
        public Test(){
            _mydelObj = s =&gt; Console.WriteLine("Delegate Invoked: " + s);
            _myeventObj = s =&gt; Console.WriteLine("Event Invoked: " + s);
        }
 
        public void TestDelegates(){
            _mydelObj.Invoke("I am a delegate");
            _myeventObj.Invoke("I am an event");
        }
    }

The main difference starts when you access events outside of the class they were declared in. I created one more class SomeOtherClass (very unimaginative!!) and invoked the public delegate objects from this. When its a plain delegate object, there is no restriction on resetting the invocation list, adding to it, removing from it and also invoking the delegate itself. But try doing that to the event object, and you the compiler will throw the The event ‘EventsAndDelegates.Test._myeventObj’ can only appear on the left hand side of += or -= (except when used from within the type ‘EventsAndDelegates.Test’)

    class SomeOtherClass{
        Test _testObj = new Test();
        public SomeOtherClass()
        {
            _testObj._mydelObj += s =&gt; Console.WriteLine("Calling from Outside class: "+s);
            _testObj._myeventObj += s =&gt; Console.WriteLine("Calling Event from Outside class " + s);
            //The below code wont work. An event's invocation list cannot be accessed
            //from outside. It can be added to or removed from.
            _testObj._myeventObj = s =&gt; Console.WriteLine("Trying to reset the invocation list");
        }
 
        public void InvokeBaseDelegate(){
            _testObj._mydelObj("Delegate Invoked");
            //This will throw an error. An event cannot be triggered from anyother type
            //other than the one which it belongs to
            _testObj._myeventObj("Event Triggered");
        }
    }

This key difference is due to the way events and delegates are exposed outside the class which they are declared in. There is an extra IL declaration for an event object which declares two accessors add and remove for the event. Only these are accessible outside the class.

.event EventsAndDelegates.Test/MyDelegate _myeventObj
{
  .addon instance void EventsAndDelegates.Test::add__myeventObj(class EventsAndDelegates.Test/MyDelegate)
  .removeon instance void EventsAndDelegates.Test::remove__myeventObj(class EventsAndDelegates.Test/MyDelegate)
} // end of event Test::_myeventObj

When this is accessed in SomeOtherClass, the Delegate.Combine method used to add to the delegate object’s invocation list is not available for the event and the only alternatives are the add and remove accessors. Similarly the Invoke method is not available outside the class because of which the events cant be triggered.

.method public hidebysig specialname rtspecialname
        instance void  .ctor() cil managed
{
//Removed for Brevity
  IL_0035:  ldsfld     class EventsAndDelegates.Test/MyDelegate EventsAndDelegates.SomeOtherClass::'CS$&lt;&gt;9__CachedAnonymousMethodDelegate2'
  IL_003a:  call       class [mscorlib]System.Delegate [mscorlib]System.Delegate::Combine(class [mscorlib]System.Delegate,
                                                                                          class [mscorlib]System.Delegate)
  IL_003f:  castclass  EventsAndDelegates.Test/MyDelegate
//Removed for brevity
  IL_0067:  ldsfld     class EventsAndDelegates.Test/MyDelegate EventsAndDelegates.SomeOtherClass::'CS$&lt;&gt;9__CachedAnonymousMethodDelegate3'
//Notice the add_ accessor being called instead of the Delegate.Combine method
  IL_006c:  callvirt   instance void EventsAndDelegates.Test::add__myeventObj(class EventsAndDelegates.Test/MyDelegate)
  IL_0071:  ret
} // end of method SomeOtherClass::.ctor

It makes sense to restrict an event’s invocation list from an outside class. For example, if your application makes use of a public API which polls for the weather at a location and raises an event when there is going to be heavy snow. Someone in your team might have subsribed to the event to send out notifications to employees take caution while travelling. However, your need to subscribe to the event could be totally different. In that case if you use the = sign instead of the += while assigning a handler, the previous code for sending out notifications would not work. Needless to say, there would be a lot of pi**ed off employees baying for your blood the next day.

Apart from this, there is one more difference between delegates and events while declaring them in an interface. An interface cannot contain delegate objects, however they can contain events. If you try to do so, you would get an error Interfaces cannot contain fields.

Dec 262009
 

In the previous post we saw how anonymous methods can help reduce verbose delegate code. With C# 3.0, there was a new language feature introduced which further reduces the delegate code – Lambda expressions.

Lambda expressions use automatic type inference, which relieves you of explicitly declaring the type. Here is a simple example of lambda expressions usage. Notice how the code for the delegate object is concisely declared. What is signifies is that the value of x is to be passed to the method, which is then squared and returned. The operator => signifies sending of the parameter (LHS) to the method (RHS).

1
2
3
4
5
6
7
8
9
10
11
	private delegate int Square(int x);
 
	// Simple Lambda expression example
	public static void Test()
	{
        //Note I dont declare the type of variable x. Its automatically inferred.
		Square myVar = x => x*x;
        //Call the delegate
		int n = myVar(5);
        Console.WriteLine(n); //prints 25
	}

When we dive into the MSIL, we find an identical code to Anonymous methods. There is a delegate which is created by the compiler automatically and also the implementation of the inline code is spun off into a separate method b_0. Whats important to note is that both the return type and the arguments of the method is automatically inferred by the compiler. This is not possible with anonymous methods, where we have to explicitly declare the list of arguments to the delegate.

1
2
3
4
5
6
7
8
.method private hidebysig static int32  '<test>b__0'(int32 x) cil managed
{
  IL_0000:  ldarg.0
  IL_0001:  ldarg.0
  IL_0002:  mul
  IL_0003:  ret
} // end of method TestLambda::'</test><test>b__0'
</test>

Since lambda expression pass the parameter to the method, the syntax is slightly different for delegates which don’t take any parameters.

1
2
3
4
5
6
7
8
9
private delegate void DoSomething();
    public static void MethodsWithNoArguments()
    {
        DoSomething _methWithNoArgs = () => Console.WriteLine(
        "Lambda Expression without arguments and return types");
 
        //prints the message.
        _methWithNoArgs();
    }

Lambda expressions can also be used to send a delegate object as a parameter to any method. In the below example, I wrote a delegate which takes in a delegate as a parameter and invokes it using the other argument. Note how lambda expressions automatically inferred the type of the delegate object being passed to it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private delegate void PrintMessage(string s);
private delegate void DoSomething();
 //Takes in the Print Message Delegate as an argument.
 private delegate void LamArguments(PrintMessage _printMsg,string _message);
 
    public static void TestDelegateParams()
    {
        //This delegate takes in the PrintMEssage delgate as the 
        // parameter and invokes it. 
        LamArguments _lamARg = (mymsg, _message) =>
        {
            mymsg.Invoke(_message);
        };
 
        //Assigning a method to the PrintMessage delegate's invocation list.
        PrintMessage _printMsg = _message =>
            {
                Console.WriteLine(_message);
            };
 
        //Sending the message 
        _lamARg(_printMsg, "Hello World");
    }
Dec 232009
 

Anonymous methods are a convenient way of using delegates in .NET 2.0 and above. For e.g. if we use a delegate for a simple 2-3 line functionality, declaring a separate method and then passing the target to the delegate seems like overkill. Anonymous methods provide an easy way out, just declare the body of the method after the delegates declaration and you have no need to write a seperate method.

Anonymous methods are a compiler feature. Hence, from the CLR’s point of view there is nothing anonymous about it. The C# compiler generates a method with your delegate declaration and adds it to the invocation list for the delegate. Here is some sample code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 class TestClass
    {
        delegate void writeToScreen(string _inpar);
 
        public static void TestDelegates()
        {
            //1.1 way of doing things. Notice the seperate method.
            writeToScreen _delObj = new writeToScreen(new TestClass().NamedMethod);
 
            //2.0 way of calling it
            _delObj += delegate(string _inpar)
            {
                Console.WriteLine("Anonymous method says: "+_inpar);
            };
 
            //Lets invoke the delegate
            _delObj.Invoke("Hello World");
        }
 
        public void NamedMethod(string _inpar)
        {
            Console.WriteLine("Named method says: " + _inpar);
        }
    }

In the above code, the 1.1 way would have you scrambling to find the definition of the NamedMethod, but in second delegate its simpler and far more easier to understand. In the IL, the compiler generates a method for the anonymous block of code that you write.

1
2
3
4
5
6
7
.method private hidebysig static void  'b__0'(string _inpar) cil managed
{
  .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 )
//removed for brevity
  IL_0010:  ret
}
// end of method TestClass::'b__0'

So far so good, but anonymous methods bring more questions to the table. How are variables in the outer scope treated? Can they be accessed? Yes they can and they have a fancy name as well – Captured variables. Here is some code for it.

1
2
3
4
5
6
7
8
9
10
11
12
13
            int _localVar = 0;
            _delObj += delegate(string _inpar)
            {
                _localVar++;
                Console.WriteLine("Anonymous method says: "+_inpar);
            };
 
            //Before invoking the delegate the value is 0
            Console.WriteLine("Local Variable : " + _localVar);
            //Lets invoke the delegate
            _delObj.Invoke("Hello World");
            //After invoking, the value becomes 1
            Console.WriteLine("Local Variable : " + _localVar);

Behind the screens the compilers does a lot of work to get captured variables work. In the MSIL, there is no sign of the local variable, instead a reference variable is created which has the local integer as a member and all modifications are done to it.

The IL shows the int declaration has disappeared in the TestDelegates method. Instead an instance of the class c_Displayclass1 is created and used. The local variable is a member of this instance class and this is the variable that is incremented both in the TestDelegates method as well as the invocation giving the illusion of usage of the local variable in the anonymous method body scope. For short declarations and one or two variables this feature would be quite useful, but a large number of captured variables would make the code difficult to understand, hence compromising the biggest advantage of anonymous methods

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
.method public hidebysig static void  TestDelegates() cil managed
{
   .locals init ([0] class AnonyMeth.TestClass/writeToScreen _delObj,
           [1] class AnonyMeth.TestClass/'&lt;&gt;c__DisplayClass1' 'CS$&lt;&gt;8__locals2')
  IL_0000:  newobj     instance void AnonyMeth.TestClass/'&lt;&gt;c__DisplayClass1'::.ctor()
  IL_0005:  stloc.1
 //removed for brevity
  IL_0019:  stfld      int32 AnonyMeth.TestClass/'&lt;&gt;c__DisplayClass1'::_localVar
  IL_001e:  ldloc.0
  IL_001f:  ldloc.1
  IL_0020:  ldftn      instance void AnonyMeth.TestClass/'&lt;&gt;c__DisplayClass1'::'b__0'(string)
  IL_0026:  newobj     instance void AnonyMeth.TestClass/writeToScreen::.ctor(object,
                                                                              native int)
  IL_002b:  call       class [mscorlib]System.Delegate [mscorlib]System.Delegate::Combine(class [mscorlib]System.Delegate,
                                                                                          class [mscorlib]System.Delegate)
  IL_0030:  castclass  AnonyMeth.TestClass/writeToScreen
  IL_0035:  stloc.0
  IL_0036:  ldstr      "Local Variable : "
  IL_003b:  ldloc.1
  IL_003c:  ldfld      int32 AnonyMeth.TestClass/'&lt;&gt;c__DisplayClass1'::_localVar
  //The instance variable of c__displayclass1 is displayed here
  //removed for brevity
  IL_0075:  ret
} // end of method TestClass::TestDelegates
Dec 092009
 

The word Asynchronous means something that is not synchronized (duh!!) i.e. which occurs out of step and is not coordinated. In programming parlance, asynchronous processes are which take place independently of other processes. For e.g. a method call. A conventional method call is blocking. i.e the calling thread waits for the method to return control to resume its operation, which means if the method is long running, it makes the whole application stop and wait for the called method to return.

This causes the irritating Not Responding screen. To avoid such scenarios we can use the Asynchronous method calls. These are methods which the main thread calls and forgets about, until the methods complete and notify it that their result can be used. If you recall we had done something similar in the BackgroundWorker component, where the long running operation was executed on another thread. Asynchronous delegates provide the same functionality as well, with much more control than a BackgroundWorker.

To Start this we will create an application which calls a long running method both synchronously and asynchronously. First the synchronous call. This is easy- just call a method which sleeps for 10 seconds and try moving the form around while that method is executing.

private void button1_Click(object sender, EventArgs e)
{
    label1.Text = "The Result is " + VeryLongRunningOperation().ToString();
}

private int VeryLongRunningOperation()
{
    Thread.Sleep(10000);
    return 5;
}

Lets do this asynchronously. The Delegate object has two methods BeginInvoke and EndInvoke, the beginInvoke starts execution of the target method on a different thread. And EndInvoke retrieves the return value. Sounds simple, but there is one tiny issue. How does the EndInvoke method know when the method is completed and the return value can be retrieved. A crude way is to use a while loop after calling BeginInvoke and checking the IsCompleted property every few seconds. If its completed then the EndInvoke can be called to get the value and we can break out of the loop after that.

But there has to a better approach than this. The delegated method should inform the main thread that it is completed and ready with the return value. This is achieved by using a Callback method. the ASyncCallBack delegate is passed to the beginInvoke method which targets the callback method and calls it once the the long running operation is executed. In the Callback method, the AsyncState property stores the delegate object which is cast as our delegate object. Then all we need to do is to check whether the execution is complete and retrieve the value by using the EndInvoke method.

delegate int forLongRunningOps();

delegate void SetLabelValue(int _result);

public partial class Form1 : Form
{
public Form1()
{
    InitializeComponent();
}

private void button2_Click(object sender, EventArgs e)
{
    forLongRunningOps _ops = new forLongRunningOps(this.VeryLongRunningOperation);

    _ops.BeginInvoke(new AsyncCallback(CompletedMethod),this);
}

private void CompletedMethod(IAsyncResult _result)
{
    AsyncResult aResult = (AsyncResult) _result;

    forLongRunningOps _delObj = (forLongRunningOps) aResult.AsyncDelegate;
    int answer = 0;

   // if(_result.IsCompleted)
    answer = _delObj.EndInvoke(_result);
    if (label1.InvokeRequired)
        label1.Invoke(new SetLabelValue(SetLabelValue),new object[]{answer});
    else
        label1.Text = "The Result is " + answer.ToString();
}

public void SetLabelValue(int _result)
{
    label1.Text = "The Result is " + _result.ToString();
}

private int VeryLongRunningOperation()
{
    Thread.Sleep(10000);
    return 5;
}

}

In this code the Callback method is the completed method. From the IAsyncResult object which is the argument, we retrieve the delegate object so that we can call EndInvoke and retrieve the result. After getting the result, I tried setting this to a label text, but got a screaming exception about a Cross Thread call. This can be avoided by the InvokeRequired property of the control. Suppose the control is not created on the thread where the current code is running, this property is true, so instead of directly accessing the control, we call the invoke method and pass it to a delegate which points to a method which sets the value for us. For If the method takes in any parameters, pass it as an object array.

Thats it. The same long running method was called in both synchronous and asynchronous and we notice how much the user experience improves when such long running operations don’t cause the Form to hang.

Nov 302009
 

I didn’t know this was possible until a few days back when a user asked about it on one of the MSDN forums. The query was on how to integrate Winforms and WPF i.e. how to display WPF user controls in Winform application. This feature can be extremely useful because some elements and effects which are easy in WPF can make you sweat a lot in Winforms.

Also this might be useful when you are eventually looking to migrate your application GUI to WPF. So when you are able to create resuable user controls and reuse them in Winforms, it will allow you to port all your winform user controls to WPF one at a time.

The control in Winforms which can do this is the ElementHost which resides in the WindowsFormsIntegration assembly. The ElementHost is responsible for loading the WPF control and painting it. Lets see how to do it. First we will create a user control in WPF. The markup is

<UserControl x:Class="WpfApplication1.SampleWPF"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Height="300" Width="300">
    <Grid>
        <StackPanel Margin="12,91,12,30">

            <TextBlock HorizontalAlignment="Center" Text="Sample WPF Control"
                       FontSize="20"
                       FontFamily="Verdana"
                       />

            <Button Name="btnClick" Click="btnClick_Click" Content="Click ME" HorizontalAlignment="Stretch" />
        </StackPanel>
    </Grid>
</UserControl>

Nothing really, just a StackPanel inside the grid with a TextBlock and a Button. Just to see a WPF Event we hookup an event handler to the Button.

public partial class SampleWPF : UserControl
{
    public SampleWPF()
    {
        InitializeComponent();
    }

    private void btnClick_Click(object sender, RoutedEventArgs e)
    {
        MessageBox.Show("WPF says Hello");
    }
}

Now that the WPF part is done, all we need to do is create a Winform Host for this user control. Create a new Winform project and add a reference to the following dlls:-

  • PresentationCore.dll
  • PresentationFramework.dll
  • WindowsBase.dll
  • WindowsFormsIntegration.dll
  • Your WPF DLL which you just created.

Now just to show interoperability between WPF and Winforms, drag a Winforms label and button and hook an event handler to it. In the Form Load handler we create an ElementHost. Since we added the WPF control’s assembly reference, we can create an object of the WPF user control. Of course we cant add the control to the Form’s control collection since the Form object has no idea how to draw the WPF control. This is where the ElementHost control comes in. The ElementHost takes in the usercontrol as its child control and is added to the Winfrom. The code is:-

private void Form1_Load(object sender, EventArgs e)
{
    ElementHost _host = new ElementHost();
    _host.Dock = DockStyle.Fill;
    WpfApplication1.SampleWPF _wpfUserControl = new WpfApplication1.SampleWPF();
    _host.Child = _wpfUserControl;
    this.Controls.Add(_host);
}

private void btnWinClick_Click(object sender, EventArgs e)
{
    MessageBox.Show("Windows Says Hello");
}

And this works great. Both the events for the WPF user control and the Winform controls work here. Some screenshots below:-


WinForm

wpfclick

winclick

The magic here is done by ElementHost and another class AvalonAdapter. Avalon as you would recall was WPF’s code name in its early stages of development. The Avalon Adapter is responsible for drawing the WPF application to the Windows form. The hWndSource object is responsible for creating the hWnd for the window. Using this you can actually make WPF interop with Win32 applications as well.

This method is not without its limitations though, you cant pretty much do anything which is possible with WPF, for e.g transparency