How do you implement an auto-complete feature?

There is not an infinite set of words out there.

Let’s say we have these words:

lady
ladybird
land
laser
laserbeam
laserface
lasergun
lemon
lemons
less
lesson
lord
lordhuron

When we get l, we return:

lady
ladybird
land
laser
laserbeam
laserface
lasergun
lemon
lemons
less
lesson
lord
lordhuron

le returns:

lemon
lemons
less
lesson

lem returns:

lemon
lemons

We would use a tree structure to store the options.

l
    a
        d
            y
                .
                b
                    i
                        r
                            d
                                .
        n
            d
                .
        s
            e
                r
                    .
                    b
                        e
                            a
                                m
                                    .
                    f
                        a
                            c
                                e
                                    .
                    g
                        u
                            n
                                .
    e
        m
            o
                n
                    .
                    s
                        .
        s
            s
                .
                o
                    n
                        .
    o
        r
            d
                .

                h
                    u
                        r
                            o
                                n
                                    .

There would need to be a special value to indicate the end of a path, . in this case. We’ll use some input to navitage down the tree. From any point, we can see which branches remain from there that terminate with .. Those are our values.

If we get las as input, we start from here:

        s
            e
                r
                    .
                    b
                        e
                            a
                                m
                                    .
                    f
                        a
                            c
                                e
                                    .
                    g
                        u
                            n
                                .

If we trace out each branch, we get:

laser.
laserbeam.
laserface.
lasergun.

I don’t know if this is the fastest approach, but it should work. Let’s see.

…

Yep, seems to work alright.

https://github.com/reergymerej/suggest

Let’s see what the “proper” way is to do this now…