Repository

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

What Will I Learn?

• Working and modifying Solidity linked lists
• Placing a new buy order on the top, bottom or middle of the buybook

Requirements

• Internet connection.
• Code editor.
• Browser.

Difficulty

• Advanced.

Tutorial Contents

In the previous class, we have worked on the data structure that manages the linked list of orders prices. We have reached as far as the decision tree that checks if we are the highest priced buy order to be placed, if we are the lowest priced order, or we are somewhere in the middle.

Now is the time to implement the logic to modify the data structure according to what branch of the decision tree we follow.

I have made this mindmap to show what has to be done in each case (this includes extra decision making):

We will get started form the easiest to implement and work our way up to the hardest, which is if the new order is not the highest, not the lowest, but somewhere in the middle.

Just a reminder, this is considering that our order is the first at that price. If there are other orders at that price, then, obviously, the price linked list is already made and we just need to add our order to the queue list to be executed after the previous ones at that price have been executed.

In case the new order is the highest on the buy book

In case the order is the highest, it will be simple.

First, remember, we had a 3 way decision tree:

if(lowestBuyPrice==0 || lowestBuyPrice>_price){
//there are no other prices in the linked list, or we are the lowest
}else if(currentBuyPrice<_price){
//new order is the highest priced
}else{
//new order is in the middle
}

As we are the highest, you can see we go to the else if statement.

This is because chances are that the person is putting his order in a price that there is no other order before, so chances are we will fall into the if statement more often than not.

The logic, as described on the mindmap above, turned into code, is:

//current highest buy prices "higher price" points to the new order
tokenList[_token].buyBook[currentBuyPrice].higherPrice=_price;
//new orders higher price points to ourselves as there is no one higher than us yet
tokenList[_token].buyBook[_price].higherPrice=_price;
//new orders lower price points to previous highest price
tokenList[_token].buyBook[_price].lowerPrice=currentBuyPrice;
//updates tokens highest price to reflect the new order
tokenList[_token].maxBuyPrice=_price;

Simple enough to understand, and prepares the field to the "next level".

We are either the lowest price or the first price for that token

if we are the lowest price, we will do something very similar to the above section. If we are the first price on the buy book too, but then we will be both, the highest and the lowest price.

If both cases, we will be the minimum price, so, let us make a decision tree that will do "something else", but in the end put us as the lowest price:

if (currentBuyPrice==0){

}else{

}
                tokenList[_token].minBuyPrice=_price;

The first statement, the if, checks if the buy book is empty, that means, if the current buy price (highest, we have set this variable in a previous class) is zero. In that case, what we do it:

//we are the highest buy price of the token
tokenList[_token].maxBuyPrice=_price;
// the higher price of the new order is itself, as it is on the top of the book
tokenList[_token].buyBook[_price].higherPrice = _price;
//the lower price or our order is zero
tokenList[_token].buyBook[_price].lowerPrice = 0;

Now, for the else statement, that is, if there are other orders on the book, but still we are the lowest priced one:

//the lowest prices lower price is the new order
tokenList[_token].buyBook[lowestBuyPrice].lowerPrice=_price;
// the new orders higher price is the old lowest priced order
tokenList[_token].buyBook[_price].higherPrice=lowestBuyPrice;
//the lower price of our order is zero
tokenList[_token].buyBook[_price].lowerPrice=0;

With that code, you can now begin to understand how are we manipulating the linked list data structure (the previous class covered more about linked lists).

You should, by now, understand that, whenever we put something somewhere in the list, we must change the references of the new item and the previous and next item so we turn into a part of the list.

If we are somewhere in the middle

Now, this is the most advanced scenario, where we will have to search through the linked list to find where do we fit, that is, we need to find a price that is lower than the new orders price, but also its higher price is higher than the new orders price.

It is easier to understand if you pay closer attention to this part of the mindmap:

First thing, we will need to variables before we start iterating through the list:

//what is the max buy price at the moment
uint buyPrice = tokenList[_token].maxBuyPrice;
//stores if we found the spot
bool finished=false;

Now, to the loop:

while(buyPrice>0&&!finished){
}

Inside that loop, we will change the buyPrice and go down the linked list storing the values on it. The loop stops when, either, the price is zero, or the action is finished.

Inside the loop we need to do 2 things over and over again:

• Check if this is the spot we want
• If it is the spot, mark the task as finished so we stop looping
• If it is not, go one item down on the linked list

Just to remember, the spot we want is where the item has a lower value than the new order, and the item's higher price is higher than the new order.

The above, turned into code, is:

//checks if this is the spot
if(buyPrice<_price && tokenList[_token].buyBook[buyPrice].higherPrice>_price){
    //if it is, place the new order between the item and the item's higher value

//marks task as complete to break out of the loop
}else{
//goes one item down on the linked list
buyPrice=tokenList[_token].buyBook[buyPrice].lowerPrice;
}

Now, if this is the spot, we need to do those "complex" linked list changes described in the image above, so that the new order is between the two places.

The code I have for that is:

//the new orders lower price is the item we have found
tokenList[_token].buyBook[_price].lowerPrice=buyPrice;
// the new orders higher price is the items higher price
tokenList[_token].buyBook[_price].higherPrice=tokenList[_token].buyBook[buyPrice].higherPrice;
// the items higher prices lower price is the new order
tokenList[_token].buyBook[tokenList[_token].buyBook[buyPrice].higherPrice].lowerPrice=_price;
//the items higher price is the new order
tokenList[_token].buyBook[buyPrice].higherPrice=_price;
//task is finished, break out of the loop
finished=true;

Remember, if the comments or the code above looks complicated, check the image. When dealing with data structures there is no shame on "programming with pen and paper", you need to keep track of the items from the list so you don't mess with the order.

As said in a previous class, the "store order" function can be called from other functions, so we need to avoid creating new variables inside it because the Ethereum compilers stack is limited, it would be a shame if our exchange can't work because it requires too much of the EVM.

But, just to make it easier to understand, I will show how the code above would be if we used variables, for easy understanding, would look like:

Token storage loadedToken = tokenList[_token];
OrderBook storage newOrder = loadedToken.buyBook[_price];
OrderBook storage foundItem = loadedToken.buyBook[buyPrice];
OrderBook storage foundItemsHigherPrice = foundItem.higherPrice;
newOrder.lowerPrice=buyPrice;
newOrder.higherPrice=foundItem.higherPrice;
foundItemsHigherPrice.lowerPrice=_price;
foundItem.higherPrice=_price;

But there are too many "heavy" variables there, and that would definitely be a bad idea to do that on a function that will be called by other functions, so, stick with the first code, the above is for better understanding.

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