Introduction
Presenting Data in order to choose an Item from is not solved sufficient yet. Imagine a Combobox with more than 300 Items - simply NoGo!
An Improvement would be a Textbox with AutoCompletion, because Autocompletion works as an easy-to-use filter, which reduces the data-amount very quickly.
But even Autocompletion has 2 disadvantages:
- It is not data-safe: a user can ignore the autocompletion-suggestions, and input any rubbish he likes.
- On large Data-Lists the user still looses the orientation, which keys are valid to continue reducing the abundance of choices to a human limit.
The concept of Coercing Autocompletion
- display a dropdown-list of options, where the user can choose from, if he likes (standard-autocompletion-behavior)
- ensure, that the user only can input valid Data. Reject invalid key-strokes immediately
- give a preview of the next valid KeyStrokes
- (optional) "WindForward": as long as only one KeyStroke is valid, autocompletion can input it automatically. This can reduce the nessecary keystrokes dramatically, but also can puzzle rapid-typing-users - So make it optional
Maybe theese concepts do not sound that "whoop! - world-changing". But assume a stable and easy-to-use standard-control, which provides theese concepts (and moreover databinding) - do you think anyone would ever use a combobox anymore? No - combobox, as we know it - perhaps/propably would die.
Several ways of looking at Data
Assume the following sorted data (some geman towns):
Genthin
Gentingen
Genzkow
Georgenberg
Georgensgmünd
Georgenthal
Georgsdorf
Georgsmühle
Geraberg
Gerabronn
Gerach
I put them into a uniform grid, and marked up some chars of specific importance:
<figure1>
At theese markup-points a user can decide, and each decision will reduce the range of further choice-options.
You can understand theese points as nodes of a decision-tree - let me draw in the available decision-pathes:
<figure2>
Moreover i can remove redundant chars from the Tree:
<figure3>
funny - isn't it?
But the most convenient view (to me) is visualizing a practical sample-selection: Lets select "Georgensgmünd", and see, how the decisions reduce choice-options in a few steps to one, which is the final selection:
<figure4>
After typing "G" one can choose any of the 11 towns. But marked up as "Decision-Node" on this level are only these 3: "n o r"
Choosing "o" reduces the choice-options to 5, and now there are only two Decision-Node: "e s"
Choosing the "e", reduces on to choice-options 3, and "b s t" are available as Decision-Nodes.
Choosing "s" finishes selection - only Option "Georgensgmünd" is left.
Proof of Concept: Sample-Application
<figure5>
My implementation is far away from beeing able to crowd out Combobox from Gui-Development: It misses Databinding-Support, the ValidNextKeys-Preview is not applicable everywhere, and it inherits a bug and some suboptimal behavior from Standard-Autocompletion. It is easy-to-use in fact, but - i admire: not (yet) as easy-to-use than combobox is...
But nevertheless i think, it already can do a good job in real-world-applications, who deal with selecting data from big data-amounts.
The sample-download is a kind of zip-code-finder, and it provides about 16000 german towns (and town-districts) to choose from.
My code-design is a kind of "Textbox-Behavior": You can attach it to a Textbox, give him data, and it will configure autocompletion, coercing, notify about Valid-Next-Keys and optional wind-forward-functionality.
Internally it simply let standard-autocompletion do its dropdown- and suggesting-job, and just extend functionality with coercion, displaying the available Chars and stuff.
In other words: a really lightweight Solution - less than 200 lines of code.
Using the code
Public Class frmOrtFinder
Private WithEvents _Coercer As New CoercingAutoCompletion
Public Sub New()
InitializeComponent()
FillDatasetFromFile(Path.GetFullPath("..\..\Data\GeoNamesDE.inf"))
Dim data = OrteDts.Ort.Select(Function(rw) ", ".Between(rw.Name, rw.Bundesland, rw.PLZ))
_Coercer.Textbox = TextBox1
_Coercer.ReadData(data)
End Sub
Private Sub _Coercer_AvailableCharsChanged(sender As Object, e As EventArgs) Handles _Coercer.AvailableCharsChanged
lbAvailable.Text = _Coercer.AvailableChars
End Sub
Private Sub _Coercer_InputDone(sender As Object, e As EventArgs) Handles _Coercer.InputDone
Dim fields = TextBox1.Text.Split({", "}, StringSplitOptions.None)
For i = 0 To bsOrt.Count - 1
If DirectCast(bsOrt(i), DataRowView).Row.ItemArray.Cast(Of String).SequenceEqual(fields) Then
bsOrt.Position = i
grdOrt.FirstDisplayedScrollingRowIndex = i
Return
End If
Next
Throw New Exception("Record not found - this should never occur!")
End Sub
- instantiate a coercer (line#3)
- set its Textbox (line#9)
- give data to it (line#10)
- handle its Events (lines#13, #17)
Implementation-Details
I separated the concern "Textbox-Behavior" from "Data-Parsing" - first a glance at the Textbox-Part:
Public Class CoercingAutoCompletion
Public Event AvailableCharsChanged As EventHandler
Public Event InputDone As EventHandler
Public Property Textbox As TextBox
Get
Return _TextBox
End Get
Set(value As TextBox)
If _TextBox Is value Then Return
If _TextBox IsNot Nothing Then Throw New Exception("Textbox already set!")
_TextBox = value
_TextBox = _TextBox
_TextBox.AutoCompleteMode = AutoCompleteMode.SuggestAppend
_TextBox.AutoCompleteSource = AutoCompleteSource.CustomSource
_TextBox.AutoCompleteCustomSource = _AutoTextSource
End Set
End Property
Private Sub _TextBox_KeyUp(sender As Object, e As KeyEventArgs) Handles _TextBox.KeyUp
With _TextBox
Dim i = .SelectionStart
Select Case e.KeyCode
Case Keys.Up, Keys.Down i = Math.Min(i, _UnselectedText.Length)
_DataParser.Parse(.Text.Substring(0, i))
_DataParser.SelStartPropose = i
Case Keys.Left, Keys.Right
i = _UnselectedText.Length + e.KeyCode - 38
_DataParser.Parse(.Text.Substring(0, i))
If e.KeyCode = Keys.Left Then _DataParser.SelStartPropose = i
Case Else
_DataParser.Parse(.Text.Substring(0, i))
If e.KeyCode = Keys.Back Then _DataParser.SelStartPropose = i
If _DataParser.FirstDivergence < i Then
System.Media.SystemSounds.Hand.Play()
.Text = .Text.Substring(0, _DataParser.FirstDivergence)
End If
End Select
ImproveSelection() End With
End Sub
Private Sub _TextBox_Leave(sender As Object, e As EventArgs) Handles _TextBox.Leave
With _TextBox
_DataParser.Parse(.Text)
_TextBox.Text = _DataParser.FirstBestMatch
RaiseEvent InputDone(Me, EventArgs.Empty)
End With
End Sub
Mainly it configures AutoCompletion and then observes the Textbox_KeyUp
-Event. And there is to distinguish between up/down, left/right, backspace and general Key-Strokes.
- Up/Down address standard-autocompletion to select next/previous entry from Dropdown-list. Therefore the text is to be re-parsed, and try restore previous selection
- Left/Right shall move the selection-start, but in every state an autocompletion-selection must reach to the end of text: that's the meaning of suggest: it immediately vanishes, when the user types anything else.
- Backspace equals Cursor-Left-Keystroke, but Autocompletion removes its suggestion (instead of re-suggesting better - i can't help that)
- other keys also cause re-parsing, and on invalid input the text gets shortened back to validity (line#22).
So far - maybe more interesting is the DataParser - concern:
Private _RawWords As Object()
Public Sub Refill(autoSource As AutoCompleteStringCollection, texts As IEnumerable(Of String))
autoSource.Clear()
Dim txts = texts.ToArray
Array.Sort(txts, StringComparer.OrdinalIgnoreCase)
autoSource.AddRange(txts)
Dim bf = BindingFlags.Instance Or BindingFlags.NonPublic
Dim inf = GetType(AutoCompleteStringCollection).GetField("data", bf)
Dim data = inf.GetValue(autoSource)
inf = GetType(ArrayList).GetField("_items", bf)
_RawWords.Be(inf.GetValue(data))
Parse("")
End Sub
Refill()
fills the AutoCompleteCollection and then hack it with reflection, to get access to the underlying Data-Array. Thats why my solution takes no additional Memory to what standard-Autocompletion takes anyway.
Note that i use StringComparer.OrdinalIgnoreCase
for sorting. The same Comparer is in use when searching the data with BinarySearch:
Private Function FindBestMatch(txt As String) As Integer
Dim i = Array.BinarySearch(_RawWords, txt, StringComparer.OrdinalIgnoreCase)
Return If(i < 0, Not i, i)
End Function
A binary search is very efficient: Eg. with only 20 internal Iterations it finds an item in a range of about 1 million sorted items. The Return-Value is tricky: If the search finds a matching item it returns its Position as a value >= 0. Otherwise binarysearch doesn't simply return -1
, but it returns a negative number - the Bit-Complement of the Position, where a matching item should be (also understand as: "insert-position").
And that is, what Dataparser
needs to know: the insert-position of the input (although it doesn't insert).
Assume the input "geo", and look back to <figure4>: FindBestMatch()
would come up with line#4, and that is the starting-line from where is to look up for the next Decision-Nodes.
Then next we must find the ending-line of the particular "option-range".
Once again apply FindBestMatch()
-binarysearch: But first append Char.MaxValue
to the input "geo", to ensure, the modified input "geo^" will retrieve the first line behind the option-range - namely line#9.
In summary we figured out, that the first "Bestmatch" to "geo" is at line#4 - "Georgenberg", and the last BestMatch is at line#8 - "Georgsmühle". From this "option-range" we must collect the "decision-nodes", which define the next level of selection.
But how find the correct column of the next available Decision-Nodes?
Not that complicated: Just compare the first line of the option-range with its last line. The occurance of the first difference will give us the x-position we're looking for - in the sample its column#6, because "Georgenberg" and "Georgsmühle" diverge from column#6 on.
Now loop from firstBestmatchPosition
to lastBestMatchPosition
and collect distinct(!) the chars at column#6. These are: "e s" - the decision-nodes, and the "available-chars" of a wind-forward-coercing-autocompletion.
The story in code:
Public Sub Parse(txt As String)
_FirstMatchPos = FindBestMatch(txt) FirstBestMatch = Words(_FirstMatchPos)
FirstDivergence = GetDivergence(txt, FirstBestMatch, 0)
If FirstDivergence < txt.Length AndAlso _FirstMatchPos > 0 Then Dim div2 = GetDivergence(txt, Words(_FirstMatchPos - 1), 0)
If div2 < FirstDivergence Then
_LastMatchPos = FindBestMatch(txt.Substring(0, FirstDivergence) & Char.MaxValue) - 1
Else
_LastMatchPos = _FirstMatchPos - 1
FirstDivergence = div2
_FirstMatchPos = FindBestMatch(txt.Substring(0, FirstDivergence))
FirstBestMatch = Words(_FirstMatchPos)
End If
Else
_LastMatchPos = FindBestMatch(txt & Char.MaxValue) - 1 End If
_DecisionColumn = GetDivergence(FirstBestMatch, Words(_LastMatchPos), FirstDivergence)
SelectionStart = If(FirstDivergence >= txt.Length AndAlso WindForward, _DecisionColumn, FirstDivergence)
End Sub
Private Function GetDivergence(s0 As String, s1 As String, start As Integer) As Integer
For i = start To s0.Length - 1
If Char.ToUpper(s0(i)) <> Char.ToUpper(s1(i)) Then Return i
Next
Return s0.Length
End Function
A complication occurs on invalid inputs: FindBestmatch()
will either return the firstBestmatch or the lastBestmatch - this depends on the sort-order of the invalid char.
Assume invalid input "Geoo": the binary-searched insert-position is line#4, because "Geoo" is smaller than "Georgenberg".
But another invalid input "Geot" will retrieve line#9, because "Geot" is bigger than "Georgsdorf". So on invalid input there is additional to re-check, whether the line was the first or the last of the option-range.
Conclusion
To me it's less important to introduce a particular tricky Textbox-Behavior-Implementation. More importent i see the introduction of the concept "Coerce-Windforward-Autocompletion" in general - not my contemplations about Data-structures or explain-code-tryals.
Even my implementation is rather poor, compared with what my fantasy imagines:
May be a Wpf-control, where on GotFocus the Valid-Next-Chars pop up as kind of tooltip, and stuff like that.
Or they get marked up within the DropDown-List.
Or - keeping good-ol' combo alive - why not extend ComboBox either with coerce-wind-forward-autocompletion?
And of course Datagrid-Coercing-Columns must be created either ...
Credits
- the sample-app's data is taken from GeoNames, under the CreativeCommons-License, which means: for free, as long as i mention them as the author - which i comply willingly.