Most of the time, our design is fixed and we don’t have to change it while it’s executing, but sometimes this is not true: we need to load the files dynamically, due to a lot of factors:

  • We have the same business rules for the project but every client needs a different UI
  • The design can be different, depending on some conditions
  • We are not sure of the design and want to make changes at runtime and see how they work

When this happens, WPF is a huge help, as it can load its design dynamically and load the XAML files at runtime.

Preparing the application

When we want to load the XAML dynamically, we must ensure that all business rules are separated from the UI – we are only loading a new UI, the business rules remain the same. A good fit for that is the MVVM pattern. With it, the business rules are completely separated from the UI and you can use Data Binding to bind the data to the UI. So, when you are designing a dynamic application you should use the MVVM pattern.

One other preparation is to know how will your application be designed: will it run on a single window, changing the content, or will it have multiple windows? If it runs on a single window, you should create a shell with a content control and load all dynamic files in that control. If the application will have multiple windows, you should create a new window every time there is new content.

Once you have the application ready, with the business rules separated from the UI and the kind of UI defined, you can load your XAML dynamically.

Loading the XAML Dynamically

WPF has a simple way to load XAML dynamically. It has a class, XamlReader that has methods to load XAML dynamically and instantiate a new control. It can be used like this:

var mainContent = XamlReader.Parse(@"<Button Width=""85"" Height=""35"" Content=""Test""
    xmlns=""http://schemas.microsoft.com/winfx/2006/xaml/presentation""
    xmlns:x = ""http://schemas.microsoft.com/winfx/2006/xaml"" />") as Button;
MainGrid.Children.Add(mainContent);

In this example, we are using the Parse method to a XAML component from a string. We could load a XAML file dynamically using the Load method:

using (FileStream fs = new FileStream("Button.xaml", FileMode.Open))
{
  mainContent = XamlReader.Load(fs) as Button;
  MainGrid.Children.Add(mainContent);
}

Note that both Load and Parse return an object and that must be typecasted to the real type of the control.

Creating a real world dynamic application

In a real world application, we can have different uses to this feature:

  • Use the same data with different layouts – in this case, we have a single viewmodel and the views connect to the same data, with different layouts
  • Use different formatting options to the same view. This is used when you want to customize the view presentation (color, layout) for different clients

For the first usage, you must create completely different views for the same data and use the MVVM pattern to connect to the data.

For the second usage, you can use the same views, but connect to different Resource Dictionaries, so the new styles can be implemented. In this post, we will implement different views for the same viewmodel.

The project I’ll be using will use a Customers list, loaded from an XML file. The app uses the MVVM pattern (I’ve chosen not to use any MVVM framework, but a simple homemade MVVM framework, with a base ViewModelBase class and a RelayCommand class, to build the infrastructure).

The Customer’s list is loaded in the CustomersViewModel, which has many properties (and commands) to interact with the views:

public class CustomersViewModel : ViewModelBase
{
    readonly CustomerRepository customerRepository = new CustomerRepository();
    private readonly ObservableCollection<CustomerViewModel> customers;

    public CustomersViewModel()
    {
        var customerViewModels = customerRepository.Customers.Select(c => new CustomerViewModel(c));
        customers = new ObservableCollection<CustomerViewModel>(customerViewModels);
        customerView = (CollectionView)CollectionViewSource.GetDefaultView(customers);
    }

    private CustomerViewModel selectedCustomer;
    public CustomerViewModel SelectedCustomer
    {
        get { return selectedCustomer; }
        set
        {
            selectedCustomer = value;
            RaisePropertyChanged("SelectedCustomer");
        }
    }

    private ICommand goFirstCommand;
    public ICommand GoFirstCommand => goFirstCommand ?? (goFirstCommand = new RelayCommand(GoFirst));

    private void GoFirst(object obj)
    {
        customerView.MoveCurrentToFirst();
        SelectedCustomer = (CustomerViewModel)customerView.CurrentItem;
    }

    private ICommand goPrevCommand;
    public ICommand GoPrevCommand => goPrevCommand ?? (goPrevCommand = new RelayCommand(GoPrev));

    private void GoPrev(object obj)
    {
        customerView.MoveCurrentToPrevious();
        SelectedCustomer = (CustomerViewModel)customerView.CurrentItem;
    }

    private ICommand goNextCommand;
    public ICommand GoNextCommand => goNextCommand ?? (goNextCommand = new RelayCommand(GoNext));

    private void GoNext(object obj)
    {
        customerView.MoveCurrentToNext();
        SelectedCustomer = (CustomerViewModel)customerView.CurrentItem;
    }

    private ICommand goLastCommand;
    public ICommand GoLastCommand => goLastCommand ?? (goLastCommand = new RelayCommand(GoLast));

    private void GoLast(object obj)
    {
        customerView.MoveCurrentToLast();
        SelectedCustomer = (CustomerViewModel)customerView.CurrentItem;
    }
    private string searchText;
    public string SearchText
    {
        get { return searchText; }
        set
        {
            searchText = value;
            RaisePropertyChanged("SearchText");
        }
    }

    public ObservableCollection<CustomerViewModel> Customers
    {
        get { return customers; }
    }

    private ICommand addCommand;
    public ICommand AddCommand
    {
        get { return addCommand ?? (addCommand = new RelayCommand(AddCustomer, null)); }
    }

    private void AddCustomer(object obj)
    {
        var customer = new Customer();
        var customerViewModel = new CustomerViewModel(customer);
        customers.Add(customerViewModel);
        customerRepository.Add(customer);
        SelectedCustomer = customerViewModel;
    }

    private ICommand removeCommand;
    public ICommand RemoveCommand
    {
        get {
            return removeCommand ??
                   (removeCommand = new RelayCommand(RemoveCustomer, c => SelectedCustomer != null));
        }
    }

    private void RemoveCustomer(object obj)
    {
        customerRepository.Remove(SelectedCustomer.Customer);
        customers.Remove(SelectedCustomer);
        SelectedCustomer = null;
    }

    private ICommand saveCommand;
    public ICommand SaveCommand
    {
        get { return saveCommand ?? (saveCommand = new RelayCommand(SaveData, null)); }
    }

    private void SaveData(object obj)
    {
        customerRepository.Commit();
    }

    private ICommand searchCommand;
    private ICollectionView customerView;

    public ICommand SearchCommand
    {
        get
        {
            if (searchCommand == null)
                searchCommand = new RelayCommand(SearchData, null);
            return searchCommand;
        }
    }

    private void SearchData(object obj)
    {
        customerView.Filter = !string.IsNullOrWhiteSpace(SearchText) ?
            c => ((CustomerViewModel)c).Country.ToLower()
                           .Contains(SearchText.ToLower()) :
            (Predicate<object>)null;
    }
}

The main property is Customer, that has the list of CustomerViewModels that will be shown in the master views and SelectedCustomer, that has the selected customer that will be edited in the details views. There are a lot of commands to filter the list, move the selected record, add, remove and save the data.

The CustomerViewModel class is:

public class CustomerViewModel : ViewModelBase
{
    public Customer Customer { get; private set; }


    public CustomerViewModel(Customer cust)
    {
        Customer = cust;
    }


    public string CustomerId
    {
        get { return Customer.CustomerId; }
        set
        {
            Customer.CustomerId = value;
            RaisePropertyChanged("CustomerId");
        }
    }

    public string CompanyName
    {
        get { return Customer.CompanyName; }
        set
        {
            Customer.CompanyName = value;
            RaisePropertyChanged("CompanyName");
        }
    }

    public string ContactName
    {
        get { return Customer.ContactName; }
        set
        {
            Customer.ContactName = value;
            RaisePropertyChanged("ContactName");
        }
    }

    public string ContactTitle
    {
        get { return Customer.ContactTitle; }
        set
        {
            Customer.ContactTitle = value;
            RaisePropertyChanged("ContactTitle");
        }
    }

    public string Region
    {
        get { return Customer.Region; }
        set
        {
            Customer.Region = value;
            RaisePropertyChanged("Region");
        }
    }

    public string Address
    {
        get { return Customer.Address; }
        set
        {
            Customer.Address = value;
            RaisePropertyChanged("Address");
        }
    }

    public string City
    {
        get { return Customer.City; }
        set
        {
            Customer.City = value;
            RaisePropertyChanged("City");
        }
    }

    public string Country
    {
        get { return Customer.Country; }
        set
        {
            Customer.Country = value;
            RaisePropertyChanged("Country");
        }
    }

    public string PostalCode
    {
        get { return Customer.PostalCode; }
        set
        {
            Customer.PostalCode = value;
            RaisePropertyChanged("PostalCode");
        }
    }

    public string Phone
    {
        get { return Customer.Phone; }
        set
        {
            Customer.Phone = value;
            RaisePropertyChanged("Phone");
        }
    }

    public string Fax
    {
        get { return Customer.Fax; }
        set
        {
            Customer.Fax = value;
            RaisePropertyChanged("Fax");
        }
    } 
}

It doesn’t do anything but expose the Customer’s properties. With this infrastructure in place, I can create my view loading. I did this in the code behind, the code is very simple, it just sets the data context for the window and loads the correct file, depending on the selection of a combobox:

public MainWindow()
{
    InitializeComponent();
    DataContext = new CustomersViewModel();
}

private void SelectedViewChanged(object sender, SelectionChangedEventArgs e)
{
    var viewIndex = (sender as ComboBox).SelectedIndex;
    FrameworkElement view = null;
    switch (viewIndex)
    {
        case 0:
            view = LoadView("masterdetail.xaml");
            break;
        case 1:
            view = LoadView("detail.xaml");
            break;
        case 2:
            view = LoadView("master.xaml");
            break;
    }
    MainContent.Content = view;
}

private FrameworkElement LoadView(string fileName)
{
    using (FileStream fs = new FileStream(fileName, FileMode.Open))
    {
        return XamlReader.Load(fs) as FrameworkElement;
    }
}

The XAML for the main window is:

<Grid>
    <Grid.RowDefinitions>
        <RowDefinition Height="40"/>
        <RowDefinition Height="*"/>
    </Grid.RowDefinitions>
    <ComboBox Height="30" Width="200" SelectionChanged="SelectedViewChanged" HorizontalAlignment="Left" Margin="5">
        <ComboBoxItem>Master/Detail</ComboBoxItem>
        <ComboBoxItem>Detail</ComboBoxItem>
        <ComboBoxItem>Master</ComboBoxItem>
    </ComboBox>
    <ContentControl Grid.Row="1" x:Name="MainContent"/>
</Grid>

As you can see, the main window is very simple, it just has the combobox to select the view and a ContentControl, where the new view is loaded. An example of the dynamic view is the Master/Detail view:

<UserControl xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
             xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
             mc:Ignorable="d"
             d:DesignHeight="600" d:DesignWidth="800">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="40" />
            <RowDefinition Height="*" />
            <RowDefinition Height="2*" />
            <RowDefinition Height="50" />
        </Grid.RowDefinitions>
        <StackPanel Orientation="Horizontal">
            <TextBlock Text="Country" VerticalAlignment="Center" Margin="5"/>
            <TextBox Height="25"
                     VerticalAlignment="Center" Margin="5,3" Width="250" Text="{Binding SearchText, Mode=TwoWay}"  />
            <Button Content="Search" Width="75" Height="25" Margin="10,5" VerticalAlignment="Center" 
                    Command="{Binding SearchCommand}" />
        </StackPanel>
        <DataGrid AutoGenerateColumns="False" x:Name="master" CanUserAddRows="False" CanUserDeleteRows="True" Grid.Row="1"
                  ItemsSource="{Binding Customers}" SelectedItem="{Binding SelectedCustomer, Mode=TwoWay}" >
            <DataGrid.Columns>
                <DataGridTextColumn x:Name="customerIDColumn" Binding="{Binding Path=CustomerId}" Header="Customer ID" Width="80" />
                <DataGridTextColumn x:Name="companyNameColumn" Binding="{Binding Path=CompanyName,ValidatesOnDataErrors=True}" Header="Company Name" Width="300" />
                <DataGridTextColumn x:Name="cityColumn" Binding="{Binding Path=City}" Header="City" Width="100" />
                <DataGridTextColumn x:Name="countryColumn" Binding="{Binding Path=Country}" Header="Country" Width="100" />
            </DataGrid.Columns>
        </DataGrid>
        <Grid DataContext="{Binding SelectedCustomer}" Grid.Row="2">
            <Grid Name="grid1" >
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="Auto" />
                    <ColumnDefinition Width="*" />
                </Grid.ColumnDefinitions>
                <Grid.RowDefinitions>
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                    <RowDefinition Height="Auto" />
                </Grid.RowDefinitions>
                <Label Content="Customer Id:" Grid.Column="0" Grid.Row="0"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="0"   Margin="3" Name="customerIdTextBox" Text="{Binding Path=CustomerId, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Company Name:" Grid.Column="0" Grid.Row="1"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="1"   Margin="3" Name="companyNameTextBox" Text="{Binding Path=CompanyName, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Contact Name:" Grid.Column="0" Grid.Row="2"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="2"   Margin="3" Name="contactNameTextBox" Text="{Binding Path=ContactName, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Contact Title:" Grid.Column="0" Grid.Row="3"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="3"   Margin="3" Name="contactTitleTextBox" Text="{Binding Path=ContactTitle, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Address:" Grid.Column="0" Grid.Row="4" HorizontalAlignment="Left" Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="4" Margin="3" Name="addressTextBox" Text="{Binding Path=Address, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center" />
                <Label Content="City:" Grid.Column="0" Grid.Row="5"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="5"   Margin="3" Name="cityTextBox" Text="{Binding Path=City, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Postal Code:" Grid.Column="0" Grid.Row="6"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="6"   Margin="3" Name="postalCodeTextBox" Text="{Binding Path=PostalCode, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Region:" Grid.Column="0" Grid.Row="7"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="7"   Margin="3" Name="regionTextBox" Text="{Binding Path=Region, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Country:" Grid.Column="0" Grid.Row="8"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="8"   Margin="3" Name="countryTextBox" Text="{Binding Path=Country, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Phone:" Grid.Column="0" Grid.Row="9"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="9"   Margin="3" Name="phoneTextBox" Text="{Binding Path=Phone, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
                <Label Content="Fax:" Grid.Column="0" Grid.Row="10"  Margin="3" VerticalAlignment="Center" />
                <TextBox Grid.Column="1" Grid.Row="10"   Margin="3" Name="faxTextBox" Text="{Binding Path=Fax, Mode=TwoWay, ValidatesOnExceptions=true, NotifyOnValidationError=true}" VerticalAlignment="Center"  />
            </Grid>
        </Grid>
        <StackPanel Orientation="Horizontal" HorizontalAlignment="Right" Margin="5" Grid.Row="3">
            <Button Width="75" Height="25" Margin="5" Content="Add" Command="{Binding AddCommand}"/>
            <Button Width="75" Height="25" Margin="5" Content="Remove" Command="{Binding RemoveCommand}"/>
            <Button Width="75" Height="25" Margin="5" Content="Save" Command="{Binding SaveCommand}" />
        </StackPanel>
    </Grid>
</UserControl>

There are some things to note, here:

  • There is no x:Class attribute in the UserControl
  • There is no code behind at all for the XAML. As this is a loose file, there should not be any cs file tied to it (and that’s a reason for not having the x:Class attribute)
  • I added the XAML files to the project, setting the Build Action to None and the Copy to Output Directory to Copy If Newer. This is an optional step, the files don’t need to be added to the project, they only need to be available on the executable directory at runtime

With this setting, you can run the application and get something like in the figure below:

clip_image002

You can see that everything works, both the data bindings and the commands. These files can be changed at will and they will be linked to the CustomersViewModel.

Conclusions

This kind of structure is very flexible and easy to use. Some uses I envision for it is to create different views for the same data, use layout customization for different clients, allow designers to be really free regarding to the design of the app, or create globalized apps (you can have different directories for each language, and each directory can have a translated view).

The next article will show subtler changes, when you only want to change the style of the controls.

The full code for the article is in https://github.com/bsonnino/DynamicXamlViews

After some time, I needed to analyze the disk space of my C: drive and used the program I have developed in my previous post and I got an “UnauthorizedAccessException”. After some thinking, I realized that was happening because of some paths that I have not access unless I am an admin.

Running as admin is not a good thing to do and, so, I thought of other ways to get the disk space. Soon, I realized that using GetFiles for all directories, although it was the easiest way to get the information, wasn’t the way to do it: at some point, there would be some path with no access and that exception would be thrown.

If I was using Powershell, I could use the -ErrorAction “SilentlyContinue” to continue without an error message, but there is no such thing in the GetFiles method (here is a suggestion for the .NET Framework designers Smile).

So, I had to enumerate all files, directory by directory and process any exception thrown. I came up to a recursive function like this one:

[sourcecode language=”csharp” padlinenumbers=”true”]
private List<FileInfo> GetFilesInDirectory(string directory)
{
    var files = new List<FileInfo>();
    try
    {
        var directories = Directory.GetDirectories(directory);
        try
        {
            var di = new DirectoryInfo(directory);
            files.AddRange(di.GetFiles("*"));
        }
        catch
        {
        }
        foreach (var dir in directories)
        {
            files.AddRange(GetFilesInDirectory(Path.Combine(directory, dir)));
        }
    }
    catch
    {
    }
   
    return files;
}
[/sourcecode]

Initially, I get all directories in the selected path, then I get all files for that directory and process the subdirectories recursively. All exceptions are caught and swallowed, so the processing doesn’t stop if I don’t have access to the folder. As I made this change, I made another one: the previous code was blocking the program while I was enumerating the files, so I used a Task to enumerate the files in the background:

[sourcecode language=”csharp”]
List<FileInfo> files = null;
await Task.Factory.StartNew( () =>
  files = GetFilesInDirectory(selectedPath)
    .Where(f => f.Length >= minSize)
    .OrderByDescending(f => f.Length)
    .ToList());
[/sourcecode]

That way, the enumeration doesn’t block the UI and the program remains responsible all times.

With these changes, everything was working fine and I had a program that could analyze my disk space, even if I had no access to all folder in the disk.

The full source code for the project is in https://github.com/bsonnino/DiskAnalysis

Some time ago, I’ve written an article about analyzing disk space using Excel and Powershell. While these tools are very easy to use and very flexible, that requires some organization: you must run a Powershell script, open the resulting file in Excel and run the analysis. To do that, I prefer to run a single command and have the data on my hands with no extra operations. So, I decided to create a WPF program to get the disk data and show it.

Getting Disk Information

The way to get disk information on .NET is to use the method GetFiles of the DirectoryInfo class, like this:

[sourcecode language=”csharp” padlinenumbers=”true”]
var di = new DirectoryInfo(selectedPath);
var files = di.GetFiles("*",SearchOption.AllDirectories);
[/sourcecode]

Then, we can add the files to a DataGrid and show them, but I’d like to get only the largest files and just some data. The best option for that is to use Linq. So, I decided to use Linq to get the same info and show it on the window.

The first step is to get the initial folder and start the enumeration. WPF doesn’t have a native folder selection , but that can be solved with the brave open source developers out there. I installed WPFFolderBrowser (http://wpffolderbrowser.codeplex.com/) using the Nuget Package Manager (just right click on the References node in the solution explorer and select Manage NuGet packages and type WPFFolderBrowser on the search box).

Then, I added the basic UI for the window. I used a TabControl with three tabs and a button at the top to select the folder and start the search:

[sourcecode language=”text” padlinenumbers=”true”]
<Grid>
    <Grid.RowDefinitions>
        <RowDefinition Height="40"/>
        <RowDefinition Height="*"/>
    </Grid.RowDefinitions>
    <StackPanel Orientation="Horizontal" HorizontalAlignment="Left" Margin="5">
        <TextBlock Text="Minimum size:" VerticalAlignment="Center" Margin="0,0,5,0"/>
        <TextBox Width="150" x:Name="MinSizeBox" Text="1048576" VerticalContentAlignment="Center"/>
    </StackPanel>
    <Button Width="85" Height="30" Content="Start" Click="StartClick"/>
    <TabControl Grid.Row="1">
        <TabItem Header="File Data">
            <Grid>
                <Grid.RowDefinitions>
                    <RowDefinition Height="*"/>
                    <RowDefinition Height="30"/>
                </Grid.RowDefinitions>
                <ListBox x:Name="FilesList">

                </ListBox>
                <StackPanel Grid.Row="1" Orientation="Horizontal">
                    <TextBlock x:Name="TotalFilesText" Margin="5,0" VerticalAlignment="Center"/>
                    <TextBlock x:Name="LengthFilesText" Margin="5,0" VerticalAlignment="Center"/>
                </StackPanel>
            </Grid>
        </TabItem>
        <TabItem Header="Extensions">
            <Grid>
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="*"/>
                    <ColumnDefinition Width="*"/>
                </Grid.ColumnDefinitions>
                <ListBox x:Name="ExtList">

                </ListBox>
            </Grid>
        </TabItem>
        <TabItem Header="ABC Curve">
            <Grid>
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="*"/>
                    <ColumnDefinition Width="*"/>
                </Grid.ColumnDefinitions>
                <ListBox x:Name="AbcList">

                </ListBox>
            </Grid>
        </TabItem>
    </TabControl>
</Grid>
[/sourcecode]

image

The code for the start button is:

[sourcecode language=”csharp”]
private void StartClick(object sender, RoutedEventArgs e)
{
    var fbd = new WPFFolderBrowserDialog();
    if (fbd.ShowDialog() != true)
        return;
    var selectedPath = fbd.FileName;
    var di = new DirectoryInfo(selectedPath);
    Int64 minSize;
    if (!Int64.TryParse(MinSizeBox.Text, out minSize))
        return;
    var files = di.GetFiles("*", SearchOption.AllDirectories)
        .Where(f => f.Length >= minSize)
        .Select(f => new {f.Name, f.Length, f.DirectoryName, f.FullName, f.Extension})
        .OrderByDescending(f => f.Length)
        .ToList();
    TotalFilesText.Text = $"# Files: {files.Count}";
    LengthFilesText.Text = $"({totalSize:N0} bytes)";
    FilesList.ItemsSource = files;
}
[/sourcecode]

This code shows the folder selection dialog. If the user selects a file, it creates a DirectoryInfo and then uses GetFiles to enumerate the files in the folder and its subfolders. I am using Linq to select only the files with size greater than the minimum size, select only the data I want and sort the resulting files by length. At the end, I am converting the enumeration to a list. I am doing that because this list will be traversed some times to get the data by extension or the ABC curve, and I wanted to avoid multiple enumeration.

If you run this code and click the start button, you will see that, after some time, the data is shown in the main window:

image

But that’s not what we want. We want a better display for the data, so we need to create an ItemTemplate for the list:

[sourcecode language=”text”]
<ListBox x:Name="FilesList">
    <ListBox.ItemTemplate>
        <DataTemplate>
            <StackPanel>
                <TextBlock Text="{Binding FullName}"/>
                <TextBlock Text="{Binding Length, StringFormat=N0}"/>
            </StackPanel>
        </DataTemplate>
    </ListBox.ItemTemplate>
</ListBox>
[/sourcecode]

And now we have the data shown in a better way:

image

We can use Linq to fill the other tabs:

[sourcecode language=”csharp”]
private void StartClick(object sender, RoutedEventArgs e)
{
    var fbd = new WPFFolderBrowserDialog();
    if (fbd.ShowDialog() != true)
        return;
    var selectedPath = fbd.FileName;
    var di = new DirectoryInfo(selectedPath);
    Int64 minSize;
    if (!Int64.TryParse(MinSizeBox.Text, out minSize))
        return;
    var files = di.GetFiles("*", SearchOption.AllDirectories)
        .Where(f => f.Length >= minSize)
        .Select(f => new {f.Name, f.Length, f.DirectoryName, f.FullName, f.Extension})
        .OrderByDescending(f => f.Length)
        .ToList();
    var totalSize = files.Sum(f => f.Length);
    TotalFilesText.Text = $"# Files: {files.Count}";
    LengthFilesText.Text = $"({totalSize:N0} bytes)";
    FilesList.ItemsSource = files;
    ExtList.ItemsSource = files.GroupBy(f => f.Extension)
        .Select(g => new {Extension = g.Key, Quantity = g.Count(), Size = g.Sum(f => f.Length)})
        .OrderByDescending(t => t.Size);
    var tmp = 0.0;
    AbcList.ItemsSource = files.Select(f =>
        {
            tmp += f.Length;
            return new {f.Name, Percent = tmp/totalSize*100};
        });
}
[/sourcecode]

For the extension list, we made a grouping by extension and selected the data we want, getting the quantity and total length for each group. For the ABC curve, we used a temporary value to get the total length for the files larger than the selected one. If you run the program, you will see that the data is not formatted. We can format the data by using the ItemTemplate for the lists:

[sourcecode language=”text”]
<TabItem Header="Extensions">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="*"/>
            <ColumnDefinition Width="*"/>
        </Grid.ColumnDefinitions>
        <ListBox x:Name="ExtList">
            <ListBox.ItemTemplate>
                <DataTemplate>
                    <StackPanel Orientation="Horizontal">
                        <TextBlock Text="{Binding Extension}" Width="100" Margin="5"/>
                        <TextBlock Text="{Binding Quantity, StringFormat=N0}" Width="100" Margin="5" TextAlignment="Right"/>
                        <TextBlock Text="{Binding Size,StringFormat=N0}" Width="150" Margin="5" TextAlignment="Right"/>
                    </StackPanel>
                </DataTemplate>
            </ListBox.ItemTemplate>
        </ListBox>
    </Grid>
</TabItem>
<TabItem Header="ABC Curve">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="*"/>
            <ColumnDefinition Width="*"/>
        </Grid.ColumnDefinitions>
        <ListBox x:Name="AbcList">
            <ListBox.ItemTemplate>
                <DataTemplate>
                    <StackPanel Orientation="Horizontal">
                        <TextBlock Text="{Binding Name}" Width="250" Margin="5"/>
                        <TextBlock Text="{Binding Percent, StringFormat=N2}" Width="100" TextAlignment="Right"/>
                    </StackPanel>
                </DataTemplate>
            </ListBox.ItemTemplate>
        </ListBox>
    </Grid>
</TabItem>
[/sourcecode]

When we run the program, we can see the data for the extensions and the ABC Curve:

image

image

Now we need only to add the charts to the window.

Adding Charts

We will add the WPF Toolkit (https://wpf.codeplex.com/releases/view/40535) to get the charts, but, as it doesn’t seem to be maintained anymore, I’ll use a fork of this project that has a NuGet package and is at https://github.com/dotnetprojects/WpfToolkit.

To add the Pie Chart on the Extensions page, we must add this XAML code:

[sourcecode language=”text”]
<chartingToolkit:Chart Title="Extensions"
               Grid.Row="0"
               Grid.Column="1"
               HorizontalAlignment="Stretch"
               VerticalAlignment="Stretch">
    <chartingToolkit:PieSeries DependentValuePath="Size"
                       IndependentValuePath="Extension"
                       x:Name="ExtSeries" />
</chartingToolkit:Chart>
[/sourcecode]

We must add the namespace at the top of the file:

[sourcecode language=”text”]
xmlns:chartingToolkit="clr-namespace:System.Windows.Controls.DataVisualization.Charting;assembly=DotNetProjects.DataVisualization.Toolkit"
[/sourcecode]

When we run the application, we see the data and the chart, side by side:

image

For the ABC Curve, we must add this XAML:

[sourcecode language=”text”]
<chartingToolkit:Chart Title="Abc Curve"
               Grid.Row="0"
               Grid.Column="1"
               HorizontalAlignment="Stretch"
               VerticalAlignment="Stretch">
    <chartingToolkit:Chart.Axes>
        <chartingToolkit:CategoryAxis Orientation="X" ShowGridLines="False"  />
        <chartingToolkit:LinearAxis Title="% Size"
                                 Orientation="Y"
                                 ShowGridLines="True" />
    </chartingToolkit:Chart.Axes>
    <chartingToolkit:LineSeries DependentValuePath="Percent"
                        IndependentValuePath="Item"
                        x:Name="AbcSeries" />
</chartingToolkit:Chart>
[/sourcecode]

Then, we change the source code to assign the data for the series:

[sourcecode language=”csharp”]
private void StartClick(object sender, RoutedEventArgs e)
{
    var fbd = new WPFFolderBrowserDialog();
    if (fbd.ShowDialog() != true)
        return;
    var selectedPath = fbd.FileName;
    var di = new DirectoryInfo(selectedPath);
    Int64 minSize;
    if (!Int64.TryParse(MinSizeBox.Text, out minSize))
        return;
    var files = di.GetFiles("*", SearchOption.AllDirectories)
        .Where(f => f.Length >= minSize)
        .Select(f => new {f.Name, f.Length, f.DirectoryName, f.FullName, f.Extension})
        .OrderByDescending(f => f.Length)
        .ToList();
    var totalSize = files.Sum(f => f.Length);
    TotalFilesText.Text = $"# Files: {files.Count}";
    LengthFilesText.Text = $"({totalSize:N0} bytes)";
    FilesList.ItemsSource = files;
    var extensions = files.GroupBy(f => f.Extension)
        .Select(g => new {Extension = g.Key, Quantity = g.Count(), Size = g.Sum(f => f.Length)})
        .OrderByDescending(t => t.Size).ToList();
    ExtList.ItemsSource = extensions;
    ExtSeries.ItemsSource = extensions;
    var tmp = 0.0;
    var abcData = files.Select(f =>
    {
        tmp += f.Length;
        return new {f.Name, Percent = tmp/totalSize*100};
    }).ToList();
    AbcList.ItemsSource = abcData;
    AbcSeries.ItemsSource = abcData.OrderBy(d => d.Percent).Select((d,i) => new {Item = i, d.Percent});
}
[/sourcecode]

When we run the code, we can see the ABC curve.

image

Conclusion

As you can see, it’s fairly easy to get the disk space in a WPF program. With some Linq queries, we can analyze the data the way we want, and then present it using the WPF visualization.

The full source code for this project is at https://github.com/bsonnino/DiskAnalysis

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

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

In the last post, I’ve talked about stacks, a LIFO (Last In – First out) data structure. In this post, I will talk about queues, a FIFO (First in – First out) data structure. A queue is like any box office queue, where the first in line are served first.

The queue has these operations:

  • Enqueue – adds an item to the end of the queue
  • Dequeue – Removes an item from the start of the queue

Like the stack, you can’t add or remove items from the middle of the queue. The node structure is the same as the nodes used in the linked list and in the stack. The Enqueue method is like this:

[sourcecode language=”csharp” padlinenumbers=”true”]
public void Enqueue(T obj)
{
NodeList&lt;T&gt; node = new NodeList&lt;T&gt;() { Data = obj };
_count++;
if (_last == null)
{
_last = _top = node;
return;
}
_last.Next = node;
_last = node;
}
[/sourcecode]

Note that there is a subtle change from the stack code: we are using an extra pointer for the last node, so we can get fast inserts and deletes in the queue.

The Dequeue method is:

[sourcecode language=”csharp”]
public T Dequeue()
{
if (_top != null)
{
NodeList&lt;T&gt; result = _top;
_top = _top.Next;
_count–;
return result.Data;
}
throw (new InvalidOperationException("The queue is empty"));
}

[/sourcecode]

We remove the top node from the queue. With these two operations, the queue is ready. We can also do the same way as the stack and use a linked list to implement it:

[sourcecode language=”csharp”]
public class QueueAsList&lt;T&gt;
{
private readonly LinkedList&lt;T&gt;_linkedList = new LinkedList&lt;T&gt;();

public void Enqueue(T obj)
{
_linkedList.Insert(obj);
}

public T Dequeue()
{
if (_linkedList.Count == 0)
throw (new InvalidOperationException("The queue is empty"));
var result = _linkedList[0];
_linkedList.Remove(result);
return result;
}

public int Count =&gt; _linkedList.Count;

public void Clear()
{
_linkedList.Clear();
}
}
[/sourcecode]

Now we have our implementations of the queue and we can move to the next article, the Tree.

image

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

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

In the last post I’ve talked about one of the most basic data structures, the linked list. In this post we will start talking about stacks.

A stack is a LIFO (Last In –First out) data structure, it’s like a pile of plates: you start stacking them and, when you need one, you remove the top of the pile, the last you’ve put.

Its structure is very similar to the linked list, but you have these operations on it:

  • Push – add a new item to the stack
  • Pop – remove the top item from the stack
  • Peek – take a look at the top of the stack but don’t remove the item

As you can see, you can only operate on the top of the stack, you cannot add or remove an item in the middle of the stack. As we’ve seen in the last article, creating a generic stack is pretty much the same as creating a non generic one, so we will only develop a generic one in this article.

The Push method will add a new item in the top of the stack, thus setting the _top field to point to the newly created node:

[sourcecode language=”csharp” padlinenumbers=”true”]
private NodeList<T> _top;
private int _count;

public void Push(T obj)
{
var node = new NodeList<T>;
{
Data = obj,
Next = _top
};
_top = node;
_count++;
}
[/sourcecode]

The Pop method checks the top of the stack. If it’s null (empty stack), it throws an InvalidOperationException. If the stack isn’t empty, the top and count are updated and the old top is returned:

[sourcecode language=”csharp”]
public T Pop()
{
if (_top == null)
throw (new InvalidOperationException("The stack is empty"));
var result = _top;
_top = _top.Next;
_count–;
return result.Data;
}
[/sourcecode]

Peek is very simple, it only checks if there is any data in the top of the stack and returns its data:

[sourcecode language=”csharp”]
public T Peek()
{
if (_top != null)
return _top.Data;
throw (new InvalidOperationException("The stack is empty"));
}
[/sourcecode]

Our stack is ready. If you take a closer look, you will see that the stack can be implemented with a Linked List: Push will insert an item at the top (with Insert), Pop will get the top item, remove it and return it. Peek will get the top item and return it:

[sourcecode language=”csharp”]
public class StackAsList<T>;
{

private readonly LinkedList<T> _linkedList = new LinkedList<T>();

public void Push(T obj)
{
_linkedList.Insert(obj);
}

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

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

public int Count => _linkedList.Count;

public void Clear()
{
_linkedList.Clear();
}

}
[/sourcecode]

Pretty simple, no? Now we have two implementations of the stack, in the next article we will see the Queue.

image

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

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

Although we use data structures daily in our programs, sometimes we forget the theory behind them. So, I decided to create this series of posts to give a refresher on the data structures theory.

This is is by no means a try to replace the current data structures (for sure, the .NET ones will be better optimized than these ones), but just a way to remember what’s going on when we use them.

They will be entirely developed in C# and I will create a WPF program to show examples of their use. So, let’s start with the first one: Linked Lists.

Linked lists are lists of elements that are linked by a pointer to the next element. Each element has a structure like this:

[sourcecode language=”csharp” padlinenumbers=”true”]
class NodeList
{
public NodeList()
{
Next = null;
}

public object Data { get; set; }
public NodeList Next { get; set; }
}
[/sourcecode]

 

Each node stores its data and a pointer to the next node. The last node in the list points to null. The linked list would be something like this:

Singly-linked-list.svg

(Source – Wikipedia)

The only thing that the list must store is its top node. Then, all traversing is done using the Next pointers of each node. So, a basic linked list would be like this:

[sourcecode language=”csharp” htmlscript=”true”]
class LinkedList
{
private NodeList _top = null;
}
[/sourcecode]

This list wouldn’t do much, we need some operations. To insert some data in the list, we could use the Insert method:

[sourcecode language=”csharp” htmlscript=”true”]
public int Insert(object obj)
{
var node = new NodeList { Data = obj };
if (_top == null)
{
_top = node;
_last = node;
}
else
{
_last.Next= node;
_last = node;
}
_count++;
return _count;
}
[/sourcecode]

I added the fields _last, that stores the last item in the list, so there is no need to traverse the list for every inserted node and _count, that stores the number of items in the list. To clear the list, we only  have to set the top node to null:

[sourcecode language=”csharp” htmlscript=”true”]
public void Clear()
{
_top = null;
_count = 0;
}
[/sourcecode]

To get the number of Items on the list, we could call the Count property:

[sourcecode language=”csharp”]
public int Count => _count;
[/sourcecode]

We can also insert some data at a fixed position:

[sourcecode language=”csharp”]
public int InsertAt(int position, object obj)
{
if (position < 0 || position >= _count)
throw (new IndexOutOfRangeException());
var node = new NodeList { Data = obj };
if (position == 0)
{
node.Next = _top;
_top = node;
}
else
{
var current = GetNodeAt(position – 1);
node.Next = current.Next;
current.Next = node;
}
_count++;
return _count;
}
[/sourcecode]

To insert a new node in any position, we first check for the special case to insert in the first position. If it is, we replace the top item with the inserted node and set the Next property to point to the old top. If it’s another position, we traverse the tree using the GetNodeAt, to get the item before the item to be inserted and replace the next pointer of the inserted node, pointing to where the found item was pointing and replacing the next pointer of the found item, pointing to the inserted node. The GetNodeAt function is:

[sourcecode language=”csharp”]
private NodeList GetNodeAt(int position)
{
if (position < 0 || position >= _count)
throw (new IndexOutOfRangeException());
var current = _top;
for(int i = 0; i < position;i++)
{
current = current.Next;
}
return current;
}
[/sourcecode]

With GetNodeAt, we can create an indexed property to get the data in the nth node:

[sourcecode language=”csharp”]
public object this[int index] => GetNodeAt(index).Data;
[/sourcecode]

 

To remove a node, we just need to set the next pointer of the node before to the node after the deleted one:

[sourcecode language=”csharp”]
public bool Remove(object obj)
{
var currentItem = Find(obj);
if (currentItem == -1)
return false;
if (currentItem == 0)
{
_top = _top.Next;
}
else
{
var previousNode = GetNodeAt(currentItem – 1);
previousNode.Next = previousNode.Next.Next;
if (previousNode.Next == null)
_last = previousNode;
}
_count–;
return true;
}
[/sourcecode]

 

We find the item related to the object we want to remove and then set the next node to the value pointed to the node to be deleted. The Find method is:

[sourcecode language=”csharp”]
public int Find(object obj)
{
if (Count == 0)
return -1;
NodeList current = _top;
int currentNo = 0;
do
{
if (current.Data.Equals(obj))
{
return currentNo;
}
current = current.Next;
currentNo++;
} while (current != null);
return -1;
}
[/sourcecode]

We can also create a RemoveAt method:

[sourcecode language=”csharp”]
public bool RemoveAt(int position)
{
if (position < 0 || position >= _count)
throw (new IndexOutOfRangeException());
if (position == 0)
{
_top = _top.Next;
}
else
{
var previousNode = GetNodeAt(position – 1);
previousNode.Next = previousNode.Next.Next;
if (previousNode.Next == null)
_last = previousNode;
}
_count–;
return true;
}
[/sourcecode]

We must still create one last method to retrieve all elements in the list:

[sourcecode language=”csharp”]
public IEnumerable GetItems()
{
if (Count == 0)
yield break;
_currentItem = _top;
while (_currentItem != null)
{
yield return _currentItem.Data;
_currentItem = _currentItem.Next;
}
}
[/sourcecode]

The LinkedList class is finished, but it has one issue, here: the Data property is an Object and this brings some issues: boxing and unboxing of objects, there is no verifying of data integrity (you can add any type of object, and the objects don’t need to be related). So, the next step is to introduce a Generic Linked List, so we can solve these issues. The new NodeList is:

[sourcecode language=”csharp”]
class NodeList<T>
{
public NodeList()
{
Next = null;
}

public T Data { get; set; }
public NodeList<T> Next { get; set; }
}
[/sourcecode]

And the new LinkedList is:

[sourcecode language=”csharp”]
public class LinkedList<T>
{
private NodeList<T> _top;
private NodeList<T> _last;
private int _count;
private NodeList<T> _currentItem;

public int Insert(T obj)
{
var node = new NodeList<T> { Data = obj };
if (_top == null)
{
_top = node;
_last = node;
}
else
{
_last.Next = node;
_last = node;
}
_count++;
return _count;
}

private NodeList<T> GetNodeAt(int position)
{
if (position < 0 || position >= _count)
throw (new IndexOutOfRangeException());
var current = _top;
for (int i = 0; i < position; i++)
{
current = current.Next;
}
return current;
}

public int InsertAt(int position, T obj)
{
if (position < 0)
throw (new IndexOutOfRangeException());
var node = new NodeList<T> { Data = obj };
if (position == 0)
{
node.Next = _top;
_top = node;
}
else
{
var current = GetNodeAt(position – 1);
node.Next = current.Next;
current.Next = node;
}
_count++;
return _count;
}

public void Clear()
{
_top = null;
_count = 0;
}

public int Count => _count;

public T this[int index] => GetNodeAt(index).Data;

public int Find(T obj)
{
if (Count == 0)
return -1;
NodeList<T> current = _top;
int currentNo = 0;
do
{
if (current.Data.Equals(obj))
{
return currentNo;
}
current = current.Next;
currentNo++;
} while (current != null);
return -1;
}

public bool Remove(T obj)
{
var currentItem = Find(obj);
if (currentItem == -1)
return false;
if (currentItem == 0)
{
_top = _top.Next;
}
else
{
var previousNode = GetNodeAt(currentItem – 1);
previousNode.Next = previousNode.Next.Next;
if (previousNode.Next == null)
_last = previousNode;
}
_count–;
return true;
}

public bool RemoveAt(int position)
{
if (position < 0 || position >= _count)
throw (new IndexOutOfRangeException());
if (position == 0)
{
_top = _top.Next;
}
else
{
var previousNode = GetNodeAt(position – 1);
previousNode.Next = previousNode.Next.Next;
if (previousNode.Next == null)
_last = previousNode;
}
_count–;
return true;
}

public IEnumerable<T> GetItems()
{
if (Count == 0)
yield break;
_currentItem = _top;
while (_currentItem != null)
{
yield return _currentItem.Data;
_currentItem = _currentItem.Next;
}
}
}
[/sourcecode]

As you can see, there was not much trouble to change from a LinkedList that stores objects to a generic Linked List.

Our Linked List is ready to be used, and in the next article we will see another data structure, the Stack.

image

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

Os novos dispositivos 2-em-1 Windows 10 trouxeram uma novidade: você pode usar os seus diversos sensores para aumentar a experiência do usuário em seus programas.

O Delphi trouxe a possibilidade de usar estes sensores em seus programas, tanto usando a VCL como no FireMonkey. A minha palestra na CodeRage Brasil mostra como você pode criar seus programas Delphi que utilizam a classe TSensor para melhorar a experiência do usuário. Confira em  https://www.youtube.com/watch?v=U2uKyuKwJcY