Today I had a close look at the Data binding possibilities provided by the Windows Presentation Foundation.

Before telling you more about that I’d like to show you good-old know alternatives and then compare them to WPF’s solution.

MFC with C++

DDX (Dialog Data Exchange) and DDV (Dialog Data Validation) are two great tools that allow us to easily set and access the values of certain MFC controls.

DDX allows us to link the value of a variable to a control. To use some DDX functions, you should override the DoDataExchange function of a dialog:

afx_msg void DoDataExchange(CDataExchange*);

The function itself can look like this, it just binds the “resource” to a member variable.

afx_msg void DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
DDX_Text(pDX, TXT_NAME, m_strName);
}

The first line calls the base class, the seconds calls that function:

void DDX_Text(CDataExchange* pDX, int nIDC, CString& value);

If we want to set the value of the controls, we can call the UpdateData passing FALSE to the UpdateData function. On the other hand, if we want to retrieve the value of the control into our CString variable, we would pass TRUE to the UpdateData function.

BOOL CWnd::UpdateData(BOOL bSaveAndValidate)
{
	CDataExchange dx(this, bSaveAndValidate);
	try
	{
		DoDataExchange(&dx);
	}
	catch(CUserException e)
	{
		return FALSE;
	}
	return TRUE;
}

For other controls such as the list box, radio button and check box, we would use the similar DDX functions DDX_CBString, DDX_Radio and DDX_Check respectively.

When using DDX for the exchange of data between controls and variables we easily can validate them.

void CSample::DoDataExchange(CDataExchange* dx)
{
	CDialog::DoDataExchange(dx);
	//{{AFX_DATA_MAP(CDlg)
	...
	DDX_Text (dx, TXT_AGE, m_iAge);
	DDV_MinMaxInt(dx, m_iAge, 0, 150);  // <- validation
	. . .
	//}}AFX_DATA_MAP
}

The DDX_Text() call transfers the contents of the edit control into the m_age data member, converting it into an integer. After that is has to pass validation.

DDV_MinMaxInt looks as follows:

void DDV_MinMaxInt(CDataExchange* dx, int value, int min, int max)
{
	if (value < min || value > max)
	{
		AfxMessageBox("Please enter a value between ...");
		dx->Fail();
	}
}

If the value doesn’t yield the condtions of the validation method a error message is shown and Fail() is invoked on the data exchange object.

Windows Forms with C#

Data binding in C# provides a more advanced way for developers to create a read/write link between the controls on a form. It’s often used for binding forms to complex data structures such as SQL databases. Windows Forms data binding allows you to access data from databases as well as data in other structures, such as arrays and collections.

Each Windows Form has at least one BindingContext object that manages the access to and from the controls. For example if you add use a textbox control to a form and bind it to a column of a table (e.g. “tblAddress.Name”) in a dataset(e.g. called “dsAddr”), the control communicates with the BindingContext object for that form.

txtname.DataBindings.Add("Tom Morello",Adresses,"tblAddress.Name");

CurrencyManager cm = (CurrencyManager)this.BindingContext[dsAddr,"tblAddress"];
foreach(object s in cm)
{
Console.WriteLine(s.ToString());
}

The CurrencyManager is used to keep data-bound controls synchronized with each other.

That way of data binding is very useful when dealing with collection controls such as ListView or ListBox.
It’s common practice to bind them to any kind of Array, Collection or List.

A quick and clever way is the usage of data bindings in C# with ADO.NET Data Objects because those data structures are suitable for binding to.

DataTables such as GridView provide DataSource and DataMember properties:

gv1.DataSource = dsAddr;
gv1.DataMember = "tlbAddresses";

other appropriate objects are:

• DataColumn
• DataView
• DataSet
• DataViewManager

You also can bind controls to other controls. Binding data of a ComboBox to a ListBox follows the same model and is no problem.

DataBinding with WPF

Now we come to the point the article originally was about.
When working with collection-like data sources in WPF, you can read properties of the selected item by writing your binding expressions directly into the XAML (eXtensible Application Markup Language) code that defines the structure of every WPF-GUI.

<DockPanel DataContext="{x:Static Persons}">
  <TextBlock DockPanel.Dock="Top"
             Text="{Binding Lastname}" >
  <ListBox ItemsSource="{Binding}"
           IsSynchronizedWithCurrentItem="True" />
</DockPanel>

In that example the source is an array of persons names and the ListBox should show the lastname of every person the array contains.
When WPF encounters a binding to a non-existent property on a collection, WPF has a fallback strategy: it looks for the named property on the current item.

If source and destination are both collections you can do

Property="{Binding /}"

to bind them to each other.

That’s nice behavoir but just the beginning of some great ideas.
There are several things you can define in the binding object:

• OneWay binding causes changes to the source property to automatically update the target property, but changes to the target property are not propagated back to the source property.
• TwoWay binding causes changes to either the source property or the target property to automatically update the other. This type of binding is appropriate for editable forms or other fully-interactive UI scenarios.
• OneWayToSource is the reverse of OneWay binding; it updates the source property when the target property changes.
• OneTime binding causes the source property to initialize the target property, but subsequent changes do not propagate. This means that if the data context undergoes a change or the object in the data context changes, then the change is reflected in the target property. This type of binding is appropriate if you are using data where either a snapshot of the current state is appropriate to use or the data is truly static.

The UpdateSourceTrigger property of the binding determines when binding should appear.

• LostFocus (default e.g. for TextBox)
• PropertyChanged
• Explecit (when calling UpdateSource)

Due data binding you could for example bind a textbox value to its background color. The property of type string in the binding source object is connected to a Color property of type Color.

IValueConverter makes it possible:

public class ColorBrushConverter : IValueConverter
{
    public object Convert(object value, Type targetType, object parameter, System.Globalization.CultureInfo culture)
    {
        Color color = (Color)value;
        return new SolidColorBrush(color);
    }

public object ConvertBack(object value, Type targetType, object parameter, System.Globalization.CultureInfo culture)
    {
        return null;
    }
}

To ensure that the user has entered the expected information we user input validate it with some logic.
At first we add a validation in description section of the GUI.

<TextBox Name="Birthday" 
    Style="{StaticResource textStyleTextBox}">
  <TextBox.Text>
    <Binding Path="BDay" UpdateSourceTrigger="PropertyChanged">
        <Binding.ValidationRules>
        <ExceptionValidationRule />
      </Binding.ValidationRules>
    </Binding&gt;
 </TextBox.Text>
</TextBox>

The ValidationRules property takes a collection of ValidationRule objects. When the user enters a value that cannot be converted to an the expected type, an exception is thrown, causing the binding to be marked as invalid.

You also can define your own rule:

<Binding.ValidationRules>
                <src:MyRule />
            </Binding.ValidationRules>

class MyRule : ValidationRule
{
    public override ValidationResult Validate(object value, CultureInfo cultureInfo)
    {
        DateTime date;
        try
        {
            date = DateTime.Parse(value.ToString());
        }
        catch (FormatException)
        {
            return new ValidationResult(false, "Invalid date!");
        }
        if (DateTime.Now.Date < date)
        {
            return new ValidationResult(false, "You cannot be born in the future.");
        }
        else
        {
            return ValidationResult.ValidResult;
        }
    }
}

You also might visualize a wrong input for the user.

<Style x:Key="textStyleTextBox" TargetType="TextBox">
  <Setter Property="Foreground" Value="#fff000" />
  <Setter Property="MaxLength" Value="10" />
  <Style.Triggers>
    <Trigger Property="Validation.HasError" Value="true">
      <Setter Property="ToolTip"
        Value="{Binding RelativeSource={RelativeSource Self},
                        Path=(Validation.Errors)[0].ErrorContent}"/>
    </Trigger>
  </Style.Triggers>
</Style>

Now a tooltip appears when the HasError property of Validation is true. You can define a so called Error Template that is used for invalid inputs, if you don’t the default is used.

There are enough and to spare features you can use when working with bindings in WPF, but telling about all of them would carry things too far.

Comparison and forecast

The way MFC programmers use is clear and easy to use. It’s not very casual to handle but it can be extented unique for the project’s necessities.

Win Forms are mostly the same - also the spreading of Win Forms applications on the software market seems to be similar to MFC apps.

From my point of view software development can be really enhanced by technolgies like those provided by the WPF. Also for non-WPF applications its always worth to think about those concepts.

When needing a container hash tables are very common data structures. They provide efficient key based operations to insert and search for data in containers.

1. What are the advantages of a hashmap in comparison to a simple array or vector and when to use it?

• Hash tables are damn fast because keys are transformed to a hash using a hash-function and a number that is used as an index in an array to locate the desired location (”bucket”) where the values should be.
• Hash tables support the efficient insertion of new entries
• Searching for the required data is often independent of the number of items stored

Hash tables are most useful when large numbers of records are to be stored, especially if the size of the data set can be predicted.

2. Things you should consider when designing a hash map

Most important is the hash function and the collision resolution mechanism. The hash function is responsible for the arithmetic operation that transforms a particular key into a particular table address. The collision resolution mechanism is responsible for dealing with keys that hash to the same address.

A good hash function is essential for good hash table performance.
Recommented for typical hash tables is Bob Jenkin’s LOOKUP3 hash function which is very well performing.

A mathematical byte-by-byte implementation that performs particularly well is the Jenkins One-at-a-time hash, adapted here from an article by Bob Jenkins, its creator. The good thing about it is that it’s very simple and can be understood easily.

uint32_t jenkins_one_at_a_time_hash(unsigned char *key, size_t key_len)
{
    uint32_t hash = 0;
    size_t i;

for (i = 0; i < key_len; i++) {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

If two keys hash to the same index, the corresponding records cannot be stored in the same location. This can cause fatal errors in data storage.

3. How to use

Although the C++ STL (Standard Template Library) does not support hash based containers, most compilers like GCC or Visual C++ have their own implementation.

• wxHashmap are implemented in wxWidgets
• MFC provides CMap and CTypedPtrMap

When getting a bit more comprehension for those maps I tried myself to make a small example:

template <
  class key, 
  class value, 
  class hash_function = hash<key>, 
  class increment = unit_increment<key>,
  class equal_key = std::equal_to<key>, 
  class allocate = std::allocator<std::pair<key, value> > >

class OwnHashMap
{
private:
  typedef std::pair<key, value> Map_pair;
  typedef hash_table <
    key,
    Map_pair,
    hash_function,
    increment,
    equal_key,
    selectFirst<Map_pair>,
};

For better accessing the table an iterator can be useful:

template <
  class hash_container,
  class constness_traits ></code>
 
<code>struct hash_table_iterator
{  
  typedef typename constness_traits::pointer ptr;
  typedef typename constness_traits::reference ref;</code>
 
  <code>reference operator*()const 
  {
    return (*this->container)[this->current].item;
  }
  pointer operator->()const 
  {
  return &(operator*());
  }
};

Now it can be used that way:

typedef MyMap<int,double> Map;
  typedef Map::value_type value_type;
  typedef Map::iterator iterator;

Map map;  
  MyMap.add(value_type(1, 1.1));
  MyMap.add(value_type(3, 3.23));

int n = map.size();
//access values
  for ( iterator it = map.begin(); 
it != map.end(); 
++it )
  {
    std::cout << it->first;
    std::cout << it->second;
  }

That’s just the easiest way of implementing a hashmap. That solution could easily be extented with sort algorithms or whatever you need for better data-storing.

Finally I’d like to advice Google SparseHash to you.

Google SparseHash project contains several hash-map implementations in use at Google, with different performance characteristics, including an implementation that optimizes for space and one that optimizes for speed. The memory-optimized one is extremely memory-efficient with only 2 bits/entry of overhead.