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