Parsing XML in ActionScript 3

I recently had a task handed down at work requiring me to parse XML data in ActionScript 3. It sounded simple, because AS3 includes documented libraries to handle XML content. But on my first pass trying to use them, I got unexpected results. After some investigation, I was able to understand what was happening. I was surprised the AS3 documentation didn't explain the behavior of the XML and XMLList classes in better detail, so I hope to fill some of the gaps with a quick write-up of my misadventure.

It was little trouble getting the XML file loaded into AS3, and I verified that the file was loading correctly by tracing the resultant XML object's contents in output. But when I tried to filter XML elements out of the XML object by tag name or attribute content, I would sporadically get unexpected results, or get no results returned at all (an empty set).

Just for some background, the XML files I was working with contained various lists of buttons for a video game UI. Each button had a button type denoted by its tag title, for example Slider, Toggle, or just plain Button. Each then had attributes, such as Name, ID, and DisplayText. So the XML would look something like this:


Note that none of the elements in the above example have any text content! My attributes have values, but the tags have no content between them. (This is legal in XML, but may have been unwise in retrospect, at least for debugging purposes.)

When I tried to filter based on button type (in other words, by tag name, e.g. Slider, Toggle, or Button) I would get strange results. When filtering MainMenu, I'd get a list of XML objects for Slider tagged elements and Button tagged elements, as desired; but would receive an empty string when filtering on Toggle tagged objects. Conversely, when filtering GfxMenu, I'd get the opposite; XML objects for Toggle tagged elements but empty strings for the others. What?!

At first, I didn't see why this would be happening, and I scoured the AS3 documentation to no avail. But after some experimentation I realized that when filtering, if only one element within the search range meets the requirements of a given search, AS3's XML class will return the text content of the element's tag automatically! And if multiple elements meet the search criteria, a list of XML elements will be returned.

I don't know if this was done to satisfy some language specifications or what, but that's what I was able to figure out!

Mystery solved.

Thanks for reading!
-- Steven Kitzes

Bitmask Basics

Working directly with bits is one of my favorite things to do as a programmer. I just find it fun! I haven't used these techniques recently in any of my projects, but I wanted to take some time to explain how bitmasks work, and some of their uses and advantages. Hopefully you'll agree they're very useful, and you'll see why I like them so much!

Higher level bitwise operations (also known as bit masking, bit flagging, etc) are great for a number of reasons. I find them quite fun, in addition to being useful and more efficient than other methods of Boolean comparisons and assignments. But before going into the methods and uses of bitmasking I should give a little bit of background on the topic. I'll be giving my examples in C++ because that's the language I'm most comfortable and familiar with, but bitmasking is possible in many languages.

First of all, what is a bitmask (or, what do I mean when I say bitmask)? In C++ (or any typed language), there are many data types that you are probably familiar with. These data types represent collections of bits, organized into bytes, stored in memory. We normally think about our variables and constants in terms of a given type (for example, int, double, or maybe even float), but behind the scenes an int or double still represents a contiguous set of bits.

Let's take the char data type in C++ as an easy example (it only represents a single byte, 8 bits). We can manipulate and compare data types such as chars in terms of their constituent bits. One way of terming such a collection of bits in this context is as a bitmask. This is often the case when using a char or int not to represent an actual character or integer, but rather to represent a condensed set of Boolean values.

At this point, you may be wondering: why is this useful? Isn't it simpler to just make a bunch of bool variables and compare those? Well, yes; that would be simpler, and easier for a human to read in the code. But it would necessitate long, convoluted argument lists if those bools ever needed to be passed around; not to mention that the bool type is very wasteful in languages like C++. Remember, the smallest size for a data type is one byte, 8 bits. So for C++ to store a bool in memory, it must allocate a full byte - 8 bits - even though only one bit is really needed to represent a Boolean value. Then, when making comparisons, an entire operation is wasted on each individual check against each individual bool. Holy smokes!

Alternatively, if we have a large number of Boolean variables that we need to track, instead of wasting an entire byte on a bool for each Boolean variable we want to track, we can track up to 8 Boolean values using a char's 8 individual bits, in the form of a bitmask! (Or, to expound on that idea, up to 16 values in a short int, 32 in a standard int, etc.) In addition to the efficiency achieved by storing several Boolean values' worth of information under a single primitive data type, this also means we can save a lot of time by comparing or manipulating several Boolean values in one go, as well! And of course, we can pass a bitmask as a single arg, which communicates a lot of Boolean data in a single variable, as opposed to needing to go through the hassle of passing multiple bools or encapsulating them in a container of some kind. So how does all this work...?

Example Time

Let's start by visualizing a C++ char's bits.

As an empty bitmask, with no bits turned on, our char would look like this:

00000000

If all the bits were flipped / turned on, it would look like this:

11111111

And with some bits on and some off, the bitmask would look like this:

00101101

Comparing two bitmasks against each other, or checking if a bitmask is either zero or non-zero works more or less as you would probably expect. Keep in mind, the following bitmasks are contained in char type variables. That's why they have 8 bits each.


C++ doesn't know or care that we're using our char as a bitmask. It just so happens that we are able to use bitwise operations and comparisons on our char. This means that while we may choose to perform bitwise operations and comparisons on our char, typical C++ comparisons like those on line 10 (comparing identical bitmasks) and line 14 (comparing differing bitmasks) return true and false results just as we would expect. Of course, zero / non-zero checks (such as on line 20) work as we are used to. And finally, assignment works as you would expect as well (such as on line 25).

The real value in bitmasks starts to become clear when we look at some of the special operators we can use to compare bitmasks against each other. These are the ampersand, the bar, and the carrot (& | ^). Let's take a look at what each of these operators does.

When using these operators with two bitmasks, the bit in each position of the first operand will be compared to the corresponding bit of the second operand. I call this vertical comparison, because it looks like this:

00101101
vvvvvvvv
10110110
vvvvvvvv
????????

The return value (the question marks) will be a new bitmask, whose bits will be flipped off or on (to 0 or 1 respectively) depending on the rules associated with the operator you are using. The ampersand (and, '&') checks to see if the corresponding bits in both bitmasks are both switched on, and flips the resultant bit on if so. The bar (or, '|') checks to see if the corresponding bits in either (or both) of the compared bitmasks are switched on, and flips the resultant bit on if so. Finally, the carrot (exclusive or, '^') checks specifically to see if one of the compared bitmasks has the bit in a given position switched on, while the corresponding bit in the other bitmask is switched off, and sets the resultant bit on if so.

This is a bit tricky to explain concisely, and a bit awkward to digest if you're not used to these concepts, so check out this Gist snippet for examples and visual representations. Here I show how each of these very useful operators works, and can be combined with a variety of comparisons and checks:

Real-World Example

Now that we have some idea of the mechanics of bitmask assignment and comparison, let's look at some real-world application. One challenge that lends itself particularly well to handling via bitmask is control input checking in video games. Video games, especially action-intensive games, must run at high frame rates, so performance is key and wasting a full bool data type's worth of data on each individual check is a monumental waste of space. As you'll see below, we can efficiently contain and check all the control input Boolean values we need in a single bitmask.

In this simple example, imagine a simple game with a perspective looking down onto the top of the player, who can move up, down, left or right, who can perform a regular attack and a special attack. Let's check out how we can manage the input for this control scheme using a bitmask! Note the use of constants here; having these constants available for use in assignment and checks is what makes bitmasks usable as arrays of Boolean values. Without the constants to check against, we wouldn't know what the individual bits in a bitmask represent! Also note the use of hexadecimal expressions to define the constants. I'll talk about this more in the example, but for now, just bear in mind that this is the easiest way (that I know of) to define a bitmask with a single bit flipped on in the position you want. (If you want to understand why I'm using hexadecimal the way I am, you need an understanding of how integers are represented in binary, which I won't explore in this post. An understanding of hexadecimal isn't required to understand this bitmask example, though!)
There is a lot of omitted error checking and pseudocode in this example, but it should give you an idea of how bitmasks can be useful in a real-world application.

Thanks for reading!
-- Steven Kitzes

Sum of Digits

While playing around and taking online classes in Python, I came across an exercise that I hadn't encountered before (in any language). The goal of the exercise was to write a function that took in an integer as an argument and returned the sum of the digits of the integer.

Because this exercise was nestled in a section of Codecademy that showcased looping strategies, for loops in particular, I starting trying to figure out a way to write a Python for loop to solve this problem. That maent I needed to figure out how to iterate over the digits of the int I received and add them up.

I had lots of wrong ideas. (Well, not "wrong," per se, but definitely "bad.") My first thought was to convert the int to a string, then iterate over the length of the string, taking each character and converting that back to an int to be added to a total (and then returned later). I didn't like this approach because it seemed clunky and inefficient. I have always felt that using strings to solve any arithmetic problem is probably among the worst ways to do it. It certainly didn't seem like the best approach here.

After a few moments of thought, I realized I could get the value of the last (rightmost) digit of any integer by taking the modulo (remainder) x % 10. Attempting to extrapolate this, I got caught up in my excitement and tried to add the values of x % 10^1, x % 10^2, ... x % 10^n, because this would translate somewhat easily to a for loop. This was sort of close to a good answer, and ultimately led me to a good answer.

I finally solved the problem by iterating through my integer x, adding x % 10 to my total and then dividing x by 10 with each iteration. This method gives each of x's original digits a turn in the ones' place, to be hit with % 10. I used a while loop instead of a for loop, and iterated through the integer dividing by 10 until my integer was 0 (rounded down). It worked like a charm ...

... until I tried a negative number! Python doesn't currently have native support for toward / away from infinity / negative infinity. When using modulo (%), Python always rounds down toward negative infinity. This meant that for any negative, single-digit number x % 10, Python would give me -1 as a result. So, my while loop would never equal 0 and would never exit!

My first thought was to write a needlessly complex snippet to catch negative numbers and use math.ceil() to ensure Python would round up in these cases. But that is more complex than it needs to be, since the remainder of any integer x / 10 will be the same (in real life) whether x is positive or negative. I fixed this by simply setting x = abs(x) (taking the absolute value of my integer) at the beginning of the function. Perfect!

Here is the code, in its beautiful simplicity (my first Python post!):


Thanks for reading!
-- Steven Kitzes

Using Recursion - Word Search

Amid efforts to broaden horizons and learn as much about different disciplines of development as possible, my C++ and heavy algorithms skills have gone somewhat untested lately. Although I have personal projects and work experience that I owe to a past rich in C++ and OOP, it's been a while since I revisited those realms. I decided it was time to test myself and see how I would do on an old challenge I'd tackled before, but not since almost four years ago when I first began seriously programming.

Long ago, a friend offered a challenge to help me learn. An aspiring developer himself, he'd taken several programming tests at job interviews. He forwarded one of them to me. The goals were as follows:

1. Goals:
2. generate a grid of random characters
3. display the grid to the screen
4. read in a dictionary file (more a word list, really)
5. iterate through the list, obeying a set of rules to search the grid for each word
1. Rules: using recursion:
2. when seeking the next letter in a word, navigate only one spot at a time
3. navigate only in the cardinal directions (up, down, left, right)
4. never use the character at a single grid location more than once on a given attempt
5. once a given word is discovered, don't search for more instances of it
6. display the number of words discovered
7. complete in 8 hours, 6 hours for bonus points

The first time I attempted this, years ago, it took me about a week's worth of evenings, totalling about 16 hours or so of total time. That's too long, and in the real world I would have failed that programmer test miserably. But it did give me an opportunity to learn about recursion.

I still need to sit down and plan out my recursive algorithms if I want them to be clean and efficient, but at least I have a firm grasp of the concept. This time around, I was able to solve the problem in under 5 hours. Here is how I tackled the task:

First thing being first, I generated a grid of chars using a two dimensional array to satisfy Goal #1, and slapped together a simple print function to cover Goal #2. Later, instead of simple characters, I came up with structs that contained both a char and a bool (for checking whether a given char had been used during any given check attempt). Then I had to (I admit) Google a way to read in a word list from a text file. Incidentally, Goals #3 and #4 were achieved with the same single while loop, but that part of the solution isn't relevant to the topic of recursion. (You can still see how I did it by viewing the project on my GitHub page, linked at the bottom of this post.)

It was finally time to sort through the grid to see if a given word was contained within it ... using recursion! First, how does recursion work? Recursion is a way of looping that's a little more confusing and involved than a simple for or while loop. These types of loops generally (if clearly and cleanly constructed) encapsulated chunks of code that run over and over again until a condition is met, then they stop looping and the program moves forward. Recursion, likewise, allows you to loop a chunk of code over and over again until a condition (usually called the "base case") is met. However, instead of a simple keyword call such as for or while, a recursive function is called. That is, a function that runs some code, and then calls itself, resulting in a looping effect.

• A recursive function runs some code and then calls itself to create a looping effect similar to a for or while loop.
• A recursive function iterates by receiving values from previous calls to itself as arguments, then checks those values to see if the "base case" has been met.
• (In some cases, a recursive function may modify and check a variable that is outside its scope and check that variable for the "base case".)
• When the "base case" is met, the ultimate result of the nested recursive function calls is returned down through the chain (or "stack") of calls to the original.

Take the following C++ snipped as an example. Notice how this simple function:
- accepts a value to get it started
- checks if the value has met the goal (or "base case") - modifies the value and passes it to another call of itself
- returns the result back down the chain



Here is a quick walkthrough of how this simple recursive function performs its duties on a call with the value 8 passed to it.

• First, recursiveExample( 8 ) is called. CompSci professors would describe this as placing a call to recursiveExample on the "call stack." In simpler terms, we're on the first layer of recursion and our value is currently 8.
• recursiveExample checks if the base case has been met; but value is less than 10.
• Since the base case was not met, we go to the else block. Here, value is incremented by 1, and recursiveExample calls itself, passing value (currently 9) as the argument.
• Now there are two instances of recursiveExample on the call stack; we are on the second layer of recursion.
• recursiveExample checks if value (currently 9) meets the base case, but it doesn't, so again we go to the else block.
• In the else block, value is iterated once more, now to 10 (can you predict what will happen next?). recursiveExample then calls itself again, passing value (currently 10) to itself as an argument.
• We now have three instances of recursiveExample on the call stack, and we're on the third level of recursion, and we have received 10 as the value for our value variable.
• recursiveExample checks the base case, and sees that it is met (value is greater or equal to 10)!
• Since the base case was met, recursiveExample returns value, which is 10. This removes one instance of recursiveExample from the call stack and returns us down to the previous call of recursiveExample.
• We are now back down on the second layer of recursion. Recall that the last thing we did on this layer was to call an instance of , the second layer of recursiveExample. We pick upu exactly where we left off, and the next thing to appear in code is another return! So that's exactly what we do; return the 10 on down the chain. The 10 is returned, and this second instance of recusiveExample is removed from the call stack.
• At last, we are back down at the bottom layer, to our original function call. Again, we pick up where we left off and the next piece of code is another return. So we pass the 10 on down, and since this is the final layer of recursion, the 10 is what ends up actually being returned to the program that originally called recursiveExample in the first place!

I used this idea of recursion in my word search program in checking the grid for successive letters of a given word. For example, taking the word "banana," I would search the grid for a 'b', then pass the word "banana" into my recursive function along with an iterator to represent the position of the next letter in "banana" that I was searching for. That function would check for the base case (in this case, if the letter position iterator had been incremented all the way up to the full length of the word I was searched for). If the base case was not met, the function would search the neighboring grid spots for the next letter in the word. If it found that letter, it would call itself, passing an incremented value as the iterator, with a reference to "banana" (or whatever word). This would continue until an instance of the letter-searching function met the base case (in which case it would return true all the way down the chain), or the function was unable to find the next letter while obeying all the rules of the WordSearch challenge (in which case it would return false all the way down the chain). Here, you can see what this recursive function looks like in my program:



You can see my WordSearch program in its entirety on my GitHub page! The recursive function itself is called checkNextLetter, and it can be found on line 76 of main.cpp, here. It's a bit more complicated than the simple example above, but you can spot some of the basic elements of a recursive function. For example, see lines 79 to 82, where checkNextLetter checks if the base case has been met and returns true if it has. Also check out lines 88, 95, 102, and 109 where checkNextLetter calls itself (and increments the spot value at the same time), creating the recursive equivalent of the looping effect.

Thanks for reading!
--
Steven Kitzes

Mounting Nexus 7 Using MTP

I'm sort of surprised no one else has come across this problem before, or posted this solution - at least, not that I could find - so I'm telling this story in the hopes it will help someone down the line. (If you want my solution to the problem, here's the Cliff's Notes at the bottom of this post.)

I ran into a problem today, trying to mount my Nexus 7 to my laptop, which is equipped with Ubuntu 12.10. When I plugged in the Nexus 7, I expected it to just work. I thought the device would appear on the desktop and in the Nautilus sidebar and just be accessible for file transfers over MTP. The device didn't show up.

I spent a good hour or so scouring the web for any help or hints I could find on how to mount a Nexus 7, running Jelly Bean, to Ubuntu. I found over a dozen convoluted work-arounds, updates, middleware installation guides, and other recommendations - all of which I tried (the free ones, anyway) and none of which made any difference at all. Using the work-arounds and various third-party software, I was able to determine that Ubuntu 12.10 could see the device, and obtain vendor and product ID information from it. But the device could not be mounted using MTP to transfer files. I got a variety of errors and warnings, which I followed up with Google searches that resulted in even more searches and fixes and updates and work-arounds, and another hour later, the device still wouldn't connect over MTP.

Scratching my head, I moved the Nexus 7 to my PC, a 64 bit Windows 7 machine. I plugged in the Nexus and it appeared in my Windows Explorer sidebar under the name I had given the device, but it was not expandable and the file system couldn't be accessed. I went into the Windows Control Panel and the device appeared there, under the correct name and in the right location, but again, couldn't be accessed. Flabbergasted, I started the whole search / update / word-around routine from scratch, this time on Win7. Again, to no avail.

I checked that the USB setting for the device itself was set to MTP, and it was. I tried restarting Ubuntu. I tried restarting Windows. I tried restarting the Nexus. I tried restarting them in varying orders. Nothing!

In desperation, I went into the USB connection setting on the Nexus 7 and switched it from MTP to PTP (the Camera protocol). I did this with the device plugged into the Windows PC, and this prompted the installation of new drivers for PTP. The device was now fully available as a media storage device, and gave me access to the part of the Jelly Bean file system where picture files are normally stored (DCIM, etc). Ah-hah! The device's file system capacity and available free space appeared, and were accurate. Ah-hah!

I switched back to MTP. No new installation of drivers, no pop-ups asking me what I wanted to do with the device, nothing changed on the surface. But when I accessed the device by name in Windows Explorer again, I now had access to the entire file system. Voila! I made some changes, moved things around, used the device some, and the file system disapparated from Windows yet again. Why?!

I repeated the steps again, did some testing (my QA experience played a role in this process), and ultimately came to the discovery that the Android device would only give Windows access to its file system when the device's "USB computer connection" settings menu was in focus, with MTP selected. Ugh!

Cliff's Notes:

To use an MTP connection between my Android 4.2 / Jelly Bean device and my computer, I must navigate to the "USB computer connection" menu on the Android device, make sure "Media device (MTP)" is selected, and leave that menu on-screen until I am done transferring files.

I want to note that I still can't get the device to mount on Ubuntu. I get a wholly new error, something about "Transport endpoint is not connected." But I have seen blog posts and articles about this error, as well. I'm sure I can spend another hour or two chasing wild geese around until I figure that one out, too. For now, I'm just glad I figured out how to knock some sense into the device itself!

Thanks for reading!
- Steven Kitzes