DB2 - WS 2015/16 - Assignment 4 (Minimal B+Tree)
================================================

1) Download.

   Download the file 'assignment4.zip' and unpack it.

   Rename nnnnnnn_4.py to matrikel_4.py, such that if your matrikel number is 
   1234567 the file is named 1234567_4.py

   In subdirectory 'test' we provided simple test cases for you to evaluate your 
   solutions. 'in.txt' stores a sequence of consecutive numbers from 1 to 10. 
   Each file 'out_mX.txt' stores the correct output for specific number of 
   pointers X.

   You may test your code by calling

   cat in.txt | python nnnnnnn_4.py M

   where M is the number of pointers in a node and 'in.txt' stores the keys.

   ATTENTION: Please stick to the naming convention because your assignments 
   are fetched, processed, and verified automatically. If the file name is 
   incorrect we may miss your assignment and you may not pass.

2) Assignment description.

   In this assignment we implement a procedure of building a minimal B+Tree for 
   a given set of keys and the number of pointers M. By minimal, we understand 
   the minimal number of levels in a tree.

   The program reads the keys from the standard input and sorts. Building the 
   B+Tree is a two-step process. 

   Step 1:
   The input keys are partitioned to leaf nodes, the nodes are created and 
   appended to a list of all nodes. 

   Step 2:
   The inner-node levels of the tree are created in a loop. The loop terminates 
   when the root node is created.
   For level k (root is level 1) the pointers to nodes from level k+1 are 
   partitioned to the nodes on level k. The keys are looked up in the leaf 
   nodes by following the pointers.

   Data structures:
   - All nodes of our tree are stored in a list.
   - Each node is also a list storing the node ID and its keys and pointers 
   (all being integer numbers).
   - The node IDs are consecutive integer numbers assigned in the order of node 
   creation. The first created node has ID=0, the last one (root) has ID equal 
   to the number of nodes in the tree minus 1.
   - Example structure of a node: [ID, p1, k1, p2, k2, p3, ... , kn-1, pn], 
   where ID is the node's ID, pi (1<=i<n) and kj (1<=j<=n) are pointers and 
   keys.
   - If a node is underfull (has too few pointers/keys), the empty pointers and 
   keys are denoted with the value '-1'.
   - Values representing pointers in the leaf nodes are always equal to '-1'
     (except for the last pointer, which points to the next leaf node).

   Example tree and nodes in our representation (M=3, input keys are 1, 2, 
   and 3):

   - Tree (node IDs assigned by our program are shown to the left of each node).
                      ┌───┬───┐
                    2 │ 3 │   │
                      └───┴───┘
                     /     \
             ┌───┬───┐      ┌───┬───┐
           0 │ 1 │ 2 │    1 │ 3 │   │
             └───┴───┘      └───┴───┘
   
   - List of all nodes after building our example tree. This is the main data
   structure in our program to store all nodes in a tree (see Data structures).
   [
     [0,-1,1,-1,2,1],
     [1,-1,3,-1,-1,-1],
     [2,0,3,1,-1,-1]
   ]

   Input:
   - List of keys stored in a text file. The keys are integer numbers. Each key 
   is written on a separate line in the file.
   - Program parameter M which denotes the number of pointers in a node.

   Output:
   - List of nodes and the values of their keys and pointers.
   - Each node is printed in a separate line.
   - Node ID, key and pointer values are separated with a colon.
   - The last line indicates the ID of the root node, preceded with letter 'r'.

   Example output for the tree above:
   0:-1:1:-1:2:1
   1:-1:3:-1:-1:-1
   2:0:3:1:-1:-1
   r2

3) Task: Fix the code.

   While building our B+Tree we do not consider the nodes being underfull 
   (having too few pointers/keys). This behaviour may occur in the last node on 
   each tree level.

   Your task is to fix this problem by distributing the keys and pointers 
   equally in the last two nodes of each tree level. If the number of keys
   to distribute is uneven, put the additional key in the last node.

   IMPORTANT: Please do not change the output format of the program.

4) Submission.

   Starting with this assignment, we're changing the submission process. You'll 
   be communicated the details with a dedicated email. Please follow precisely 
   the instructions.

5) Python.

   To install python on your personal computer, follow the guidelines on 
   https://www.python.org/

   To edit python code, use any text editor. We recommend vim, emacs, sublime 
   text. For our purposes, using any sophisticated IDE is simply overwhelming. 
   Though, we don't discourage to do that.

   The source code, that we provide for each assignment, should be 
   self-explained and no python-specific knowledge is required to understand it 
   (assuming experience with any other programming language). 

   If you need more help, a great source of information is the python website:
   - documentation https://docs.python.org/2/
   - tutorial https://docs.python.org/2/tutorial/index.html
   - beginners guide https://wiki.python.org/moin/BeginnersGuide

   If you do not have python installed (or cannot install) on your personal 
   computer, the machines in the computer lab room and the 'sshstud' machine 
   have it installed.