Repository

https://github.com/igormuba/DEX/tree/master/Class4

What Will I Learn?

• Decision tree for placing a sell order
• Manipulating the linked list to fit the new order

Requirements

• Internet connection.
• Code editor.
• Browser.

Difficulty

• Advanced.

Tutorial Contents

As we are working with relatively complex and interconnected data structures, I have separated the previous tutorial, on storing a buy order, in two. One of them was dedicated to creating the decision tree depending on where on the linked list the new order would go, the other was dedicated to the logic of working with linked lists in Solidity.

But both two were about doing that for buy orders. This tutorial will cover the same but for sell orders. Both functions are similar, but inverse. To avoid repetition, I will touch very briefly on the part that is similar to what we have done before and will focus on how to "invert" the logic, so that it for the sell order too.

If you did not follow the previous two tutorials, I highly recommend you to do so, because each one of them was very focused on their topics and I have explained in detail every decision the code took and how the linked list behaves according to that decision.

The function

This function will receive the data of how many tokens the user wants to sell and at what price. We are assuming that this order did not fill any buy order, that is, this function will be called to store, either an order that did not match any buy price or the remainder of an order that filled some buy orders, but couldn't be completed itself for lack of buy volume at the given limit price. We will cover the operations and logic for filling the order on a future tutorial, because for that, we need to be able to store the buy and orders in the book, without storing orders we have nothing to fill!

The function to store looks like:

//stores a new sell order on the book
function storeSellOrder(address _token, uint _price, uint _amount, address _maker) public{
//increase the length of how many orders are there at this price
    tokenList[_token].sellBook[_price].offerLength++;
//places this order as the last one in the queue for selling at this price (FIFO)
    tokenList[_token].sellBook[_price].offers[tokenList[_token].sellBook[_price].offerLength] = Offer(_amount, _maker);
//if this is the first order in the queue at this price  
    if (tokenList[_token].sellBook[_price].offerLength==1){
}
}

If this is the first order in the queue at this price

Inside the checking described above, in case our order is the first at its price we need to add it to the linked list of prices, either in the end, the beginning, or the middle of the list, and rearrange the neighbor nodes of the list. If it is not the first at its price, the if from the last section will be false and nothing needs to be done, because the linked list already has a place for our price, we just need to add ourselves on the queue of orders at this price.

First, step, covered in another tutorial, but adapted here to the selling side, is to test if this new selling order to be stored is in the top, the bottom, or the middle of the selling book.

What we will do now is inside the if from the last section, that is, this is the first order at its price, so the list needs to be modified to fit it.

But before the decision taking, we need to work on a few variables first:

//sets the pointer of the order queue at this price to this new order (the first)
tokenList[_token].sellBook[_price].offerPointer=1;
//tells the token there is a new sell price, or "node", on the linked list of prices
tokenList[_token].amountSellPrice++;
//the current selling price is the lowest, the first that will be filled by takers
uint currentSellPrice = tokenList[_token].minSellPrice;
//the highest is the last
uint highestSellPrice = tokenList[_token].maxSellPrice;

Decision tree

This is where we are starting to see the differences from the buy side and the sell side. Because they are on "opposite" sides, the logic operations are similar but reversed.

Take a look at the buy order decision tree in the second tutorial. Now, take a look at the sell order decision tree:

//if there is no other sell order or we are the highest
if (highestSellPrice==0 || highestSellPrice<_price){

}
//else, if we are the lowest sell order
else if(currentSellPrice>_price){

}
//or we are in the middle (advanced case)
else{

}

I will show all Tre very briefly, as they are similar, but inverse, of what we have done for storing the buy order. If it sounds too complicated, in the last tutorial I explain very in depth what happens, here it is the inverse, but the "overall logic" of working with linked lists apply!

If we are the cheapest

This case will go on the else if decision. We are starting from this one because it is the most simple

If our sell order is the lowest, we just need to place it at the "bottom" of sell book, to be filled first:

//the previous lowest price points the new order as its "lower price"
tokenList[_token].sellBook[currentSellPrice].lowerPrice=_price;
//new orders "higher price" points to the previous low 
tokenList[_token].sellBook[_price].higherPrice=currentSellPrice;
//the new orders lower price is zero
tokenList[_token].sellBook[_price].lowerPrice=0;
//the lowest sell price (first order) of the token is the new order
tokenList[_token].minSellPrice=_price;

That was the simplest one, let us go to the next case.

There is no other order or we are the highest

This will go on the first if statement of the decision tree of where to place the order. We are putting these two cases first because they are relatively similar.

Inside here we have another decision to take:

//if the current (lowest) sell price is zero we are the first price on the linked list
if(currentSellPrice==0){

}else{

}

According to the decision above, if we are indeed the first price in the linked list:

//the minimum sell price of the token is the new order
tokenList[_token].minSellPrice=_price;
//both, higher and lower prices are zero, as there are no other orders
tokenList[_token].sellBook[_price].higherPrice=0;
tokenList[_token].sellBook[_price].lowerPrice=0;

If we fall into the else statement, then, obviously we are the highest priced order and we are not the first on the linked list (on the buy side this checked if we were the lowest). Here are the operations we need to do to place it on the top:

//the previous higher price points the new order as the price that is above it
tokenList[_token].sellBook[highestSellPrice].higherPrice = _price;
//the new order points the previous highest price as its "lower price"
tokenList[_token].sellBook[_price].lowerPrice = highestSellPrice;
//the higher price of the new order does not exist as it is the highest one in the book
tokenList[_token].sellBook[_price].higherPrice = 0;

If it is in the middle

The last case is if the order is in the middle. What we do here is similar to the iteration through the list we have done on the buy book, but instead of going from the highest to the lowest, we go from the lowest the highest until we find "the spot" where the node's price is lower than our price, but the node's higher price is higher than our price.

The two variables used to do this control are:

uint sellPrice = tokenList[_token].minSellPrice;
bool finished=false;

And the loop is:

//runs until the "right spot" is found
while(sellPrice>0 && !finished){
//if the right spot is found
    if(sellPrice<_price&&tokenList[_token].sellBook[sellPrice].higherPrice>_price){
        //operations to place the new order in the middle of the linked list
    }
    //goes up one node on the linked list
    sellPrice=tokenList[_token].sellBook[sellPrice].higherPrice;
}

At each iteration of the loop, it will move up one node of the linked list and "check if this is the spot". If the right place is found, the logic to place it is:

//the lower price of the new order is the node found
tokenList[_token].sellBook[_price].lowerPrice = sellPrice;
//the higher price of the new order is the higher price the found node points to
tokenList[_token].sellBook[_price].higherPrice = tokenList[_token].sellBook[sellPrice].higherPrice;
//the lower price of the higher price of the found node points to the new order
tokenList[_token].sellBook[tokenList[_token].sellBook[sellPrice].higherPrice].lowerPrice=_price;
//the higher price of the node found points to the new order  
tokenList[_token].sellBook[sellPrice].higherPrice = _price;

Again, this code is just to show how the inverse of the logic from the buy order works, if you want to understand in depth how the linked list works, in solidity I recommend reading the previous tutorial.

How it should work

It works very similarly to the buy order storage:

But in this case, notice that the highest priced order is the "last" on the linked list, while the lowest priced is the "first" of the list.

This is because, when a buy order fills sell orders, it needs to fill first the cheapest ones. Opposite to that, when a sell order fills buy orders, it fills first the higher priced ones, and then the lowest priced ones.

Curriculum

• (Part 2) Decentralized Exchange - Storing Buy Orders, Using The Linked Lists And Queues(PT 2)
• (Part 1) Decentralized Exchange - Smart Contract API, Order Book And Orders (PT 1)

Beneficiaries

This post has as beneficiaries

• @utopian.pay with 5%
• @steempeak with 1%

using the SteemPeak beneficiary tool