Nowadays it’s very common to receive JSON data from many sources and to process it in our programs. I have the same problem and, sometimes, I also have to debug the received data to see what’s coming from the server. Many times, the data is minimized and it’s very difficult to analyze what’s coming. On the other side, I have formatted JSON data and want to save space, minimizing it.

You can go to online sites (just do a search for “json formatter” in your preferred search engine) and format the JSON data, to get the formatted output.

image

But, as a developer, I wanted to create a program that does that. So I decided to create a Windows UWP program to process the JSON data.

The first step is to create a UWP program in Visual Studio:

image

In MainPage.xaml, we add the two textboxes, one for the minified JSON and the other for the processed JSON:

[sourcecode language=”xml”]
<Grid Background="{ThemeResource ApplicationPageBackgroundThemeBrush}">
<Grid.ColumnDefinitions>
<ColumnDefinition Width="*"/>
<ColumnDefinition Width="Auto"/>
<ColumnDefinition Width="*"/>
</Grid.ColumnDefinitions>
<TextBox x:Name="MiniBox" Margin="5" AcceptsReturn="True" TextWrapping="Wrap"/>
<StackPanel Grid.Column="1" VerticalAlignment="Center">
<Button Width="85" Height="40" Content="Format &gt;&gt;" Margin="5" />
<Button Width="85" Height="40" Content="&lt;&lt; Minify" Margin="5" />
</StackPanel>
<TextBox x:Name="FormBox" Margin="5" Grid.Column="2" AcceptsReturn="True" TextWrapping="Wrap"/>
</Grid>
[/sourcecode]

To process the JSON data, we use the Newtonsoft Json.NET library (http://www.newtonsoft.com/json). We can add it using NuGet. In the Solution Explorer, right click in References and select “Manage NuGet packages” and add the library Newtonsoft.Json.

Then, in MainPage.xaml, add the handler for the Click handler for the Format button:

[sourcecode language=”xml”]
<Button Width="90" Height="40" Content="Format &gt;&gt;"  Margin="5" Click="FormatJsonClick"/>
[/sourcecode]

Select the Click event handler and press F12 to create the event handler in code and type this code:

[sourcecode language=”csharp”]
private async void FormatJsonClick(object sender, RoutedEventArgs e)
{
try
{
if (!string.IsNullOrWhiteSpace(MiniBox.Text))
{
FormBox.Text = JsonConvert.SerializeObject(
JsonConvert.DeserializeObject(MiniBox.Text), Formatting.Indented);
}
}
catch (JsonReaderException ex)
{
await new MessageDialog($&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;Error parsing JSON: {ex.Message}&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;).ShowAsync();
}
}
[/sourcecode]

We are using two functions of the library to format the data: DeserializeObject, to transform the string into an object and then SerializeObject to transform the object into a string again. This time, we use the Formatting.Indented to format the result and add it to the destination box. To minify the JSON, you must use the same procedure, but use Formatting.None:

[sourcecode language=”csharp”]
private async void MinifyJsonClick(object sender, RoutedEventArgs e)
{
try
{
if (!string.IsNullOrWhiteSpace(FormBox.Text))
{
MiniBox.Text = JsonConvert.SerializeObject(
JsonConvert.DeserializeObject(FormBox.Text), Formatting.None);
}
}
catch (JsonReaderException ex)
{
await new MessageDialog($&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;Error parsing JSON: {ex.Message}&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;).ShowAsync();
}
}
[/sourcecode]

If you run the program and paste some JSON into the first box and click Format, the formatted JSON is shown in the second box.

image

If you want to reverse the process, just click on the Minify button.

Easy, no? Just one line of code and you have a Minifier/Formatter for JSON data.

If you want to take a look at the source code for the project, you can go to https://github.com/bsonnino/ProcessJson

After finishing the series of articles about data structures (see here, here, here and here) I started to think about the GetItems method I had implemented in the Linked List and in the Tree. This method was iterating on the structure and retrieving the items as IEnumerable.

That was not what I was expecting of the class. I was expecting to replicate the .NET data structures, and they implemented IEnumerable<T>, instead of using a special method for getting the items. So I decided to implement IEnumerable<T> on the data structures.

In order to implement IEnumerable<T>, we must create two methods:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()

IEnumerator IEnumerable.GetEnumerator()
[/sourcecode]

In reality, we should create only one function:  the second one calls the first one and doesn’t need to be implemented. As the linked list already had the GetItems implemented, I only had to remove its code and add it to GetEnumerator:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

That was simple, and caused no troubles. For the stack, I hadn’t implemented the GetItems method, so I needed to create the enumerator for it, but it was really simple, as it’s very similar to the one in the linked list:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

When it came to add the IEnumerable in the stack implementation as a linked list, it was also easy:

[sourcecode language='csharp'  padlinenumbers='true']
public IEnumerator<T> GetEnumerator()
{
    return _linkedList.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

But then I wrote a unit test to test this feature:

[sourcecode language='csharp' ]
[TestMethod]
public void StackAddFiveItemsIterateInReverseOrder()
{
    var stack = new StackAsList<int>();
    for (int i = 0; i < 5; i++)
    {
        stack.Push(i);
    }
    var num = 4;
    foreach (var item in stack)
    {
        Assert.AreEqual(num, item);
        num--;
    }
}
[/sourcecode]

And it failed. The data was iterated in the normal order, and not in the reversed order (last pushed should be the first in the iteration). The problem was that I was inserting the data at the end and retrieving the last item. That worked fine, but it wasn’t a real stack: the items should be piled in the beginning of the list. So, the implementation should be changed:

[sourcecode language='csharp' ]
public void Push(T obj)
{
    _linkedList.InsertAt(0, obj);
}

public T Peek()
{
    if (_linkedList.Count == 0)
        throw (new InvalidOperationException("The stack is empty"));
    return _linkedList[0];
}

public T Pop()
{
    if (_linkedList.Count == 0)
        throw (new InvalidOperationException("The stack is empty"));
    var result = _linkedList[0];
    _linkedList.RemoveAt(0);
    return result;
}
[/sourcecode]

With these changes, the test passed. The code of GetEnumerator for the queue is the same as for the stack:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

For the tree, implementing IEnumerable was also easy, as we already had the GetItems method:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (_root == null)
        yield break;
    foreach (var data in VisitNode(_root))
        yield return data;
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

That way, we have implemented IEnumerable in all data structures we’ve developed. The source code for the data structures is in https://github.com/bsonnino/DataStructures

Posts in this Series:
Linked Lists
Stacks
Queues
Trees (this post)

To conclude the data structures shown in this series, we will show the tree. The tree will store organized data – when you add an item to a tree, it will be stored in a way that it can be easily retrieved in a sorted way.

The first node added to the tree acts as a root node and it has two pointers, one to its left node and one to its right node. The tree is traversed recursively, checking the left and right nodes, until the nodes have no more children.

Its node structure is like this:

[sourcecode language=”csharp” padlinenumbers=”true”]
public class TreeNode&lt;T&gt; where T : IComparable&lt;T&gt;
{

public TreeNode()
{
Left = null;
Right = null;
}

public T Data { get; set; }
public TreeNode&lt;T&gt; Left { get; set; }
public TreeNode&lt;T&gt; Right { get; set; }
}
[/sourcecode]

The treenode’s data must implement IComparable<T>, so it can be compared with other tree elements. The tree is a sorted data structure, so we must know how one element compares to the other. Besides that, it has two pointers, one to its left child and another to its right child.

Once we have the node data structure, we can start adding operations to the tree. The first one is to insert data in the tree:

 

[sourcecode language=”csharp”]
public void Add(T data)
{
var treenode = new TreeNode&lt;T&gt;() { Data = data };
if (_root == null)
{
_root = treenode;
_count++;
return;
}
_currentNode = _root;
while (true)
{
var comparison = treenode.Data.CompareTo(_currentNode.Data);
if (comparison == 0)
throw new InvalidOperationException(&quot;Data already in the tree&quot;);
else if (comparison &lt; 0)
{
if (_currentNode.Left != null)
_currentNode = _currentNode.Left;
else
{
_currentNode.Left = treenode;
_count++;
break;
}
}
else
{
if (_currentNode.Right != null)
_currentNode = _currentNode.Right;
else
{
_currentNode.Right = treenode;
_count++;
break;
}
}
}
}
[/sourcecode]

For the insertion, we have two different cases:

  • if the root node is null, the tree is empty, so the new node becomes the root
  • If the tree is not null, we have to find the insertion point, navigating through the tree – if the inserted data is smaller than the current node’s data, we go to its left child; if it’s larger, we go to its right node. If it’s the same, the data is already inserted and we show an error. We navigate through the tree until we find a node that has no more left or right nodes (depending on the comparison) and we insert the new node in the empty node.

Removing data from the tree is more complex and all can be summed in three cases:

  • The node to be removed has no children. In this case, we set its parent’s node pointing to it to null

image

  • The node to be removed has only one child (left or right). In this case, we set its parent’s left or right node to point to the child node of the deleted node.

image

  • The node to be removed has both the left and right nodes. In this case, we must find the predecessor of this node (the first one that is smaller than it and has no children at the right) and replace the deleted node with the predecessor and update the link from the parent of the predecessor to the predecessor right child (if it exist).

image

The code for deleting a node is:

[sourcecode language=”csharp” padlinenumbers=”true”]
public bool Remove(T obj)
{
var nodeAndParent = FindParentAndNode(obj);
if (nodeAndParent == null)
return false;
var parent = nodeAndParent.Item1;
var currentNode = nodeAndParent.Item2;

if (currentNode.Left == null &amp;&amp; currentNode.Right == null)
{
if (parent == null)
_root = null;
else if (parent.Left == currentNode)
parent.Left = null;
else
parent.Right = null;
_count–;
return true;
}

if (currentNode.Left == null)
{
if (parent == null)
_root = currentNode.Right;
else if (parent.Left == currentNode)
parent.Left = currentNode.Right;
else
parent.Right = currentNode.Right;
_count–;
return true;
}

if (currentNode.Right == null)
{
if (parent == null)
_root = currentNode.Left;
else if (parent.Left == currentNode)
parent.Left = currentNode.Left;
else
parent.Right = currentNode.Left;
_count–;
return true;
}

var parentAndPredecessor = FindParentAndPredecessor(currentNode);
var predParent = parentAndPredecessor.Item1;
var pred = parentAndPredecessor.Item2;
if (predParent == currentNode)
{
if (parent.Left == currentNode)
{
parent.Left = pred;
pred.Right = currentNode.Right;
}
else
{
parent.Right = pred;
pred.Right = currentNode.Right;
}
}
else
{
predParent.Right = pred.Left;
currentNode.Data = pred.Data;
}
return false;
}

[/sourcecode]

At the beginning, we find the node to be deleted and its parent. The FindParentAndNode function traverses the tree and returns the node to be deleted and its parent as a tuple:

[sourcecode language=”csharp”]
public Tuple&lt;TreeNode&lt;T&gt;, TreeNode&lt;T&gt;&gt; FindParentAndNode(T obj)
{
TreeNode&lt;T&gt; currentNode = _root;
TreeNode&lt;T&gt; parentNode = null;
while (true)
{
int comparison = obj.CompareTo(currentNode.Data);
if (comparison &lt; 0)
{
if (currentNode.Left != null)
{
parentNode = currentNode;
currentNode = currentNode.Left;
}
else
return null;
}
else if (comparison &gt; 0)
{
if (currentNode.Right != null)
{
parentNode = currentNode;
currentNode = currentNode.Right;
}
else
return null;
}
else
return Tuple.Create(parentNode, currentNode);
}
}
[/sourcecode]

After finding the node and its parent, when then check for any of the three cases: if it’s a leaf node (no left and right children), then we remove the link from its parent to it. It it has one of the children, we set the link from its parent to its children. If it has both children, then we find its predecessor and the predecessor’s parent and replace the links from the predecessor parent to the deleted node children and replace the data from the deleted node with the predecessor’s data. The FindParentAndPredecessor function is:

[sourcecode language=”csharp”]
private Tuple&lt;TreeNode&lt;T&gt;,TreeNode&lt;T&gt;&gt; FindParentAndPredecessor(TreeNode&lt;T&gt; currentNode)
{
var parent = currentNode;
var pred = currentNode.Left;
while (pred.Right != null)
{
parent = pred;
pred = parent.Right;
}
return Tuple.Create(parent, pred);
}
[/sourcecode]

Now we have all the operational methods in place. Now we need the methods to retrieve data. The first one is the Exists method, that searches an item and returns true if it exists:

[sourcecode language=”csharp”]
public bool Exists(T obj)
{
if (_root == null)
return false;
TreeNode&lt;T&gt; currentNode = _root;
while (true)
{
int comparison = obj.CompareTo(currentNode.Data);
if (comparison &lt; 0)
{
if (currentNode.Left != null)
currentNode = currentNode.Left;
else
return false;
}
else if (comparison &gt; 0)
{
if (currentNode.Right != null)
currentNode = currentNode.Right;
else
return false;
}
else
return true;
}
}
[/sourcecode]

This method will traverse the tree comparing the nodes’ data: if the data of the searched node is greater than the current node’s data, then we go to the right branch. If it is smaller, we go to the left branch. If we reach a node with no corresponding branch, the item is not in the tree. If we find a node where the data is equal to the searched data, we return true.

The other method is GetItems, that returns the sorted items:

[sourcecode language=”csharp”]
public IEnumerable&lt;T&gt; GetItems()
{
if (_root == null)
yield break;
foreach (var data in VisitNode(_root))
yield return data;
}

private IEnumerable&lt;T&gt; VisitNode(TreeNode&lt;T&gt; node)
{
if (node.Left != null)
foreach (var data in VisitNode(node.Left))
yield return data;
yield return node.Data;
if (node.Right != null)
foreach (var data in VisitNode(node.Right))
yield return data;
}
[/sourcecode]

To get the ordered items data, we use a recursive function that does what is called “InOrder Traversal”: for each node in the tree, it traverses the left node, emits the data for the current node and then traverses the right node.

That way we have finished our journey to knowing the binary tree. This is a data structure more complex that the ones we have seen before, but it is also extensively used.

image

The source code for this series of articles is in https://github.com/bsonnino/DataStructures