# ZIP-8: Hybrid CDA - Addendum: CEX-Style order matching
## CEX-style order matching (sketch)
The idea of a CEX-style (Centralized Exchange -style) order matching in the context of a hybrid amm/oderbook algorithm is that the system tries to achieve the best price for the order request by filling orders and trading the AMM.

:::info
**Examples.** (1.1) On a two outcome (A,B) hybrid AMM/orderbook market with collateral in UNIT, Alice wants to purcharse 100 A for at most $p=0.6 A/UNIT$.

Alice submits the order. The system now
1. Fills all orders that are below $p$ and below the current AMM price
2. Trades with the AMM until the AMM price is either above $p$ or above the next best offer in the orderbook
3. Continues at 1. if ALICE's order is not filled and the current price of the orderbook or the AMM for A/UNIT is still below $p$
4. Here Alice's order is either filled or can't be filled because neither the oderbook nor the AMM can satisfy here price request $p$
a. Order filled: Nothing to do
b. Order not filled: Strategy based on Alice's preference
:::

In the case of the order not being able to be filled completely below price $p$, the following strategies could be selected by the orderer:
1. All-or-nothing: Partial fills are not okay, reverts all buys and trades and returns the funds to ALICE
2. Partial-and-exit: Partial fills are okay, the remaining balance is returned to ALICE
3. Partial-and-order: Partial fills are okay, the remaining balance is put into an order at price $p$

The research behind finding the optimal balance between orders to fill and amount to trade in the AMM is still to be done. An easy approach would be to fill orders until the price are above the price of the AMM and then trade the AMM up to the price of the next order. Repeat as long as possible. An algorithm might reduce load on the system by calculating which orders have to be filled and how much has to be traded with the AMM, thus allowing the system to execute a single trade instead of multiple trades.

This approach has the advantage that it provides the best possible price (except it does not inherently incorporate mint-sell and buy-burn strategies) by always taking the best price the orderbook and the AMM have to offer. Another major advantage is that the trading experience is very similar to the trading experience on CEXes. One disadvantage is, that it is a bit more complex than the present alternative solutions, which demands for abusal mitigation strategies and a a very efficient design.

### Architectural considerations
To efficiently match orders, it is required that the orders are maintained in a sorted list. In a blockchain environment, those lists can't get arbitrarily long though because the cost to write them to the storage and read them from the storage would quickly exceed the available capacity. In addition to that, small orders can congest the chain in the storage and computation requirements rise drastically. The latter issue can be partially solved by enforcing a sensible minimum order limit. The first issue requires a thoughtful efficient design.

#### Design proposal (sketch)
A design is required that offers efficiently searching for orders (sorted), while limiting the maximum size of a storage query response to a reasonable size. It's unfeasible and unreasonable to fetch and write back potentially millions of orders when only a small subset of the orders is relevant to fulfill the request.

The solution proposed here is to utilize the following data structures together:
1. Sorted array
2. DoubleLinkedList
3. Bins

The fundamental idea here is to split the whole price range $p_{range} = (0, 1.0)$ into multiple bins each of size $pd$. Each bin can contain at most $bin_{size}$ orders, which are stored within a sorted array within the bin. Now the concept of DoubleLinkedList is used, as every element that would be at a position greater than $bin_{size}$ or lower than position 0 would be put into another bin which is referenced within the current bin. This allows quick search of elements while maintaining reasonable order query reponses sizes. The following figure demonstrates this data structure:

##### Parameter selection
First of all a reasonable price delta $pd$ is selected. It should be selected in a way that within such a price delta, a reasonable amount of orders are distributed. For example, choosing a price delta $pd = 1$ is not reasonable, because all orders will be contained within (assuming outcome token per UNIT in a prediction market context). A $pd = 0.0001$ is probably too small, because order segregation will be huge and an enormous amount of bins exist. This would result in many single storage queries to find all the relevant orders.
In addition to that, the minimum order amount should be specified to a reasonable value, such as $10 to avoid spamming of the storage (which in itself already costs a lot due to transaction fees).

##### Adding order
We want to add an order.

###### Description of the algorithm in natural language
1. The order bin for $p$ does not exists. Create the bin and add the order.
2. The order bin for $p$ exists.
* a. The bin is full:
* * I. order price is between min bin price and max bin price: Insert order sorted and split bin
* * II. order price is lower than min bin price or bigger than max bin price: Move to next bin in the DoubleLinkedList and start over at step 1.
* b. The bin is not full:
* * I. Insert order sorted, the bin is within the maximum bin size: Done
* * II. Insert order sorted, the bin exceeds the maximum bin size: Split bin

Whenever a new bin is created, it is inserted into the DoubleLinkedList and references to previous, current and next bins are updated appropriately.
Whenever a bin is full, it is split into two bins. The new bin is inserted into the DoubleLinkedList and references to previous, current and next bins are updated appropriately.

###### Pseudocode

Bin layout:

struct Bin {
    orders: Array
    this: StorageAddr
    next: StorageAddr
    prev: StorageAddr
}

Order layout:

struct Order {
    wants: Outcome
    wants_amount: Amount
    gives: Outcome
    price: Price
}

Add code:

const PD = 0.05
const MAX_BIN_SIZE = 100

fn create_bin_before(orders, from_bin):
    # Create new bin and insert order
    bin = new_bin()
    bin.orders = array(orders)
    split(None, bin, from_bin)
    
fn create_bin_after(orders, from_bin):
    # Create new bin and insert order
    bin.this = generate_bin_address()
    bin.orders = array(orders)
    split(from_bin, bin, None)
    
fn split(bin_before, bin_new, bin_after):
    bin_new.next = bin_after.this
    bin_new.prev = bin_before.this
    bin_after.prev = bin_new.this
    bin_before.next = bin_new.this

fn recursive_add(bin, order):
    if bin.orders.len() == MAX_BIN_SIZE:
        if bin.orders.first().price >= order.price:
            if bin.prev.exists():
                recursive_add(get_bin(bin.prev), order)
            else:
                create_bin_before(order, from_bin)
                return
        else if bin.orders.last().price <= order.price:
            if bin.next.exists():
                recursive_add(get_bin(bin.next), order)
            else:
                create_bin_after(order, from_bin)
                return
                
    # We have arrived at the correct bin here.
    bin.orders.insert_sorted(order)
    
    if bin.orders.len() > MAX_BIN_SIZE:
        (first_half, second_half) = bin.orders.split_at_index(bin.orders.len() / 2)
        bin.orders = first_half
        # Can be optimized to split in a way such that search always starts in the middle of the DoubleLinkedList
        create_bin_after(second_half, bin)

fn add(order):
    # Assuming address is map that always tracks bin number to bin address mapping
    let bin_address = address(floor(e.price / pd))
    let bin = storage.get_bin(bin_address)
    recursive_add(bin, order)
    write_storage()