C++: Sorting the Contents of an Array Based on the Contents of Another
I often find while programming that I want to sort the contents of one array based on that of another. For instance, say I had the arrays
int rankings[] = {1,4,2,5,3} string names[] = {"George", "Fred", "Gary", "John", "Bob"}
and I wanted to resort both arrays based on ranking. That is, I would want the following result:
int rankings[] = {1,2,3,4,5} string names[] = {"George", "Gary", "Bob", "Fred", "John"}
Now in Python, this would be easy to do.
rankings = [1, 4, 2, 5, 3] names = ["George", "Fred", "Gary", "John", "Bob"] toSort = zip(rankings, names) toSort.sort() rankings, names = zip(*toSort)
Unfortunately you can’t zip C arrays or C++ STL containers up like that. There is probably some mechanism for doing so using Boost, but I figured it would be better to just use the standard C++ algorithms and iterators. I thus present the following code (dualsort.h):
#pragma once #include <algorithm> #include <stdexcept> #include <vector> #include <utility> namespace xenoscope { namespace utility { template <class Compare, class RandomAccessIterator> struct dual_sort_compare_wrapper { dual_sort_compare_wrapper(Compare comparer) : _comparer(comparer) { } bool operator() (std::pair<size_t, RandomAccessIterator> x, std::pair<size_t, RandomAccessIterator> y) { return _comparer(*x.second, *y.second); } Compare _comparer; }; template <class T> struct dual_sort_basic_compare { bool operator() (T x, T y) { return x < y; } }; template <class IndexIterator, class RandomAccessIterator, class OutputRandomAccessIterator> void index_shuffle_copy(IndexIterator begin, IndexIterator end, RandomAccessIterator toSort, OutputRandomAccessIterator output) { while(begin != end) { *output = *(toSort + begin->first); begin++; output++; } } //Unfortunately we have to make a copy buffer. Moving //data in-place would be O(n log n) at minimum, if not more. template <class RandomAccessIteratorType1, class RandomAccessIteratorType2, class Compare> void dual_sort(RandomAccessIteratorType1 it1_begin, RandomAccessIteratorType1 it1_end, RandomAccessIteratorType2 it2_begin, RandomAccessIteratorType2 it2_end, Compare comp) { //Count how many elements we have unsigned n1 = it1_end - it1_begin; unsigned n2 = it2_end - it2_begin; //Do checking if(n1 == 0) { return; } if(n1 < 0) { //We got some messed up values throw std::invalid_argument("First set of iterator arguments are invalid."); } if(n1 != n2) { //The arrays were different sizes throw std::invalid_argument("Containers have different sizes."); } //Create a tracker with indices 0, n1-1 that we can use to see how the //order of the data changed. std::vector<std::pair<size_t, RandomAccessIteratorType1> > order(n1); size_t n = 0; for(RandomAccessIteratorType1 it = it1_begin; it != it1_end; it++, n++) { order[n] = std::make_pair(n, it); } //Do the sorting std::sort(order.begin(), order.end(), dual_sort_compare_wrapper<Compare, RandomAccessIteratorType1 >(comp)); //Order vectors appropriately std::vector<typename std::iterator_traits<RandomAccessIteratorType1>::value_type > copyBuffer1(n1); std::vector<typename std::iterator_traits<RandomAccessIteratorType2>::value_type > copyBuffer2(n2); index_shuffle_copy(order.begin(), order.end(), it1_begin, copyBuffer1.begin()); index_shuffle_copy(order.begin(), order.end(), it2_begin, copyBuffer2.begin()); std::copy(copyBuffer1.begin(), copyBuffer1.end(), it1_begin); std::copy(copyBuffer2.begin(), copyBuffer2.end(), it2_begin); } template <class RandomAccessIteratorType1, class RandomAccessIteratorType2> void dual_sort(RandomAccessIteratorType1 it1_begin, RandomAccessIteratorType1 it1_end, RandomAccessIteratorType2 it2_begin, RandomAccessIteratorType2 it2_end) { dual_sort(it1_begin, it1_end, it2_begin, it2_end, dual_sort_basic_compare<typename std::iterator_traits<RandomAccessIteratorType1>::value_type>()); } } }
This code implements two templated algorithms which extend the standard sort algorithm. They function identically to std::sort, except that they take an extra pair of iterators to a second container which you wanted to be reordered corresponding to the new order in the first container. Here’s an example of how to use it:
#include <vector> #include <string> #include <cstdio> #include "dualsort.h" using namespace std; using namespace xenoscope::utility; int origRankings[] = {1, 4, 2, 5, 3}; string origNames[] = {"George", "Fred", "Gary", "John", "Bob"}; vector<int> rankings; vector<string> names; void printData() { printf("Rankings ordering is:\n"); vector<int>::iterator rit; for(rit = rankings.begin(); rit != rankings.end(); rit++) { printf("\t%i\n", *rit); } printf("Names ordering is:\n"); vector<string>::iterator nit; for(nit = names.begin(); nit != names.end(); nit++) { printf("\t%s\n", nit->c_str()); } printf("\n\n"); } struct ReverseCompare { bool operator() (int i, int j) { return (i > j); } } revComparer; int main() { //Create a dataset rankings = vector<int>(origRankings, origRankings + 5); names = vector<string>(origNames, origNames + 5); printData(); //Sort into ascending order dual_sort(rankings.begin(), rankings.end(), names.begin(), names.end()); printData(); //Sort into descending order using a custom comparer dual_sort(rankings.begin(), rankings.end(), names.begin(), names.end(), revComparer); printData(); return 0; }
It produces the following output:
Rankings ordering is:
1
4
2
5
3
Names ordering is:
George
Fred
Gary
John
Bob
Rankings ordering is:
1
2
3
4
5
Names ordering is:
George
Gary
Bob
Fred
John
Rankings ordering is:
5
4
3
2
1
Names ordering is:
John
Fred
Bob
Gary
George
The code is currently just limited to two containers, but you can easily extend it to more. You can also just make copies of the index vector and call dual_sort for as many vectors as you have. Let me know if you have any trouble with it, or any recommendations. I’m making this code public-domain, so feel free to use it in any project, commercial, open source, whatever. I hate licenses. Credit is of course appreciated, but by no means required.
Downloads:
dualsort.h
Anamnesis Launched
I have just put up the code for a project I’ve been working on called Anamnesis. It is a SIMBL-based plugin for Safari on Mac OS X that adds “Reopen Last Closed Tab” functionality. Please check out the Anamnesis page (see links @ top of page) for more information.
Reading and Parsing USB GPS Data in C (with NmeaLib)
I’m currently working on a project that requires GPS data, and need a way to retrieve data from a USB-based GPS receiver I purchased (a USGlobSat BU-353 USB GPS receiver). Fortunately, most GPS receivers, particularly USB ones, support the NMEA 0183 protocol. NMEA 0183 is a serial-based protocol was developed by the National Marine Electronics Association and is used to collect data from a variety of aquatic electronic devices (such as sonar, GPS, and others). Most USB-based GPS receivers have a serial-to-USB converter built in, which allows data to be read from a device as if it were a serial device. For instance, the BU-353 shows up in Mac OS X as /dev/cu.usbserial. If you plug in your GPS device and boot up minicom, you’ll see output that looks a lot like this
Sample NMEA 0183 Strings
Obviously the strings are somewhat cryptic, but you can discern some data among them that looks like GPS data. Unfortunately the protocol is not open, and costs at least $270 to buy from the NMEA. Fortunately, most of it has been reverse engineered, and there is a great library which already exists to parse these strings into useable data. It is called NmeaLib and it is released under the LGPL. The way it works is that you first initialize it, then just feed it every string that the GPS device feeds you over the serial device, and it will interpret the data and keep a cumulative collection of all available data from the GPS receiver. In addition to the basic latitude and longitude data, it will also report the number of satellites in view, the number satellites being used, the signal strengths of both, as well as the current GPS time and many other useful pieces of information.
The big remaining task once you have the library is to read from the GPS serial device. Reading from a serial device might seem like it would be as simple as reading from a file (and in some ways it is), but because serial port data can come at various rates and in various formats (for instance it might come at 9600 Baud with no parity bit and with 8 bits of data), there are some other calls you need to make to set the various serial settings.
To begin with, we need to get a file descriptor for the serial port. This can be done simply with
gpsFd = open("/dev/cu.usbserial", O_RDONLY | O_NOCTTY | O_NONBLOCK);
You will also need some of the structures and functions included in termios.h, the POSIX terminal definitions, in order to set the appropriate terminal settings.
struct termios options; struct termios origPortOptions; //Get the existing options so they can be restored tcgetattr(gpsFd, &origPortOptions); bzero(&options, sizeof(options)); //Set the BAUD rate to NMEA specifications cfsetospeed(&options, B4800); options.c_cflag |= (CLOCAL | CREAD); //Settings equivalent to 8N1 options.c_cflag &= ~PARENB; //Disabled parity options.c_cflag &= ~CSTOPB; //Set 1 stop bit (| would give us 2 stop bits) options.c_cflag |= CS8; //Set character size to 8 bits options.c_cflag |= CRTSCTS; //Enable hardware flow control options.c_oflag |= (OPOST | ONLCR); //Processed output and mapping of newlines to CR-LF pairs tcsetattr(gpsFd, TCSAFLUSH, &options); //Flush buffers and apply the new settings
After that, you can read from gpsFd like any other file descriptor. If you want to get the number of bytes waiting in the buffer to be read, you can use ioctl() as follows:
int bytesInBuffer; //Get the number of bytes waiting in the serial buffer ioctl(gpsFd, FIONREAD, &bytesInBuffer);
I have attached a simple library (with NmeaLib included) that you can use in your own projects (assuming your serial or USB GPS device uses the same data settings). To use it, you simply call initializeGps(), then get the most recent GPS info by calling getGpsInfo() (which returns an NmeaLib structure). Once you’re finished retrieving GPS data, call closeGps() to free up the serial port and restore its previous settings.
The library uses setitimer() to install an alarm that will call a read handler that will pull all data waiting in the serial buffer and then parse it using NmeaLib. You can change the update frequency if you like, but it is already much faster than it really needs to be, and I’d recommend just leaving it alone as it is very low overhead.
I’ve also included a test program that shows how to use the code in gps.h/.c. Its output looks something like the following:
Sample GPS Data
Yeah so now you know where I live, but I suppose a determined individual could get that from a domain registrar anyway.
Feel free to reuse this code however you see fit, although if you do, some credit is always appreciated. Have fun building those autonomous spy blimps.
How to Monitor Parallel Port Interrupts in User Space in Linux
DISCLAIMER: A computer is not a cheap device and home-made electronics are not always reliable. I take no responsibility for damage caused by you sticking shit into your parallel port or anywhere else on your computer to see what happens. I also take no responsibility for any side-effects of the following code. That said, if you’re careful, the parallel port can be a very useful device for interfacing your computer with external devices, and the following code is working fine for me.
Anyway, I’m guessing you want to install an interrupt handler for the parallel port, but aren’t a kernel hacker and don’t want to read a ton of documentation? Well, fortunately I had the same issue and was able to get something similar working. Unfortunately dealing with the parallel port in user space isn’t exactly the same as writing a kernel module, and there are a few important things to remember:
- Code which accesses the parallel port must be run as root
- Only one piece of code which uses this method may listen for interrupts at a time
- The parallel port cannot be sharing an IRQ (although this shouldn’t be an issue since the parallel port usually has a dedicated IRQ anyway, number 5 or 7 most of the time)
So without further ado, here is what I’ve got:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <linux/ppdev.h> #include <linux/parport.h> #include <stropts.h> #include <stdio.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <sys/ioctl.h> #include <sys/select.h> #define PP_DEV_NAME "/dev/parport0" int main() { //Get a file descriptor for the parallel port int ppfd; ppfd = open(PP_DEV_NAME, O_RDWR); if(ppfd == -1) { printf("Unable to open parallel port!\n"); return 1; } //Have to claim the device if(ioctl(ppfd, PPCLAIM)) { printf("Couldn't claim parallel port!\n"); close(ppfd); return 1; } while(1) { //Set up the control lines for when an interrupt happens int int_count; int busy = PARPORT_STATUS_ACK | PARPORT_STATUS_ERROR; int acking = PARPORT_STATUS_ERROR; int ready = PARPORT_STATUS_ACK | PARPORT_STATUS_ERROR; char int_value; ioctl(ppfd, PPWCTLONIRQ, &busy); //Let ppdev know we're ready for interrupts ioctl(ppfd, PPWCONTROL, &ready); //Wait for an interrupt fd_set rfds; FD_ZERO(&rfds); FD_SET(ppfd, &rfds); if(select(ppfd + 1, &rfds, NULL, NULL, NULL)) { printf("Received interrupt\n"); } else continue; //Caught a signal //Fetch the associated data ioctl(ppfd, PPRDATA, &int_value); //Clear the interrupt ioctl(ppfd, PPCLRIRQ, &int_count); if(int_count > 1) printf("Uh oh, missed %i interrupts!\n", int_count - 1); //Acknowledge the interrupt ioctl(ppfd, PPWCONTROL, &acking); usleep(2); ioctl(ppfd, PPWCONTROL, &busy); } return 0; } |
As you can see, what you’re essentially doing is just opening the parallel port device like any old file and then calling select() to wait until an interrupt (or some other signal) happens. Here all I’m doing is writing a line to the console whenever an interrupt is received, but of course you can do anything (so long as the interrupt handler is fast enough to deal with your interrupt frequency). There are also a few ioctl() calls for claiming the port and clearing interrupts, but for the most part, the comments are self-explanatory and the code can just be copied into your project.
There is of course one fundamental issue with this code, and that is that it blocks until an interrupt is received. My suggestion, and the way I use this code, is to launch off another thread that runs this code and just sits dormant until an interrupt occurs. This seems to be relatively low overhead and pretty reliable. I’ve avoided giving the sample code in a threaded example so that it’s easy to extract and use in your own projects. Feel free to email me if you have a question or suggestion.
Also, in case you’re wondering how to trigger a parallel port interrupt, it’s triggered on the rising edge (or on some boards the falling edge) of a signal on pin 10, so just short pin 10 to ground (pins 18-15) and you should see an interrupt triggered (it may be triggered when you unshort it).
Here is a zipped copy of the code for your viewing/programming pleasure:
Sample Code for Parallel Port Interrupt Handling in Linux
keep looking »