Let IntRange's And and Or handle negative values
diff --git a/lib/interval/interval.go b/lib/interval/interval.go
index 8390ee9..45f556c 100644
--- a/lib/interval/interval.go
+++ b/lib/interval/interval.go
@@ -42,13 +42,35 @@
one = big.NewInt(1)
)
-func bigIntClone(i *big.Int) *big.Int {
+// bitMask returns ((1<<n) - 1), where n is the largest of n0 and n1.
+func bitMask(n0 int, n1 int) *big.Int {
+ n := n0
+ if n < n1 {
+ n = n1
+ }
+ if n > (1 << 30) {
+ panic("interval: input is too large")
+ }
+ z := big.NewInt(1)
+ z = z.Lsh(z, uint(n))
+ z = z.Sub(z, one)
+ return z
+}
+
+func bigIntNewSet(i *big.Int) *big.Int {
if i != nil {
return big.NewInt(0).Set(i)
}
return nil
}
+func bigIntNewNot(i *big.Int) *big.Int {
+ if i != nil {
+ return big.NewInt(0).Not(i)
+ }
+ return nil
+}
+
func bigIntMul(i *big.Int, j *big.Int) *big.Int { return big.NewInt(0).Mul(i, j) }
func bigIntQuo(i *big.Int, j *big.Int) *big.Int { return big.NewInt(0).Quo(i, j) }
@@ -263,6 +285,35 @@
return x[0] != nil && x[1] != nil && x[0].Sign() == 0 && x[1].Sign() == 0
}
+// split2Ways splits x into negative and non-negative sub-intervals. The
+// IntRange values returned may be empty, which means that x does not contain
+// any negative or non-negative elements.
+func (x IntRange) split2Ways() (neg IntRange, nonNeg IntRange) {
+ if x.Empty() {
+ return empty(), empty()
+ }
+ if x[0] != nil && x[0].Sign() >= 0 {
+ return empty(), x
+ }
+ if x[1] != nil && x[1].Sign() < 0 {
+ return x, empty()
+ }
+
+ neg[0] = x[0]
+ neg[1] = big.NewInt(-1)
+ if x[1] != nil && x[1].Cmp(neg[1]) < 0 {
+ neg[1] = x[1]
+ }
+
+ nonNeg[0] = big.NewInt(0)
+ if x[0] != nil && x[0].Cmp(nonNeg[0]) > 0 {
+ nonNeg[0] = x[0]
+ }
+ nonNeg[1] = x[1]
+
+ return neg, nonNeg
+}
+
// split splits x into negative, zero and positive sub-intervals. The IntRange
// values returned may be empty, which means that x does not contain any
// negative or positive elements.
@@ -293,14 +344,14 @@
func (x IntRange) Unite(y IntRange) (z IntRange) {
if x.Empty() {
return IntRange{
- bigIntClone(y[0]),
- bigIntClone(y[1]),
+ bigIntNewSet(y[0]),
+ bigIntNewSet(y[1]),
}
}
if y.Empty() {
return IntRange{
- bigIntClone(x[0]),
- bigIntClone(x[1]),
+ bigIntNewSet(x[0]),
+ bigIntNewSet(x[1]),
}
}
@@ -330,9 +381,9 @@
}
if x[0] == nil {
- z[0] = bigIntClone(y[0])
+ z[0] = bigIntNewSet(y[0])
} else if y[0] == nil {
- z[0] = bigIntClone(x[0])
+ z[0] = bigIntNewSet(x[0])
} else if x[0].Cmp(y[0]) < 0 {
z[0] = big.NewInt(0).Set(y[0])
} else {
@@ -340,9 +391,9 @@
}
if x[1] == nil {
- z[1] = bigIntClone(y[1])
+ z[1] = bigIntNewSet(y[1])
} else if y[1] == nil {
- z[1] = bigIntClone(x[1])
+ z[1] = bigIntNewSet(x[1])
} else if x[1].Cmp(y[1]) < 0 {
z[1] = big.NewInt(0).Set(x[1])
} else {
@@ -627,15 +678,54 @@
//
// ok is false (and z will be IntRange{nil, nil}) if x or y contains at least
// one negative value. Otherwise, ok is true.
-//
-// TODO: implement bit-wise operations (with tight bounds) on negative
-// integers. In that case, we could drop the "ok" return value.
func (x IntRange) And(y IntRange) (z IntRange, ok bool) {
if x.Empty() || y.Empty() {
return empty(), true
}
- if x.ContainsNegative() || y.ContainsNegative() {
- return IntRange{}, false
+ if !x.ContainsNegative() && !y.ContainsNegative() {
+ return andBothNonNeg(x, y), true
+ }
+
+ xNeg, xNon := x.split2Ways()
+ yNeg, yNon := y.split2Ways()
+ hasXNeg := !xNeg.Empty()
+ hasXNon := !xNon.Empty()
+ hasYNeg := !yNeg.Empty()
+ hasYNon := !yNon.Empty()
+
+ z = empty()
+ if hasXNeg {
+ if hasYNeg {
+ w := orBothNonNeg(IntRange{
+ bigIntNewNot(xNeg[1]),
+ bigIntNewNot(xNeg[0]),
+ }, IntRange{
+ bigIntNewNot(yNeg[1]),
+ bigIntNewNot(yNeg[0]),
+ })
+ z = z.Unite(IntRange{
+ bigIntNewNot(w[1]),
+ bigIntNewNot(w[0]),
+ })
+ }
+ if hasYNon {
+ z = z.Unite(andOneNegOneNonNeg(xNeg, yNon))
+ }
+ }
+ if hasXNon {
+ if hasYNeg {
+ z = z.Unite(andOneNegOneNonNeg(yNeg, xNon))
+ }
+ if hasYNon {
+ z = z.Unite(andBothNonNeg(xNon, yNon))
+ }
+ }
+ return z, true
+}
+
+func andBothNonNeg(x IntRange, y IntRange) (z IntRange) {
+ if x.Empty() || x.ContainsNegative() || y.Empty() || y.ContainsNegative() {
+ panic("pre-condition failure")
}
zMax := (*big.Int)(nil)
@@ -643,13 +733,13 @@
if y[1] != nil {
zMax = x.andMax(y)
} else {
- return IntRange{big.NewInt(0), big.NewInt(0).Set(x[1])}, true
+ return IntRange{big.NewInt(0), big.NewInt(0).Set(x[1])}
}
} else {
if y[1] != nil {
- return IntRange{big.NewInt(0), big.NewInt(0).Set(y[1])}, true
+ return IntRange{big.NewInt(0), big.NewInt(0).Set(y[1])}
} else {
- return IntRange{big.NewInt(0), nil}, true
+ return IntRange{big.NewInt(0), nil}
}
}
@@ -665,22 +755,86 @@
zMin := notX.orMax(notY)
zMin.Not(zMin)
- return IntRange{zMin, zMax}, true
+ return IntRange{zMin, zMax}
+}
+
+func andOneNegOneNonNeg(neg IntRange, non IntRange) (z IntRange) {
+ if neg.Empty() || neg.ContainsZero() || neg.ContainsPositive() || non.Empty() || non.ContainsNegative() {
+ panic("pre-condition failure")
+ }
+
+ if neg[0] == nil {
+ return IntRange{big.NewInt(0), bigIntNewSet(non[1])}
+ } else if non[1] == nil {
+ mask := bitMask(neg[0].BitLen(), non[0].BitLen())
+ biasedNeg := IntRange{
+ big.NewInt(0).And(mask, neg[0]),
+ big.NewInt(0).And(mask, neg[1]),
+ }
+ w := andBothNonNeg(biasedNeg, IntRange{non[0], mask})
+ return IntRange{w[0], nil}
+ } else {
+ mask := bitMask(neg[0].BitLen(), non[1].BitLen())
+ biasedNeg := IntRange{
+ big.NewInt(0).And(mask, neg[0]),
+ big.NewInt(0).And(mask, neg[1]),
+ }
+ return andBothNonNeg(biasedNeg, non)
+ }
}
// Or returns z = x | y.
//
// ok is false (and z will be IntRange{nil, nil}) if x or y contains at least
// one negative value. Otherwise, ok is true.
-//
-// TODO: implement bit-wise operations (with tight bounds) on negative
-// integers. In that case, we could drop the "ok" return value.
func (x IntRange) Or(y IntRange) (z IntRange, ok bool) {
if x.Empty() || y.Empty() {
return empty(), true
}
- if x.ContainsNegative() || y.ContainsNegative() {
- return IntRange{}, false
+ if !x.ContainsNegative() && !y.ContainsNegative() {
+ return orBothNonNeg(x, y), true
+ }
+
+ xNeg, xNon := x.split2Ways()
+ yNeg, yNon := y.split2Ways()
+ hasXNeg := !xNeg.Empty()
+ hasXNon := !xNon.Empty()
+ hasYNeg := !yNeg.Empty()
+ hasYNon := !yNon.Empty()
+
+ z = empty()
+ if hasXNeg {
+ if hasYNeg {
+ w := andBothNonNeg(IntRange{
+ bigIntNewNot(xNeg[1]),
+ bigIntNewNot(xNeg[0]),
+ }, IntRange{
+ bigIntNewNot(yNeg[1]),
+ bigIntNewNot(yNeg[0]),
+ })
+ z = z.Unite(IntRange{
+ bigIntNewNot(w[1]),
+ bigIntNewNot(w[0]),
+ })
+ }
+ if hasYNon {
+ z = z.Unite(orOneNegOneNonNeg(xNeg, yNon))
+ }
+ }
+ if hasXNon {
+ if hasYNeg {
+ z = z.Unite(orOneNegOneNonNeg(yNeg, xNon))
+ }
+ if hasYNon {
+ z = z.Unite(orBothNonNeg(xNon, yNon))
+ }
+ }
+ return z, true
+}
+
+func orBothNonNeg(x IntRange, y IntRange) (z IntRange) {
+ if x.Empty() || x.ContainsNegative() || y.Empty() || y.ContainsNegative() {
+ panic("pre-condition failure")
}
zMax := (*big.Int)(nil)
@@ -698,10 +852,10 @@
// value is contained in the other interval. For example, if both xx
// and yy can be x[0], then (x[0] | x[0]) is simply x[0].
if x.ContainsInt(y[0]) {
- return IntRange{big.NewInt(0).Set(y[0]), nil}, true
+ return IntRange{big.NewInt(0).Set(y[0]), nil}
}
if y.ContainsInt(x[0]) {
- return IntRange{big.NewInt(0).Set(x[0]), nil}, true
+ return IntRange{big.NewInt(0).Set(x[0]), nil}
}
if x[1] == nil && y[1] == nil {
panic("unreachable")
@@ -738,7 +892,21 @@
zMin := notX.andMax(notY)
zMin.Not(zMin)
- return IntRange{zMin, zMax}, true
+ return IntRange{zMin, zMax}
+}
+
+func orOneNegOneNonNeg(neg IntRange, non IntRange) (z IntRange) {
+ w := andOneNegOneNonNeg(IntRange{
+ bigIntNewNot(non[1]),
+ bigIntNewNot(non[0]),
+ }, IntRange{
+ bigIntNewNot(neg[1]),
+ bigIntNewNot(neg[0]),
+ })
+ return IntRange{
+ bigIntNewNot(w[1]),
+ bigIntNewNot(w[0]),
+ }
}
// The andMax and orMax algorithms are tricky.
@@ -999,7 +1167,7 @@
// - Etc.
func bitFillRight(i *big.Int) {
if s := i.Sign(); s < 0 {
- panic("TODO: implement bit-wise operations on negative integers")
+ panic("pre-condition failure")
} else if s == 0 {
return
}
diff --git a/lib/interval/interval_test.go b/lib/interval/interval_test.go
index 874a5a5..cbf1f77 100644
--- a/lib/interval/interval_test.go
+++ b/lib/interval/interval_test.go
@@ -24,6 +24,36 @@
"testing"
)
+var fromNeg7ToPos7 = []*big.Int{
+ big.NewInt(-7),
+ big.NewInt(-6),
+ big.NewInt(-5),
+ big.NewInt(-4),
+ big.NewInt(-3),
+ big.NewInt(-2),
+ big.NewInt(-1),
+ big.NewInt(+0),
+ big.NewInt(+1),
+ big.NewInt(+2),
+ big.NewInt(+3),
+ big.NewInt(+4),
+ big.NewInt(+5),
+ big.NewInt(+6),
+ big.NewInt(+7),
+ nil,
+}
+
+var fromNeg3ToPos3 = []*big.Int{
+ big.NewInt(-3),
+ big.NewInt(-2),
+ big.NewInt(-1),
+ big.NewInt(+0),
+ big.NewInt(+1),
+ big.NewInt(+2),
+ big.NewInt(+3),
+ nil,
+}
+
// TestMotivatingExample tests the "motivating example" given in the package
// doc comment.
func TestMotivatingExample(tt *testing.T) {
@@ -311,33 +341,13 @@
}
func TestBruteForceAgreesSystematically(tt *testing.T) {
- ints := []*big.Int{
- big.NewInt(-7),
- big.NewInt(-6),
- big.NewInt(-5),
- big.NewInt(-4),
- big.NewInt(-3),
- big.NewInt(-2),
- big.NewInt(-1),
- big.NewInt(+0),
- big.NewInt(+1),
- big.NewInt(+2),
- big.NewInt(+3),
- big.NewInt(+4),
- big.NewInt(+5),
- big.NewInt(+6),
- big.NewInt(+7),
- nil,
- }
-
for _, opKey := range intOperatorsKeys {
-
- for _, x0 := range ints {
- for _, x1 := range ints {
+ for _, x0 := range fromNeg7ToPos7 {
+ for _, x1 := range fromNeg7ToPos7 {
x := IntRange{x0, x1}
- for _, y0 := range ints {
- for _, y1 := range ints {
+ for _, y0 := range fromNeg7ToPos7 {
+ for _, y1 := range fromNeg7ToPos7 {
y := IntRange{y0, y1}
if err := testBruteForceAgrees(x, y, opKey); err != nil {
@@ -422,7 +432,7 @@
got, gotOK := intOperators[opKey](x, y)
if !got.Eq(want) || gotOK != wantOK {
- return fmt.Errorf("package code: got %v, %t, want %v, %t", got, gotOK, want, wantOK)
+ return fmt.Errorf("got %v, %t, want %v, %t", got, gotOK, want, wantOK)
}
return nil
}
@@ -755,46 +765,46 @@
func TestOpAnd(tt *testing.T) {
testOp(tt,
- "[ 3, 3] & [ -5, -5] == invalid",
+ "[ 3, 3] & [ -5, -5] == [ 3, 3]",
"[ 3, 3] & [ 0, 0] == [ 0, 0]",
- "[ 0, 0] & [ -7, 7] == invalid",
+ "[ 0, 0] & [ -7, 7] == [ 0, 0]",
"[ 0, 2] & [ 0, 5] == [ 0, 2]",
"[ 3, 6] & [ 10, 15] == [ 0, 6]",
- "[ 3, +∞) & [ -4, -2] == invalid",
+ "[ 3, +∞) & [ -4, -2] == [ 0, +∞)",
"[ 3, +∞) & [ 10, 15] == [ 0, 15]",
- "[ 3, +∞) & ( -∞, 15] == invalid",
- "[ 3, 6] & ( -∞, 15] == invalid",
- "[ 3, 6] & ( -∞, +∞) == invalid",
- "( -∞, +∞) & ( -∞, +∞) == invalid",
- "( -∞, +∞) & [ 1, 2] == invalid",
- "( -∞, +∞) & [ 0, 0] == invalid",
+ "[ 3, +∞) & ( -∞, 15] == [ 0, +∞)",
+ "[ 3, 6] & ( -∞, 15] == [ 0, 6]",
+ "[ 3, 6] & ( -∞, +∞) == [ 0, 6]",
+ "( -∞, +∞) & ( -∞, +∞) == ( -∞, +∞)",
+ "( -∞, +∞) & [ 1, 2] == [ 0, 2]",
+ "( -∞, +∞) & [ 0, 0] == [ 0, 0]",
"[ 3, 6] & [...empty..] == [...empty..]",
"[...empty..] & [ 10, 15] == [...empty..]",
"[...empty..] & [...empty..] == [...empty..]",
"( -∞, +∞) & [...empty..] == [...empty..]",
- "[ 1, 4] & [ -11, -10] == invalid",
+ "[ 1, 4] & [ -11, -10] == [ 0, 4]",
- "[ 1, 4] & [ -6, 2] == invalid",
+ "[ 1, 4] & [ -6, 2] == [ 0, 4]",
- "[ -3, -1] & [ 0, 3] == invalid",
- "[ -1, 4] & [ 0, 3] == invalid",
+ "[ -3, -1] & [ 0, 3] == [ 0, 3]",
+ "[ -1, 4] & [ 0, 3] == [ 0, 3]",
"[ 0, 4] & [ 0, 3] == [ 0, 3]",
"[ 1, 4] & [ 0, 3] == [ 0, 3]",
- "[ -3, -1] & [ 2, 3] == invalid",
- "[ -1, 4] & [ 2, 3] == invalid",
+ "[ -3, -1] & [ 2, 3] == [ 0, 3]",
+ "[ -1, 4] & [ 2, 3] == [ 0, 3]",
"[ 0, 4] & [ 2, 3] == [ 0, 3]",
"[ 1, 4] & [ 2, 3] == [ 0, 3]",
- "[ -9, +∞) & [ 2, +∞) == invalid",
- "[ -1, +∞) & [ 2, +∞) == invalid",
+ "[ -9, +∞) & [ 2, +∞) == [ 0, +∞)",
+ "[ -1, +∞) & [ 2, +∞) == [ 0, +∞)",
"[ 0, +∞) & [ 2, +∞) == [ 0, +∞)",
"[ 1, +∞) & [ 2, +∞) == [ 0, +∞)",
"[ 7, +∞) & [ 2, +∞) == [ 0, +∞)",
- "[ -1, 1] & ( -∞, +∞) == invalid",
- "[ 0, 0] & ( -∞, +∞) == invalid",
- "[ 1, 1] & ( -∞, +∞) == invalid",
+ "[ -1, 1] & ( -∞, +∞) == ( -∞, +∞)",
+ "[ 0, 0] & ( -∞, +∞) == [ 0, 0]",
+ "[ 1, 1] & ( -∞, +∞) == [ 0, 1]",
"[ 1, 3] & [ 4, 9] == [ 0, 3]",
"[ 3, 4] & [ 5, 6] == [ 1, 4]",
@@ -816,51 +826,54 @@
"[ 5, 9] & [ 9, +∞) == [ 0, 9]",
"[ 5, 6] & [ 12, +∞) == [ 0, 6]",
"[ 5, 9] & [ 12, +∞) == [ 0, 9]",
+
+ "( -∞, -3] & [ -3, -2] == ( -∞, -3]",
+ "[ 2, +∞) & [ 1, 2] == [ 0, 2]",
)
}
func TestOpOr(tt *testing.T) {
testOp(tt,
- "[ 3, 3] | [ -5, -5] == invalid",
+ "[ 3, 3] | [ -5, -5] == [ -5, -5]",
"[ 3, 3] | [ 0, 0] == [ 3, 3]",
- "[ 0, 0] | [ -7, 7] == invalid",
+ "[ 0, 0] | [ -7, 7] == [ -7, 7]",
"[ 0, 2] | [ 0, 5] == [ 0, 7]",
"[ 3, 6] | [ 10, 15] == [ 11, 15]",
- "[ 3, +∞) | [ -4, -2] == invalid",
+ "[ 3, +∞) | [ -4, -2] == [ -4, -1]",
"[ 3, +∞) | [ 10, 15] == [ 10, +∞)",
- "[ 3, +∞) | ( -∞, 15] == invalid",
- "[ 3, 6] | ( -∞, 15] == invalid",
- "[ 3, 6] | ( -∞, +∞) == invalid",
- "( -∞, +∞) | ( -∞, +∞) == invalid",
- "( -∞, +∞) | [ 1, 2] == invalid",
- "( -∞, +∞) | [ 0, 0] == invalid",
+ "[ 3, +∞) | ( -∞, 15] == ( -∞, +∞)",
+ "[ 3, 6] | ( -∞, 15] == ( -∞, 15]",
+ "[ 3, 6] | ( -∞, +∞) == ( -∞, +∞)",
+ "( -∞, +∞) | ( -∞, +∞) == ( -∞, +∞)",
+ "( -∞, +∞) | [ 1, 2] == ( -∞, +∞)",
+ "( -∞, +∞) | [ 0, 0] == ( -∞, +∞)",
"[ 3, 6] | [...empty..] == [...empty..]",
"[...empty..] | [ 10, 15] == [...empty..]",
"[...empty..] | [...empty..] == [...empty..]",
"( -∞, +∞) | [...empty..] == [...empty..]",
- "[ 1, 4] | [ -11, -10] == invalid",
+ "[ 1, 4] | [ -11, -10] == [ -11, -9]",
- "[ 1, 4] | [ -6, 2] == invalid",
+ "[ 1, 4] | [ -6, 2] == [ -6, 6]",
- "[ -3, -1] | [ 0, 3] == invalid",
- "[ -1, 4] | [ 0, 3] == invalid",
+ "[ -3, -1] | [ 0, 3] == [ -3, -1]",
+ "[ -1, 4] | [ 0, 3] == [ -1, 7]",
"[ 0, 4] | [ 0, 3] == [ 0, 7]",
"[ 1, 4] | [ 0, 3] == [ 1, 7]",
- "[ -3, -1] | [ 2, 3] == invalid",
- "[ -1, 4] | [ 2, 3] == invalid",
+ "[ -3, -1] | [ 2, 3] == [ -2, -1]",
+ "[ -1, 4] | [ 2, 3] == [ -1, 7]",
"[ 0, 4] | [ 2, 3] == [ 2, 7]",
"[ 1, 4] | [ 2, 3] == [ 2, 7]",
- "[ -9, +∞) | [ 2, +∞) == invalid",
- "[ -1, +∞) | [ 2, +∞) == invalid",
+ "[ -9, +∞) | [ 2, +∞) == [ -9, +∞)",
+ "[ -1, +∞) | [ 2, +∞) == [ -1, +∞)",
"[ 0, +∞) | [ 2, +∞) == [ 2, +∞)",
"[ 1, +∞) | [ 2, +∞) == [ 2, +∞)",
"[ 7, +∞) | [ 2, +∞) == [ 7, +∞)",
- "[ -1, 1] | ( -∞, +∞) == invalid",
- "[ 0, 0] | ( -∞, +∞) == invalid",
- "[ 1, 1] | ( -∞, +∞) == invalid",
+ "[ -1, 1] | ( -∞, +∞) == ( -∞, +∞)",
+ "[ 0, 0] | ( -∞, +∞) == ( -∞, +∞)",
+ "[ 1, 1] | ( -∞, +∞) == ( -∞, +∞)",
"[ 1, 3] | [ 4, 9] == [ 5, 11]",
"[ 3, 4] | [ 5, 6] == [ 5, 7]",
@@ -882,5 +895,82 @@
"[ 5, 9] | [ 9, +∞) == [ 9, +∞)",
"[ 5, 6] | [ 12, +∞) == [ 13, +∞)",
"[ 5, 9] | [ 12, +∞) == [ 12, +∞)",
+
+ "( -∞, -3] | [ -3, -2] == [ -3, -1]",
+ "[ 2, +∞) | [ 1, 2] == [ 2, +∞)",
)
}
+
+func TestOpAndWithMinusOne(tt *testing.T) {
+ minusOne := IntRange{big.NewInt(-1), big.NewInt(-1)}
+ for _, x0 := range fromNeg3ToPos3 {
+ for _, x1 := range fromNeg3ToPos3 {
+ x := IntRange{x0, x1}
+ want := x
+
+ if got, _ := x.And(minusOne); !got.Eq(want) {
+ tt.Fatalf("%v & -1: got %v, want %v", x, got, want)
+ }
+ if got, _ := minusOne.And(x); !got.Eq(want) {
+ tt.Fatalf("-1 & %v: got %v, want %v", x, got, want)
+ }
+ }
+ }
+}
+
+func TestOpAndWithZero(tt *testing.T) {
+ zero := IntRange{big.NewInt(+0), big.NewInt(+0)}
+ for _, x0 := range fromNeg3ToPos3 {
+ for _, x1 := range fromNeg3ToPos3 {
+ x := IntRange{x0, x1}
+ want := zero
+ if x.Empty() {
+ want = empty()
+ }
+
+ if got, _ := x.And(zero); !got.Eq(want) {
+ tt.Fatalf("%v & +0: got %v, want %v", x, got, want)
+ }
+ if got, _ := zero.And(x); !got.Eq(want) {
+ tt.Fatalf("+0 & %v: got %v, want %v", x, got, want)
+ }
+ }
+ }
+}
+
+func TestOpOrWithMinusOne(tt *testing.T) {
+ minusOne := IntRange{big.NewInt(-1), big.NewInt(-1)}
+ for _, x0 := range fromNeg3ToPos3 {
+ for _, x1 := range fromNeg3ToPos3 {
+ x := IntRange{x0, x1}
+ want := minusOne
+ if x.Empty() {
+ want = empty()
+ }
+
+ if got, _ := x.Or(minusOne); !got.Eq(want) {
+ tt.Fatalf("%v | -1: got %v, want %v", x, got, want)
+ }
+ if got, _ := minusOne.Or(x); !got.Eq(want) {
+ tt.Fatalf("-1 | %v: got %v, want %v", x, got, want)
+ }
+ }
+ }
+}
+
+func TestOpOrWithZero(tt *testing.T) {
+ zero := IntRange{big.NewInt(+0), big.NewInt(+0)}
+ for _, x0 := range fromNeg3ToPos3 {
+ for _, x1 := range fromNeg3ToPos3 {
+ x := IntRange{x0, x1}
+ want := x
+
+ if got, _ := x.Or(zero); !got.Eq(want) {
+ tt.Fatalf("%v | +0: got %v, want %v", x, got, want)
+ }
+ if got, _ := zero.Or(x); !got.Eq(want) {
+ tt.Fatalf("+0 | %v: got %v, want %v", x, got, want)
+ }
+ }
+ }
+}
diff --git a/lib/interval/radial_test.go b/lib/interval/radial_test.go
index 102280d..e69acfb 100644
--- a/lib/interval/radial_test.go
+++ b/lib/interval/radial_test.go
@@ -83,7 +83,8 @@
const (
radialNaN = -1 << 31
- // Note that radialInput.Or requires that (riRadius + 1) is a power of 2.
+ // Note that radialInput.And and radialInput.Or require that (riRadius + 1)
+ // is a power of 2.
riRadius = 15
roRadius = 16 << 16
@@ -343,36 +344,56 @@
if x == radialNaN || y == radialNaN {
return radialOutPair{radialNaN, radialNaN}
}
- if x < 0 || y < 0 {
- // TODO: handle negative numbers.
- return radialOutPair{radialNaN, radialNaN}
- }
ox := x.canonicalize()
oy := y.canonicalize()
- if ox > +riRadius {
- if oy > +riRadius {
+ // r is a power of 2, so that its binary representation contains one "1"
+ // digit, and that digit is not shared with any "small" value <= riRadius.
+ const r = riRadius + 1
+
+ if ox < -riRadius {
+ if oy < -riRadius {
+ return radialOutPair{roLargeNeg, -r}
+ } else if oy > +riRadius {
return radialOutPair{0, roLargePos}
+ } else if oy < 0 {
+ return radialOutPair{roLargeNeg, -r}
} else {
return radialOutPair{0, oy}
}
- } else {
- if oy > +riRadius {
- return radialOutPair{0, ox}
+ } else if ox > +riRadius {
+ if oy < -riRadius {
+ return radialOutPair{0, roLargePos}
+ } else if oy > +riRadius {
+ return radialOutPair{0, roLargePos}
+ } else if oy < 0 {
+ return radialOutPair{+r, roLargePos}
} else {
- return radialOutPair{ox & oy, ox & oy}
+ return radialOutPair{0, oy}
}
}
+
+ if oy < -riRadius {
+ if ox < 0 {
+ return radialOutPair{roLargeNeg, -r}
+ } else {
+ return radialOutPair{0, ox}
+ }
+ } else if oy > +riRadius {
+ if ox < 0 {
+ return radialOutPair{+r, roLargePos}
+ } else {
+ return radialOutPair{0, ox}
+ }
+ }
+
+ return radialOutPair{ox & oy, ox & oy}
}
func (x radialInput) Or(y radialInput) radialOutPair {
if x == radialNaN || y == radialNaN {
return radialOutPair{radialNaN, radialNaN}
}
- if x < 0 || y < 0 {
- // TODO: handle negative numbers.
- return radialOutPair{radialNaN, radialNaN}
- }
ox := x.canonicalize()
oy := y.canonicalize()
@@ -380,19 +401,43 @@
// digit, and that digit is not shared with any "small" value <= riRadius.
const r = riRadius + 1
- if ox > +riRadius {
- if oy > +riRadius {
- return radialOutPair{r, roLargePos}
+ if ox < -riRadius {
+ if oy < -riRadius {
+ return radialOutPair{roLargeNeg, -1}
+ } else if oy > +riRadius {
+ return radialOutPair{roLargeNeg, -1}
+ } else if oy < 0 {
+ return radialOutPair{oy, -1}
} else {
- return radialOutPair{oy | r, roLargePos}
+ return radialOutPair{roLargeNeg, oy | -r}
}
- } else {
- if oy > +riRadius {
- return radialOutPair{ox | r, roLargePos}
+ } else if ox > +riRadius {
+ if oy < -riRadius {
+ return radialOutPair{roLargeNeg, -1}
+ } else if oy > +riRadius {
+ return radialOutPair{+r, roLargePos}
+ } else if oy < 0 {
+ return radialOutPair{oy, -1}
} else {
- return radialOutPair{ox | oy, ox | oy}
+ return radialOutPair{oy | +r, roLargePos}
}
}
+
+ if oy < -riRadius {
+ if ox < 0 {
+ return radialOutPair{ox, -1}
+ } else {
+ return radialOutPair{roLargeNeg, ox | -r}
+ }
+ } else if oy > +riRadius {
+ if ox < 0 {
+ return radialOutPair{ox, -1}
+ } else {
+ return radialOutPair{ox | +r, roLargePos}
+ }
+ }
+
+ return radialOutPair{ox | oy, ox | oy}
}
var riOperators = map[string]func(radialInput, radialInput) radialOutPair{
