title: Match buyers and sellers based on date ranges and quantity of shares
body: <p>I'm building a trading application that matches buyers/sellers that own subscription. Subscriptions have a certain quantity amount for a certain duration of time. There are 8 order types which are:</p>
  <ul>
  <li>Buy/sell subscription (can either be partially filled in regards to quantity or time)</li>
  <li>Buy/sell all quantity subscription (can only be partially filled in regards to time)</li>
  <li>Buy/sell all time subscription (can only be partially filled in regards to quantity)</li>
  <li>Buy/sell all quantity and time subscription (cannot be partially filled, all or nothing)</li>
  </ul>
  <p>Each user that fills the</p>
  <hr />
  <h1>Example 1</h1>
  <p>Assuming all orders in this example can be partially filled in regards to quantity and time lets say User A places a buy order asking for 100 shares between 1/2/2014 - 1/3/2014 (dd/mm/yyyy).</p>
  <p>There are 4 sell orders currently in the order book</p>
  <ul>
  <li>User B is selling 25 shares between 1/1/2014 - 5/1/2014</li>
  <li>User C is selling 50 shares between 1/1/2014 - 15/2/2014</li>
  <li>User D is selling 70 shares between 10/2/2014 - 1/7/2014</li>
  <li>User E is selling 5 shares between 15/2/2014 - 25/2/2014</li>
  </ul>
  <p>Which would look like</p>
  <pre><code>User A                 |--------------100-----------|
  User B    |----------------------------25-----------------------|
  User C    |-------------------50---|
  User D                       |--------------70------------------|
  User E                             |--5--|
  </code></pre>
  <p>After the matching is done each users orders in the order book would look like</p>
  <pre><code>User A                 |-25--|           |----5-----|
  User B    |------25----|                            |----25-----|
  User C    |------50----|
  User D                                              |----70-----|
  User E has no open orders
  </code></pre>
  <p>After all said and done the order book would look like:</p>
  <ul>
  <li>User A is buying 25 shares between 1/2/2014 - 10/2/2014</li>
  <li>User A is buying 5 shares between 15/2/2014 - 1/3/2014</li>
  <li>User B is selling 25 shares between 1/1/2014 - 1/2/2014</li>
  <li>User B is selling 25 shares between 1/3/2014 - 5/1/2014</li>
  <li>User C is selling 50 shares between 1/1/2014 - 1/2/2014</li>
  <li>User D is selling 70 shares between 1/3/2014 - 1/7/2014</li>
  <li>User E isn't selling anything</li>
  </ul>
  <h1>Example 2</h1>
  <p>This example is exactly the same except User B is of sell all quantity and time subscription type. In other words User B wants to sell his/her's entire position.</p>
  <p>After the matching is done each users orders in the order book would look like</p>
  <pre><code>User A                 |-50--|     |--25-|----30----|
  User B    |----------------------------25-----------------------|
  User C    |------50----|
  User D                       |-20--|                |----70-----|
  User E has no open orders
  </code></pre>
  <p>After all said and done the order book would look like:</p>
  <ul>
  <li>User A is buying 50 shares between 1/2/2014 - 10/2/2014</li>
  <li>User A is buying 25 shares between 15/2/2014 - 25/3/2014</li>
  <li>User A is buying 30 shares between 25/2/2014 - 1/3/2014</li>
  <li>User B is selling 25 shares between 1/1/2014 - 5/1/2014 (doesn't even match because this order doesn't allow partial filling)</li>
  <li>User C is selling 50 shares between 1/1/2014 - 1/2/2014</li>
  <li>User D is selling 70 shares between 15/2/2014 - 25/2/2014</li>
  <li>User D is selling 70 shares between 1/3/2014 - 1/7/2014</li>
  <li>User E isn't selling anything</li>
  </ul>
  <hr />
  <h1>Process</h1>
  <p>Another requirement is I need to be able to keep track of how the orders are filled in the database. When User A's buy order comes in it will first match to User B's which would result in:</p>
  <pre><code>User A                 |--------------75------------|
  User B    |------25----|                            |----25-----|
  </code></pre>
  <p>Both of those states would need to be saved to the database. Once that is complete then User C's order is matched up, which would look like:</p>
  <pre><code>User A                 |-----25----|------75--------|
  User B    |------25----|                            |----25-----|
  User C    |------50----|
  </code></pre>
  <p>Keep going:</p>
  <pre><code>User A                 |--25-|     |-------5--------|
  User B    |------25----|                            |----25-----|
  User C    |------50----|
  User D                                              |----70-----|
  </code></pre>
  <p><strong>Current Process</strong></p>
  <ol>
  <li>Get all of the sell orders (responders) that overlap the buy orders' (requester) date range (this would be opposite if it was an incoming sell order. The requester is referred to as the person who trigger the incoming order. Responder's are the potential matches)</li>
  <li>Sort the sell orders by price first then by time</li>
  <li>Loop through each of the sell orders
  <ul>
  <li>Calculate agreed price</li>
  <li>Calculate quantity to trade</li>
  <li>Get the buyers date range in relation to the current sell orders date range</li>
  <li>Determine by the date range relation between buyer and seller if its a partial fill</li>
  <li>If the seller does not allow partial fills, then continue to the next order</li>
  <li>Process the sell order
  <ul>
  <li>Does the sell order come before but overlap the buyers order? If so split the sell order and process the right end overlap and subtract the quantity requested from the buyer.</li>
  <li>Does the sell order come inside the buyers order? If so don't split anything just process that order completely and subtract the quantity requested from the buyer.</li>
  <li>Does the sell order come after but inside the buyer order? If so split the sell order and process the left side overlap and subtract the quantity requested from the buyer.</li>
  <li>Is the sell order a larger date range then the buyer order? If so split at the start and end and process the middle piece by subtracting the quantity requested from the buyer.</li>
  </ul>
  </li>
  </ul>
  </li>
  </ol>
  <p>That's as far as I've made it without it working properly when multiple orders are in the order book. The problem might be that for each sell order that comes in I'm always compare that to the original buy order when in fact the buy order gets filled up as sell orders are iterated. Maybe I need another nested loop? I'm not sure.</p>
  <hr />
  <h1>Question</h1>
  <p>Is there any existing algorithm to do what I'm asking?</p>
  <p><strong>EDIT</strong>: After some searching it sort of seems like I'm after an interval tree or a segment tree where I can sum up what's in the tree for a given time range. However I need to be able to store the modifications to the tree in a database with the start and dates. Are there any implementations out there of this done with LINQ or SQL?</p>
  <p><strong>EDIT 2:</strong> In my first edit I thought it was an interval tree but now it looks more like <a href="http://mathworld.wolfram.com/Bin-PackingProblem.html" rel="nofollow noreferrer">bin packing algorithm</a></p>
  <p><strong>EDIT 3</strong> OK so I really seemed to have not conveyed my questions properly here. I don't really have a coding problem but more of a thinking problem of how to achieve this properly. I need a flow diagram or steps of execution to be able to process buyers and sellers by splitting their subscriptions based on the conditions outlined at the top.</p>
  <p>I have posted this same question @ <a href="https://softwareengineering.stackexchange.com/questions/225404/match-buyers-and-sellers-based-on-date-ranges-and-quantity-of-shares">https://softwareengineering.stackexchange.com/</a> as well in case this was the wrong site to post this question on.</p>