# Tab Completion

Home -->
Programming Projects -->
Miscellaneous -->
Tab Completion

# The Problem

Suppose you are making an application which allows the
user to type some string.
Furthermore, suppose this entered string must be a
member of some set S which your program stores.
It would be nice to allow the user to hit the
tab key to complete what they have typed so far.
This is done, for example, in terminals.
The purpose of this page is to describe a simple
algorithm to accomplish this.
The tab completion algorithm will only append
to the *end* of what is typed
(as opposed to "glob completion", which completes
a string containing wildcards).

# Tab Completion API

The following abstract class
has the method `Complete`
which should be called
to tab complete a given string.
The bool `is_done` is set to
true iff the input string has been
successfully completed to a string
in S.
The bool `is_valid`
is set to true iff there exists a
suffix which can be appended to
the input to get a string in S.
class TabCompleter {
public:
virtual void Complete(
const string & input,
string & output,
bool & is_done,
bool & is_valid);
};

As it stands, our description for
the behavior of `Complete` is ambiguous.
The confusion is in what happens when there exist
two distinct strings in S with one an initial
segment of the other.
Because of this, we must be very careful how
we define the behavior of the function.
Here is desired behavior:
- Let A be the set of all elements of S
that have
`input` as an initial segment.

- If A is empty, then set
`is_done` to false
and `is_valid` to false.
Otherwise, proceed to the next step.

- If A has exactly one element, then set
`output` to this element,
set `is_done` to true, and
`is_valid` to true.
Otherwise, proceed to the next step.

- Compute the largest common initial segment
x of the elements of A.

- If x is in S, then
set
`output` to x,
`is_done` to true, and
`is_valid` to true.
If not, proceed to the next step.

- Set
`output` to x,
`is_done` to false, and
`is_valid` to true.

The strange step is #5.
We might want to modify the API
so that the caller knows when
this case has happened.
However, I don't immediately see
a situation where the caller would want
to know this information.

# A Simple Derived Class

If we have the set of strings S
at our disposal, then we can easily
impliment the algorithm described
above using a
Radix Tree.
class RadixTreeTabCompleter : public TabCompleter {
private:
//The radix tree should be stored here.
//...
public:
void BuildRadixTree(
const set<string> & all_strings)
{
//Build the radix tree.
//...
}
void Complete(
const string & input,
string & output,
bool & is_done,
bool & is_valid)
{
//Do the obvious thing.
//...
}
};

# Combining Tab Completers

Suppose we have two different
tab completers
T_{1} and
T_{2}.
The tab completer T_{1}
allows us to complete an input
string to an element of some
set S_{1},
and T_{2} allows us
to complete an input string to
an element of some set
S_{2}.
There is a very simple way in
which we can complete an input string
to an element of the union of
S_{1} and
S_{2}.
Namely, we take the
largest common initial segment
of the output of
T_{1} and
T_{2}
(provided they return valid
outputs).