Author:  Gregg Irwin
Date:    1-Oct-2001
Comment: Part I
Part:    1 | 2

Contents

• Objective
• Introduction
• Think outside the box
• What's the point?
• But what are they good for?
• Does 2 pair beat 4 of a kind?
• Cleaning up

Objective

Investigate the pair! datatype and use it in an OO context.

Introduction

I have to be honest with you. I'm just a beginner when it comes to Rebol, and I hate being a beginner. It's so frustrating to know that there's so much power locked away inside this great tool and you have no clue about how to unleash it! Also, I want to see the Rebol community grow, and to do what I can to help achieve that. So, rather than viewing my amateur status as a liability, I'm going to exploit it. How so? Well, you see, one good thing about being a beginner, and writing from that perspective is that you, kind reader, get to watch me struggle, and we can all learn from my mistakes.

After you've become an expert with a tool it is difficult, if not downright impossible, to remember what it was like when you started out. It's easy to gloss over details that you've learned over the years and to assume that everyone else is aware of all the tricks and traps you've discovered through many long nights at the console. So, please bear with me, I feel your pain, misery loves company, and all that rot.

Now, on with the show.

Think outside the box

Rebol has a large number of built in data types which provide a great deal of functionality. Taking advantage of them can make your life much easier. Being new to Rebol myself, and having spent quite a bit of time "doing objects" in another language, I was thrilled to see the pair! datatype, and curious about how I could learn more about it and put it to good use.

A pair! is so simple, you might think it wouldn't provide much value. If so, you would be wrong. Very wrong. Complex objects and structures are composed of smaller, simpler objects. Solving any problem is always easier if you break it down into managable pieces. One caveat is that you need to know how to use those smaller pieces correctly or the larger objects you assemble from them may not behave as you expect.

A pair!, per the Core documentation, "is used to indicate spatial coordinates". I'll go along with that, but I'll add that you shouldn't think only of X-Y coordinates in terms of a GUI display system (even though that may be where you see them used most often). Consider a 2-dimensional array of data or nodes in a graph.

What's the point?

A pair! is just two values bound together and treated as one. Those values are limited to integer! values and you can access them individually if you want. Suppose we have a pair! called p which references a value of 5x10.

>> p: 5x10
== 5x10

To access the first value you can do any of the following:

>> first p
== 5
>> p/1
== 5
>> p/x
== 5

To access the second value you can do any of the following:

>> second p
== 10
>> p/2
== 10
>> p/y
== 10

The Core docs cover the basics of pair! operation pretty well, so look at those. I'll just add a couple points that are non-obvious.

First, while you can enter integer! values in Rebol using an apostrophe as a visual group delimiter (e.g. 2'000'000), you can't use them when defining a pair! (as of Core 2.5 anyway).

Second, and this is a good one, some of Rebols native functions operate on pair! values in ways you might not expect. Exploring at the console is a great way to have fun, and learn something in the process. Try the following:

>> p1: 10x10
== 10x10
>> p2: 5x20
== 5x20
>> minimum p1 p2
== 5x10
>> maximum p1 p2
== 10x20

Notice what minimum and maximum return. They don't return one of the values you passed to them as arguments. They return values computed by treating the two values in each pair independently. Pretty slick, eh?

What other functions can you use on pair! values? Here's what I've found:

• // (remainder)
• abs
• negate
• random
• zero?

Play around with those functions in the console to see how they work. I'll wait.

You can also compare pair! values for equality and inequality, but not for greater-than/less-than comparisons. Not being able to do greater-than/less-than comparisons makes some sense, and would lead you to believe that minimum-of and maximum-of won't work either, which is not true.

Minimum-of and maximum-of, while they don't choke on pair! values, don't give you the same results that minimum and maximum do. They will, instead, return one of the values that you give them. Some of their results are easy to rationalize:

>> first minimum-of [1x1 2x2 3x3]
== 1x1
>> first maximum-of [1x1 2x2 3x3]
== 3x3

Other results are a bit more opaque:

>> first maximum-of [10x0 2x2 0x10]
== 0x10
>> first minimum-of [10x0 2x2 0x10]
== 10x0

After a bit of console time, fiddling around with various combinations of numbers, I came to the following conclusion about how I think they go about their business.

The second value in each pair has priority. If one item has the most extreme value, in the second value of the pair (pair/2 or pair/y), then that pair is the winner. If two, or more, items have the same y value, then their x values are compared and the more extreme wins. If the x values also match, the first one in the series is the winner.

We use first on their result because both minimum-of and maximum-of return the original series at the offset of the item they select.

Now, you might be thinking that the difference in behavior is a bad thing. I thought so too but, as you'll see, they are both useful in their own way. The important thing is to be aware of the difference.

But what are they good for?

Well, suppose you want to know, as the crow flies, how far it is from point a to point b? Thanks to Pythagoras, we can do that.

distance: func [
    "Always returns a positive value"
    a[pair!] b[pair!]
][
    square-root add (power first (a - b) 2) (power second (a - b) 2)
]

Could you do this without pairs? Sure you could. You would just have twice as many parameters and you would have to keep track, yourself, of which values go together.

What if you have a whole bunch of points and you want to know which one is closest to a particular point you have in mind? Well, the first thing we'll do is bring in Larry Palmiter's nifty map function because it will make our lives so much easier. You can certainly do it yourself with a foreach loop, as my first implementation did, but I think using map is cleaner.

map: func [fn blk args /local result][
    result: copy []
    repeat el blk [append/only result fn :el args]
    return result
]

Now we'll make use of it:

nearest-point: func [
    "Returns the point nearest the specified point."
    pt[pair!] "The reference point"
    points[any-block!] "The points you want to check"
][
    pick points index? minimum-of (map :distance points pt)
]

If you're new to Rebol, take a little time to look at what is going on here. Pick gives us a single point from the block of points. Index? tells us which point to pick and is applied to the result of minimum-of. Minimum-of finds the smallest value in the block returned by map. Map returns a block of values which are the result of applying the distance function to each value in the block of points (using the reference point as the second argument when calling the distance function). Wow! All that work done in one line of code! If we want to be orthogonal, we can add the following to our growing library:

farthest-point: func [
    "Returns the point farthest from the specified point."
    pt[pair!] "The reference point"
    points[any-block!] "The points you want to check"
][
    pick points index? maximum-of (map :distance points pt)
]

Notice that the only difference between nearest-point and farthest-point is the use of maximum-of versus minimum-of. Leverage all you can.

What if you know two of the corners for a rectangle but, for some reason, you need to know what all the corners are?

all-corners: func [
    {Returns all corners of the rectangle
    given the upper-left and lower-right corners.}
    ul[pair!] "The upper-left corner of the rectangle"
    lr[pair!] "The bottom-right corner of the rectangle"
    /local result
][
    result: make block! 4
    repend result [
        ul
        to-pair compose [(first ul) (second lr)]  ;ur
        to-pair compose [(first lr) (second ul)]  ;ll
        lr
    ]
    return result
]

Are all these functions really useful? I mean, sure, they're neat but can you solve any real-world problems with them? You bet. I built them for a specific purpose. I had need to draw a line from a known point to the nearest corner of a rectangle, and here's what it boiled down to (minus the actual drawing of the line):

nearest-corner: func [
    "Returns the corner of the retangle nearest the specified point."
    pt[pair!] "The reference point"
    ul[pair!] "The upper-left corner of the rectangle"
    lr[pair!] "The bottom-right corner of the rectangle"
][
    nearest-point pt all-corners ul lr
]

If it weren't for all the documentation, there would be nothing left!

Does 2 pair beat 4 of a kind?

Now that I've got a handle on some of the basics, let me think, where else have I seen this kind of thing used...oh yeah! In rectangles.

A rectangle is made up of four corners, at least where I come from, so that means I'm going to need four pairs...but wait! I've got that nifty all-corners function that only needs two corners to figure out the rest. So I only need two pair, not four.

Momentary Aside

It might appear that I'm one of those people who likes really terse code. I mean, just look at how little code there is so far! Not all is as it seems, however. I'm normally one of the most verbose developers you'll encounter. People say that my function and variable names are longer than necessary, that I add documentation where it isn't really needed (because, hey, that function is so small) and that they have a hard time just getting me to shut up. Can you believe that?

My goal is not brevity, but clarity. To be honest, I'm often surprised by the coding style I find myself using in Rebol. Most times, it seems that the more I take out, the more it makes sense when I read it, but what is clear to me may not be clear to you or, more likely, the reverse will be true.

Now where was I...oh yes, rectangles. Ahh, OOP. If I were an OOP guy, I'd probably build a rectangle object based around my new best friend, the pair! datatype. And I think I will. Rectangle...rectangle...corners, location, extent, and a few standard operations yields (for the sake of argument anyway):

rect: context [
    ul:
    lr:
    top?:
    left?:
    right?:
    bottom?:
    height?:
    width?:
    height:
    width:
    empty?:
    equal?:
    inflate:
    offset:
    contains?:
    intersects?:
    intersection:
    union:
            none
]

We now have a starting point. This is what all rectangles will support. If we flesh everything out, and wrap it up in an easy to use function, we might end up with something like this:

make-rect: func [upper-left[pair!] lower-right[pair!]] [
    make rect [
        ul:      upper-left
        lr:      lower-right
        top?:    does [ul/y]
        left?:   does [ul/x]
        right?:  does [lr/x]
        bottom?: does [lr/y]
        height?: does [bottom? - top?]
        width?:  does [right? - left?]
        height:  func [value[integer!]] [
            lr: to-pair compose [(lr/x) (add ul/y value)]
        ]
        width:   func [value[integer!]] [
            lr: to-pair compose [(add ul/x value) (lr/y)]
        ]
        empty?:  func [
            "An empty rectangle is one with no area"
        ][
            any [(height? <= 0) (width? <= 0)]
        ]
        equal?:  func [
            "Equal rectangles have the same coordinates"
            other "The rectangle you want to compare against"
        ][
            all [(other/ul = self/ul) (other/lr = self/lr)]
        ]
        inflate: func [
            {Grows a rectangle by the specified amounts.
             Negative values shrink it.}
            value[pair!] "The amount(s) to increase/decrease"
        ][
            ul: subtract ul value
            lr: add lr value
        ]
        offset: func [
            {Moves a rectangle by the specified amount(s).
            Negative values are allowed.}
            value[pair!] "The amount(s) to move"
        ][
            ul: add ul value
            lr: add lr value
        ]
        contains?: func [
            {Returns true if the specified point lies within
            the rectangle.}
            pt[pair!]  "The reference point"
            /exclusive {Points lying on borders are not considered
                         to be contained.}
        ][
            either exclusive [
                all [
                    (pt/x > ul/x) (pt/y > ul/y)
                    (pt/x < lr/x) (pt/y < lr/y)
                ]
            ][
                all [
                    (pt/x >= ul/x) (pt/y >= ul/y)
                    (pt/x <= lr/x) (pt/y <= lr/y)
                ]
            ]
        ]
        intersects?: func  [
            "Returns true if the rectangles intersect."
            other {The rectangle you want to check the
                intersection with}
            ; TBD Add /exclusive refinement?
        ][
            any [
                (contains? other/ul)
                (contains? other/lr)
                (other/contains? self/ul)
                (other/contains? self/lr)
                all [
                    (self/left? < other/right?)
                    (other/left? < self/right?)
                    (self/top? < other/bottom?)
                    (other/top? < self/bottom?)
                ]
            ]
        ]
        intersection?: func [
            {Returns the intersection of the two rectangles
             as a block of 2 pair!}
            other {The rectangle you want to create the
                intersection with}
            ; TBD Add /exclusive refinement?
        ][
            either intersects? other [
                make block! reduce [
                    maximum other/ul self/ul
                    minimum other/lr self/lr
                ]
            ][
                make block! [0x0 0x0]
            ]
        ]
        union?: func [
            {Returns the union of the two rectangles as
            a block of 2 pair!}
            other "The rectangle you want to create the union with"
        ][
            make block! reduce [
                minimum other/ul self/ul
                maximum other/lr self/lr
            ]
        ]
    ]
]

So much for brevity. None of the functions are overly long, there are just a bunch of them lumped together in there. Now, let's test things to see if it works.

rect-tests: context [
    r: make-rect 3x3 8x8
 
    contains?: does [
        either all [
            (r/contains? 5x5)
            (not r/contains? 2x2)
            (not r/contains? 2x3)
            (not r/contains? 3x2)
            (r/contains? 8x8)
            (not r/contains? 8x9)
            (not r/contains? 9x8)
            (not r/contains? 9x9)
            (r/contains? 5x8)
            (r/contains? 8x5)
        ][print "contains? passed"][print "contains? failed"]
    ]
 
]

OK, so this is only testing the contains? function. Did I test the others? Of course! What kind of developer would I be if I didn't test my own code? (Don't answer that. It's a rhetorical question.)

Where are the other tests, you ask? Well, you see, I load things into the console and I type them interactively, and if I were smart I would save those console doodlings as the basis for reusable test suites. After some doodling, I came up with the idea for a "test context", which is what rect-tests is, and thought I'd see how I liked the look of it. Now, if I remember, when I'm doing interactive testing in console, I'll just copy my tests out of it, particuarly those that cause things to fail, and put them into a context that I can use again and again.

A couple things to note, before I forget. I didn't know how I was going to figure out the intersects?, intersection?, and union? functions. Not because they would be terribly complex but because my first instinct said they would be tedious, with loads of comparisons. Of course I could have gone through some books on my shelf to find one that had the answers, but I'm a sick person and wanted to figure it out myself in this case.

Intersects? isn't too bad, we have comparisons to see if we contain a corner of the other rectangle or vice versa. That handles everything except the case where the two rectangles intersect but only their middles overlap, like a cross. That case is handled by the all block which does a kind of criss-cross check of the corners. Rebol has two words 'any and 'all, that are enormously helpful in making your code clearer and more concise where you need and/or logic. Use them. Now where is that Knuth volume...?

Intersection? and union? take advantage of the way minimum and maximum work with pair! values to make the job a no-brainer, and they are just mirror images of each other. What I thought would be a lot of work, and a lot of code resulting from that work, turned out to be almost nothing. The hard part was believing that it actually did what I wanted.

Cleaning up

I'm...sorry, what was that? Oh, yes, you're right intersection? and union? probably should return rectangle objects rather than a block of 2 pair! values. No problem.

intersection?: func [
    {Returns the intersection of the two rectangles
        as a block of 2 pair!}
    other {The rectangle you want to create
            the intersection with}
    ; TBD Add /exclusive refinement?
][
    either intersects? other [
        make-rect maximum other/ul self/ul minimum other/lr self/lr
    ][
        make-rect 0x0 0x0
    ]
]
union?: func [
    {Returns the union of the two rectangles as
     a block of 2 pair!}
    other "The rectangle you want to create the union with"
][
    make-rect reduce minimum other/ul self/ul maximum other/lr self/lr
]

Now, let's test it.

>> r: make-rect 10x10 20x20
>> r2: make-rect 8x12 25x18
>> r/intersection? r2

Hmmm. No result? Oh, that's right, I'm getting an object back now so I need to interrogate it.

>> r3: r/intersection? r2
>> r3/ul
== 10x12
>> r3/lr
== 20x18

Hey, it worked! It's too bad the resulting object isn't auto-interrogated on return from the function. That would make it easier to test things interactively, which I like to do. Something else that is nagging me is the fact that, because Rebol clones objects, every rectangle is going to have it's own copy of all the functions. In some cases that can be valuable because you can have objects which behave differently, but still conform to the same interface. For rectangles, though, they should probably all work the same, and even though memory is cheap, what if you had a really large number of them?

My rectangle stores two corners whereas the standard in Rebol/View, for faces and such, seems to be the use of offset and size. What would it look like, and how would it work, if I made the rectangle object contain only the data elements and moved all the functions out into their own context? What would the code look like that used them? How could I use them with pair! values that aren't contained in rectangle objects? Will Thor marry Susan?

Stay tuned...