Linked List Quiz - Part II !!!


In the last part, we saw the academic (not general purpose) version of a Linked List used to solve the puzzles, and solved the following puzzles on linked list.

  • Reverse the list recursively
  • Reverse the list iteratively
  • Find if a list is cyclic

In this part, I will be solving the remaining two puzzles that I listed in the last part.

Finding the cyclic node in a cyclic linked list
  1. According to my solution, the node which is actually supposed to be the end of the linked list is the cyclic node. Let us call Cn. Taking node Cn as the cyclic one has an advantage wherein you can break the cycle; assign Cn->next = nullptr;
  2. But some people take the node after Cn as the cyclic node. The node after Cn is the node somewhere back in the list. This way it is not possible to break the cycle as we would traversed past Cn.

LinkedList::Node* LinkedList::FindCyclicNode() const
{
   int iterCount = 0;

   auto jmpBy1Ptr = root;
   auto jmpBy2Ptr = root;

   while (jmpBy1Ptr != nullptr
      && jmpBy2Ptr != nullptr
      && jmpBy2Ptr->Next() != nullptr)
   {
      jmpBy1Ptr = jmpBy1Ptr->Next();
      jmpBy2Ptr = jmpBy2Ptr->Next()->Next();
      if (jmpBy1Ptr == jmpBy2Ptr)
      {
         const int noOfNodesInLoop = CountNoOfNodesInLoop(jmpBy1Ptr);
         cout << "No of nodes in loop: " << noOfNodesInLoop << std::endl;
         auto p1= root;
         auto p2 = GetNthNode(noOfNodesInLoop - 1); // zero based index
         cout << "Node at index " << noOfNodesInLoop << ": " << p2->Item() << std::endl;
         // Pointers meet at eye of the loop (this node is as per point #2 above)
         while (p1 != p2)
         {
            p1 = p1->Next();
            p2 = p2->Next();
         }
         // This piece of code takes you to the loop 
         // starting node (this node is as per #1 above)
         p2 = p2->Next();

         while(p2->Next() != p1)
         {
            p2 = p2->Next();
         }
         return p2;
      }
      ++iterCount;
   }

   return nullptr;
}

int LinkedList::CountNoOfNodesInLoop(Node* stopNode) const
{
 int count = 1;
 auto p1 = stopNode;
 auto p2 = stopNode;

 while (p1->Next() != p2)
 {
  p1 = p1->Next();
  ++count;
 }

 return count;
}

The code above is the result of several iterations of discussions with Azhagu. It wasn't written that way the first time. The first version was much complex and naive. I think it looks better now. What do you say?

Reversing every K nodes in the list: This is an interesting puzzle. You should not reverse the whole list instead only every K nodes, where N >= K > 1 and N is the number of nodes in the list. For instance, if you reverse 2 nodes (K = 2) in the following list

1 -> 2 -> 3 -> 4 -> 5 -> 6

the resulting list would be

2 -> 1 -> 4 -> 3 -> 6 -> 5

void LinkedList::Reverse(int k)
{
 prevHead = nullptr;

 auto head = root;
 root = _Reverse(head, k);
 head = head->Next();

 while (head != nullptr)
 {
  _Reverse(head, k);
  head = head->Next();
 }

 prevHead = nullptr;
}

LinkedList::Node* LinkedList::_Reverse(Node* head, int k)
{
 int iter = k;

 Node* current = head;
 Node* prev = nullptr;
 Node* next = nullptr;

 while (current != nullptr && iter >= 1)
 {
  next = current->Next();
  current->Next() = prev;

  if (next == nullptr)
  {
  break;
  }

  prev = current;
  current = next;
  --iter;
 }

 if (prevHead != nullptr)
 {
  prevHead->Next() = next != nullptr ? prev : current;
 }

 prevHead = head;
 head->Next() = next;

 return prev;
}

I hope the code covers all the corner cases of the puzzle. Give it a try and let me know if it all works for you.

Offering __FILE__ and __LINE__ for C# !!!


THIS POST USES SYNTAXHIGHLIGHTER AND HAS ISSUES RENDERING CODE ONLY IN CHROME

Not the same way but we could say better.

Visual Studio 2012, another power packed release of Visual Studio, among a lot of other powerful fancy language features, offers the ability to deduce the method caller details at compile time.

C++ offered the compiler defined macros __FILE__ and __LINE__ (and __DATE__ and __TIME__), which are primarily intended for diagnostic purposes in a program, whereby the caller information is captured and logged. For instance, using __LINE__ would be replaced with the exact line number in the file where this macro has been used. That sometimes beats the purpose and doesn't gives us what we actually expect. Let's see.

For instance, suppose you wish to write a verbose Log method with an idea to print rich diagnostic details, it would look something like this.

void LogException(const std::string& logText,
                  const std::string& fileName,
                  int lineNumber)
{
   cout << "[" << fileName.c_str() << " (" << lineNumber << ")]: " << logText.c_str() << std::endl;
}

Although it solves the purpose, it is not really developer friendly. You'll have to explicitly pass the __FILE__ and __LINE__ parameters while calling the Log method. This results in these macros being scattered all over the files. What if there was a way to avoid passing these parameters explicitly. Yeah, you could make them default parameters - const std::string& fileName = __FILE__, int lineNumber = __LINE__. However, the funny thing that happens is they are replaced with the line numbers of the parameters where they appear in the Log method declaration. Not only that, there is no macro for getting the method name. Any C++ developer would have experienced this difficulty.

C# does not offer the caller information facility directly but developers until now have been resorting to reflection. Although reflection help achieve what is required, it is not quite beautiful in the eyes of a developer. It requires a boring boiler plate code, and requires explicit use of some method call that deduces the caller information. Above all it is not something provided by the compiler itself for use during compile time, which means deducing the line number would not work, since reflection is totally a runtime thing. It also hurts performance (especially in the cases like logging).

Come Visual Studio 2012 (with C# 5.0), developers get the compile time facility to deduce caller information. This is different in two ways from what we have seen in C++. First, we are not going to use macros; we are going to use attributes. Second, we are going to do something at the place (in the method) where the caller information is required rather than at the place of method invocation as in C++. Let us see in action.

using System.Runtime.CompilerServices;

void Log(string logText,
        [CallerFileName] string fileName = "",
        [CallerMemberName] string methodName = "",
        [CallerLineName] int lineNumber = 0)
{
   string fmtLogText = string.Format("[{0} ({1})] {2}: {3}",
          fileName,
          lineNumber,
          methodName,
          logText);

   Trace.WriteLine(fmtLogText);
}

If you see, there are CallerXXXName attributes that the parameters have been decorated with, and they are made optional arguments. The compiler sees these attributes, and identifies that the method expects the caller information and takes the responsibility of silently passing them itself. Since the parameters are made optional, you don't have to explicitly mention the caller information in any way. The call sites thus are not littered with the caller information. It is transparent and clean. So you would just say Log("some log message") and the Log method gets the information of the calling method. As you see, the C# folks cleverly inverted the model used in C++. Besides, if you see that the caller method name attribute is named CallerMemberName. It is for a reason. Let us see it in the light of its application.

It is common that the caller information is employed for logging in most applications. But there is one other application of the caller information that I love, and solves the problem in an elegant way. It is in WPF for property changed event. Until before caller information attributes, this too was patched using reflection.

public class SomeModel : INotifyPropertyChanged
{
   // SomeModel ctor and other members

   public event PropertyChangedEventHandler PropertyChanged;

   public string SomeProperty
   {
      get
      {
         return this.someProperty;
      }
      set
      {
         this.someProperty = value;
         NotifyPropertyChanged();
      }
   }

   private void NotifyPropertyChanged([CallerMemberName] String propertyWhichChanged  = "")
   {
      if (PropertyChanged != null)
      {
         PropertyChanged(this, new PropertyChangedEventArgs(propertyWhichChanged));
      }
   }
}

Caller could be a method, property or event. Hence the attribute has been named CallerMemberName. The compiler silently passes the property (caller) name at the place of invocation. The story does not end there. Although this feature has been introduced in C# 5.0/.NET 4.5, it supports multi-targeting too. That means when you use the C# 5.0 compiler for compiling against the older versions of the .NET framework, you can still make it work by defining the caller info attributes in the right namespace (System.Runtime.CompilerServices). The compiler expects the presence of the attributes and picks it up for processing by passing the caller information to the concerned method. Developers, happy?

There are other powerful features in C# 5.0 like async-await. However, the caller information attributes, despite being a miniature, holds its share.

Linked List Quiz - Part I

A short while back, Azhagu quizzed me on linked list based problems; singly linked list.

I am recording those problems, solutions and my experience as a two part series. In the first part, I am introducing the linked list class, which I wrote for packaging the implementation of the solutions. This class pertains to the context of the problem(s) and cannot be used as a general purpose linked list. A std::list might more pertinent in the context of the general purpose implementation of a list.

Here are some of the problems that Azhagu asked me to solve:-
  1. Reverse the list recursively
  2. Reverse the list iteratively
  3. Find if the list is cyclic
  4. Find the node that causes the cycle (and break the cycle)
  5. Reverse every K nodes in the list
I will be solving reversing the list (both iteratively and recursively) and finding if the list is cyclic problems in this episode.

#pragma once

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class LinkedList
{
public: class Node
        {
        private: T item;
        private: Node* next;

        public: Node(const T& item)
                {
                     this->item = item;
                     this->next = nullptr;
                }

        public: Node(const T& item, Node* next)
                {
                     this->item = item;
                     this->next = next;
                }

        public: T& Item()
                {
                     return this->item;
                }

        public: const T& Item() const
                {
                     return this->item;
                }

        public: LinkedList<T>::Node*& Next()
                {
                     return this->next;
                }
        };

private: LinkedList<T>::Node* root;
private: LinkedList<T>::Node* end;

public: LinkedList()
        {
           root = end = nullptr;
        }

public: ~LinkedList()
        {
            // If a cycle exists, break it; else the delete loop
            // below will never end, and lead to undefined behavior/crash.
            if (IsCyclic())
            {
               auto cyclicNode = FindCyclicNode();
               cyclicNode->Next() = nullptr;
            }

            // Delete all nodes
            auto current = root;
            while (current != nullptr)
            {
               auto temp = current->Next();
               delete current;
               current = temp;
            }
        }

public: Node* operator[](int index) const
        {
            return GetNthNode(index);
        }

public: LinkedList<T>::Node* GetNthNode(int index) const // index is zero-based.
        {
            auto node = root;
            while (index >= 0 && node != nullptr)
            {
               node = node->Next();
               --index;
            }

            return node;
        }

public: Node* Append(T item)
        {
           Node* node = new Node(item);
           if (root == nullptr)
           {
              root = end = node;
           }
           else
           {
              end->Next() = node;
              end = node;
           }

           return node;
        }

public: LinkedList<T>::Node* Root() const
        {
           return this->root;
        }

public: void Print(std::ostream& ostr = std::cout,
           const std::string& separator = " -> ",
           const std::string& terminator = "\r\n")
        {
           Node* currentNode = root;

           while (currentNode != nullptr)
           {
              const bool lastNode = currentNode->Next() == nullptr;
              const std::string linkText = (lastNode ? "" : separator);
              ostr << currentNode->Item() << linkText.c_str();

              currentNode = currentNode->Next();
           }

           ostr << terminator.c_str();
        }

public: void ReverseIteratively();
public: void ReverseRecusively();
public: bool IsCyclic() const;

private: Node* UnitReverse(Node* current, Node* next);
}

The above list class allows creating cycles in the list (see Node::Next() method). The Node::Next method returns a reference to the next item pointer in the list, which allows pointing it to a previous Node in the list. The linked list class will be improved based on the problem being solved.

Since reversing the list recursively came to me naturally, I'll go with it first. It was natural since the unit work of reversal involving current and next pointers is repeated until there are no more nodes in the list.

void LinkedList::ReverseRecursively()
{
   root = UnitReverse(root, nullptr);
}

Node* LinkedList::UnitReverse(Node* current, Node* next)
{
   if (current == nullptr)
   {
      return nullptr;
   }

   if (next == nullptr)
   {
      // First time call.
      next = current->Next();
      current->Next() = nullptr;
      end = current;
   }

   Node* nextNext = next->Next();
   next->Next() = current;

   if (nextNext == nullptr)
   {
      // Reached end of list!
      return next;
   }

   return UnitReverse(next, nextNext);
}

Iterative version of reversal. Cute, eh!

void LinkedList::ReverseIteratively()
{
   Node* current = this->root;
   Node* prev = nullptr;
   Node* next = nullptr;

   while (current != nullptr)
   {
     next = current->Next();
     current->Next() = prev;

     if (next == nullptr)
     {
        break;
     }

     prev = current;
     current = next;
   }

   this->end = this->root;
   this->root = current;   
}

A cycle in a list is where the next pointer of the current node points to one of the previous nodes in the list; like the one below.

1 -> 2 -> 3 -> 4 -> 5 ->
             ^-----------------|

Above, the list doesn't end at 5, instead cycles back to 3. And as everybody knows, a traversal of the nodes in the list would never end. If one was using a traditional list implementation, it would not have allowed creating cycle(s) deliberately. However, the data from which the list is created may bear cycles or back references, in which case the data is assumed to corrupt. For instance, an employee reporting to manager, and the manager reporting back to the employee. But our list implementation above, for the purposes of illustration of the problem at hand, allows creating cycles. And we will see a solution later to resolve them too.

Finding if there is a cycle in the list was tough for me. I sort of need a hammer and some hints from Azhagu. But implementing it was fun, as always!

bool IsCyclic() const
{   
   auto jmpBy1Ptr = root;
   auto jmpBy2Ptr = root;

   while (jmpBy1Ptr != nullptr
      && jmpBy2Ptr != nullptr
      && jmpBy2Ptr->Next() != nullptr)
   {
      jmpBy1Ptr = jmpBy1Ptr->Next();
      jmpBy2Ptr = jmpBy2Ptr->Next()->Next();

      if (jmpBy1Ptr == jmpBy2Ptr)
      {
         cout << "Stop node is " << jmpBy1Ptr->Item() << std::endl;
         return true;
      }
   }

   return false;
}

Here is some code to test the above methods:-

void main()
{
   LinkedList<int> ll;
   LinkedList<int>::Node* lastNode = nullptr;

   for (int i = 1; i <= 10; ++i)
   {
      lastNode = ll.Append(i);
   }

   cout << "Initial Sequence...." << std::endl;
   ll.Print();

   cout << "Reverse (iteratively)..." << std::endl;
   ll.ReverseIteratively();
   ll.Print();

   cout << "Reverse (recursively).....Back to original sequence!" << std::endl;
   ll.ReverseRecursively();
   ll.Print();

   // This should return false, as the list has no cycles yet.
   cout << "IsCyclic: " << ll.IsCyclic() << std::endl;

   // Get the 4th node from root (element 4)
   auto node = ll.Root()->Next()->Next()->Next();
   
   // Point the last node to the 4th node (a previous node in the list).
   // This creates a cycle or loop.
   lastNode->Next() = node;

   // This should return true now!
   cout << "IsCyclic: " << ll.IsCyclic() << std::endl;
}

We'll see the rest of the problems in the next episode. Let me know your comments on the solution, implementation, and bugs if any!

Sms FireWall Update !!!

I gave SMS FireWall a refresh with a couple of features requested by users:-
  • An option 'Allow and Move' in the settings screen, which when checked moves the messages from the quarantine vault when opted to be added to the allowed list. Although it might be clear to you, let me explain it in a few words how it works. When you long press a sender in the quarantine vault, a menu with two options appear - Allow, Delete. When 'Allow' is clicked, the sender is added to the allowed list. And when the 'Allow and Move' setting is checked, the messages from this sender are moved to the inbox.
  • A confirmation dialog prompt when attempted to empty the quarantine vault
  • A few minor (internal) improvements
Hope they are useful to others too. And let me know if you need any other features to be in the application.

OrderedThreadPool - Bug Fix !!!

Hugh pointed out a bug in the OrderedThreadPool.

I think there is a small window for error in the OrderedThreadPool class. Bascially, if an item of work is queued, then a worker thread runs, takes the item off the queue and is about to call wcb(state) - but at that instant is (say) context switched. Then another item gets queued and another worker thread runs and dequeues the item and then again is about to call wcb(state). There is scope here for the two operations to run concurrently or even out of order...

Here is the fixed version of the same.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace System.Threading
{
 public class OrderedThreadPool
 {
  private Queue workItemQ = new Queue();
  private bool loopWorkRunning = false;

  public void QueueUserWorkItem(WaitCallback wcbDelegate, object state)
  {
   lock (workItemQ)
   {
    workItemQ.Enqueue(new ThreadPoolTaskInfo(wcbDelegate, state));

    if (workItemQ.Count == 1 && !loopWorkRunning)
    {
     loopWorkRunning = true;
     ThreadPool.QueueUserWorkItem(LoopWork);
    }
   }
  }

  private void LoopWork(object notUsed)
  {
   WaitCallback wcb = null;
   object state = null;

   lock (workItemQ)
   {
    if (workItemQ.Count == 0)
    {
     loopWorkRunning = false;
     return;
    }

    ThreadPoolTaskInfo tptInfo = workItemQ.Dequeue();
    state = tptInfo.State;
    wcb = tptInfo.CallbackDelegate;
    Debug.Assert(wcb != null);
   }

   try
   {
    wcb(state);
   }
   finally
   {
    ThreadPool.QueueUserWorkItem(LoopWork, notUsed);
   }
  }

  public struct ThreadPoolTaskInfo
  {
   public readonly WaitCallback CallbackDelegate;
   public readonly object State;

   public ThreadPoolTaskInfo(WaitCallback wc, object state)
   {
    Debug.Assert(wc != null);
    CallbackDelegate = wc;
    State = state;
   }
  }
 }
}

Unique Id Generation !!!

A short while I was engaged in a little project where I had to interact with a third party service provider who required a (30 length) unique id as part of the transaction. I am little dumb and am used to GUIDs for a long time when it comes to unique ids. But GUIDs are more than 30 in length. I was trying out some stupid ways like stripping out the trail part of the GUID to make 30 length unique but my intuition wasn't convinced about the tricks I was working out.

Finally, Sriram helped me with it. I am sharing his code for the benefit of others.

string GenerateUniqueId(int length)
{
   string asciiChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
   char[] chars = asciiChars.ToCharArray();
   byte[] randombytes = new byte[length];

   RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider();
   crypto.GetNonZeroBytes(randombytes);
   StringBuilder result = new StringBuilder(length);

   foreach (byte b in randombytes)
   {
      result.Append(chars[b % asciiChars.Length]);
   }

   return result.ToString();
}

Thanks Sriram.