Listing Available Package Versions in Ubuntu: The “Madison” Subcommand

There is an unlisted subcommand to apt-cache called “madison”. This will simply list all available versions:

$ apt-cache madison git
git | 1:2.11.0-2~ppa0~ubuntu14.04.1 | trusty/main amd64 Packages
git | 1:1.9.1-1ubuntu0.3 | trusty-updates/main amd64 Packages
git | 1:1.9.1-1ubuntu0.3 | trusty-security/main amd64 Packages
git | 1:1.9.1-1 | trusty/main amd64 Packages
git | 1:1.9.1-1 | trusty/main Sources
git | 1:1.9.1-1ubuntu0.3 | trusty-updates/main Sources
git | 1:1.9.1-1ubuntu0.3 | trusty-security/main Sources

In all likelihood this will work under Debian, too.


Disabling the Touchscreen under Linux/X11

I am specifically using Ubuntu, but it does not matter as long as you have the xinput tool installed.

At the command-line, run xinput --list to list all of your HID devices:

$ xinput --list
⎡ Virtual core pointer                      id=2    [master pointer  (3)]
⎜   ↳ Virtual core XTEST pointer                id=4    [slave  pointer  (2)]
⎜   ↳ SynPS/2 Synaptics TouchPad                id=13   [slave  pointer  (2)]
⎜   ↳ eGalax Inc. eGalaxTouch EXC7910-1026-13.00.00 id=10   [slave  pointer  (2)]
⎣ Virtual core keyboard                     id=3    [master keyboard (2)]
    ↳ Virtual core XTEST keyboard               id=5    [slave  keyboard (3)]
    ↳ Power Button                              id=6    [slave  keyboard (3)]
    ↳ Video Bus                                 id=7    [slave  keyboard (3)]
    ↳ Sleep Button                              id=8    [slave  keyboard (3)]
    ↳ Lenovo EasyCamera                         id=9    [slave  keyboard (3)]
    ↳ Ideapad extra buttons                     id=11   [slave  keyboard (3)]

Identify the ID of the one that corresponds to your screen. Disable it:

$ sudo xinput disable 10
[sudo] password for dustin: 

To make the change permanent, add the second command to a script in /etc/X11/Xsession.d (e.g. “98disablexinput”):


xinput disable 10

Space-Filling Curves to Map Multidimensional Data to a Single Dimension

A space-filling curve (SFC) is, essentially, a line that bends through a space and hits every point. It was made possible by a proof created by Georg Cantor in the late 1800s. You can then map a coordinate in N-dimensions on to it to determine a single, identifying, scalar index. Google’s S2 library uses a specific SFC called a Hilbert curve (which is a fractal) and some other tricks to map geographic coordinates to a single 64-bit integer. This has the characteristic of assigning any coordinate within the same locality a very similar index; the closer the points are, the more of the prefix will be the same. Indeed, the difference between one SFC and another is, physically, how the curve bends and, ultimately, how it preserves locality. Hilbert is most popular for this though it is not the simplest SFC. For a list of various curves, look in the “See also” section of the Wikipedia page. Each of those references shows illustrations of what the curves look like.

As far as the index produced by S2, you can compare smaller, finer areas and larger, rougher areas by comparing a larger prefix or a smaller prefix, respectively. This not only allows you to easily search an index for places in a specific area but to also implicitly determine if one area contains another.

If you are interested in the mechanics of S2 (the Go version), the mapping magic happens in the following progression.

First, convert the LatLng to a Point (which just encapsulates a vector type provided by the R3 sibling project for three-dimensional coordinate systems):

func PointFromLatLng(ll LatLng) Point {
    phi := ll.Lat.Radians()
    theta := ll.Lng.Radians()
    cosphi := math.Cos(phi)
    return Point{r3.Vector{math.Cos(theta) * cosphi, math.Sin(theta) * cosphi, math.Sin(phi)}}

Second, convert the Point to face coordinates:

func cellIDFromPoint(p Point) CellID {
    f, u, v := xyzToFaceUV(r3.Vector{p.X, p.Y, p.Z})
    i := stToIJ(uvToST(u))
    j := stToIJ(uvToST(v))
    return cellIDFromFaceIJ(f, i, j)

Third, convert the face coordinates to the one-dimensional index (a 64-bit integer aliased as the CellID type):

func cellIDFromFaceIJ(f, i, j int) CellID {
    // Note that this value gets shifted one bit to the left at the end
    // of the function.
    n := uint64(f) <= 0; k-- {
        mask := (1 <>uint(k*lookupBits))&mask) <>uint(k*lookupBits))&mask) <>2) << (uint(k) * 2 * lookupBits)
        bits &= (swapMask | invertMask)
    return CellID(n*2 + 1)

There is also the function that allows you to step along the curve, which is very inexpensive:

func (ci CellID) AdvanceWrap(steps int64) CellID {
    if steps == 0 {
        return ci

    // We clamp the number of steps if necessary to ensure that we do not
    // advance past the End() or before the Begin() of this level.
    shift := uint(2*(maxLevel-ci.Level()) + 1)
    if steps > shift); steps > shift)
            steps %= wrap
            if steps > shift); steps > max {
            wrap := int64(wrapOffset >> shift)
            steps %= wrap
            if steps > max {
                steps -= wrap

    // If steps is negative, then shifting it left has undefined behavior.
    // Cast to uint64 for a 2's complement answer.
    return CellID(uint64(ci) + (uint64(steps) << shift))

The S2 project has its own Hilbert implementation. To see an implementation that excludes all of the sphere mechanics (the presence of which makes things considerably more complicated), see Google’s hilbert (Go implementation) project.

Space-filling functions are a fantastically-useful method for clustering anything that you might have a requirement for, though you might need a mathematician to come up with a process to adjust your coordinates if they are not initially acceptable as inputs (the qualification of which might also require said mathematician). Also, SFCs are non-injective: The index that you get is not necessarily unique for any two coordinates, though, in such a situation, you are guaranteed that two coordinates resulting in an identical index would basically have to be very similar themselves (the accuracy of this depends on which SFC you use).

For reference, there also exists a reversible geographic-to-string conversion library called Geohash (also here). However, this does not use SFCs and, I believe, suffers from distortion either over the equator or for great distances though I am having trouble finding where I saw that, just now. The Hilbert/S2 approach does not have this problem.

Google’s S2, geometry on the sphere, cells and Hilbert curve (great article)

Space-filling curve

Peano curve (the first known space-filling curve)

Analysis of the Clustering Properties of Hilbert Space-filling Curve (paper)

Mapping N-dimensional value to a point on Hilbert curve (SO)

S2 (Go package)

Resolving Go Import URLs

The package path that you import may not directly correlate to a repository URL. If Go can not find the package in your GOPATH, it will load the URL, redirecting as necessary, and will either look for a “meta” tag with a “name” attribute having value “go-import” or take whatever URL we are at when no more HTTP redirects are necessary (if any).

To speed things up, I wrote a short Python tool to do this and stashed it in a gist.

Make sure to install the dependencies:

  • requests
  • beautifulsoup4


import sys
import argparse
import urllib.parse

import requests
import bs4

def _get_cycle(url):
    while 1:
        print("Reading: {}".format(url))

        r = requests.get(url, allow_redirects=False)

        bs = bs4.BeautifulSoup(r.text, 'html.parser')

        def meta_filter(tag): 
            # We're looking for meta-tags like this:
            # <meta name="go-import" content=" git">
            return \
       == 'meta' and \
                tag.attrs.get('name') == 'go-import'

        for m in bs.find_all(meta_filter):
            phrase = m.attrs['content']
            _, vcs, repo_url_root = phrase.split(' ')
            if vcs != 'git':

            return repo_url_root

        next_url = r.headers.get('Location')
        if next_url is None:

        p = urllib.parse.urlparse(next_url)
        if p.netloc == '':
            # Take the schema, hostname, and port from the last URL.
            p2 = urllib.parse.urlparse(url)
            updated_url = '{}://{}{}'.format(p2.scheme, p2.netloc, next_url)
            print("  [{}] => [{}]".format(next_url, updated_url))

            url = updated_url
            url = next_url

    return url

def _main():
    description = "Determine the import URL for the given Go import path"
    parser = argparse.ArgumentParser(description=description)
        help='Go import path')

    args = parser.parse_args()

    initial_url = "https://{}".format(args.import_path)
    final_url = _get_cycle(initial_url)

    print("Final URL: [{}]".format(final_url))

if __name__ == '__main__':

Geometric Hashing

Like clustering (but in the backwards Bizarro World):

This principle is widely used in computer graphics, computational geometry and many other disciplines, to solve many proximity problems in the plane or in three-dimensional space, such as finding closest pairs in a set of points, similar shapes in a list of shapes, similar images in an image database, and so on. In these applications, the set of all inputs is some sort of metric space, and the hashing function can be interpreted as a partition of that space into a grid of cells. The table is often an array with two or more indices (called a grid file, grid index, bucket grid, and similar names), and the hash function returns an index tuple. This special case of hashing is known as geometric hashing or the grid method. Geometric hashing is also used in telecommunications (usually under the name vector quantization) to encode and compress multi-dimensional signals.

I could not find a sample/pseudocode implementation quickly.



Hash function