by Malcolm Phillips
This page contains some of my most complete and re-usable C++ work, most of which I still actively maintain.
What's this you may ask? It's the algorithm typically used for a spelling suggestor in real programs. It's not limited to words that start with the same letter or anything like that. It simply calculates how many changes it would take to turn word A into word B. The words in your list which require the fewest changes are most likely the intended word. This version is optimised to use less memory than any other implementation out there, and has plenty of speed.LevenshteinDistance.h
This file contains new kinds of standard library containers. There are variants of set, multiset, map and multimap where the underlying storage is in a vector, and the items are not normally in fully sorted order. If you don't care about sortedness, care strongly about memory usage, or want something faster (except for erasing), then this class should work well for you.
Sometimes you don't need as much accuracy as a float has, and would like to conserve memory usage by storing floating-point values in just 16-bits. This is great for halving memory used by a height-map for example. This class simply wraps the ultra-fast table-driven implementation by Jeroen van der Zijp, designed as a drop-in replacement for a float.
Bigint is a class for handling large integers. Basically it gives you the means of effectively having an integer data type that is as large as you want. Need a 128-bit / 256-bit / 2048-bit integer etc - no problem, use bigint. Bigint is designed to work as close to a real integer of the specified size as possible. The memory layout is exactly how a built-in type of the specified size would be. It even contains signed bigints if you want negatives. The source file contains ubigint and sbigint, for unsigned and signed numbers respectively. Due to popular demand, this file has been updated a lot over the years and is now very competitive in performance with any other such libraries. I also make the claim that it easier to use (and understand) than any other such library.
VarBigint is a class for handling variable-sized large integers. It is much like BigInt above, except that the amount of memory used by the class is variable, using dynamic memory allocation. This is very useful when you don't know ahead of time how big the number is going to be. However, the number is still stored in two's-complement form, meaning that you can also 'and', 'or', and 'xor' etc, and get the results you'd expect with regular ints, even when the two objects are holding integers of different lengths. Update 1st September: This class has now been split into signed (svarbigint) and unsigned (uvarbigint) versions, for those that do not need to deal with signed values. The original class has now been deprecated, but is still available as the typedef varbigint.
uvarbigint.cpp uvarbigint.h svarbigint.cpp svarbigint.h
Just in case you thought I didn't already have enough bigint classes, allow me to introduce stringint. Stringint is another class for handling variable-sized large integers. This one stores the data internally as a string, rather than in binary. It is primarily for values which are constructed from a string, or displayed, a lot more than you do maths on them because most non-trivial operations e.g. division, are significantly slower.
Part of my hobby software 3D engine, this file contains the guts of my policy-based-design pixel manipulation routines for 32bit(8,8,8), 24bit(8,8,8), 16bit(5,6,5), 16bit(5,5,5), 8bit(3,3,2), 8bit(6*6*6), and 8bit(greyscale) images. Contains some nice stuff such as bilinear interpolation (bilerp) in both heavily optimised C++, or in some cases MMX. 16bit bilerp using only 3 multiplies! Fast and fully accurate conversions between all the above colour depths. Pattern dithering routines for when reducing the bit depth of an entire image. Lots of insanely optimised goodies!
This class is for representing and manipulating values that no built-in type can handle, such as 1/3rd.With this class you can do all sorts of maths on fractions without any fear of inaccuracy due to limited precision of the float or double data types. You could even combine this with bigint or varbigint to have fractions with very large, or arbitrarily large numerators and denominators.
This file contains all sorts of Universal and non-universal encoding and decoding algorithms. These algorithms are used for compressing values where the larger a number is, the less often it comes up, and when the largest value isn't necessarily known in advance. Fibonacci and Tribonacci encoding are my personal favourites here. They work pretty good on values up to about the 16-bit and 32-bit range. Some of these I have adapted for supplying as code examples on Wikipedia.
Thanks to the bigint class above, this class is able to represent extra-large floating point data types. Need an extremely accurate 256-bit floating point data type? No problem, use megafloat.
This is basically a class for representing fixed-point values of various sizes, and various numbers of whole and real bits.
The purpose of this class is to enable use of algorithms written specifically for a big-endian processor to be used on a little-endian processor, or vice-versa. It was used in the development and testing of the bigInt class above.
I wrote this because it seems to be quite a common programming problem that a lot of people have dificulties with. It contains a function for converting a number such as 31415 to the string "thirty one thousand four hundred and fifteen". It also contains functions for converting to and from Roman Numerals, including with perfectly accurate validation.
Late 2008 I gave in and decided to write my own Sudoku solver. This takes at most a couple of milliseconds to solve a board. I've also included a method for determining if there are multiple solutions to a board, and a function to generate a (hopefully) human-solvable Sudoku board. It works with 9x9, 16x16, and 25x25 board sizes.
I wrote this one for my wife who was busy designing a website that needed to show the areas of local districts, allowing users to select their area. My full application had to extract the data from an XML file, reduce the number of points, perform an affine transformation between coordinate systems, and finally encode the polygon areas into google ployline encoded data. The rest of the code was just kind of thrown together, but I put some effort into producing a tidy class for the encoding. A decoder is included as well.
Okay so every man and his dog has written a function for testing if a number is prime right? Most people's implementations are pretty damn slow. I don't claim mine are the fastest, but they're pretty good for their size. This file includes implementations of 3 different methods, and each one outputs a vector of all primes less than the input value.
I wrote this to demonstrate how to replace a large voxel map with a smaller trie structure with fast log(k) lookups. Can be modified for use in implementing any sparse type of array. E.g. a 2D array of size 1 million squared.
If you're familiar with Pascal or Delphi and want the ability to have an integral data type that only allows values in a specific range, then this class is for you. An exception is thrown when the variable is made to contain an out of range value.
This class was designed to be a high-performance vector (and matrix) class for any size vector. It uses expression templates to reduce instances of code that creates temporary values.