MLIR  20.0.0git
Fraction.h
Go to the documentation of this file.
1 //===- Fraction.h - MLIR Fraction Class -------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is a simple class to represent fractions. It supports arithmetic,
10 // comparison, floor, and ceiling operations.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef MLIR_ANALYSIS_PRESBURGER_FRACTION_H
15 #define MLIR_ANALYSIS_PRESBURGER_FRACTION_H
16
17 #include "llvm/ADT/DynamicAPInt.h"
18 #include "llvm/Support/raw_ostream.h"
19
20 namespace mlir {
21 namespace presburger {
22 using llvm::DynamicAPInt;
23
24 /// A class to represent fractions. The sign of the fraction is represented
25 /// in the sign of the numerator; the denominator is always positive.
26 ///
27 /// Note that overflows may occur if the numerator or denominator are not
28 /// representable by 64-bit integers.
29 struct Fraction {
30  /// Default constructor initializes the represented rational number to zero.
31  Fraction() = default;
32
33  /// Construct a Fraction from a numerator and denominator.
34  Fraction(const DynamicAPInt &oNum, const DynamicAPInt &oDen = DynamicAPInt(1))
35  : num(oNum), den(oDen) {
36  if (den < 0) {
37  num = -num;
38  den = -den;
39  }
40  }
41  /// Overloads for passing literals.
42  Fraction(const DynamicAPInt &num, int64_t den)
43  : Fraction(num, DynamicAPInt(den)) {}
44  Fraction(int64_t num, const DynamicAPInt &den = DynamicAPInt(1))
45  : Fraction(DynamicAPInt(num), den) {}
46  Fraction(int64_t num, int64_t den)
47  : Fraction(DynamicAPInt(num), DynamicAPInt(den)) {}
48
49  // Return the value of the fraction as an integer. This should only be called
50  // when the fraction's value is really an integer.
51  DynamicAPInt getAsInteger() const {
52  assert(num % den == 0 && "Get as integer called on non-integral fraction!");
53  return num / den;
54  }
55
56  llvm::raw_ostream &print(llvm::raw_ostream &os) const {
57  return os << "(" << num << "/" << den << ")";
58  }
59
60  /// The numerator and denominator, respectively. The denominator is always
61  /// positive.
62  DynamicAPInt num{0}, den{1};
63 };
64
65 /// Three-way comparison between two fractions.
66 /// Returns +1, 0, and -1 if the first fraction is greater than, equal to, or
67 /// less than the second fraction, respectively.
68 inline int compare(const Fraction &x, const Fraction &y) {
69  DynamicAPInt diff = x.num * y.den - y.num * x.den;
70  if (diff > 0)
71  return +1;
72  if (diff < 0)
73  return -1;
74  return 0;
75 }
76
77 inline DynamicAPInt floor(const Fraction &f) { return floorDiv(f.num, f.den); }
78
79 inline DynamicAPInt ceil(const Fraction &f) { return ceilDiv(f.num, f.den); }
80
81 inline Fraction operator-(const Fraction &x) { return Fraction(-x.num, x.den); }
82
83 inline bool operator<(const Fraction &x, const Fraction &y) {
84  return compare(x, y) < 0;
85 }
86
87 inline bool operator<=(const Fraction &x, const Fraction &y) {
88  return compare(x, y) <= 0;
89 }
90
91 inline bool operator==(const Fraction &x, const Fraction &y) {
92  return compare(x, y) == 0;
93 }
94
95 inline bool operator!=(const Fraction &x, const Fraction &y) {
96  return compare(x, y) != 0;
97 }
98
99 inline bool operator>(const Fraction &x, const Fraction &y) {
100  return compare(x, y) > 0;
101 }
102
103 inline bool operator>=(const Fraction &x, const Fraction &y) {
104  return compare(x, y) >= 0;
105 }
106
107 inline Fraction abs(const Fraction &f) {
108  assert(f.den > 0 && "denominator of fraction must be positive!");
109  return Fraction(abs(f.num), f.den);
110 }
111
112 inline Fraction reduce(const Fraction &f) {
113  if (f == Fraction(0))
114  return Fraction(0, 1);
115  DynamicAPInt g = gcd(abs(f.num), abs(f.den));
116  return Fraction(f.num / g, f.den / g);
117 }
118
119 inline Fraction operator*(const Fraction &x, const Fraction &y) {
120  return reduce(Fraction(x.num * y.num, x.den * y.den));
121 }
122
123 inline Fraction operator/(const Fraction &x, const Fraction &y) {
124  return reduce(Fraction(x.num * y.den, x.den * y.num));
125 }
126
127 inline Fraction operator+(const Fraction &x, const Fraction &y) {
128  return reduce(Fraction(x.num * y.den + x.den * y.num, x.den * y.den));
129 }
130
131 inline Fraction operator-(const Fraction &x, const Fraction &y) {
132  return reduce(Fraction(x.num * y.den - x.den * y.num, x.den * y.den));
133 }
134
135 // Find the integer nearest to a given fraction.
136 inline DynamicAPInt round(const Fraction &f) {
137  DynamicAPInt rem = f.num % f.den;
138  return (f.num / f.den) + (rem > f.den / 2);
139 }
140
141 inline Fraction &operator+=(Fraction &x, const Fraction &y) {
142  x = x + y;
143  return x;
144 }
145
146 inline Fraction &operator-=(Fraction &x, const Fraction &y) {
147  x = x - y;
148  return x;
149 }
150
151 inline Fraction &operator/=(Fraction &x, const Fraction &y) {
152  x = x / y;
153  return x;
154 }
155
156 inline Fraction &operator*=(Fraction &x, const Fraction &y) {
157  x = x * y;
158  return x;
159 }
160
161 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Fraction &x) {
162  x.print(os);
163  return os;
164 }
165
166 } // namespace presburger
167 } // namespace mlir
168
169 #endif // MLIR_ANALYSIS_PRESBURGER_FRACTION_H
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const Fraction &x)
Definition: Fraction.h:161
Fraction & operator-=(Fraction &x, const Fraction &y)
Definition: Fraction.h:146
Fraction operator+(const Fraction &x, const Fraction &y)
Definition: Fraction.h:127
bool operator==(const Fraction &x, const Fraction &y)
Definition: Fraction.h:91
bool operator>(const Fraction &x, const Fraction &y)
Definition: Fraction.h:99
bool operator<(const Fraction &x, const Fraction &y)
Definition: Fraction.h:83
int compare(const Fraction &x, const Fraction &y)
Three-way comparison between two fractions.
Definition: Fraction.h:68
DynamicAPInt floor(const Fraction &f)
Definition: Fraction.h:77
bool operator>=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:103
DynamicAPInt ceil(const Fraction &f)
Definition: Fraction.h:79
Fraction reduce(const Fraction &f)
Definition: Fraction.h:112
Fraction operator-(const Fraction &x)
Definition: Fraction.h:81
bool operator<=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:87
DynamicAPInt round(const Fraction &f)
Definition: Fraction.h:136
Fraction & operator*=(Fraction &x, const Fraction &y)
Definition: Fraction.h:156
Fraction abs(const Fraction &f)
Definition: Fraction.h:107
Fraction & operator/=(Fraction &x, const Fraction &y)
Definition: Fraction.h:151
bool operator!=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:95
Fraction & operator+=(Fraction &x, const Fraction &y)
Definition: Fraction.h:141
Fraction operator*(const Fraction &x, const Fraction &y)
Definition: Fraction.h:119
Fraction operator/(const Fraction &x, const Fraction &y)
Definition: Fraction.h:123
Include the generated interface declarations.
A class to represent fractions.
Definition: Fraction.h:29
Fraction()=default
Default constructor initializes the represented rational number to zero.
Fraction(int64_t num, const DynamicAPInt &den=DynamicAPInt(1))
Definition: Fraction.h:44
Fraction(const DynamicAPInt &oNum, const DynamicAPInt &oDen=DynamicAPInt(1))
Construct a Fraction from a numerator and denominator.
Definition: Fraction.h:34
DynamicAPInt getAsInteger() const
Definition: Fraction.h:51
Fraction(const DynamicAPInt &num, int64_t den)
Overloads for passing literals.
Definition: Fraction.h:42
Fraction(int64_t num, int64_t den)
Definition: Fraction.h:46
DynamicAPInt num
The numerator and denominator, respectively.
Definition: Fraction.h:62
llvm::raw_ostream & print(llvm::raw_ostream &os) const
Definition: Fraction.h:56