{{Short description|Computing operation which compares two values}} In computer science, a '''three-way comparison''' takes two values A and B belonging to a type with a total order and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical law of trichotomy.
It can be implemented in terms of a function (such as <code>strcmp</code> in C), a method (such as <code>compareTo</code> in Java), or an operator (such as the '''spaceship operator''' <code><=></code> in Perl, PHP and C++).
== Machine-level computation == Most processors have instruction sets that support such an operation on primitive types. On some machines the compare instructions set flags{{efn|Different machines have different nomenclature; some common terms are ''condiftion code'', ''flag'', ''indicator'' and ''status''.}} that can be tested by subsequent conditional branch instructions.{{efn|E.g., Compare with A (CMPA), Compare with Q (CMPQ), Compare with AQ (CMPAQ), Compare with X<sub>n</sub> (CMPXn), Compare with Limits (CWL), Compare Magnitude (CMG), on the GE 635<ref>{{cite book | title = GE-635 Programming Reference Manual | id = CPB-1004 | date = July 1964 | pages = II-83-II-88 | section = Comparison--Compare | section-url = https://www.bitsavers.org/pdf/ge/GE-6xx/CPB-1004_GE-635_Prog_Ref_Man_196407.pdf#page=102 | series = THE COMPATIBLES/600 | publisher = GE | url = https://www.bitsavers.org/pdf/ge/GE-6xx/CPB-1004_GE-635_Prog_Ref_Man_196407.pdf | access-date = April 6, 2025 }} </ref>}}
On some word-oriented machines the compare instructions are skips, continuing at PC, PC+1 or PC+2 depending on the result of the compare.{{efn|E.g. Compare accumulator to storage (CAS) and compare Logical accumulator to storage (LAS) on the IBM 7094.<ref>{{cite book | title = IBM 7094 Principles of operation | id = A22-6703-4 | section = Control instructions | section-url = http://bitsavers.org/pdf/ibm/7094/A22-6703-4_7094_PoO_Oct66.pdf#page=45 | page = [http://bitsavers.org/pdf/ibm/7094/A22-6703-4_7094_PoO_Oct66.pdf#page=53 53] | url = http://bitsavers.org/pdf/ibm/7094/A22-6703-4_7094_PoO_Oct66.pdf | series = Systems reference library | access-date = September 22, 2025 }} </ref>}} Most of these machies also have conditional branch instructions.
Some machines have signed integers based on a sign-and-magnitude or ones' complement representation (see signed number representations), both of which allow a differentiated positive and negative zero. This does not violate trichotomy as long as a consistent total order is adopted: either −0 = +0 or −0 < +0 is valid. Common floating point types, however, have an exception to trichotomy: there is a special value "NaN" (not a number) such that ''x'' < NaN, ''x'' > NaN, and ''x'' = NaN are all false for all floating-point values ''x'' (including NaN itself).
== High-level languages == === Abilities === In C, the functions <code>strcmp</code> and <code>memcmp</code> perform a three-way comparison between strings and memory buffers, respectively. They return a negative number when the first argument is lexicographically smaller than the second, zero when the arguments are equal, and a positive number otherwise. This convention of returning the "sign of the difference" is extended to arbitrary comparison functions by the standard sorting function <code>qsort</code>, which takes a comparison function as an argument and requires it to abide by it.
In Perl (for numeric comparisons only, the <code>cmp</code> operator is used for string lexical comparisons), PHP (since version 7), Ruby, and Apache Groovy, the "spaceship operator" <code><=></code> returns the values −1, 0, or 1 depending on whether A < B, A = B, or A > B, respectively. The Python 2.x <code>cmp</code>(removed in 3.x), OCaml <code>compare</code>, and Kotlin <code>compareTo</code> functions compute the same thing. In the Haskell standard library, the three-way comparison function <code>compare</code> is defined for all types in the <code>Ord</code> class; it returns type <code>Ordering</code>, whose values are <code>LT</code> (less than), <code>EQ</code> (equal), and <code>GT</code> (greater than):<ref>[http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Ord.html#t:Ordering Data.Ord]</ref>
<syntaxhighlight lang="haskell"> data Ordering = LT | EQ | GT </syntaxhighlight>
Many object-oriented programming languages have a three-way comparison function, which performs a three-way comparison between the object and another given object. For example, in Java, any class that implements the <code>Comparable</code> interface has a [http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html#compareTo%28T%29 <code>compareTo</code>] method which either returns a negative integer, zero, or a positive integer, or throws a <code>NullPointerException</code> (if one or both objects are <code>null</code>). Similarly, in the .NET framework, any class that implements the <code>IComparable</code> interface has such a [http://msdn.microsoft.com/en-us/library/system.icomparable.compareto.aspx <code>CompareTo</code>] method. In C++, any class that can be three-way compared can be a parameter to instances of [https://en.cppreference.com/w/cpp/utility/compare/compare_three_way <code>std::compare_three_way</code>], [https://en.cppreference.com/w/cpp/utility/compare/strong_order <code>std::strong_order</code>], [https://en.cppreference.com/w/cpp/utility/compare/weak_order <code>std::weak_order</code>], or [https://en.cppreference.com/w/cpp/utility/compare/partial_order <code>std::partial_order</code>].
Since Java version 1.5, the same can be computed using the <code>Math.signum</code> static method if the difference can be known without computational problems such as arithmetic overflow mentioned below. Many computer languages allow the definition of functions so a ''compare(A,B)'' could be devised appropriately, but the question is whether or not its internal definition can employ some sort of three-way syntax or else must fall back on repeated tests.
When implementing a three-way comparison where a three-way comparison operator or method is not already available, it is common to combine two comparisons, such as A = B and A < B, or A < B and A > B. In principle, a compiler might deduce that these two expressions could be replaced by only one comparison followed by multiple tests of the result, but mention of this optimization is not to be found in texts on the subject.
In some cases, three-way comparison can be simulated by subtracting A and B and examining the sign of the result, exploiting special instructions for examining the sign of a number. However, this requires the type of A and B to have a well-defined difference. Fixed-width signed integers may overflow when they are subtracted, floating-point numbers have the value NaN with undefined sign, and character strings have no difference function corresponding to their total order. At the machine level, overflow is usually tracked and can be used to determine order after subtraction, but this information is usually unavailable to higher-level languages.
In one case of a three-way conditional provided by the programming language, Fortran's now-deprecated three-way arithmetic IF statement considers the sign of an arithmetic expression and offers three labels to jump to according to the sign of the result:
<syntaxhighlight lang="fortran"> IF (expression) negative,zero,positive </syntaxhighlight>
The common library function strcmp in C and related languages is a three-way lexicographic comparison of strings; however, these languages lack a general three-way comparison of other data types.
===Spaceship operator=== The three-way comparison operator or "spaceship operator" for numbers is denoted as <code><=></code> in Perl, Ruby, Apache Groovy, PHP, Eclipse Ceylon, and C++.<ref>{{cite web |url=http://perldoc.perl.org/Math/Complex.html |title=Math::Complex |website=Perl Programming Documentation |accessdate=26 September 2014}}</ref>
In C++, the C++20 revision adds the spaceship operator <code><=></code>, which returns a value that encodes whether the two values are equal, less, greater, or unordered and can return different types depending on the strictness of the comparison.<ref>Herb Sutter proposed adding a three-way comparison operator to the C++ standard with the <code><=></code> syntax, in a paper entitled "Consistent Comparison". See [http://open-std.org/JTC1/SC22/WG21/docs/papers/2017/p0515r0.pdf "Consistent Comparison"] It was successfully merged into the C++20 draft in November 2017.</ref>
The name's origin is due to it reminding Randal L. Schwartz of the spaceship in an HP BASIC ''Star Trek'' game.<ref>{{cite web |url=https://groups.google.com/a/dartlang.org/d/msg/misc/WS5xftItpl4/jcIttrMq8agJ |title=Spaceship history (was Re: [dart-misc] DEP meeting notes)}}</ref> Another coder has suggested that it was so named because it looked similar to Darth Vader's TIE fighter in the ''Star Wars'' saga.<ref>{{cite web|url=http://www.perlmonks.org/?node_id=45627|date=2000-12-08|accessdate=2014-08-06|title=Super Spaceship Operator}}</ref>
Example in PHP: <syntaxhighlight lang="php"> echo 1 <=> 1; // 0 echo 1 <=> 2; // -1 echo 2 <=> 1; // 1 </syntaxhighlight>
Example in C++: <syntaxhighlight lang="c++"> 1 <=> 1; // evaluates to std::strong_ordering::equal 1 <=> 2; // evaluates to std::strong_ordering::less 2 <=> 1; // evaluates to std::strong_ordering::greater </syntaxhighlight>
===Composite data types===
Three-way comparisons have the property of being easy to compose and build lexicographic comparisons of non-primitive data types, unlike two-way comparisons.
Here is a composition example in Perl. <syntaxhighlight lang="perl"> sub compare($$) { my ($a, $b) = @_; return $a->{unit} cmp $b->{unit} || $a->{rank} <=> $b->{rank} || $a->{name} cmp $b->{name}; } </syntaxhighlight> Note that <code>cmp</code>, in Perl, is for strings, since <code><=></code> is for numbers. Two-way equivalents tend to be less compact but not necessarily less legible. The above takes advantage of short-circuit evaluation of the <code>||</code> operator, and the fact that 0 is considered false in Perl. As a result, if the first comparison is equal (thus evaluates to 0), it will "fall through" to the second comparison, and so on, until it finds one that is non-zero, or until it reaches the end.
In some languages, including Python, Ruby, Haskell, etc., comparison of lists is done lexicographically, which means that it is possible to build a chain of comparisons like the above example by putting the values into lists in the order desired; for example, in Ruby: <syntaxhighlight lang="ruby">[a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]</syntaxhighlight>In C++:<syntaxhighlight lang="c++">std::tie(a.unit, a.rank, a.name) <=> std::tie(b.unit, b.rank, b.name)</syntaxhighlight>
===SQL join operator=== In some SQL dialects, <code><=></code> is used as a null-safe join operator which will match operands if both are null.<ref>https://dev.mysql.com/doc/refman/8.4/en/comparison-operators.html#operator_equal-to</ref>
== See also== * Sign function * Three-valued logic
== Notes == {{Notelist}}
== References == {{Reflist}}
{{DEFAULTSORT:Three-Way Comparison}} Category:Conditional constructs Category:Operators (programming)