Binary Delta CRUD

Update: this spec was moved to https://github.com/SkySpiral7/BinaryDeltaCrud/blob/trunk/docs/spec.md see that for the latest version.

I learned about the format of a (unified) patch file from the Unix command diff -u and was inspired to make a new delta format that is very compact, supports binary (it is not human readable), and is payload type agnostic. Since I don't know anything about this subject area I based this format on CRUD (Create, read, update, and delete) and so am calling this format Binary Delta CRUD. Note that the use of delta here is referring to math where delta is used to show change.

The scope of this doc is only for the delta format and not for describing the algorithm to analyze the data in order to create the delta. Analyzing the data is very important and the most complex step and would need it's own doc. However I don't know anything about how you would do this data analysis, there's no perfect solution to this problem, and you can read existing papers on compression and file comparison therefore I likely won't have a doc for such data analysis.

To describe this format I will use the names inputStream, deltaStream, and outputStream because the payloads might not be files (although files are the main use case I can think of). Note it is not required to know the number of bytes involved in a stream ahead of time as long as you know when it ends. The final operation in deltaStream will always have an operation size of 0 (explained later). Obviously each stream must be finite. It is possible to process the streams without needing to go backward: a buffer isn't needed if you are performing the operations normally (not reversed) or know the size of deltaStream. Note that all numbers in this specification are unsigned big endian where a * in binary means "any bit".

Each operation in the deltaStream starts with a single header byte which indicates which action to take and what to do with the bytes that follow. The outline of the header byte is: the highest 3 bits is the operation, the next bit (the lowest bit in the highest nibble) is an operation size flag, and the lowest nibble is a size (which might be the operation size).

The operations are:

0 (binary 000* ****) "add" operation (C in CRUD)

1 (binary 001* ****) "unchanged" operation (R in CRUD mnemonic)

2 (binary 010* ****) "replace" operation (U in CRUD)

3 (binary 011* ****) "remove" operation (D in CRUD)

4 (binary 100* ****) "reversible replace" operation

5 (binary 101* ****) "reversible remove" operation

6-7 [unused operations] 2 spots

If the operation size flag bit is 0 then the lowest nibble is the operation size (1 to 15 bytes). If the operation size flag bit is 1 then the lowest nibble is the size (1 to 15 bytes) of the operation size and the actual operation size (1 to 256^15 bytes) will follow the header byte. The operation size is the number of bytes that the operation will use. An operation size of 0 is infinite which means the operation will be performed on the remaining bytes then the program will terminate. When the operation size flag bit is 1 the operation size is allowed to have leading 0 bytes (although this is a waste of bytes in the deltaStream).

For example given a header (in binary) of: 0000 0010 means that 2 bytes will be added. A deltaStream that starts with 0011_0010 0000_0001 0000_0001 means that 257 bytes will be unchanged since the header indicated that the next 2 bytes should be used for the operation size.

"add" operation means that a number of bytes should be added to outputStream. The bytes that will be added will follow the operation size. It is invalid if deltaStream does not have enough bytes left.

"add remaining" is an "add" operation with an operation size of 0. It means that all of the bytes remaining in deltaStream should be added to outputStream then terminate. It is invalid for inputStream to contain any remaining bytes. It is invalid for deltaStream to not have any more bytes (since it failed to add anything).

"unchanged" operation means that a number of bytes should remain unchanged (ie read with no-op) simply copy them from inputStream into outputStream. No bytes will follow the operation size. It is invalid if inputStream does not have enough bytes left.

"remaining unchanged" (ie "done" or "no more changes") is an "unchanged" operation with an operation size of 0. It means that the remaining bytes in inputStream should be unchanged (copied to outputStream) then terminate. It is invalid for deltaStream to contain more bytes. It is permitted for inputStream to not have any more bytes (this allows an empty file to remain unchanged for example) since an empty set of bytes being unchanged is logically valid.

"replace" operation means that a number of bytes in deltaStream will replace the same number of bytes in the inputStream (ie add deltaStream bytes to outputStream and ignore bytes from inputStream). The new byte values will follow the operation size. Unlike "reversible replace" this operation is more compact but can't be undone since the previous byte values are unknown. It is invalid if inputStream or deltaStream do not have enough bytes left.

"replace remaining" is a "replace" operation with an operation size of 0. It means that all of the bytes remaining in deltaStream should replace the same number of bytes in inputStream then terminate (ie add rest of deltaStream to outputStream and ignore rest of inputStream). It is invalid if inputStream and deltaStream do not have the same number of remaining bytes. It is invalid if inputStream or deltaStream have no bytes left (since it failed to replace anything).

"remove" operation means that a number of bytes should be removed ie these bytes in inputStream should not go to the outputStream. No bytes will follow the operation size. Unlike "reversible remove" this operation is more compact but can't be undone since the previous byte values are unknown. It is invalid if inputStream does not have enough bytes left.

"remove remaining" (ie "close outputStream" or "write no more bytes") is a "remove" operation with an operation size of 0. It means that the remaining bytes in inputStream should be removed (not sent to outputStream) then terminate effectively making this a "close outputStream" operation since there is no more data to write (only thing left is to validate). It is invalid for deltaStream to contain more bytes. It is invalid for inputStream to not have any more bytes (since it failed to remove anything).

"reversible replace" operation is the same as "replace" except reversible and less compact. After the operation size there will be that number of bytes which are the old values then that number of bytes which are the new values. This exists so that after running through deltaStream normally you can later decide to undo the change by running the opposite of deltaStream (assuming deltaStream is a file or something that can be referenced again). Additionally this has a validity check built in since if the old bytes do not match inputStream then deltaStream is invalid. It is also invalid for inputStream or deltaStream to not have enough bytes left.

"reversible replace remaining" is a "reversible replace" operation with an operation size of 0. It means that the first half of the remaining bytes are the old values and the last half are the new values (see "reversible replace" for details) afterwards terminate. It is invalid for deltaStream to have an odd number of bytes left. It is invalid if deltaStream does not have exactly twice the number of bytes that remains in inputStream. It is invalid for inputStream or deltaStream to not have any more bytes (since it failed to replace anything). While is it possible to execute deltaStream as you get it (counting the bytes but not needing a buffer), trying to do the opposite of deltaStream will require you to read the rest of deltaStream first. As a quick proof: start counting while validating inputStream until it runs out (or fails validation) then count down while writing to outputStream until deltaStream runs out (or fails validation). If doing the opposite of deltaStream you won't know when to stop writing to outputStream unless you already know the number of bytes in deltaStream (in which case you won't need a buffer).

"reversible remove" operation is the same as "remove" except reversible and less compact. After the operation size there will be that number of bytes which are the old values. This exists so that after running through deltaStream normally you can later decide to undo the change by running the opposite of deltaStream (assuming deltaStream is a file or something that can be referenced again). Additionally this has a validity check built in since if the old bytes do not match inputStream then deltaStream is invalid. It is also invalid for inputStream or deltaStream to not have enough bytes left.

"reversible remove remaining" is a "reversible remove" operation with an operation size of 0. It means that all of the remaining bytes are the old values (see "reversible remove" for details) afterwards terminate. It is invalid if inputStream and deltaStream do not have the same number of remaining bytes. It is invalid for inputStream or deltaStream to not have any more bytes (since it failed to remove anything).

For a concrete example given that deltaStream contains (in binary): 0010_0101 0000_0010 0011_1000 0100_1110 0010_0000 translates to: unchanged with operation size 5, add with operation size 2, the first byte added is hex 38, the second byte added is hex 4E, done (keep the rest of inputStream). A shorter description (rather than a byte by byte one) is that the first 5 bytes are unchanged, add the hex bytes 38 and 4E, then the rest of the bytes in inputStream.

For an example of why the reversible operations exist: suppose I have a file named mainFile and a file named deltaFile. I run a program using mainFile as inputStream, mainFile as outputStream (writing to same file), and deltaFile as deltaStream. I examine the new state of mainFile and decide that I want it to return to the previous state (perhaps it failed quality control or checksum). I run a program using mainFile as inputStream, mainFile as outputStream (writing to same file), and deltaFile as deltaStream along with a flag that indicates that I would like a reverse done. If deltaFile does not contain any of replace or remove operations (including operation size of 0) then it is possible to restore mainFile back to the previous state by simply performing the opposite instruction in the deltaStream. This is useful for version control systems so that it can cause a file to go forward or back a version by only looking at a single delta (similar to git). This is likewise useful if you send out an update then later decide you need to rollback the change. For the sake of network compactness: a reversible delta can be created from a non-reversible delta while reading it (this requires a buffer the size of the largest replace operation).

The exact number of bytes for outputStream will be unknown until the deltaStream has been completely processed. The maximum sizeOf(outputStream) = sizeOf(inputStream) + sizeOf(deltaStream) - 2 - sizeOf(sizeOf(inputStream)) unless sizeOf(inputStream) is 15 or less in which case add 1 (counteracting the sizeOf sizeOf). This maximum can be achieved with a deltaStream of: unchanged, size of inputStream, add remaining, entire deltaStream.

Note that 64 bit computers only need 8 bytes to express the maximum file size (16 EiB exbibytes) which is expressible (in binary) ***1_1000 1111_1111 1111_1111 1111_1111 1111_1111 1111_1111 1111_1111 1111_1111 1111_1111. Notice that the maximum number of bytes supported for operation size is 15. 15 bytes for the operation size would mean the total size that can be handled with 1 header is 256^15 which is 1.3e36 bytes or 1.1e12 yobibytes. For any larger sizes you will need to perform the same operation multiple times (this will never be needed).

Warning: make sure you trust the deltaStream and have enough memory/disk space to handle the various operation size 0s. An attacker could send binary 0000 0000 followed by an endless stream of junk bytes in order to fill up the RAM or hard drive. That said it makes little sense to allow public access to change something using a deltaStream in the first place.

Does this format do better with a sparse or dense delta? It handles both very well. If an entire 4 GiB payload is being replaced (every byte changed) the overhead is only 1 byte (replace remaining, entire payload). If only a single byte is replaced in a 4 GiB payload the overhead is a maximum of only 7 bytes (unchanged size 4, 4 bytes op size, replace op size 1, new byte, done) with a minimum overhead of 2 bytes (replace op size 1, new byte, done). For an unchanged payload (of any size) the entire delta is 1 byte (done).

Does this format do better with plain text or binary payloads? The delta is not human readable. It is able to handle binary and text/plain is just a type of binary therefore it is agnostic to payload media type. Contrast a patch file which is designed to be human readable, can't handle binary, and includes info for the file name and date (ie it assumes a file system).

Can this format do everything a patch file can? No: this format doesn't handle file names or last modified timestamp (which are filesystem dependent). You could use this format 3 times for the name, modified timestamp, and file contents. Or you could use this format on a tar etc. For multiple files you can make a delta for each file (a delta can be add all or remove all for adding/removing files) or tar the files together and delta that. Which is to say that this format can do what you need but since it's payload agnostic (doesn't assume files) you'll need to do bookkeeping yourself in order to attach meaning.

I thought of operations for flipping the bits of the bytes or filling a length with a certain specified byte but the later is not in the spirit of a delta (that would be compression) and the former is questionable (there is still enough space for flipping if someone wants it) so I didn't.

I thought of an operation for paste (as in copy/paste) which would require a clipboard index to be setup at the beginning of the deltaStream. While this operation makes sense from a perspective of "how a human would edit something" this format isn't intended for human operations and this is another operation that seems like a compression thing.

Semantic versioning applications

A summary of Semantic versioning (see http://semver.org/ for more):

Given a version number MAJOR.MINOR.PATCH, increment the:

• MAJOR version when you make incompatible API changes,
• MINOR version when you add functionality in a backwards-compatible manner, and
• PATCH version when you make backwards-compatible bug fixes.

Above is the official definitions for the 3 integers in a semantic version number. I'm not going to talk about pre-release or build metadata labels (after the next paragraph). Also this document assumes that you are versioning your releases rather than releasing your versions which isn't better but makes this topic easier to discuss because it avoids release issues.

A snafu about patch is that people often use it for an additional meaning beyond the definition. The definition only names bug fixes but how do you track smaller changes? If I make a change that is not an incompatible API change, is not new functionality (from the client's perspective), and does not fix incorrect behavior then Semantic versioning can't track this change. Examples include removing dead code, updating the legal information, rewording text visible to clients, and updating versions of dependencies (only if invisible to clients). Pre-release isn't appropriate since the change could be released and build metadata can't be used since build metadata has no precedence. Which means that tracking this change requires either adding another integer to the version or changing the definition of existing integer(s). The common practice is to rename "patch" to "increment" changing the definition to "any change that isn't major or minor". For the rest of this document I will use increment with this definition.

Semantic versioning does not specify what this version number can be used for, it only provides a format definition with meaning and an order of precedence. So the whole point of this document is to talk about what semantic versioning can (or can't) be used for and what the meaning of "incompatible API" and "add functionality" are within a given context. There are many semantic versioning edge cases and while some may be covered the purpose of this document is to focus on what semantic versioning can be applied to. Additionally an API is generally only defined for expected behavior and therefore what happens when errors occur is not part of the API. Generally speaking an incompatible change means that what a client was doing is no longer supported and adding functionality means that a client can now do something that he previously could not (by these definitions changing a required field to be optional is a minor version).

Starting with the easiest I'll talk about the happy path that semantic versioning was likely made for: RESTful services. Specifically an entire RESTful service as a single black box with a defined API that clients use to make requests and receive responses. An incompatible API change occurs when the service makes a change such that a client is required to change (either request creation or response parsing) in order to continue getting the same behavior as before the service change. Adding functionality means that there is a new type of request, new optional fields in a request, or new fields in a response. An increment version would include removing dead code (since that isn't part of the API).

If the implementation of an API has a separate version number than the API and the API documentation does not use the same version as the API then the API can't make use of the increment version. Therefore it seems that semantic versioning was not intended to track an abstract API but rather an implementation that has an API (eg: why patch calls out "bug fix" which isn't possible for abstract APIs). Indeed the description of semantic versioning talks about packaged code (which would include implementation). In cases where the increment is lacking a placeholder 0 can be used so that the version can qualify as semantic (as long as major and minor meet requirements). In cases where the API documentation is tied to the API version number then updating documentation (such as rewording or correcting spelling mistakes) is considered an increment. In cases where the API implementation is tied to the API version number then things like refactoring or removing dead code is an increment.

Similar but more granular is semantic versioning for a single RESTful endpoint (request/response). The URI, HTTP method, and some of the headers (specifically Accept) are used to define a single endpoint. Examples of an incompatible API change includes changing the URI or request body. Now the interesting thing is: if I have a RESTful service that supports multiple types of requests each with a semantic version then what is the version of the service as a whole? Depending on the setup it is possible that the entire service doesn't need a version however let's suppose it does require a version because the service as a whole is a maven artifact. An incompatible API change for the service as a whole is the same whether the individual requests have semantic versioning or not. Whenever any endpoint increments a version the whole service does as well. If multiple endpoints are changing then the service increments a single number of the highest type used (major, minor, or increment). So if the Alice endpoint increases 2 major versions and Bob increases a minor version within a single release of the service then the service increases the major version once. Note that the service version generally won't match any endpoint version. Removing an endpoint is an incompatible API change (major version) and adding an endpoint is new functionality (minor version) to the service version.

What if a service supports multiple versions of a single RESTful endpoint? The endpoint version is handled normally and is agnostic to whether or not other versions of itself will exist. Removing support for a version of an endpoint is an incompatible API change (major version) and adding support for a version of an endpoint is new functionality (minor version) to the service version. If all of the endpoints are grouped into a single semantic version and a service supports multiple versions of that then the exact same principles apply (since the API of a service is the union of all supported versions of all endpoints). If any version that the service supports is increased then the version of the service is increased in the same way.

What about a server storing documents client side? The service mandates the file format of the document so it is considered the same as any endpoint. For example if a client is able to download his session and later upload it to regain the state he previously had then the upload is just like any other endpoint with the session file being the body. The same principle can be applied to saving files to databases or file systems if anything else has access to it. If your service has exclusive access to these files or database tables then it could be considered an implementation detail and any change would be a increment version. This is true if the document is JSON or a docx. In order to version the document itself rather than just how it is used continue reading.

What about a software library? All exposed code is part of the API (eg public classes). All private code and dependencies are not part of the API. Semantic versioning is used as normal.

What about a maven artifact that pulls in an API artifact? The main artifact is either a library or a service. Either way the service has a version number based on the API but separate from it. It does not matter whether the API artifact uses the same version as the version of the API itself. The API artifact is considered part of the service's API rather than an implementation detail like other dependencies are because it is exposed to be used.

What about something like a web browser? If the program only supports HTTP 1.0 then adding support for HTTP 1.1 is a functionality (minor version) and removing support for HTTP 1.0 is an incompatible change (major version). Likewise for HTML versions, CSS versions, etc. This is also true for browser plugins so the plugin API should have its own version for simplicity. This will lead to a browser having tons of semantic versions that it uses and a single overall semantic version with the overall semantic version not being very useful.

What about programs that support multiple operating systems? Nope, semantic versioning breaks down and can't be used as-is. There would be a core program with semantic versioning, an OS with semantic versioning, and a bridge that connects them which can't have semantic versioning. The core program's version includes the API to talking to the bridge and OS version is for the API that the bridge talks to. The problem is that there needs to be a bridge for each OS name and major version. So if the OS is Alice OS 10.1.2 the bridge can require at least Alice OS 10.0.0 and aggregate that together with the core program semantic version to get a semantic version so that the bridge version would be "Alice OS 10 bridge version 1.2.3" at a minimum. It would be a good idea to include the entire OS version to allow supporting more combinations. Of course it should also tell the user what the core version is. This setup allows the core program to be upgraded on each supported OS while maintaining unique numbers for the bridge. This same system is true for any adapter or facade such as a kernel which allows a shell to talk to the hardware: if there is more than 1 adapter then the adapter's name or version needs to state which thing and version of it that the adapter is adapting to.

What if the user can change the dependency versions as he desires? For example if an OS has semantic versioning when a user upgrades the version of a downloaded program then the OS version doesn't change because the OS version is the version of the API that programs use to talk to the OS.

What about programs like Microsoft Word where the user's document (in a standardized format) is also the primary purpose of the program? The file is treated like any other API in that the file contents as a whole has a version number (whether stored in the file or not) so if the program supports that document then the program edits the file without issue otherwise the program tells the user that the program can't open the file. Any file that can be edited can be saved in that same format or converted to a different file type. Since the file is standardized, complications occur when the same file is used by programs that support different versions of the standard format or if the file contains something that isn't part of the file version (see next topics).

How can a program account for a request for something that may or may not be supported? For example HTML 5 allows images tags to be .png or .jpg but a browser might not support both image formats because the image format is not part of the HTML version nor can there be any kind of image format version (although .png itself could have versions). The list of image formats support is part of the browser version but is not part of the HTML version. The browser version also includes the list of which .png versions are supported etc.

If multiple programs edit the same file and each program supports different versions of the standard format that the file is in, what happens? If the standard format is the same major version then the file uses the lowest version that supports the file contents. If the standard format major version number is different then it is treated as though it was an unrelated standardized format.

How much of the version number should be in the client's request or stored document? If it doesn't contain the major version number then the best the program can do is attempt the operation and if it fails tell the client "bad request/corrupted file or wrong major version number. Not sure which.". Additionally without a major version number it would be difficult for a service/program to support multiple major versions. If the client has a major and minor version number that is ahead of the service/program then the program can perform the function and return the result with a warning "You asked for X but I used Y. Therefore this is a partial response and is missing functionality that you might require.". This is likewise true for increment version with the warning "My response might contain a bug". If the client doesn't care about a feature or isn't tracking increment versions then he can simply send a 0 for those numbers. There are 2 reasons for a client to send non-0 version numbers: one reason is that if there are multiple versions of the service running (such as during an upgrade) then the request routing can make sure that the clients expecting the newest version go to the newest service etc. The other reason is so that the client gets a more specific warning or error message in the case of mismatch.

Does an increment version exist for stored documents? No. It could trigger a warning if the parser doesn't support that version however it doesn't make sense for the document to say "if you don't have this version then your parser has a bug". Unlike an API increment version there isn't any internal implementation details so I can't name any way for the format to have an increment version. For example the specification for YAML had things added to it in a backwards compatible way so major and minor numbers make sense but an increment number doesn't.

Can a computer language have semantic versioning? The language syntax is the same as any other file so no: only major and minor. The compiler, IDE, etc can have full semantic versioning.

Can a human language have semantic versioning? Not quite (even for synthetic languages). Incompatibility could be defined as "does this retain the same meaning" which would mean that any word or grammar that is dropped or changed would be incompatible. New words and new definitions to existing words could be added as "new functionality" but an increment number doesn't make sense. Grammar rules can't really be changed since that likely invalidates previously legal statements. For natural languages versioning of any kind is impossible due to the chaotic definition. A synthetic language could use versioning but would just use major and minor.

Can hardware have semantic versioning? No but I don't know enough about hardware. If switching from 1 Microsoft mouse to a newer one can use the same drivers etc then it wasn't a major version change. But I don't think that's possible: everything has unique drivers. While "new functionality" is subjective there isn't any type of increment version number that would make sense. For devices that don't connect to others like a non-smart digital watch then there's nothing to be incompatible with (watch battery type?) and the versioning breaks down. What about a standard port like USB 3.0? If the name was instead 1.3 then it would be nearly semantic but there's still no increment version so it isn't semantic.

Can a game like Dungeons and Dragons use semantic versioning? Not quite. Expansion books could be considered added functionality but there's no order and any combination of them can be used so the version of the core rules can't use them. Considering only the core rules a player character sheet could be used to test incompatibility obviously a breaking change occurs when the decisions made on a character sheet are no longer legal. But what about game play? Generally if any of the rules for a game changes then it isn't the same game anymore which is especially important for games like D&D where there's plenty of time for the game to change between sessions even though the same character sheet is used again (albeit altered). But that criteria is very strict and while it is possible to make an additive change, most changes would be breaking which would make semantic version useless. A more useful numbering would be more like major version for "very serious change that you likely can't use the same character sheet at all" and a minor for "every other change (might require character sheet changes)" which is what D&D did with 3.5 edition (granted it should have been 3.1) but isn't semantic.

Can a printed novel like Lord of the Rings use semantic versioning? No. The content of the book is informational and that information can't change without it being different information and therefore everything would be an incompatible change. Realistically books are allowed to reword small things between editions of a book which sounds like justification for a major version number rather than being considered a whole new book. Spelling mistakes could be considered an increment version number but "adding functionality" has no meaning to books. This is why books use a single number which is edition along with descriptive text like "hard back", "pictures are printed in color", or "includes a map".

Semantic versioning also can't be used for things like blueprints for a book shelf, cooking recipes, telescopes, vehicle safety standards, governmental laws.

To summarize semantic versioning can be used for all software except adapters and can't be used for things that aren't software (not even software specifications or abstract APIs).

Sorting Algorithms: Ascii, Alphabetical, and Title

It bugs me when I see people use the phrases "sort alphabetically" and "ascii sort" or "by character code" interchangeably, they are not the same thing. But instead of ranting about it I decided to define them. I will be assuming all sorts are ascending. The definition for Ascii is fairly well accepted and this is the simplest sort.

Sort by Character code

Input must only be strings of known length.

Compare the character codes of each character until they are different at which point the lower code number comes first. If one string starts with the other then the shorter string comes first. Note that this includes the null character.

Implementation problem: some programming languages use null terminated strings but this sorting algorithm allows null within the string therefore special care will be needed.

Note that the algorithm can correctly sort strings of any fixed width character encoded without needing to know how to read the characters. Variable width character encoding, on the other hand, would need to be interpreted to get the correct order. Because of the ability to handle other encodings beyond ascii it would more accurately be called character code sorting.

Here is a javascript implementation for it (javascript allows nulls in strings):
function characterCodeAscending(a,b)
{
   for (var i=0; i < a.length; i++)
   {
       if(i >= b.length) return 1;
       if(a.charAt(i) !== b.charAt(i)) return (a.charCodeAt(i) - b.charCodeAt(i));
   }
    if(b.length > a.length) return -1;
    return 0;
}
//that was for the sake of illustration. for brevity use this instead:
function compareTo(a,b)
{
    if(a === b) return 0;
    if(a > b) return 1;
    return -1;
}

Alphabetical sort algorithm definition.

Input must only be strings of known length. Strings can't contain non-printable characters (such as null). Case is ignored and the rest is the same as character code sorting. This definition is accepted as far as I know.

Since strings don't normally contain non-printable characters the similarity of definitions is why people sometimes confuse them. But the big difference between them is that Alphabetical is case insensitive. This means that "STRING VALUE" has the same order as "string value".

Note that null terminated strings don't need special handling for alphabetical. But encoding must always be known to determine upper and lower case.

javascript implementation (input is not validated for printable characters):
function alphabetical(a,b){return compareTo(a.toLowerCase(),b.toLowerCase());}  //see above for compareTo definition

Book Title sort algorithm definition.

It is used for books, movies, and other media. Input must only be strings of known length. Strings can't contain non-printable characters (such as null). The only whitespace allowed is a space. A space may not be next to another space. Trailing and leading spaces are not allowed. Start with the definition for alphabetical with some differences.

Punctuation is ignored, only alphabetical and numeric symbols are used when determining order. Eg, "Joe's?" is the same as "j!O,e...s". What is considered alphabetical is determined by the language (linguistic). Note that the number of alphanumeric characters must be counted to determine the effective string length.

Leading articles are ignored: "a", "an", and "the". If the string starts with one of these 3 articles (or equivalent if not using English) it will be ignored for name comparison. Only the first word will be ignored and only if it contains at least 2 words. Eg, "The the name" only ignores the first word but for "The" and "But I..." nothing is ignored. If 2 titles differ only by leading article then they should be sorted with the article included thus "The Wind" will come before "Wind".

Titles should be split by the first colon. The part before the colon is the series name and the part after is the subtitle. The subtitle is ignored unless the series name is the same. If a colon does not exist then the entire thing is considered the series name. The series name may end in a number in which case they should be sorted numerically ascending. For example "1999 Encyclopedia Volume 2" comes before "1999 Encyclopedia Volume 10" even though alphabetically 10 comes before 2. This should take into account any numbering system such as Roman numerals, numeric, and numbers as words. Humans can do their best to determine the numbering system but this is where computer implementation becomes impossible. If the series names are the same then the subtitle is compared alphabetically (not via title sort, eg do not ignore the word "the" etc). A series name that does not have a number should come first (ie be considered 1).

Example difficulties. There is a video game named "Final Fantasy X-2" (ten two) it is a sequel to ten but is not related to eleven, a human would sort them "Final Fantasy X", "Final Fantasy X-2", "Final Fantasy XI" (apparently FF11 has a box). But even if a computer recognized the Roman numeral numbering it would see "X-2" as unrelated text and place it before all of the ones in the number sequence (it would actually make more sense to have "-2" be the subtitle and therefore be placed after 10). These Metal Gear Solid games should be in this order:
Metal Gear
Metal Gear 2: Solid Snake
Metal Gear Rising: Revengeance
Metal Gear Solid
Metal Gear Solid: Peace Walker
Metal Gear Solid 2: Sons of Liberty
Metal Gear Solid 3: Snake Eater
Metal Gear Solid 4: Guns of the Patriots
Metal Gear Solid V: Ground Zeroes
Metal Gear Solid V: The Phantom Pain
A title without a numeric should be considered 1 (or rather negative infinity). Notice how it switches from numeric digits to Roman numerals and how there are 2 "Metal Gear Solid V"s (and 1s even though Peace Walker isn't actually).

Despite these programmatic difficulties the algorithm should not go to great lengths to account for everything. It is impossible to account for all possible scenarios therefore use a fairly simple algorithm and then manually rearrange the exceptions afterwards.

Here is a javascript implementation for Book Title sorting. It only uses non-extended ascii and is English.
function titleSort(titleA, titleB)
{
    var stripA = titleA.toLowerCase().replace(/[^a-z0-9 :]/g, '').trim().replace(/ +/g, ' ');
    var stripB = titleB.toLowerCase().replace(/[^a-z0-9 :]/g, '').trim().replace(/ +/g, ' ');

    if(stripA !== stripB && stripA.replace(/^(?:an?|the) /, '') === stripB.replace(/^(?:an?|the) /, '')) return compareTo(stripA, stripB);
    stripA = stripA.replace(/^(?:an?|the) /, '');
    stripB = stripB.replace(/^(?:an?|the) /, '');

    var seriesA, seriesB, subA, subB;
   if (stripA.indexOf(':') !== -1)
   {
       seriesA = stripA.split(':')[0];
       subA = stripA.substr(stripA.indexOf(':')+1);
   }
    else{seriesA = stripA; subA = '';}
   if (stripB.indexOf(':') !== -1)
   {
       seriesB = stripB.split(':')[0];
       subB = stripB.substr(stripB.indexOf(':')+1);
   }
    else{seriesB = stripB; subB = '';}

    var numberA, numberB;

    if((/\d+$/).test(seriesA)){numberA = parseInt((/ (\d+)$/).exec(seriesA)[1]); seriesA = seriesA.replace(/ \d+$/, '');}
    else numberA = -Infinity;
    if((/\d+$/).test(seriesB)){numberB = parseInt((/ (\d+)$/).exec(seriesB)[1]); seriesB = seriesB.replace(/ \d+$/, '');}
    else numberB = -Infinity;

    if(seriesA !== seriesB) return compareTo(seriesA, seriesB);
    if(numberA !== numberB) return compareTo(numberA, numberB);
    //only if from the same series. don't subtract due to -Infinity
    //note that if you have different numbering schemes then set numberA/B to the numeric value for comparison sake

    return compareTo(subA, subB);
    //see above for compareTo definition
}

//This one has too much meat for plain text so paste it into a syntax highlighter.