Jan 202012
 

I wrote a small application to extract post and user data for groups in the popular enterprise microblogging portal, Socialcast. It lets users access data instantly about the activity going on in their groups and the number of likes/comments being posted by group members.

The details about the API can be found here and their side demo.socialcast.com can be used for testing. There are three main calls in the application

  • Message Data for the group (Using the parameters Group_Id and since to filter by the data)
  • To find the group Id using the group name using the Groups.xml API call.
  • Then finding the group members using groupname/members.xml.

The method to retrieve group_id from the groupname needed improvement. Most organizations contain upwards of a 1000 groups. Making two heavy API calls for finding out the group id from the name is a bit of a drag on the performance of the application. To avoid this, I just cached all the group Ids and names in a Dictionary<string, int> object and used that to lookup the id. For groups that were created after the tool was distributed, the API call was a fallback.

The UI of the tool is fairly simple. Just a textbox to enter the group URL and two datagridviews to display the data along with two listboxes to display the stats. Since data retrieval is a very slow process, a backgroundworker with a progress bar make sure the application doesnt freeze and the user is shown some progress.  There is also a dropdown to select the time for which the user wants to retrieve messages and whether the member information is required or not. The quickest options are selected by default.


The API access code is in a library which hides the webservice calls from the client application. Each method contains the standard page and number of records per page argument. Apart from them, there are other parameter which are needed to make the call e.g GroupName, member id etc. To simply the URL construction for the web service call a class contains the skeleton urls for each call like given below

public static class ObjectType
 {
 static string defaultFormat = ".xml";
 public static string Users = "users" + defaultFormat;
 public static string Streams = "streams" + defaultFormat;
 public static string Messages = "messages" + defaultFormat;
 public static string StreamMessages = "streams/{0}/messages" + defaultFormat;
 public static string MessagesById = "messages/{0}" + defaultFormat;
 public static string SearchUsers = "users/search" + defaultFormat;
 public static string Groups = "groups" + defaultFormat;
 public static string GroupMembers = "groups/{0}/members" + defaultFormat;
 }

public class SocialCastData
 {
 ///
<summary> /// These are the private variables which are configured
 /// as per your socialcast site
 /// </summary>
 string skeletonURL = "https://{0}.socialcast.com/api/{1}";
//Rest of code here
}

The method to construct the service url takes in the Object Type member, and appends it to the skeleton url along with filling in the domain of the socialcast site and any additional parameter (e.g. group id). This approach allows me to add new service calls easily with just one more variable in the ObjectType class. Any additional query string parameters are supplied using the serviceParams which is a list of keyvaluepairs. The list is iterated through and appended after the url. The SocialcastAuthDetails object is a must in every calls since it contains the domain, the username and password all of which are required to be supplied for getting the response.

Here is the method to get the Group ID from the groupName. The GroupQuery.QueryForGroupId accesses the cache and returns immediately if found. If not then another API call is made to get all the groups, iterate through them and identify the id. If the group id is still not found, an exception is thrown.

        private int GetGroupIdByGroupName(string groupName,SocialCastAuthDetails auth)
        {

            int _groupId = 0;
            int _pageNumber =1;
            bool moreItems = true;

            _groupId = GroupsQuery.QueryForGroupID(groupName);
            if (_groupId != 0)
                return _groupId;
            else
            {

                while (moreItems)
                {
                    XmlDocument group = new XmlDocument();
                    var serviceParams = new List>();
                    serviceParams.Add(new KeyValuePair("page", _pageNumber.ToString()));
                    serviceParams.Add(new KeyValuePair("per_page", "500"));
                    group.LoadXml(base.MakeServiceCalls(helper.GetSocialcastURL(ObjectType.Groups, auth.DomainName, null, serviceParams),GetCredentials(auth.Username,auth.Password)));
                    if (group.SelectNodes("//groups/group") == null || group.SelectNodes("//groups/group").Count == 0)
                        moreItems = false;
                    else
                    {
                        foreach (XmlNode groupNode in group.SelectNodes("//groups/group"))
                        {
                            if (String.Compare(GetNodeInnerText(groupNode, "groupname"), groupName, true) == 0)
                            {
                                string id = GetNodeInnerText(groupNode, "id");
                                _groupId = Convert.ToInt32(id);
                                GroupsQuery.AddToDictionary(groupName, _groupId);
                                moreItems = false;
                                break;
                            }
                        }
                    }
                    _pageNumber++;
                }
                return _groupId;
            }
        }

In the front end, a background worker is used to perform the time consuming operation asynchronously. Here is the code (Rough, not refactored)

    class GetStatistics
    {
        APIAccessor _api = new APIAccessor();

        public AppData GetData(string urlEnteredbyUser, string sinceWhatPeriod, bool loadUserData)
        {
            var serviceUrl = UrlReplace(urlEnteredbyUser.Trim());
            List<SocialcastMessage> messages = null;
            List<UserProfile> users = null;
            if (serviceUrl == string.Empty)
            {
                throw new GroupNotFoundException(null, "The group Url you have entered is not valid");
            }
            else
            {
                messages = GetMessageStats(serviceUrl, sinceWhatPeriod);
                if(loadUserData)
                        users = GetAllGroupUsers(serviceUrl);
                return new AppData(messages, users);
            }
        }

        private List<UserProfile> GetAllGroupUsers(string groupName)
        {
            List<UserProfile> Users = new List<UserProfile>();
            int userCount = 500;
            int pageNumber = 1;
            bool moreItems = true;
            while (moreItems)
            {
                var xdoc = _api.GetGroupMembers(groupName, pageNumber.ToString(), userCount.ToString(), GetCredentials());
                if (xdoc.SelectNodes("//users/user") == null || xdoc.SelectNodes("//users/user").Count == 0)
                    moreItems = false;
                else
                {
                    foreach (XmlNode userNode in xdoc.SelectNodes("//users/user"))
                    {
                        string name = GetNodeInnerText(userNode, "name");
                        string userName = GetNodeInnerText(userNode, "username");
                        string email = GetNodeInnerText(userNode, "contact-info/email");
                        int followingCount = Convert.ToInt32(GetNodeInnerText(userNode, "following-count"));
                        int followersCount = Convert.ToInt32(GetNodeInnerText(userNode, "followers-count"));

                        Users.Add(new UserProfile()
                        {
                            Name = name,
                            userName = userName,
                            Email = email,
                            FollowerCount = followersCount,
                            FollowingCount = followingCount
                        });
                       
                    }
                    pageNumber++;
                }
            }

            return Users;
        }

        private List<SocialcastMessage> GetMessageStats(string serviceUrl, string sinceWhatPeriod)
        {
            List<SocialcastMessage> Messages = new List<SocialcastMessage>();
            int messageCount = 500;
            int pageNumber = 1;
            bool moreItems = true;
            long sinceWhen = GetSinceWhenValue(sinceWhatPeriod);
            while (moreItems)
            {
                var xdoc = GetMessagesForTheGroup(serviceUrl, messageCount, pageNumber, sinceWhen);
                if (xdoc.SelectNodes("//messages/message") == null || xdoc.SelectNodes("//messages/message").Count == 0)
                    moreItems = false;
                else
                {
                    foreach (XmlNode node in xdoc.SelectNodes("//messages/message"))
                    {
                        DateTime createdDate;
                        DateTime.TryParse(GetNodeInnerText(node, "created-at"), out createdDate);
                        string ticksLastUpdatedDate = GetNodeInnerText(node, "last-interacted-at");
                        var epoch = new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc);
                        epoch = epoch.AddSeconds(Int64.Parse(ticksLastUpdatedDate));
                        string permaUrl = GetNodeInnerText(node, "permalink-url");
                        string commentsCount = GetNodeInnerText(node, "comments-count");
                        string likesCount = GetNodeInnerText(node, "likes-count");
                        string title = GetNodeInnerText(node, "title");
                        string user = GetNodeInnerText(node, "user/name");

                        Messages.Add(new SocialcastMessage()
                        {
                            Title = title,
                            Url = permaUrl,
                            CreatedDate = createdDate,
                            UpdatedDate = epoch,
                            Comments = int.Parse(commentsCount),
                            Likes = int.Parse(likesCount),
                            UserName = user
                        });

                    }
                    pageNumber++;
                }
            }


            return Messages;

        }


        private long GetSinceWhenValue(string sinceWhatPeriod)
        {
            switch (sinceWhatPeriod)
            {
                case "All Messages":
                    return 0;
                case "Since Last week":
                    return GetTicksSince1970(7);
                case "Since Last Month":
                    return GetTicksSince1970(30);
                default:
                    return 0;
            }
        }

        private static long GetTicksSince1970(int days)
        {
            DateTime sinceLastWeek = DateTime.Now.Subtract(new TimeSpan(days, 0, 0, 0, 0));
            DateTime epoch = new DateTime(1970, 1, 1);
            return Convert.ToInt64(sinceLastWeek.Subtract(epoch).TotalSeconds);
        }


        private XmlDocument GetMessagesForTheGroup(string streamName, int numberOfPosts, int page, long sinceWhen)
        {
            string sinceWhenString = null;
            if (sinceWhen != 0)
                sinceWhenString = sinceWhen.ToString();
            var xdoc = _api.GetStreamMessages(streamName, numberOfPosts.ToString(), page.ToString(), sinceWhenString, GetCredentials());
           return xdoc;
        }


        private string UrlReplace(string enteredByUser)
        {
        
            string regexPattern = @"https://demo.socialcast.com/groups/([A-Za-z0-9\-]+)";
            Match match = Regex.Match(enteredByUser, regexPattern,
                RegexOptions.IgnoreCase);

            // Here we check the Match instance.
            if (match.Success)
            {
                // Finally, we get the Group value and return it
                string key = match.Groups[1].Value;
                return key;
            }
            return string.Empty;
        }

        private SocialCastAuthDetails GetCredentials()
        {
            return new SocialCastAuthDetails()
            {
                Password = "demo",
                Username = "emily@socialcast.com",
                DomainName = "demo"
            };

        }

        private string GetNodeInnerText(XmlNode node, string xpath)
        {
            try
            {
                if (node.SelectSingleNode(xpath) != null)
                {
                    return node.SelectSingleNode(xpath).InnerText.Trim();
                }
                return String.Empty;
            }
            catch
            {
                return string.Empty;
            }
        }
    }
Dec 272010
 

Since the last post, I changed the library/API wrapper a bit. I removed all the ugly reflection stuff to retrieve the specific API urls and substituted them with static variables in a separate class. However this does have the added disadvantage that the urls are exposed to the client, but at least it wont break any client code if Socialcast decides to change the API in the future. Also in the previous example, the username, password and subdomain are variables in the wrapper itself. In the absence of oAuth, every call needs to be authenticated with the user credentials. To avoid having to handle the responsibility of storing user information, I created a class to encapsulate this information (SocialcastAuthDetails) which is passed to the API Accessor for every call. I also added the data objects to return strongly typed responses from the API accessor instead of an XmlDocument, but havent gotten around to incorporate them yet.

Here is the code to Post a message and Get the company stream. Accessing the Company Stream requires two calls – first to get the Stream ID and the next to get the messages for the particular stream.

        public XmlDocument GetCompanyStream(SocialCastAuthDetails auth)
        {
            XmlDocument streams = new XmlDocument();
            if (companyStreamID == 0)
            {
                streams.LoadXml(base.MakeServiceCalls(helper.GetSocialcastURL(ObjectType.Streams,auth.DomainName,null), GetCredentials(auth.Username,auth.Password)));

                foreach (XmlNode node in streams.GetElementsByTagName("stream"))
                {
                    if (node.SelectSingleNode("name").InnerText.ToLower() == "company stream")
                    {
                        companyStreamID = int.Parse(node.SelectSingleNode("id").InnerText);
                        break;
                    }
                }
            }
            streams = new XmlDocument();
            streams.LoadXml(base.MakeServiceCalls(
                                 helper.GetSocialcastURL(ObjectType.StreamMessages,auth.DomainName,companyStreamID.ToString()),
                                 GetCredentials(auth.Username,auth.Password)));
            return streams;
        }

        public XmlDocument PostMessage(string title,string body,SocialCastAuthDetails auth)
        {
            string data = String.Format("message[title]={0}&message[body]={1}", HttpUtility.UrlEncode(title), HttpUtility.UrlEncode(body));
            XmlDocument update = new XmlDocument();
            update.LoadXml(base.MakeServiceCallsPOST(
                                helper.GetSocialcastURL(ObjectType.Messages, auth.DomainName, null),
                                GetCredentials(auth.Username, auth.Password), data));
            return update;
        }

Since any messages which manipulates data requires a POST call instead of a GET, the WebServiceHelper class needs a new method to make the service call using POST. Also the data which is to be posted is URL encoded before being sent to this method.

  protected string MakeServiceCallsPOST(string _requestURL, NetworkCredential credentials, string data)
        {
            // Create the web request
            HttpWebRequest request = WebRequest.Create(_requestURL) as HttpWebRequest;

            request.Credentials = credentials;
            request.ContentType = "application/x-www-form-urlencoded";
            request.Method = "POST";

            byte[] bytes = Encoding.UTF8.GetBytes(data);

            request.ContentLength = bytes.Length;
            using (Stream requestStream = request.GetRequestStream())
            {
                requestStream.Write(bytes, 0, bytes.Length);

                using (WebResponse response = request.GetResponse())
                {
                    using (StreamReader reader = new StreamReader(response.GetResponseStream()))
                    {
                        return reader.ReadToEnd();
                    }
                }
            }
        }

This is the client code to post the message. The socialcast auth details class is initialized by the client and sent, so its their headache to maintain passwords and other sensitive information.

    class Program
    {
        static SocialCastAuthDetails auth = new SocialCastAuthDetails()
        {
            DomainName = "demo",
            Username = "emily@socialcast.com",
            Password = "demo"
        };
        static void Main(string[] args)
        {
            int _messageCounter=1;
            APIAccessor api = new APIAccessor();
            api.PostMessage("Posting from API", "this is a test message posted through C#", auth);
            var xdoc = api.GetCompanyStream(auth);
            Console.WriteLine("Company Steam of demo.socialcast.com");
            Console.WriteLine("******************************************************");
            foreach(XmlNode node in xdoc.GetElementsByTagName("message"))
            {
                Console.WriteLine("Message {0} posted by {1}", _messageCounter++, node.SelectSingleNode("user/name").InnerText);
                Console.WriteLine("Message: {0} {1}", node.SelectSingleNode("title").InnerText, node.SelectSingleNode("body").InnerText);
                Console.WriteLine("====================================================");
            }
        }
    }

It works!!

Dec 252010
 

Socialcast is one of the better enterprise microblogging tools out there. I have been trying to use its API to understand better how people use microblogging in the enterprise. There is no better way to validate (or invalidate) set hypotheses than by actually mining data and identifying patterns in them. If sufficient data exists which is spread across a larger time period, fascinating patterns emerge. In this older post, I had correlated the length of each blog post (in my previous organization’s internal blogging platform) with the number of comments it received. After a senior colleague helped me make sense out of the data, a clear conclusion was that the shorter a blog post is, the more likely people will comment on it.

To attempt something similar with Socialcast, I finally got around to using their API through C# after procrastinating for a very long time. I didnt map the API responses/arguments to .NET objects yet, just wrote a few classes to make it easier to make different service calls without repeating code. In the below code, I used the API to return user details of some of the users. Similarly there are different calls to get groups, streams, followers etc. All the information which is gotten from the site needs a GET call, anything where information is changed (commenting, posting a message etc.) has to be done via POST.

Every socialcast site has a different subdomain (e.g. demo.socialcast.com) and a username/password to authorize requests. Since oAuth is not yet available, this information needs to be stored in the application itself. I saved it in a class for now but a better way would be to store it in a config file (and encrypt it for good measure). The SocialCastData class has all the client specific details like api urls, usernames , password etc. All these properties are protected and only the Helper class which inherits from the data class can access it. The helper class provides the API URL and credentials to the APIAccessor class.

    class SocialCastData
    {
        /// <summary>
        /// These are the private variables which are configured
        /// as per your socialcast site
        /// </summary>
        string domainName = "demo";
        string skeletonURL = "https://{0}.socialcast.com";
        string userName = "emily@socialcast.com";
        string passWord = "demo";
        string _usersURL = "/api/users.xml";

        //Protected properties to give access to the username/password and API
        //URL only to the helper class which inherits from this data classes
        protected string UserName { get { return userName; } }
        protected string Password { get { return passWord; } }
        protected string usersURL { get { return _usersURL; } }

        //Get the basic URL of the site, without any API call
        protected string GetSocialCastURL()
        {
            return String.Format(skeletonURL, domainName);
        }

        //This method uses reflection to provide the API url
        // value based on an agument to this method
        protected string GetSocialCastURL(string apiFilter)
        {
            try
            {
                PropertyInfo _allProperties = this.GetType().GetProperty(apiFilter + "URL", BindingFlags.NonPublic | BindingFlags.Instance);
                if (_allProperties == null)
                    throw new Exception("There was no corresponding API URL found");
                else
                {
                    string value = _allProperties.GetValue(this, null).ToString();
                    return GetSocialCastURL() + value;
                }
            }
            catch (Exception _eObj) { throw new Exception("There was no corresponding API URL found", _eObj); }
        }

    }

    /// <summary>
    /// This is the helper class which provides the URL
    /// and Credentials to the WebServiceHelper object. Only the Helper
    /// class has access to the SocialCastData members since all its
    /// members are protected.
    /// </summary>
    class SocialcastHelper:SocialCastData
    {

        //use the base class data to get the Credentials object.
        public NetworkCredential GetCredentials()
        {
            return new NetworkCredential(base.UserName, base.Password);
        }

        //Get the URL for the socialcast website. The overloaded methods are for
        //returning the appropriate URL depending on the function and if any additional
        //query parameters are to be appended to the URL.
        public string GetSocialcastURL()
        {
            return base.GetSocialCastURL();
        }

        public string GetSocialcastURL(string _apiURL)
        {
            return base.GetSocialCastURL(_apiURL);
        }

        public string GetSocialcastURL(string _apiURL, List<KeyValuePair<string, string>> _paramMessages)
        {
            //Get the URL from the base class method and append
            //the query params
            string _url = base.GetSocialCastURL(_apiURL);
            if (_paramMessages.Count > 0)
            {
                _url += "?";
                foreach (var item in _paramMessages)
                {
                    //appending each param key and value
                    _url += String.Format("{0}={1}&", item.Key, item.Value);
                }
                //String the last ampersand sign
                return _url.Substring(0, _url.Length - 1);
            }
            return _url;
        }
    }

The APIAccessor is the class which contains Business logic functions like GetUsers or GetMessages etc. It sends in its parameters as a List of Keyvalue pairs to the helper class which constructs the actual REST call URL out of the parameters.

 class WebServiceHelper
    {
        public string MakeServiceCalls(string _requestURL, NetworkCredential credential)
        {

            // Create the web request
            HttpWebRequest request = WebRequest.Create(_requestURL) as HttpWebRequest;
            request.Credentials = credential;
            // Get response
            using (HttpWebResponse response = request.GetResponse() as HttpWebResponse)
            {
                // Get the response stream
                StreamReader reader = new StreamReader(response.GetResponseStream());

                // Console application output
                return reader.ReadToEnd();
            }
        }
    }
    class APIAccessor:WebServiceHelper
    {
        //Creating the Helper class Instance
        SocialcastHelper helper = new SocialcastHelper();

        public XmlDocument GetUsers(string numberOfusers,string page)
        {
            XmlDocument Users = new XmlDocument();
            var serviceParams = new List<KeyValuePair<string,string>>();
            serviceParams.Add(new KeyValuePair<string,string>("per_page",numberOfusers));
            serviceParams.Add(new KeyValuePair<string,string>("page",page));

            Users.LoadXml(base.MakeServiceCalls(helper.GetSocialcastURL("users", serviceParams), helper.GetCredentials()));
            return Users;
        }
    }

The test code is below to display the name of users from the socialcast demo site.

 class Program
    {
        static void Main(string[] args)
        {
            var _xDoc = new APIAccessor().GetUsers("30", "1");
            foreach (XmlNode item in _xDoc.GetElementsByTagName("user"))
            {
                XmlNode name = item.SelectSingleNode("name");
                Console.WriteLine(name.InnerText);
            }

        }
   }

The Sample code can be downloaded here.

May 082010
 

When I looked at the first post in this series, I realized had jumped the gun a bit by going straight to generics and didn’t do enough justice to the fundamentals. So in this post, I have made an effort to go back to the basics.

The CLR (Common Language Runtime) is the heart of .NET. It’s the virtual execution system responsible for converting the platform neutral CIL (Common Intermediate Language) into platform specific and optimized code. The CLR provides services like memory management, garbage collection, exception handling and type verification. Thus it allows language designers to concentrate solely on outputting good CIL and provides a uniform API to allow language interoperability.

The only truth in .NET is the assembly code which is the final product. All the rest are virtual constraints enforced by the execution system in a very robust manner. For e.g. A memory address declared as int cannot take a string value, not because the memory is not able to take the value, but rather the CLR makes sure the values conform to the types declared – a feature called type verification. Usually this happens at the compilation level, but still rechecked at runtime.

Microsoft released the code of the CLI (Common Language Infrastructure) under the name SSCLI (Shared Source CLI). It can be downloaded here. Joel Pobar and others wrote a great book about it. Unfortunately the 2.0 version is still a draft.

Type safety is the most important aspect of .NET programming and a lot of thought went into it. A type can be thought of as a contract which the objects need to conform to. For e.g. in the following code, the Person class is a type – which is supposed to have five public variables and one method. Any object that claims itself to be a person type must necessarily fulfill this contract – or the CLR will reject it during runtime. While working with the more mature compilers like C# and VC++, these checks are already done while converting the code to CIL.

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
class Person
{
    public string _name;
    public int _ssn;
    public char _middleName;
    public decimal _phoneNumber;
    public char _bloodGroup;
 
    public Person(string name, int ssn, char middleName, decimal phoneNumber, char bloodGroup)
    {
        this._name = name;
        this._ssn = ssn;
        this._middleName = middleName;
        this._phoneNumber = phoneNumber;
        this._bloodGroup = bloodGroup;
    }
 
    public string GetSomeDetails()
    {
        return String.Empty;
    }
}
 
static void Main(string[] args)
{
    Person _p = new Person("John Doe", 4454353, 'B', 324242432, 'O');
    _p.GetSomeDetails();
}

The code for object class can be found at sscli20\clr\src\vm\object.h in the SSCLI code and the Type class at \sscli\clr\src\vm\typehandle.h. The Type class which is extensively used in Reflection for reading the type metadata is a wrapper for this TypeHandle class. Lets look at the underlying code for some familiar methods of the TypeHandle, some of which you see in Type Class. So every object that declares itself of this type, indirectly points to the data structure to define itself.

1
2
3
4
5
6
7
8
    BOOL IsEnum() const;
    BOOL IsFnPtrType() const;
    inline MethodTable* AsMethodTable() const;
    inline TypeDesc* AsTypeDesc() const;
    BOOL IsValueType() const;
    BOOL IsInterface() const;
    BOOL IsAbstract() const;
    WORD GetNumVirtuals() const;

The MethodTable that you see is the datastructure which contains the frequently used fields needed to call the methods. Along with another structure called EEClass, it defines the type identity of an object in .NET. The difference is that the MethodTable contains data that is frequently accessed by the runtime while the EEClass is a larger store of type metadata. This metadata helps querying type information and dynamically invoking methods using the Reflection API. Using the SOS dll’s DumpHeap command, the address of all the types can be gotten and used to see the EEClass and MethodTables. Lets examine the Person type in the above example.

.load SOS
extension C:\Windows\Microsoft.NET\Framework\v2.0.50727\SOS.dll loaded
 
!DumpHeap -type Person
PDB symbol for mscorwks.dll not loaded
 Address       MT     Size
020a34d4 001530f0       36
total 1 objects
Statistics:
      MT    Count    TotalSize Class Name
001530f0        1           36 DebugApp.Person
Total 1 objects
 
//Getting the address and using the DumpObj command
 
!DumpObj 020a34d4
Name: DebugApp.Person
MethodTable: 001530f0
EEClass: 001513d0
Size: 36(0x24) bytes
 (D:\Ganesh Ranganathan\Documents\Visual Studio 2005\Projects\DebugApp\DebugApp\bin\Debug\DebugApp.exe)
Fields:
      MT    Field   Offset                 Type VT     Attr    Value Name
70d00b68  4000001        4        System.String  0 instance 020a34b0 _name
70d02db4  4000002        8         System.Int32  1 instance  4454353 _ssn
70d01848  4000003        c          System.Char  1 instance       42 _middleName
70cd7f00  4000004       10       System.Decimal  1 instance 020a34e4 _phoneNumber
70d01848  4000005        e          System.Char  1 instance       4f _bloodGroup

Lets dissect this output. First the DumpObj command lists both the MethodTable and the EEClass address and the proceeds to list the fields . See how the value column lists the direct value for the int and char fields while the address is listed for the reference type string. However the bigger decimal type, which actually is a struct and hence a value type, displays the reference. Though SOS displays the reference, we can observe that the address is actually an offset from the object header, which means that it is still stored by value and not the reference. Looking at the memory window for the string and decimal fields’s address gives their original values.


Viewing the object in the memory window shows a pattern of how the runtime stores the values in memory. The object starts with a reference to the MethodTable, then the fields are lined up. It can be observed that there is a difference in how the runtime stores the values of the fields and how we defined them. For e.g. The two character fields are pushed together in spite of not being declared sequentially. This is done to save memory and the runtime is able to manage this situation because all it stores is the memory offset of the fields from the header. To avoid this behavior, types can be decorated with the [StructLayout(LayoutKind.Sequential)] attribute, often used while marshalling data out of managed code, because unmanaged code cant deal with such vagaries. You should also pin your objects, especially references while passing them to unmanaged code, because the runtime keeps moving the memory blocks around.

Now lets look at the MethodTable through SOS. As you can see, every type also inherits the methods from its parent, in this case System.Object. The MethodTable also contains a pointer to the EEClass. When it is laid out during type creation, the method points to a temporary piece of code called a thunk. The thunk in turn calls the JIT compiler and asks it to compile the method. This lazy compilation works wonders for performance and the memory footprint. Once the method is compiled the JIT updates the method to point to the compiled code instead of the thunk.

!DumpMT -MD 001230f0
EEClass: 001213d0
Module: 00122c5c
Name: DebugApp.Person
mdToken: 02000005  (D:\Ganesh Ranganathan\Documents\Visual Studio 2005\Projects\DebugApp\DebugApp\bin\Debug\DebugApp.exe)
BaseSize: 0x24
ComponentSize: 0x0
Number of IFaces in IFaceMap: 0
Slots in VTable: 6
--------------------------------------
MethodDesc Table
   Entry MethodDesc      JIT Name
70c56aa0   70ad4a34   PreJIT System.Object.ToString()
70c56ac0   70ad4a3c   PreJIT System.Object.Equals(System.Object)
70c56b30   70ad4a6c   PreJIT System.Object.GetHashCode()
70cc7550   70ad4a90   PreJIT System.Object.Finalize()
0012c030   001230c4      JIT DebugApp.Person..ctor(System.String, Int32, Char, System.Decimal, Char)
0012c038   001230d4     NONE DebugApp.Person.GetSomeDetails()

You can see the JIT column says none for the GetSomeDetails method and thats because it hasnt been called yet. After its called for the first time, the method is JIT compiled and the MethodDesc shows the code address where the compiled code can be found. Note however, that the MethodDesc is not the usual route for the runtime to execute methods, it is rather done directly. Only when the method is invoked by its name, is the MethodDesc required.

!DumpMT -MD 001230f0
EEClass: 001213d0
Module: 00122c5c
Name: DebugApp.Person
mdToken: 02000005  (D:\Ganesh Ranganathan\Documents\Visual Studio 2005\Projects\DebugApp\DebugApp\bin\Debug\DebugApp.exe)
BaseSize: 0x24
ComponentSize: 0x0
Number of IFaces in IFaceMap: 0
Slots in VTable: 6
--------------------------------------
MethodDesc Table
   Entry MethodDesc      JIT Name
70c56aa0   70ad4a34   PreJIT System.Object.ToString()
70c56ac0   70ad4a3c   PreJIT System.Object.Equals(System.Object)
70c56b30   70ad4a6c   PreJIT System.Object.GetHashCode()
70cc7550   70ad4a90   PreJIT System.Object.Finalize()
0012c030   001230c4      JIT DebugApp.Person..ctor(System.String, Int32, Char, System.Decimal, Char)
0012c038   001230d4      JIT DebugApp.Person.GetSomeDetails()
 
!DumpMD 001230d4
Method Name: DebugApp.Person.GetSomeDetails()
Class: 001213d0
MethodTable: 001230f0
mdToken: 06000007
Module: 00122c5c
IsJitted: yes
CodeAddr: 009f01c8

In this post we saw basic functioning of the CLR and how it creates and stores internal data structures to facilitate code execution at the same time abstracting away all the gory details from the developer and allowing him to solely concentrate on his applications. Below the hood everything is simply memory addresses pointing to each other and a bunch of assembly code. To give it such a high degree of structure and definition is by no means an easy task. Hats off to the developers in the .NET and Java teams!! Hope I am able to reach their skill levels one day. 🙂

Mar 122010
 

I have always believed that strong typing is the holy grail of .NET, which is not to be messed with, and it has been my primary grouse with VB.NET is that it uses sneaky workarounds to circumvent the typing rules of the CLR. C# for most of its initial existence followed static typing religiously with slight changes being seen in 3.0 with the var keyword. But in 4.0, everything changed with the introduction of the Dynamic Language Runtime (DLR).

The DLR according to wikipedia is “an ongoing effort to bring a set of services that run on top of the Common Language Runtime (CLR) and provides language services for several different dynamic languages.” As the definition says, it is independent of the CLR and adds no new OpCodes to the IL. Languages like C# used the DLR to introduce dynamic typing while maintaining the existing mechanism of statically determining types.

The dynamic keyword is the C# construct introduced for this. In short – it tells the compiler that the call to this method is to be resolved at runtime and not to be bothered by throwing compiler errors. Lets see a simple example for the usage of the dynamic keyword. Suppose you have a book class which has four main properties – Author, Publisher, Price and Number Of Pages. However, each book may have a lot of other properties as well, which you wont know at design time. So the question arises, how to store the additional information? The first answer that would come to mind is storing them in a collection class and later retrieving it. The dynamic class provides you with a neat way of doing this shown in the code below :-

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Program
    {
        static void Main(string[] args)
        {
            // The dynamic keyword bypasses any compile time checking for this object
            dynamic _daVinciCode = new Book("Sample Author", "SomePublisher", 250, 450);
 
            /*** EXTRA PROPERTIES - NOT PRESENT IN THE OBJECT***/
            _daVinciCode.BookStores = new string[] { "Landmark", "Oddyssey", "Crosswords" };
            _daVinciCode.CitiesAvailable = new string[] { "Delhi", "Bangalore", "Chennai" };
            _daVinciCode.ExtraVat = 45;
 
            /*** PRINTING OUT EXTRA PROPERTIES VALUE ***/
            Console.WriteLine(_daVinciCode.ExtraVat);
        }
 
    }
 
    /// <summary>
    /// This is our dynamic class. It defines 4 concrete properties
    /// and a dictionary class for storing any other property values
    /// as well. The abstract class DynamicObject is implemented
    /// </summary>
    public class Book:DynamicObject
    {
        //Our four defined properties
        public string Author { get; private set; }
        public string Publisher { get; private set; }
        public double Price { get; private set; }
        public int NumberOfPages { get; private set; }
 
        //Constructor - Parametrized
        public Book(string _author, string _publisher, double _price, int _numberOfPages)
        {
            this.Author = _author;
            this.Publisher = _publisher;
            this.Price = _price;
            this.NumberOfPages = _numberOfPages;
        }
 
        //This collection object stores all the extra properties
        public Dictionary<string, object> _extraProperties = new Dictionary<string, object>();
 
        //At runtime this method is called in order to bind the propertyname to a Getter
        public override bool TryGetMember(GetMemberBinder binder, out object result)
        {
            return _extraProperties.TryGetValue(binder.Name.ToLower(), out result);
        }
 
        //At runtime this method is called in order to bind the propertyname to a setter
        public override bool TrySetMember(SetMemberBinder binder, object value)
        {
            _extraProperties.Add(binder.Name.ToLower(), value);
            return true;
        }
    }

The Book class is a dynamic type and derives from the abstract class DynamicObject. This base class can help determine how binding should occur at runtime. In our example, the dictionary object stores all the additional properties of the book class. The two overriden methods TryGetMember and the TrySetMember are responsible for the binding of the new properties to the dictionary object. The first time a property on a dynamic type is encountered, the DLR binds the property and then caches its address. So any subsequent calls are faster.

More on the DLR in future posts.

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.