A problem
In these notes I am going to develop a C++ program to solve a problem based on a final exam problem from CMSC 250. The problem is to construct a simple system to manage trades in an electronic marketplace. In this problem traders will submit requests for trades to a central clearing house. For simplicity, we will assume that only one commodity trades in this market and that prices are not taken into account. Traders will submit requests to buy or sell a certain number of units of the commodity in question, and the system simply has to match buyers with sellers and produce a list of trades.
In the program I will describe in these notes the buy and sell orders will come in in the form of a text file containing a list of buy and sell orders. Each order includes the id number of the trade who placed the order and the number of units they want to buy or sell. Here is an example of a typical input file:
buy 105 250 sell 333 100 sell 409 500 buy 632 400 sell 375 100
The system will match the buyers and sellers and emit a second text file with a list of all the trades that should be made. Here is the output file that goes along with the input example above:
333 sells 100 units to 105 409 sells 150 units to 105 409 sells 350 units to 632 375 sells 50 units to 632
Source code for the project
Here is an archive containing the full source code for this example.
The order class
The first step in constructing a solution is to construct a simple class in C++ to represent orders. This class stores the name of the trader and number of units they want to trade. The order class does not contain information about whether this is an order to buy or sell - the system will record that information by putting buy and sell orders on separate lists.
Here is the C++ class declaration for the order class:
class Order {
private:
std::string trader;
int quantity;
public:
Order(std::string name, int amount) {
trader = name;
quantity = amount;
}
std::string getName() { return trader; }
int getAmount() { return quantity; }
void reduceAmount(int amt) {
quantity -= amt;
}
};
This class declaration appears in a C++ header file, Order.h.
Creating and working with objects
Once we have constructed a class declaration we are in a position to start working with Order objects. C++ has two distinct systems for creating and interacting with objects. In the first system, we create objects as ordinary variables. Here is an example:
Order example("Joe",200);
example.reduceAmount(100);
In this approach, we use a special syntax to declare and initialize the Order object named example. The syntax in the first statement above simultaneously declares a variable example of type Order and also invokes the constructor for the Order class to initialize that object with a trader name and a quantity. Once we have initialize the object we can interact with it by calling methods on the object using the dot method call syntax.
The second system for working with objects makes use of a pointer variable and the new operator:
Order *example = new Order("Joe",200);
example->reduceAmount(100);
The first statement above has two parts: a variable declaration and an initialization. The variable declaration part,
Order *example;
declares a variable named example whose type is "pointer to Order". A pointer is a type of variable that carries location information. In this case, the example variable will store the address of an Order object that we want to interact with. We initialize the pointer variable by using the C++ new operator to construct a new object of type Order. The new operator returns a pointer to the newly created object as a side effect of making the object for us.
example = new Order("Joe",200);
Once we have created an object and obtained a pointer to it, we will interact with the object via the pointer variable. Pointers support one important operation, dereferencing, via the C++ dereference operator, *. Dereferencing a pointer to an object gives us access to the object itself, so we can call its methods using the usual dot notation:
(*example).reduceAmount(100);
Because calling a method on an object accessed via a pointer is a such a common scenario in C++, the language provides a more convenient syntactical equivalent. The expression
example->reduceAmount(100);
is a more convenient equivalent form.
Finally, when we are done working with an object that we created with new, we need to make the object disappear by using the delete operator.
delete example;
This will free up the space that the object occupies, making that space available for other purposes in the program.
A queue class
The next thing we are going to need in our program is some way to make a list of buy and sell order objects. For this purpose I am going to introduce another class that will implement a simple linear data structure that can store orders.
The class is a queue class. A queue is a linear data structure that supports two operations, an enqueue operation that puts new items at the end of the queue, and a dequeue operation that removes items from the front of the queue.
A queue structure is typically implemented as a collection of nodes held together by pointers. The picture below illustrates this arrangement.
Each Node object contains some data (in this case a pointer to an Order object) and a pointer to the previous Node in the chain. The Queue object itself contains two pointers, a pointer to the Node at the head of the queue and a pointer to the Node at the tail of the queue.
Here now are the class declarations that set up the Queue and Node classes.
template <typename T>
class Node {
public:
Node<T>* link;
T data;
Node(T item) { link = nullptr; data = item; }
T getData() { return data; }
};
template <typename T>
class Queue {
private:
Node<T>* head;
Node<T>* tail;
public:
Queue() { head = tail = nullptr; }
// Add a new item to the tail of the queue
void enqueue(T item) {
if (head == nullptr) {
head = tail = new Node<T>(item);
}
else {
Node<T>* newNode = new Node<T>(item);
tail->link = newNode;
tail = newNode;
}
}
// Remove the item at the head of the queue
void dequeue() {
if (head == nullptr)
return;
Node<T>* toRemove = head;
head = head->link;
if (head == nullptr)
tail = nullptr;
delete toRemove;
}
bool isEmpty() {
return head == nullptr;
}
// Return the data item at the front of the queue
T front() {
return head->data;
}
};
These class declarations appear in a header file named Queue.h.
To make the Queue class more flexible, we make use of the C++ template mechanism to make both of these classes template classes. A template class contains placeholders for one or more types. In this case, we use a place holder T for the type of data stored in the queue nodes. To make a class a template class we place the notation
template <typename T>
at the start of the class declaration.
When we instantiate a Queue, we use the template notation to specify what type should be used for the placeholder type T. In this application we will want to create Queue objects that store pointers to Order objects, so we will use the syntax
Queue<Order*> buyOrders;
to declare Queue objects with the T replaced by the concrete type Order*, which means "pointer to Order".
The Market class
With the creation of the Order and Queue classes we now have all of the elements in place to solve the market making problem. We now introduce a Market class that will be responsible for storing the orders and running the order matching algorithm.
Here is the class declaration for this Market class.
class Market {
private:
Queue<Order*> buyOrders;
Queue<Order*> sellOrders;
public:
Market() {
}
void addBuyOrder(std::string trader, int qty) {
buyOrders.enqueue(new Order(trader, qty));
}
void addSellOrder(std::string trader, int qty) {
sellOrders.enqueue(new Order(trader, qty));
}
void clearTrades(std::string fileName);
};
This class declaration appears in a file named Market.h. Note that the class is missing code for one of its methods, the clearTrades method. In cases where a method's code would take up too much space in the class declaration, C++ allows us to simply list the method in the class declaration. The actual code for the method then appears in a separate file, Market.cpp. Here is the code for the missing method as it appears in that separate file:
void Market::clearTrades(std::string fileName) {
ofstream out;
out.open(fileName);
while (!buyOrders.isEmpty() && !sellOrders.isEmpty()) {
Order* buy = buyOrders.front();
Order* sell = sellOrders.front();
int toBuy = buy->getAmount();
int toSell = sell->getAmount();
if (toBuy > toSell) {
out << sell->getName() << " sells " << toSell << " units to " << buy->getName() << endl;
buy->reduceAmount(toSell);
sellOrders.dequeue();
delete sell;
}
else if (toBuy == toSell) {
out << sell->getName() << " sells " << toSell << " units to " << buy->getName() << endl;
buyOrders.dequeue();
delete buy;
sellOrders.dequeue();
delete sell;
}
else {
out << sell->getName() << " sells " << toBuy << " units to " << buy->getName() << endl;
buyOrders.dequeue();
delete buy;
sell->reduceAmount(toBuy);
}
}
out.close();
}
The :: notation that appears at the start of the method code indicates that this is code for the clearTrades method in the Market class.
The main function
The last thing needed to make this example work is a main function. The code for that function appears in the file main.cpp:
void main() {
ifstream in;
in.open("orders.txt");
string kind, name;
int qty;
Market market;
while (in >> kind >> name >> qty) {
if (kind == "buy")
market.addBuyOrder(name, qty);
else
market.addSellOrder(name, qty);
}
in.close();
market.clearTrades("trades.txt");
}
The code here opens the text file containing the order information and reads the orders. Each order has a kind, a trader name, and a quantity, so we can read the details of a single order by doing something like
in >> kind >> name >> qty
Since we don't know in advance how many orders are in the file, we execute the reading code in a while loop. We use a somewhat peculiar construct that uses the reading code as the test for a while loop. This approach takes advantage of the fact that the reading code not only reads data from the file: it also has a side effect. Evaluating the reading code returns information about whether or not the read was successful. If the read was successful, the reading expression evaluates to true, causing us to evaluate the code in the body of the loop. When we reach the end of the file and the read fails, the reading expression produces a side-effect value that evaluates to false, causing us to exit the while loop.