.. image:: https://drone.io/bitbucket.org/saaj/fangorn/status.png
  :target: https://drone.io/bitbucket.org/saaj/fangorn/latest
.. image:: https://codecov.io/bitbucket/saaj/fangorn/coverage.svg?branch=default
  :target: https://codecov.io/bitbucket/saaj/fangorn?branch=default 
.. image:: https://badge.fury.io/py/Fangorn.png
  :target: https://pypi.python.org/pypi/Fangorn

*******
Fangorn
*******

Nested Sets aka Modified Pre-order Tree Traversal (MPTT) *SQL* tree implemented in Python 
for *MySQL* and *SQLite*. Uses both traversal markup (left, right) and adjacency list 
parentId for more ad-hoc query flexibility. 

Provides tree structure validation and "memorisation" via SQLite *:memory:* for quick reads. 

Example
=======

We want to achieve the following tree. Node is represented by ``name id → parentId (l, r)``. 
To output a tree this way ``fangorn.test.visualize`` function can be used.

.. sourcecode:: text

  R 1 → None (1, 18)
  └─A1 2 → 1 (2, 5)
    └─B1 3 → 2 (3, 4)
  └─A2 4 → 1 (6, 13)
    └─B2 5 → 4 (7, 8)
    └─B3 6 → 4 (9, 12)
      └─C1 7 → 6 (10, 11)
  └─A3 8 → 1 (14, 17)
    └─B4 9 → 8 (15, 16)

First we need a table to represent the tree. And we want a tree node to have a name.    

.. sourcecode:: python

  import MySQLdb as mysql
  conn = mysql.connect(user = 'guest', db = 'test')
  conn.query('''
    CREATE TABLE `node` (
      `node_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
      `parent_id` int(10) unsigned DEFAULT NULL,
      `l` int(10) unsigned NOT NULL,
      `r` int(10) unsigned NOT NULL,
      `name` varchar(8) NOT NULL,
      PRIMARY KEY (`node_id`),
      KEY `l` (`l`),
      KEY `r` (`r`),
      KEY `parent_id` (`parent_id`),
      CONSTRAINT `node_has_node` FOREIGN KEY (`parent_id`)
        REFERENCES `node` (`node_id`)
        ON DELETE CASCADE
        ON UPDATE CASCADE
    ) ENGINE=InnoDB;
  ''')

Now we can create tree instance. Note that DAO that the tree relies on is expected to support 
*named* DB-API paramstyle (i.e. `WHERE node_id = :nodeId`). Also transaction control methods 
are recommended to implement nested transaction support. However test suite requires nested 
transactions to run. For `MySQLdb` and `sqlite3` there're compatibility wrappers under 
`fangorn.compat`. 

.. sourcecode:: python

  import fangorn
  from fangorn.compat.mysqldb import Mysqldb as MysqldbWrapper
  tree = fangorn.NestedSetsTree(MysqldbWrapper(conn), 'node', ('name',))
  
  rId  = tree.add(dict(name = 'R'))
  a1Id = tree.add(dict(name = 'A1'), parentId = rId)
  tree.add(dict(name = 'B1'), parentId = a1Id)
  a2Id = tree.add(dict(name = 'A2'), parentId = rId)
  b2Id = tree.add(dict(name = 'B2'), parentId = a2Id)
  b3Id = tree.add(dict(name = 'B3'), prevId = b2Id)
  tree.add(dict(name = 'C1'), parentId = b3Id)
  a3Id = tree.add(dict(name = 'A3'), parentId = rId)
  tree.add(dict(name = 'B4'), parentId = a3Id)
  
  tree.move(a1Id, rId)
  tree.move(a3Id, prevId = a2Id)
  
Now we can play with the tree.

.. sourcecode:: python

  print(tree.isDescendantOf(a2Id, 4)) # False
  print(tree.isDescendantOf(a2Id, 6)) # True
  print(tree.isDescendantOf(a2Id, 7)) # True
  print(tree.isDescendantOf(a2Id, 9)) # False

  print([n['name'] for n in tree.getChildren(a2Id)])    # ['B2', 'B3']
  print([n['name'] for n in tree.getDescendants(a2Id)]) # ['B2', 'B3', 'C1']
  print([n['name'] for n in tree.getPath(7)])           # ['R', 'A2', 'B3', 'C1']

  print(tree.getNode(8))   # {'left': 14L, 'right': 17L, 'nodeId': 8L, 'name': 'A3', 'parentId': 1L}
  print(tree.getParent(8)) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}
  print(tree.getRoot())    # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}

  tree.edit(1, dict(name = 'RR'))
  print(tree.getRoot()) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'RR', 'parentId': None}

  print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2', 'B3', 'C1'])
  tree.remove(b3Id)
  print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2'])
  

For more usage examples look at project's 
`test suite <https://bitbucket.org/saaj/fangorn/src/default/fangorn/test/>`_.
