Random Testing (RT) is a fundamental software testing technique. Adaptive Random Testing (ART) improves the fault-detection capability of RT by employing the location information of previously executed test cases. Compared with RT, test cases generated in ART are more evenly spread across the input domain. ART has conventionally been applied to programs that have only numerical input types, because the distance between numerical inputs is readily measurable. The vast majority of computer programs, however, involve non-numerical inputs. To apply ART to these programs requires the development of effective new distance measures. Different from those measures that focus on the concrete values of program inputs, in this paper we propose a method to measure the distance using coverage information. The proposed method enables ART to be applied to all kinds of programs regardless of their input types. Empirical studies are further conducted for the branch coverage Manhattan distance measure using the replace and space programs. Experimental results show that, compared with RT, the proposed method significantly reduces the number of test cases required to detect the first failure. This method can be directly applied to prioritize regression test cases, and can also be incorporated into code-based and model-based test case generation tools.