• The Old New Thing

    Seattle to Portland (STP) 2007 trip report, part 2 of 4: Spanaway to Toledo

    • 7 Comments

    Note: This story makes much more sense if you read Part 1 first. It won't be any more interesting, but at least it'll be a coherent sort of boring.

    12:20pm: We arrive in Spanaway for the lunch break (54 miles) [pic]. The consensus among seasoned riders appears to be that the Saturday lunch is pretty lame this year. It consists of a rice and bean wrap, a bagel, and a handful of grapes. I don't think it's so bad, but then again, I don't know what to expect either.

    Given that we lost a good chunk of time, I suggest that S, Z and I get a head start, since we tend to go slower. (S's normal pace is a bit slower; Z is slower thanks to mechanical problems; and I'm slower because I'm making sure we don't lose S and Z.) "Grab our bikes and meet back here." S and I grab our bikes and meet back here. We can't find Z. By the time we find him, the rest of the group (the "fast half" I'll call them) had already decided it was time for them to go, too, so even our head start evaporated before we hit the street at 12:40pm.

    I think that S and Z are ahead of me, so I pick up the pace. Flying down Highway 507 is a blast. The bulk of the riders head single file down the highway, with faster riders forming a "passing lane" just to the left. It's close quarters since the highway still has traffic on it, but everybody seems to know what to do and the miles fly by. I'm glad I have my bell because it saves me from having to put any more stress on my sore throat, which has been worsening throughout the day. Discussing the ride afterwards, A noted that when he did STP in one day, it was on this stretch of road between Spanaway and Roy that he joined a paceline and was able to go really fast. Not everybody thinks that this stretch of 507 is all that great, though. (Day Two.) And here's another rider's impressions of the cars on 507. (Day Two.)

    There was one tricky part about riding along this stretch of road: The white line at the edge of the road had divots cut out of it at regular intervals. For example, it would be clear for twenty feet, and then for twenty feet there would be pits cut into the road. And then clear for twenty feet, and so on. (The purpose is to warn drivers who wander off the edge of the road.) This made changing lanes tricky since you not only had to watch for traffic in the lane you want to change into, but you also have to time your crossing to coincide with one of the clear patches rather than the pitted segment. Apparently not everyone was able to negotiate this obstacle successfully.

    Between Roy and McKenna, around 295th St, I catch up to the lead group and ask them, "Have you seen S and Z?" No they haven't; I must've left them behind. I pull over at the entrance to the gravel facility and wait. Six minutes later, they show up, and I'm back on the road.

    At the end of the day, S asked me, "So did you see the Y in Roy?"

    What, Y as in YMCA?

    "No, Y like a fork in the road. People were talking about 'Make sure you don't miss the Roy Y' but I didn't see it."

    The only Y I remember was back in Spanaway, where we turned right at the Shell gas station onto Highway 507.

    It turns out I was right without even realizing it. The "Roy Y" is the point in Spanaway where Highway 507 starts. It's called the "Roy Y" not because it's in Roy but because it leads to Roy.

    We continue past the McKenna mini-stop without stopping because it's only four more miles to the next mini-stop.

    2:10pm: Yelm (mile 72). We take a longer-than-usual break here because Z is suffering from fatigue thanks to a suboptimal bicycle. ("Where are the sofas?" he asks.) Inside the portable toilets, there's a sticker that reads "Sanitary seat covers supplied for an additional charge, upon request of supperintendent." I don't know what a supperintendent is, but I don't want him hanging around in portable toilets.

    We are by now well into the hottest part of the day, and I have to resort to pouring water on my head to cool off. They do it on TV all the time and make it look so easy. It's quite nice, but also a minor challenge to keep the water from dripping onto your glasses.

    The fast group heads out first, and some minutes later, us slowpokes get on our bikes and continue onward.

    Or at least we try to.

    We are sort of the head of a clump of riders who leave at the same time, and I'm not able to stop them after they miss a turn. I shout feebly (sore throat), but they don't hear me. I finally catch up when they find themselves at a dangerous intersection with no Dan Henry to tell them what to do. "Hey, you missed a turn back there."

    We all turn around and head back, but the damage has been done. We became the trailblazers for hundreds of cyclists who are now heading the wrong way. As we backtrack, we try to tell them, "Wrong way! Go this way!" but they either don't hear us or don't understand what we're trying to say. They probably won't figure it out until they get to the same dangerous intersection and realize, "Oh, they were trying to tell us we were going the wrong way."

    Now on the correct route, we wait for a police officer to stop traffic so we can cross Highway 507 and ride on the Yelm/Rainier/Tenino trail. The first stretch of this trail is tricky since you're in a big clump, but eventually things spread out and you can ride at your target pace. At mile 77, Z's rear tire springs a flat. S goes on ahead, figuring that she's the slowest of the group and could use the head start. (We won't see her again until Centralia.) I pull out my patch kit and repair the puncture. A few minutes later, the tube is back in business, and we resume our travels.

    The bike mirror comes in really handy here, because I can ride ahead of Z and check in the mirror that he's still with me. I've figured out that the trick for not getting too far ahead is to shift to a lower gear to slow down; that way I can keep pedaling at my natural cadence without accidentally pulling away. I'm exerting practically no effort at this point in the ride.

    We reach the crossing at milepost 84 and watch one of the two police officers directing traffic nearly cause an accident. There are two officers at the point where the trail crosses the highway, one standing on each side of the crossing, and each holding a sign that reads STOP on one side and SLOW on the other. The officers agree to stop car traffic, and one one officer turns his sign from SLOW to STOP. The other, however, forgets to turn his sign, so it still reads SLOW. The first officer shouts, "Mike! ... Mike, turn the sign!" But Mike doesn't seem to hear him. Instead, he's distracted by a motorcycle coming down the highway that fails to come to a stop. He shouts at the motorcyclist and waves the sign in the rider's face, nearly knocking the rider off the motorcycle. Mike angrily runs to his police cruiser prepared to chase down the motorcyclist for failing to stop, but his partner finally gets his attention. "Mike, I was trying to tell you: You forgot to turn your sign. It still said SLOW."

    The officers check their signs (STOP) and wave us bicyclists across. A few miles later, we reach the Tenino ministop but keep going because we're pretty far behind schedule at this point.

    3:55pm: We reach the Tenino railroad crossing just in time to watch the Amtrak Cascades 507 go past at 70 mph. I've ridden the Talgo trains many a time, but those are different stories for a different time. It was just interesting seeing the train from the outside.

    5pm: Z and I are in Centralia, drawing close to the official midpoint stop at Centralia College, but oh, we get stuck at another railroad crossing. And this isn't a fast crossing like that Amtrak train. This is a cargo train, so it goes nice and slow, and it drags a hundred boxcars behind it. The midpoint stop taunts me from only a mile away. (At least at this crossing, nobody gets impatient and tries to sneak between two train cars, like they did at the finish, or crawl under a stopped train like people allegedly did in Puyallup.)

    Centralia College is the stopping place for a large number of cyclists, so by the time Z and I roll in under the misters it's a pretty festive atmosphere. We missed the orange creamsicles on the way in, but S helps us find them. Ah, ice cream. Z has been taunted all day by promises of ice cream and met with abject disappointment at each rest stop when he discovers that they don't have any. But now, he has his ice cream.

    5:35pm: We still have another 23 miles to go before we reach our Day One destination, Toledo High School. Once out of downtown Centralia, the route follows Airport Road, with the airport on one side and farmland on the other. There I see the world's largest garden hose reel, about ten feet tall. We also catch up to and chat with a gentleman on a unicycle before resuming speed and continuing to Chehalis. (Here's the web page of a fellow who rode a unicycle in the 2005 STP.)

    In Chehalis, we diverge from the official route and instead take Jackson Highway, which runs roughly parallel to the east. This was the dreariest part of the ride. It's been a long day, we have 17 miles to go, the rural scenery becomes tiresome, there are hills, it sucks the life out of you. But we have to get there before dark, so we soldier on. (If it's any consolation, J says that the main route through Napavine and Winlock is equally dreary.)

    While riding along Jackson Highway, the lead group passes a woman in her sixties who stops her bicycle and starts to turn around. S senses that the woman may be in trouble, and she stops to ask her if she needs any help. Turns out that she's trying to get to the Bethel Church which is her Day One stopping point. (Many churches and schools make themselves available to STP participants.) The woman pulls out a map which has the route to the church highlighted on it. Unfortunately, she's nowhere near that route. We call the church's phone number, but nobody answers. When S asks her what she's doing on Jackson Highway instead of following the directions on the sheet, she responds, "Well, I got a green wristband, so I thought I should follow the green arrows painted on the road."

    Actually, the green arrows lead to Toledo High School.

    S spots a road sign and cycles to it to figure out where we are. (She also calls the lead group to let them know we've stopped to help a lost cyclist.) Meanwhile, I study the map and make small talk. Have you ridden STP before? I ask.

    "This is my first time."

    Are you riding with anybody else?

    "Nope, I'm by myself."

    Wow, that's very, um, courageous of you.

    S returns with a location fix, and we realize that the woman is not too far from her destination, even though she definitely chose a suboptimal route to get there. We ride with her to Bishop Road and give her the rest of the directions ("turn left at Rush Road and you're back on track"). I didn't want to say "Good-bye", since that sounds rather ominous, so instead I said, "See you in Portland." For the rest of the trip, I used that farewell when talking to another rider. It has a very hopeful ring to it.

    After the woman bicycles away, S wonders aloud, "Doesn't she have kids and grandkids that tell her not to go do stuff like this by herself?"

    The woman also happens to have the highest bib number I'll see during the entire ride: 8973. Everybody on STP plays the bib number game, looking for the lowest and highest. Up to this point in the ride, my lowest is 41, part of a group of three riders numbered 41, 42 and 43 who passed me on the Yelm/Rainier/Tenino trail. This record will hold until midway through Day Two, when I see my lowest bib number, 17. (ZappoMan meets Rider Zero, which is the lowest possible bib number unless they have negative numbers.)

    6:45pm: It turns out that our delay for helping the lost woman doesn't cost us any time, because when S and I reach (I am not making this up) Vista Road, we find the lead group sitting by the side of the road tending to a flat tire. M ran over a sharp object. And yes, if you look at the map, Vista Road is a dead end. Omen? Who can say.

    Okay, tube all patched up, back onto the road. Just twelve miles to go. The twelve most dreadful miles of the entire trip. M and A spring ahead, and I take the opportunity to join the lead group for a change, leaving J to make sure we don't lose S and Z. We regroup at the Highway 12 crossing and ride past the John R. Jackson House, a building that I'm sure carries great historical significance for the area, but we weren't really in the mood to care by this point. Not far past the John R. Jackson house is the Jackson Prairie Speedway, which is already roaring with the sound of auto racing when we cycle past. At least now we know what people in Chehalis do on Saturday nights.

    After several shouts of "Are we there yet?" we finally... Nope, just kidding. We're not there yet.

    My sore throat by this point has gotten so bad I can talk only with some difficulty and pain. I try to get by with nods and hand gestures.

    At last, we... nope, still not there. What looks from a distance to be a high school athletic field is just a softball facility. The local softball team won the state championship in 2001, so this area is all softball crazy.

    Okay, finally we reach Toledo High School. The kitchen is making a new batch of spaghetti, so we can't eat quite yet. We take the opportunity to stow our bicycles, move our stuff into the classroom we reserved (our group is large enough that we get an entire classroom to ourselves), take a shower, and settle in. By the time we finish eating, it's nearing ten o'clock, and we really aren't interested in doing much beyond falling asleep.

    That was a long Day One. (You thought reading about it was long and tiring, try doing it!)

  • The Old New Thing

    News flash: Work-at-home job offers are mostly just scams

    • 8 Comments

    McClatchy Newspapers discovers, to everyone's surprise, that work-at-home job offers are mostly just scams. Of course, this is something Rob Cockerham discovered years ago. (He also has a rundown of all his articles on the subject, in case you haven't gotten enough.)

  • The Old New Thing

    The 2013/2014 Seattle Symphony subscription season at a glance

    • 10 Comments

    For many years, I've put together a little pocket guide to the Seattle Symphony subscription season for my symphony friends to help them decide which ticket package they want. In the years that have passed since I started doing this, nearly all of the members of the group have started families, and we tried things like splitting tickets, but even that became difficult to maintain, and last year, we ended up not ordering any tickets at all. (Well, no tickets for adults. We did buy tickets to kids concerts.)

    I compiled the at-a-glance season guide for the 2013/2014 season anyway, but I didn't bother adding my comments since we know we're not ordering any tickets. Moreover, the Seattle Symphony created online playlists where you can listen to the pieces in the upcoming season, so you can decide for yourself whether you like them or not!

    Here is the official brochure for those who want to read the details, and you can see what The Seattle Times thinks of it. To access the playlists, go to www.naxos­music­library.com and log on with userid SymphonySubs with password 20132014. Once you've logged in, click Playlists in the navigation bar and choose the concerts you want to hear.

    Week Program 21 13 7A
    7B
    7C
    7D
    7E
    7F
    7G 4A HS SU WG
    09/19
    2013
    Ravel: Alborada del gracioso
    Ravel: Concerto for Left Hand in D
    Ravel: Rapsodie espagnole
    Ravel: Pavane pour une infante défunte
    Ravel: Piano Concerto in G
    Ravel: Boléro
                   
     

     
     

     
     
    10/03
    2013
    Beethoven: Triple Concerto
    Schubert: Symphony #9 in C The Great
                       
    10/10
    2013
    Purcell: Suite
    Mozart: Piano Concerto #23 in A
    Vaughan Williams: Symphony #5
                       
    10/18
    2013
    Mozart: Divertimento for String in D
    Dittersdorf: Sinf. concertante for Double Bass & Viola
    Mozart: Exsultate jubilate K.65
    Mozart: Symphony #29
                       
    10/24
    2013
    Elgar: Serenade
    Haydn: Cello Concerto in C
    Mozart: Symphony #37
    Tchaikovsky: Serenade for Strings
                       
    11/07
    2013
    Boulez: Notation
    Mahler: Symphony #6
                       
    11/13
    2013
    Sibelius: Tapiola
    Pascal Dusapin: Violin Concerto
    Beethoven: Symphony #6 Pastoral
                       
    11/21 Verdi: Requiem                    
    12/13 Vivaldi: The Four Seasons                    
    12/20 Handel: Messiah                    
    12/23 Christmas carols (Northwest Sinfonia)                    
    12/31
    2013
    Gershwin: Rhapsody in Blue
    Tchaikovsky/Ellington: Nutcracker excerpts
    Williams: Star Wars excerpts
    other amusements
                       
    01/02
    2014
    Brahms: Variations on a Theme by Haydn
    Beethoven: Symphony #9 Choral
                   
     
     
    01/23
    2014
    Prokofiev: Symphony #1 Classical
    Haydn: Piano Concerto in D
    Prokofiev: Piano Concerto #4
    Mozart: Symphony #35 Haffner
                       
    01/30
    2014
    John Adams: The Chairman Dances
    Shostakovich: Piano Concerto #2
    Liszt (arr John Adams): The Black Gondola
    Shostakovich: Symphony #9
                   
     

     
     
    02/13
    2014
    Schumann: Cello Concerto
    Berlioz: Symphonie fantastique
                       
    03/06
    2014
    R. Strauss: Don Juan
    R. Strauss: Burleske
    R. Strauss: Divertimento
    R. Strauss: Suite from Der Rosenkavalier
                       
    03/13
    2014
    Dvořák: The Noonday Witch
    Bartók: Violin Concerto #2
    Mozart: Symphony #38 Prague
                       
    03/20
    2014
    Rimsky-Korsakov: Suite from The Snow Maiden
    Alexander Raskatov: Piano Concerto
    Tchaikovsky: Symphony #6 Pathetique
                       
    03/27
    2014
    Dvořák: Cello Concerto
    Varèse: Déserts
    Debussy: La Mer
                       
    04/03
    2014
    Haydn: Symphony #100 Military
    Orff: Carmina burana
                       
    04/17
    2014
    James MacMillan: The Death of Oscar
    Beethoven: Piano Concerto #3
    Rachmaninoff: Symphony #2
                       
    04/24
    2014
    Martinů: Memorial to Lidice
    Brahms: Violin Concerto
    Dvořák: Symphony #7
                       
    06/05
    2014
    Dutilleux: Symphony #2 Le double
    Ravel: Daphnis et Chloé complete ballet
                       
    06/12
    2014
    J. Strauss: Emperor Waltzes
    Schoenberg: Piano Concerto
    Brahms: Symphony #2
                       
    06/19
    2014
    Stravinsky: The Firebird
    Stravinsky: Petrushka
    Stravinsky: The Rite of Spring
                   
     


     
    Week Program 21 13 7A
    7B
    7C
    7D
    7E
    7F
    7G 4A HS SU WG

    Legend:

    21Masterworks 21-concert series (Choice of Thursdays or Saturdays)
    13Masterworks 13-concert series (Choice of Thursdays or Saturdays)
    7AMasterworks 7-concert series A (Thursdays)
    7BMasterworks 7-concert series B (Saturdays)
    7CMasterworks 7-concert series C (Thursdays)
    7DMasterworks 7-concert series D (Saturdays)
    7EMasterworks 7-concert series E (Thursdays)
    7FMasterworks 7-concert series F (Saturdays)
    7GMasterworks 7-concert series G (Sunday afternoons)
    4AMasterworks 4-concert series A (Friday afternoons)
    HSHolidays at the Symphony
    SUSymphony Untuxed (Fridays, reduced program)
    WGWolfGang (Various evenings), see notes below

    For those not familiar with the Seattle Symphony ticket package line-ups: Most of the ticket packages are named Masterworks nX where n is the number is the number of concerts in the package, and the letter indicates which variation. Ticket packages have been combined if they are identical save for the day of the week. For example, 7C and 7D are the same concerts; the only difference is that 7C is for Thursday nights, while 7D is for Saturday nights.

    The WolfGang series is available only to members of the WolfGang club. It also includes two concerts not listed above (Opening Night and Sonic Evolution).

    This chart doesn't include "one-off" concert series such as the Mainly Mozart or Distinguished Artists series. A "one-off" series is a concert series which shares no concerts with any other series. This year, the Beyond the Score multimedia concerts fell into that category.

    According to the Seattle Times article, the new music director has "always dreamed of spending a whole evening with a composer," and he went big this year, with three concerts consist of multiple works by a single composer.

    Symphony trivia: The audience for the Sunday afternoon concerts (series 7G) leans toward what we in the United States euphemistically call senior citizens. I find it interesting to see what those sweet old ladies get put through every year. For example, this year, they get a performance of Carmina burana, which will probably offend half of the audience and delight the other half.

  • The Old New Thing

    The three things you need to know about tsunamis

    • 9 Comments

    One of my friends is involved with Science on Tap, a free, informal monthly get-together in the Seattle area covering science topics for the general public. (Recent coverage in the Seattle-PI.) The topic for July 30th is "The three things you need to know about tsunamis", and a title like that pretty much sells itself.

  • The Old New Thing

    A complex family calculus

    • 16 Comments

    I spent the other night at a relative's house, and I was woken the next morning by my young niece who politely asked me to make her breakfast. (Her technique for waking me up is to come in and call my name. If the door is closed, she pounds on the bedroom door and shouts, "Wake up! Wake up!" If I fail to open the door, she opens it herself. If the door is locked, she jiggles the handle until she forces the door open. I just leave the door open now. Making the best of a bad situation.)

    Anyway, later that morning, the following conversation took place between my niece and an adult family member (which conversation I have taken the liberty of translating into English):

    "Why did you wake up Uncle Raymond?"

    I wanted cereal for breakfast.

    "Why didn't you ask Mommy?"

    Mommy was still sleeping.

  • The Old New Thing

    Who decides what can be done with an object or a control?

    • 8 Comments

    This is one of those things that is obvious to me, but perhaps is not obvious to everyone. An object establishes what can be done with it. Any rights granted by the object go to the creator. The creator can in turn grant rights to others. But if you're a third party to the object/creator relationship, you can't just step in and start messing around without the permission of both the object and the creator.

    For example, unless you have permission of the creator of a list view control, you can't go around adding, removing, and changing items in the list view. The creator of the list view decides what goes in it, and at most you can look at it to see what the creator decided to put in it. I say "at most" because you often can't even do that: If the fact that the item is a list view control is not public, then the program that created the list view might decide to use some other control in a future version, and then your code that tries to look at the list view will stop working.

    Naturally, any private data associated with a control (such as the LPARAM associated with a list item) is entirely under the purview of the control's creator. The creator of the control decides what the item data means, and that can change from version to version if not explicitly documented. (For example, the meaning of the item data associated with the main list view in Explorer windows has changed at pretty much every major release of Windows.)

    Generally speaking, without the permission of the creator of a control and the control itself, you can't do anything to it. You can't hide it, show it, move it, change its scroll bars, mess with its menus (assuming it even uses menus at all), change its text, or destroy it. The code that created the control and the control itself presumably maintain their own state (the control maintains state about itself, and the creator maintains state about what it has done to the control). If you start messing with the control yourself, you may find that your changes seem to work for a while and then are suddenly lost when the control decides to re-synchronize its internal state with its external state. Or worse, things will just be permanently out of sync, and the program will start acting strange. If the control and the control's creator have not provided a way to coordinate your actions with them, then you can't mess with the control.

    If you're tempted to go mess with somebody else's controls, think about how you would like it if the tables were turned. How would you feel if somebody wrote a program that took the controls in your program and started messing with them, say adding items to your list box and using the item data to extract information out of your program? What if they started filing bugs against you for changing the way your program operates internally?

  • The Old New Thing

    The mystery of the garbage lady

    • 11 Comments

    Last year, my good friend and colleague Sarah transfered from the Redmond offices to Microsoft UK in Reading. One of her most popular lunchtime stories is the mystery of the garbage lady, which she finally got around to posting on her blog.

    Some of my other favorite stories from her blog:

    A colleague of mine experienced the phenomenon of clouded geography in reverse. He was temporarily assigned to Microsoft UK and while living there had occasion to drive out to Wales. He pulled out his handy road map and studied it: "Okay, I need to take this highway west, over the mountain range, and then take that exit, and then I'll be there." He hopped in his car and started driving.

    After a while he started getting nervous. It was getting late, and he still hadn't reached the mountain range yet. He started worrying that the people he was meeting at the destination would be concerned when he failed to show up on time. (I guess he picked up the British habit of worrying about other people being worried.)

    And then he saw the exit, and boom, he was at his destination.

    Afterwards, he went back to the map to see what happened.

    The first issue was one of scale. His map was of all of Great Britain, and he assumed that the scale of such a map was comparable to maps of large areas of the United States. A route that goes halfway across a large map, say a map of the state of Washington, will take a few hours to cover. The UK is comparatively much more compact. From Reading, you can get to the Welsh border in 90 minutes.

    The second issue was one of geography. What was notated on the map as a mountain range was, to someone more familiar with the mountains of western North America, just a hill.

  • The Old New Thing

    Answers to exercises

    • 0 Comments

    Exercise: Explain why we used 0x7FFF to represent infinite height.

    Answer: Commenter "Reiko" got this right. 0x7FFF is the maximum integer coordinate supported by Windows 95, 98 and Me.

    Exercise: Explain the line rcWindow.bottom += rcTemp.top.

    Answer: The more precise way of writing the line would have been

        rcWindow.bottom += (rcTemp.top - rcWindow.top) - (0 - rcWindow.top);
    
    The first term is the amount of non-client space consumed at the top of the window. The second term is the amount of non-client space consumed at the top of the window, taking wrapping into account. The difference, therefore is the amount by which AdjustWindowRectEx needs to be adjusted. But the two instances of rcWindow.top cancel out, leaving just rcTemp.top.
  • The Old New Thing

    Enumerating bit strings with a specific number of bits set (binomial coefficients strike again)

    • 9 Comments

    Today's Little Program prints all bit strings of length n subject to the requirement that the string have exactly k 1-bits. For example, all bit strings of length 4 with 2 bits set are 0011, 0101, 0110, 1001, 1010, and 1100. Let's write BitString(n, k) to mean all the bit strings of length n with exactly k bits set.

    Let's look at the last bit of a typical member of BitString(n, k). If it is a zero, then removing it leaves a string one bit shorter but with the same number of bits set. Conversely every BitString(n − 1, k) string can be extended to a BitString(n, k) string by adding a zero to the end.

    If the last bit is a one, then removing it leaves a bit string of length n − 1 with exactly k − 1 bits set, and conversely every bit string of length n − 1 with exactly k − 1 bits set can be extended to a bit string of length n with exactly k bits set by adding a one to the end.

    Therefore, our algorithm goes like this:

    • Handle base cases.
    • Otherwise,
      • Recursively call BitString(n − 1, k) and add a 0 to the end.
      • Recursively call BitString(n − 1, k − 1) and add a 1 to the end.

    This algorithm may look awfully familiar. The overall recursive structure is the same as enumerating subsets with binomial coefficients; we just decorate the results differently.

    That's because this problem is the same as the problem of enumerating subsets. You can think of the set bits as selecting which elements get put into the subset.

    It's not surprising, therefore, that the resulting code is identical except for how we report the results. (Instead of generating arrays, we generate strings.)

    function repeatString(s, n) {
     return new Array(n+1).join(s);
    }
    
    function BitString(n, k, f) {
     if (k == 0) { f(repeatString("0", n)); return; }
     if (n == 0) { return; }
     BitString(n-1, k, function(s) { f(s + "0"); });
     BitString(n-1, k-1, function(s) { f(s + "1"); });
    }
    

    If k is zero, then that means we are looking for strings of length n that contain no bits set at all. There is exactly one of those, namely the string consisting of n zeroes.

    If k is nonzero but n is zero, then that means we want strings of length zero with some bits set. That's not possible, so we return without generating anything.

    Finally, we handle the recursive case by generating the shorter strings and tacking on the appropriate digits.

    Since this is the same algorithm as subset generation, we should be able to write one in terms of the other:

    function BitString(n, k, f) {
     Subsets(n, k, function(s) {
      var str = "";
      for (var i = 1; i <= n; i++) {
       str += s.indexOf(i) >= 0 ? "1" : "0";
      }
      f(str);
     });
    }
    
  • The Old New Thing

    When you share an input queue, you have to wait your turn

    • 15 Comments

    Now that we've had a quick introduction to asynchronous input, let's look at some of the details. Remember, this is a peek under the hood at how the sausage is made. The algorithm described here is not part of the API contract and it can change at any time, as long as it services the overall goal of serializing input.

    Let's start by looking at how things worked in the 16-bit world. Even though 16-bit Windows didn't use the term thread (since each application was single-threaded), I will still use the term since that makes the transition to the 32-bit world more straightforward.

    As a point of terminology, I say that a message belongs to a thread if the message targets a window which belongs to that thread. Equivalently, the thread owns the message.

    Now, the goal is to dispatch input messages in chronological order: Only the thread which owns the next input message can retrieve it. All other input must wait their turn to come to the front of the input queue.

    In 16-bit Windows, all input gets added to a system-wide input queue, and the basic algorithm used by Peek­Message and Get­Message for retrieving messages from the input queue goes like this.

    • Look at the first message in the input queue:
      • If the message belongs to some other thread, then stop. Return no message to the caller.
      • Otherwise, return the message we found.
    • If there are no messages in the input queue, then there is no input. Return no message.

    All the rest is tweaking the boundary cases.

    For example, suppose there are two input messages in the input queue, message 1 for thread A, and message 2 for thread B. Thread A calls Get­Message, and the above algorithm returns message 1 to thread A, at which point the new "first message" is message 2, and if thread B calls Get­Message, it will get message 2.

    The catch is that according to the above algorithm, thread B can be told about message 2 before thread A has finished processing message 1. You've introduced a race condition that breaks the rule that input is processed sequentially: Thread B can race ahead of thread A and start processing message 2 before thread A can even get started processing message 1.

    To fix this, we add a new state to the input queue that says "Yea, I just gave somebody an input message, and I'm waiting for that thread to finish processing it before I will hand out another input message."

    • (New!) If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
    • (New!) If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting. (We finished processing it and have come back for more!)
    • Look at the first message in the input queue:
      • If the message belongs to some other thread, then stop. Return no message to the caller.
      • Otherwise, (New!) mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
    • If there are no messages in the input queue, then there is no input. Return no message.

    Okay, we fixed a race condition. But now there's a new problem: Suppose thread A retrieves an input message (and therefore puts the input queue into the "waiting for thread A" state), and then thread A sends a message to thread B, and thread B wants to display a dialog box or a menu. According to the rules as we have them so far, we would have a deadlock: That Send­Message call will not return to the first thread until the modal UI is complete, but the modal UI cannot complete because the input queue is waiting for thread A to finish processing the input message.

    The fix for this special case is that if a thread asks for an input message, and it is handling an inbound Send­Message, then the input queue declares that any in-progress input message has finished processing. One way of interpreting this rule is to say, "If a thread sends a message to another thread, then that implicitly completes input processing."

    • (New!) If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
    • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
    • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
    • Look at the first message in the input queue:
      • If the message belongs to some other thread, then stop. Return no message to the caller.
      • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
    • If there are no messages in the input queue, then there is no input. Return no message.

    Recall that you are allowed to pass a message range filter and a window handle filter to the Peek­Message and Get­Message functions. The above algorithm was developed on the assumption that there was no message retrieval filter. First, let's add the message range filter to the algorithm:

    • If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
    • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
    • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
    • Look at the first message in the input queue which satisfies the message range filter (New!):
      • If the message belongs to some other thread, then stop. Return no message to the caller.
      • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
    • If there are no messages in the input queue which satisfy the message range filter (New!), then there is no input. Return no message.

    That wasn't so hard. If you pass a message range filter, then we care only about messages that pass the filter in determining which one is "at the head of the input queue". Without this additional rule, you wouldn't be able to "peek into the future" to see if, for example, there is a mouse message in the input queue sitting behind the keyboard message that is at the front of the input queue.

    Adding the window handle filter is a little trickier, because we still want to let input be processed in order (among messages which satisfy the message range filter).

    • If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
    • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
    • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
    • Look at the first message in the input queue which satisfies the message range filter and (New!) either belongs to some other thread or belongs to the current thread and matches the window handle filter.
      • If the message belongs to some other thread, then stop. Return no message to the caller.
      • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
    • If no such message exists, then there is no input. Return no message.

    In other words, the window handle is used to control which message is ultimately retrieved, but it does not let you deny another thread access to input which matches the message range filter.

    Whew, that's how 16-bit Windows dispatched input.

    How do we port this to 32-bit Windows and asynchronous input?

    First, we give each thread group its own input queue, rather than having a single system-wide input queue.

    Second, whenever the above algorithm says the input queue, change it to say the calling thread's input queue.

    And that's it!

    In the absence of thread attachment, each thread has its own input queue, so most of the above rules have no effect. For example, You will never see a message that belongs to another thread, because messages that belong to other threads go into those other threads' input queues, not yours. You will never find that your input queue is waiting for another thread, because no other threads have access to your input queue. In the case where there is only one thread associated with an input queue, the algorithm simplifies to

    • Return the first message in the input queue that satisfies both the message range filter and the window handle filter, if any.

    It's only if you start attaching threads to each other that you have multiple threads associated with a single input queue, and then all these extra rules start to have an effect.

    Next time, we'll explore some of the consequences of synchronous input by writing some poorly-behaving code and observing how the system responds. Along the way, we'll discover an interesting paradox introduced by the above algorithm.

    Exercise: The alternative interpretation I gave above does not match the description of the rule, because the rule allows any thread processing an inbound Send­Message to clear the input queue's wait state. Why does the actual rule permit any thread clear the wait state, instead of first checking that the inbound Send­Message is coming from the thread that the input queue is waiting for?

Page 378 of 455 (4,543 items) «376377378379380»