add urwidtrees lib

12 files changed, 1966 insertions, 0 deletions

diff --git a/alot/foreign/urwidtrees/README.md b/alot/foreign/urwidtrees/README.md
new file mode 100644
index 00000000..b186b729
--- /dev/null
+++ b/alot/foreign/urwidtrees/README.md
@@ -0,0 +1,88 @@
+Urwid Tree Container API
+========================
+
+This is a POC implementation of a new Widget Container API for the [urwid][urwid] toolkit.
+Its design goals are
+
+* clear separation classes that define, decorate and display trees of widgets
+* representation of trees by local operations on node positions
+* easy to use default implementation for simple trees
+* Collapses are considered decoration
+
+We propose a `urwid.ListBox`-based widget that display trees where siblings grow vertically and
+children horizontally.  This `TreeBox` widget handles key presses to move in the tree and
+collapse/expand subtrees if possible.
+
+The choice to define trees by overwriting local position movements allows to
+easily define potentially infinite tree structures. See `example4` for how to
+walk local file systems.
+
+The overall structure of the API contains three parts:
+
+
+Structure
+---------
+
+`tree.Tree` objects define a tree structure by implementing the local movement methods
+
+    parent_position
+    first_child_position
+    last_child_position
+    next_sibling_position
+    prev_sibling_position
+
+Each of which takes and returns a `position` object of arbitrary type (fixed for the Tree)
+as done in urwids ListWalker API. Apart from this, a `Tree` is assumed to define a dedicated
+position `tree.root` that is used as fallback initially focussed element,
+and define the `__getitem__` method to return its content (usually a Widget) for a given position.
+
+Note that `Tree` only defines a tree structure, it does not necessarily have any decoration around
+its contained Widgets.
+
+There is a ready made subclass called `SimpleTree` that offers the tree API for a given 
+nested tuple structure. If you write your own classes its a good idea to subclass `Tree`
+and just overwrite the above mentioned methods as the base class already offers a number of
+derivative methods.
+
+
+Decoration
+----------
+
+Is done by using (subclasses of ) `decoration.DecoratedTree`. Objects of this type
+wrap around a given `Tree` and themselves behave like a (possibly altered) tree.
+Per default, `DecoratedTree` just passes every method on to its underlying tree.
+Decoration is done *not* by overwriting `__getitem__`, but by offering two additional
+methods
+
+  get_decorated()
+  decorate().
+
+`get_decorated(pos)` returns the (decorated) content of the original tree at the given position.
+`decorate(pos, widget,..)` decorates the given widget assuming its placed at a given position.
+The former is trivially based on the latter, Containers that display `Tree`s use `get_decorated`
+instead of `__getitem__` when working on `DecoratedTree`s.
+
+The reason for this slightly odd design choice is that first it makes it easy to read
+the original content of a decorated tree: You simply use `dtree[pos]`.
+Secondly, this makes it possible to recursively add line decoration when nesting (decorated) Trees.
+
+The module `decoration` offers a few readily usable `DecoratedTree` subclasses that implement
+decoration by indentation, arrow shapes and subtree collapsing:
+`CollapsibleTree`, `IndentedTree`, `CollapsibleIndentedTree`, `ArrowTree` and `CollapsibleArrowTree`.
+Each can be further customized by constructor parameters.
+
+
+Containers
+----------
+
+`widgets.TreeBox` is essentially a `urwid.ListBox` that displays a given `Tree`.
+Per default no decoration is used and the widgets of the tree are simply displayed line by line in
+depth first order. `TreeBox`'s constructor accepts a `focus` parameter to specify the initially
+focussed position. Internally, it uses a `TreeListWalker` to linearize the tree to a list.
+
+`widgets.TreeListWalker` serve as adapter between `Tree` and ListWalker APIs:
+They implement the ListWalker API using the data from a given `Tree` in depth-first order.
+As such, one can directly pass on a `TreeListWalker` to an `urwid.ListBox` if one doesn't want
+to use tree-based focus movement or key bindings for collapsing subtrees.
+
+[urwid]: http://excess.org/urwid/
diff --git a/alot/foreign/urwidtrees/__init__.py b/alot/foreign/urwidtrees/__init__.py
new file mode 100644
index 00000000..ffa23356
--- /dev/null
+++ b/alot/foreign/urwidtrees/__init__.py
@@ -0,0 +1,13 @@
+try:
+    # lru_cache is part of the stdlib from v3.2 onwards
+    import functools.lru_cache as lru_cache
+except:
+    # on older versions we use a backport
+    import lru_cache as lru_cache
+
+from tree import Tree, SimpleTree
+from decoration import DecoratedTree, CollapsibleTree
+from decoration import IndentedTree, CollapsibleIndentedTree
+from decoration import ArrowTree, CollapsibleArrowTree
+from nested import NestedTree
+from widgets import TreeBox
diff --git a/alot/foreign/urwidtrees/decoration.py b/alot/foreign/urwidtrees/decoration.py
new file mode 100644
index 00000000..d70d4bef
--- /dev/null
+++ b/alot/foreign/urwidtrees/decoration.py
@@ -0,0 +1,512 @@
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+from tree import Tree, SimpleTree
+import urwid
+import logging
+
+NO_SPACE_MSG = 'too little space for requested decoration'
+
+
+class TreeDecorationError(Exception):
+    pass
+
+
+class DecoratedTree(Tree):
+    """
+    :class:`Tree` that wraps around another :class:`Tree` and allows to read
+    original content as well as decorated versions thereof.
+    """
+    def __init__(self, content):
+        if not isinstance(content, Tree):
+            # do we need this?
+            content = SimpleTree(content)
+        self._tree = content
+        self.root = self._tree.root
+
+    def get_decorated(self, pos):
+        """
+        return widget that consists of the content of original tree at given
+        position plus its decoration.
+        """
+        return self.decorate(pos, self[pos])
+
+    def decorate(self, pos, widget, is_first=True):
+        """
+        decorate `widget` according to a position `pos` in the original tree.
+        setting `is_first` to False indicates that we are decorating a line
+        that is *part* of the (multi-line) content at this position, but not
+        the first part. This allows to omit incoming arrow heads for example.
+        """
+        return widget
+
+    # pass on everything else to the original tree.
+
+    def parent_position(self, pos):
+        return self._tree.parent_position(pos)
+
+    def first_child_position(self, pos):
+        return self._tree.first_child_position(pos)
+
+    def last_child_position(self, pos):
+        return self._tree.last_child_position(pos)
+
+    def next_sibling_position(self, pos):
+        return self._tree.next_sibling_position(pos)
+
+    def prev_sibling_position(self, pos):
+        return self._tree.prev_sibling_position(pos)
+
+    def __getitem__(self, pos):
+        return self._tree[pos]
+
+
+class CollapseMixin(object):
+    """
+    Mixin for :class:`Tree` that allows to collapse subtrees.
+
+    This works by overwriting
+    :meth:`[first|last]_child_position <first_child_position>`, forcing them to
+    return `None` if the given position is considered collapsed. We use a
+    (given) callable `is_collapsed` that accepts positions and returns a
+    boolean to determine which node is considered collapsed.
+    """
+    def __init__(self, is_collapsed=lambda pos: False,
+                 **kwargs):
+        self._initially_collapsed = is_collapsed
+        self._divergent_positions = []
+
+    def is_collapsed(self, pos):
+        """checks if given position is currently collapsed"""
+        collapsed = self._initially_collapsed(pos)
+        if pos in self._divergent_positions:
+            collapsed = not collapsed
+        return collapsed
+
+    # implement functionality by overwriting local position transformations
+
+    # TODO: ATM this assumes we are in a wrapper: it uses self._tree.
+    # This is not necessarily true, for example for subclasses of SimpleTree!
+    # maybe define this whole class as a wrapper?
+
+    def last_child_position(self, pos):
+        if self.is_collapsed(pos):
+            return None
+        return self._tree.last_child_position(pos)
+
+    def first_child_position(self, pos):
+        if self.is_collapsed(pos):
+            return None
+        return self._tree.first_child_position(pos)
+
+    def collapsible(self, pos):
+        return not self._tree.is_leaf(pos)
+
+    def set_position_collapsed(self, pos, is_collapsed):
+        if self.collapsible(pos):
+            if self._initially_collapsed(pos) == is_collapsed:
+                if pos in self._divergent_positions:
+                    self._divergent_positions.remove(pos)
+            else:
+                if pos not in self._divergent_positions:
+                    self._divergent_positions.append(pos)
+
+    def toggle_collapsed(self, pos):
+        self.set_position_collapsed(pos, not self.is_collapsed(pos))
+
+    def collapse(self, pos):
+        self.set_position_collapsed(pos, True)
+
+    def collapse_all(self):
+        self.set_collapsed_all(True)
+
+    def expand_all(self):
+        self.set_collapsed_all(False)
+
+    def set_collapsed_all(self, is_collapsed):
+        self._initially_collapsed = lambda x: is_collapsed
+        self._divergent_positions = []
+
+    def expand(self, pos):
+        self.set_position_collapsed(pos, False)
+
+
+class CollapseIconMixin(CollapseMixin):
+    """
+    Mixin for :classs:`Tree` that allows to allows to collapse subtrees
+    and use an indicator icon in line decorations.
+    This Mixin adds the ability to construct collapse-icon for a
+    position, indicating its collapse status to :class:`CollapseMixin`.
+    """
+    def __init__(self,
+                 is_collapsed=lambda pos: False,
+                 icon_collapsed_char='+',
+                 icon_expanded_char='-',
+                 icon_collapsed_att=None,
+                 icon_expanded_att=None,
+                 icon_frame_left_char='[',
+                 icon_frame_right_char=']',
+                 icon_frame_att=None,
+                 icon_focussed_att=None,
+                 **kwargs):
+        """TODO: docstrings"""
+        CollapseMixin.__init__(self, is_collapsed, **kwargs)
+        self._icon_collapsed_char = icon_collapsed_char
+        self._icon_expanded_char = icon_expanded_char
+        self._icon_collapsed_att = icon_collapsed_att
+        self._icon_expanded_att = icon_expanded_att
+        self._icon_frame_left_char = icon_frame_left_char
+        self._icon_frame_right_char = icon_frame_right_char
+        self._icon_frame_att = icon_frame_att
+        self._icon_focussed_att = icon_focussed_att
+
+    def _construct_collapse_icon(self, pos):
+        width = 0
+        widget = None
+        char = self._icon_expanded_char
+        charatt = self._icon_expanded_att
+        if self.is_collapsed(pos):
+            char = self._icon_collapsed_char
+            charatt = self._icon_collapsed_att
+        if char is not None:
+
+            columns = []
+            if self._icon_frame_left_char is not None:
+                lchar = self._icon_frame_left_char
+                charlen = len(lchar)
+                leftframe = urwid.Text((self._icon_frame_att, lchar))
+                columns.append((charlen, leftframe))
+                width += charlen
+
+            # next we build out icon widget: we feed all markups to a Text,
+            # make it selectable (to toggle collapse) if requested
+            markup = (charatt, char)
+            widget = urwid.Text(markup)
+            charlen = len(char)
+            columns.append((charlen, widget))
+            width += charlen
+
+            if self._icon_frame_right_char is not None:
+                rchar = self._icon_frame_right_char
+                charlen = len(rchar)
+                rightframe = urwid.Text((self._icon_frame_att, rchar))
+                columns.append((charlen, rightframe))
+                width += charlen
+
+            widget = urwid.Columns(columns)
+        return width, widget
+
+
+class CollapsibleTree(CollapseMixin, DecoratedTree):
+    """Undecorated Tree that allows to collapse subtrees"""
+    def __init__(self, tree, **kwargs):
+        DecoratedTree.__init__(self, tree)
+        CollapseMixin.__init__(self, **kwargs)
+
+
+class IndentedTree(DecoratedTree):
+    """Indent tree nodes according to their depth in the tree"""
+    def __init__(self, tree, indent=2):
+        """
+        :param tree: tree of widgets to be displayed
+        :type tree: Tree
+        :param indent: indentation width
+        :type indent: int
+        """
+        self._indent = indent
+        DecoratedTree.__init__(self, tree)
+
+    def decorate(self, pos, widget, is_first=True):
+        line = None
+        indent = self._tree.depth(pos) * self._indent
+        cols = [(indent, urwid.SolidFill(' ')), widget]
+        # construct a Columns, defining all spacer as Box widgets
+        line = urwid.Columns(cols, box_columns=range(len(cols))[:-1])
+        return line
+
+
+class CollapsibleIndentedTree(CollapseIconMixin, IndentedTree):
+    """
+    Indent collapsible tree nodes according to their depth in the tree and
+    display icons indicating collapse-status in the gaps.
+    """
+    def __init__(self, walker, icon_offset=1, indent=4, **kwargs):
+        """
+        :param walker: tree of widgets to be displayed
+        :type walker: Tree
+        :param indent: indentation width
+        :type indent: int
+        :param icon_offset: distance from icon to the eginning of the tree
+                            node.
+        :type icon_offset: int
+        """
+        self._icon_offset = icon_offset
+        IndentedTree.__init__(self, walker, indent=indent)
+        CollapseIconMixin.__init__(self, **kwargs)
+
+    def decorate(self, pos, widget, is_first=True):
+        """
+        builds a list element for given position in the tree.
+        It consists of the original widget taken from the Tree and some
+        decoration columns depending on the existence of parent and sibling
+        positions. The result is a urwid.Culumns widget.
+        """
+        void = urwid.SolidFill(' ')
+        line = None
+        cols = []
+        depth = self._tree.depth(pos)
+
+        # add spacer filling all but the last indent
+        if depth > 0:
+            cols.append((depth * self._indent, void)),  # spacer
+
+        # construct last indent
+        # TODO
+        iwidth, icon = self._construct_collapse_icon(pos)
+        available_space = self._indent
+        firstindent_width = self._icon_offset + iwidth
+
+        # stop if indent is too small for this decoration
+        if firstindent_width > available_space:
+            raise TreeDecorationError(NO_SPACE_MSG)
+
+        # add icon only for non-leafs
+        is_leaf = self._tree.is_leaf(pos)
+        if not is_leaf:
+            if icon is not None:
+                # space to the left
+                cols.append((available_space - firstindent_width,
+                             urwid.SolidFill(' ')))
+                # icon
+                icon_pile = urwid.Pile([('pack', icon), void])
+                cols.append((iwidth, icon_pile))
+                # spacer until original widget
+                available_space = self._icon_offset
+            cols.append((available_space, urwid.SolidFill(' ')))
+        else:  # otherwise just add another spacer
+            cols.append((self._indent, urwid.SolidFill(' ')))
+
+        cols.append(widget)  # original widget ]
+        # construct a Columns, defining all spacer as Box widgets
+        line = urwid.Columns(cols, box_columns=range(len(cols))[:-1])
+
+        return line
+
+
+class ArrowTree(IndentedTree):
+    """
+    Decorates the tree by indenting nodes according to their depth and using
+    the gaps to draw arrows indicate the tree structure.
+    """
+    def __init__(self, walker,
+                 indent=3,
+                 childbar_offset=0,
+                 arrow_hbar_char=u'\u2500',
+                 arrow_hbar_att=None,
+                 arrow_vbar_char=u'\u2502',
+                 arrow_vbar_att=None,
+                 arrow_tip_char=u'\u27a4',
+                 arrow_tip_att=None,
+                 arrow_att=None,
+                 arrow_connector_tchar=u'\u251c',
+                 arrow_connector_lchar=u'\u2514',
+                 arrow_connector_att=None, **kwargs):
+        """
+        :param walker: tree of widgets to be displayed
+        :type walker: Tree
+        :param indent: indentation width
+        :type indent: int
+        """
+        IndentedTree.__init__(self, walker, indent)
+        self._childbar_offset = childbar_offset
+        self._arrow_hbar_char = arrow_hbar_char
+        self._arrow_hbar_att = arrow_hbar_att
+        self._arrow_vbar_char = arrow_vbar_char
+        self._arrow_vbar_att = arrow_vbar_att
+        self._arrow_connector_lchar = arrow_connector_lchar
+        self._arrow_connector_tchar = arrow_connector_tchar
+        self._arrow_connector_att = arrow_connector_att
+        self._arrow_tip_char = arrow_tip_char
+        self._arrow_tip_att = arrow_tip_att
+        self._arrow_att = arrow_att
+
+    def _construct_spacer(self, pos, acc):
+        """
+        build a spacer that occupies the horizontally indented space between
+        pos's parent and the root node. It will return a list of tuples to be
+        fed into a Columns widget.
+        """
+        parent = self._tree.parent_position(pos)
+        if parent is not None:
+            grandparent = self._tree.parent_position(parent)
+            if self._indent > 0 and grandparent is not None:
+                parent_sib = self._tree.next_sibling_position(parent)
+                draw_vbar = parent_sib is not None and \
+                    self._arrow_vbar_char is not None
+                space_width = self._indent - 1 * (draw_vbar) - self._childbar_offset
+                if space_width > 0:
+                    void = urwid.AttrMap(urwid.SolidFill(' '), self._arrow_att)
+                    acc.insert(0, ((space_width, void)))
+                if draw_vbar:
+                    barw = urwid.SolidFill(self._arrow_vbar_char)
+                    bar = urwid.AttrMap(barw, self._arrow_vbar_att or
+                                        self._arrow_att)
+                    acc.insert(0, ((1, bar)))
+            return self._construct_spacer(parent, acc)
+        else:
+            return acc
+
+    def _construct_connector(self, pos):
+        """
+        build widget to be used as "connector" bit between the vertical bar
+        between siblings and their respective horizontab bars leading to the
+        arrow tip
+        """
+        # connector symbol, either L or |- shaped.
+        connectorw = None
+        connector = None
+        if self._tree.next_sibling_position(pos) is not None:  # |- shaped
+            if self._arrow_connector_tchar is not None:
+                connectorw = urwid.Text(self._arrow_connector_tchar)
+        else:  # L shaped
+            if self._arrow_connector_lchar is not None:
+                connectorw = urwid.Text(self._arrow_connector_lchar)
+        if connectorw is not None:
+            att = self._arrow_connector_att or self._arrow_att
+            connector = urwid.AttrMap(connectorw, att)
+        return connector
+
+    def _construct_arrow_tip(self, pos):
+        """returns arrow tip as (width, widget)"""
+        arrow_tip = None
+        width = 0
+        if self._arrow_tip_char:
+            txt = urwid.Text(self._arrow_tip_char)
+            arrow_tip = urwid.AttrMap(
+                txt, self._arrow_tip_att or self._arrow_att)
+            width = len(self._arrow_tip_char)
+        return width, arrow_tip
+
+    def _construct_first_indent(self, pos):
+        """
+        build spacer to occupy the first indentation level from pos to the
+        left. This is separate as it adds arrowtip and sibling connector.
+        """
+        cols = []
+        void = urwid.AttrMap(urwid.SolidFill(' '), self._arrow_att)
+        available_width = self._indent
+
+        if self._tree.depth(pos) > 0:
+            connector = self._construct_connector(pos)
+            if connector is not None:
+                width = connector.pack()[0]
+                if width > available_width:
+                    raise TreeDecorationError(NO_SPACE_MSG)
+                available_width -= width
+                if self._tree.next_sibling_position(pos) is not None:
+                    barw = urwid.SolidFill(self._arrow_vbar_char)
+                    below = urwid.AttrMap(barw, self._arrow_vbar_att or
+                                          self._arrow_att)
+                else:
+                    below = void
+                # pile up connector and bar
+                spacer = urwid.Pile([('pack', connector), below])
+                cols.append((width, spacer))
+
+            #arrow tip
+            awidth, at = self._construct_arrow_tip(pos)
+            if at is not None:
+                if awidth > available_width:
+                    raise TreeDecorationError(NO_SPACE_MSG)
+                available_width -= awidth
+                at_spacer = urwid.Pile([('pack', at), void])
+                cols.append((awidth, at_spacer))
+
+            # bar between connector and arrow tip
+            if available_width > 0:
+                barw = urwid.SolidFill(self._arrow_hbar_char)
+                bar = urwid.AttrMap(
+                    barw, self._arrow_hbar_att or self._arrow_att)
+                hb_spacer = urwid.Pile([(1, bar), void])
+                cols.insert(1, (available_width, hb_spacer))
+        return cols
+
+    def decorate(self, pos, widget, is_first=True):
+        """
+        builds a list element for given position in the tree.
+        It consists of the original widget taken from the Tree and some
+        decoration columns depending on the existence of parent and sibling
+        positions. The result is a urwid.Culumns widget.
+        """
+        line = None
+        if pos is not None:
+            original_widget = widget
+            cols = self._construct_spacer(pos, [])
+
+            # Construct arrow leading from parent here,
+            # if we have a parent and indentation is turned on
+            if self._indent > 0:
+                if is_first:
+                    indent = self._construct_first_indent(pos)
+                    if indent is not None:
+                        cols = cols + indent
+                else:
+                    parent = self._tree.parent_position(pos)
+                    if self._indent > 0 and parent is not None:
+                        parent_sib = self._tree.next_sibling_position(pos)
+                        draw_vbar = parent_sib is not None
+                        void = urwid.AttrMap(urwid.SolidFill(' '),
+                                             self._arrow_att)
+                        if self._childbar_offset > 0:
+                            cols.append((self._childbar_offset, void))
+                        if draw_vbar:
+                            barw = urwid.SolidFill(self._arrow_vbar_char)
+                            bar = urwid.AttrMap(
+                                barw, self._arrow_vbar_att or self._arrow_att)
+                            rspace_width = self._indent - \
+                                1 - self._childbar_offset
+                            cols.append((1, bar))
+                            cols.append((rspace_width, void))
+                        else:
+                            cols.append((self._indent, void))
+
+            # add the original widget for this line
+            cols.append(original_widget)
+            # construct a Columns, defining all spacer as Box widgets
+            line = urwid.Columns(cols, box_columns=range(len(cols))[:-1])
+        return line
+
+
+class CollapsibleArrowTree(CollapseIconMixin, ArrowTree):
+    """Arrow-decoration that allows collapsing subtrees"""
+    def __init__(self, treelistwalker, icon_offset=0, indent=5, **kwargs):
+        self._icon_offset = icon_offset
+        ArrowTree.__init__(self, treelistwalker, indent, **kwargs)
+        CollapseIconMixin.__init__(self, **kwargs)
+
+    def _construct_arrow_tip(self, pos):
+
+        cols = []
+        overall_width = self._icon_offset
+
+        if self._icon_offset > 0:
+            # how often we repeat the hbar_char until width icon_offset is
+            # reached
+            hbar_char_count = len(self._arrow_hbar_char) / self._icon_offset
+            barw = urwid.Text(self._arrow_hbar_char * hbar_char_count)
+            bar = urwid.AttrMap(barw, self._arrow_hbar_att or self._arrow_att)
+            cols.insert(1, (self._icon_offset, bar))
+
+        # add icon only for non-leafs
+        if self.collapsible(pos):
+            iwidth, icon = self._construct_collapse_icon(pos)
+            if icon is not None:
+                cols.insert(0, (iwidth, icon))
+                overall_width += iwidth
+
+        # get arrow tip
+        awidth, tip = ArrowTree._construct_arrow_tip(self, pos)
+        if tip is not None:
+            cols.append((awidth, tip))
+            overall_width += awidth
+
+        return overall_width, urwid.Columns(cols)
diff --git a/alot/foreign/urwidtrees/example1.py b/alot/foreign/urwidtrees/example1.py
new file mode 100755
index 00000000..ac1d16e6
--- /dev/null
+++ b/alot/foreign/urwidtrees/example1.py
@@ -0,0 +1,82 @@
+#!/usr/bin/python
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+import urwid
+from tree import SimpleTree
+from widgets import TreeBox
+
+
+# define some colours
+palette = [
+    ('body', 'black', 'light gray'),
+    ('focus', 'light gray', 'dark blue', 'standout'),
+    ('bars', 'dark blue', 'light gray', ''),
+    ('arrowtip', 'light blue', 'light gray', ''),
+    ('connectors', 'light red', 'light gray', ''),
+]
+
+# We use selectable Text widgets for our example..
+
+
+class FocusableText(urwid.WidgetWrap):
+    """Selectable Text used for nodes in our example"""
+    def __init__(self, txt):
+        t = urwid.Text(txt)
+        w = urwid.AttrMap(t, 'body', 'focus')
+        urwid.WidgetWrap.__init__(self, w)
+
+    def selectable(self):
+        return True
+
+    def keypress(self, size, key):
+        return key
+
+# define a test tree in the format accepted by SimpleTree. Essentially, a
+# tree is given as (nodewidget, [list, of, subtrees]). SimpleTree accepts
+# lists of such trees.
+
+
+def construct_example_simpletree_structure(selectable_nodes=True, children=3):
+
+    Text = FocusableText if selectable_nodes else urwid.Text
+
+    # define root node
+    tree = (Text('ROOT'), [])
+
+    # define some children
+    c = g = gg = 0  # counter
+    for i in range(children):
+        subtree = (Text('Child %d' % c), [])
+        # and grandchildren..
+        for j in range(children):
+            subsubtree = (Text('Grandchild %d' % g), [])
+            for k in range(children):
+                leaf = (Text('Grand Grandchild %d' % gg), None)
+                subsubtree[1].append(leaf)
+                gg += 1  # inc grand-grandchild counter
+            subtree[1].append(subsubtree)
+            g += 1  # inc grandchild counter
+        tree[1].append(subtree)
+        c += 1
+    return tree
+
+
+def construct_example_tree(selectable_nodes=True, children=2):
+    # define a list of tree structures to be passed on to SimpleTree
+    forrest = [construct_example_simpletree_structure(selectable_nodes,
+                                                      children)]
+
+    # stick out test tree into a SimpleTree and return
+    return SimpleTree(forrest)
+
+if __name__ == "__main__":
+    # get example tree
+    stree = construct_example_tree()
+
+    # put the tree into a treebox
+    treebox = TreeBox(stree)
+
+    # add some decoration
+    rootwidget = urwid.AttrMap(treebox, 'body')
+    urwid.MainLoop(rootwidget, palette).run()  # go
diff --git a/alot/foreign/urwidtrees/example2.arrows.py b/alot/foreign/urwidtrees/example2.arrows.py
new file mode 100755
index 00000000..8a4f4121
--- /dev/null
+++ b/alot/foreign/urwidtrees/example2.arrows.py
@@ -0,0 +1,27 @@
+#!/usr/bin/python
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+from example1 import construct_example_tree, palette  # example data
+from decoration import ArrowTree  # for Decoration
+from widgets import TreeBox
+import urwid
+
+if __name__ == "__main__":
+    # get example tree
+    stree = construct_example_tree()
+    # Here, we add some decoration by wrapping the tree using ArrowTree.
+    atree = ArrowTree(stree,
+                      # customize at will..
+                      # arrow_hbar_char=u'\u2550',
+                      # arrow_vbar_char=u'\u2551',
+                      # arrow_tip_char=u'\u25B7',
+                      # arrow_connector_tchar=u'\u2560',
+                      # arrow_connector_lchar=u'\u255A',
+                      )
+
+    # put the into a treebox
+    treebox = TreeBox(atree)
+
+    rootwidget = urwid.AttrMap(treebox, 'body')
+    urwid.MainLoop(rootwidget, palette).run()  # go
diff --git a/alot/foreign/urwidtrees/example3.collapse.py b/alot/foreign/urwidtrees/example3.collapse.py
new file mode 100755
index 00000000..362dd071
--- /dev/null
+++ b/alot/foreign/urwidtrees/example3.collapse.py
@@ -0,0 +1,41 @@
+#!/usr/bin/python
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+from example1 import construct_example_tree, palette  # example data
+from decoration import CollapsibleIndentedTree  # for Decoration
+from widgets import TreeBox
+import urwid
+
+if __name__ == "__main__":
+    # get some SimpleTree
+    stree = construct_example_tree()
+
+    # Use (subclasses of) the wrapper decoration.CollapsibleTree to construct a
+    # tree where collapsible subtrees. Apart from the original tree, these take
+    # a callable `is_collapsed` that defines initial collapsed-status if a
+    # given position.
+
+    # We want all grandchildren collapsed initially
+    if_grandchild = lambda pos: stree.depth(pos) > 1
+
+    # We use CollapsibleIndentedTree around the original example tree.
+    # This uses Indentation to indicate the tree structure and squeezes in
+    # text-icons to indicate the collapsed status.
+    # Also try CollapsibleTree or CollapsibleArrowTree..
+    tree = CollapsibleIndentedTree(stree,
+                                   is_collapsed=if_grandchild,
+                                   icon_focussed_att='focus',
+                                   # indent=6,
+                                   # childbar_offset=1,
+                                   # icon_frame_left_char=None,
+                                   # icon_frame_right_char=None,
+                                   # icon_expanded_char='-',
+                                   # icon_collapsed_char='+',
+                                   )
+
+    # put the tree into a treebox
+    treebox = TreeBox(tree)
+
+    rootwidget = urwid.AttrMap(treebox, 'body')
+    urwid.MainLoop(rootwidget, palette).run()  # go
diff --git a/alot/foreign/urwidtrees/example4.filesystem.py b/alot/foreign/urwidtrees/example4.filesystem.py
new file mode 100755
index 00000000..a81107dc
--- /dev/null
+++ b/alot/foreign/urwidtrees/example4.filesystem.py
@@ -0,0 +1,127 @@
+#!/usr/bin/python
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+import urwid
+import os
+from example1 import palette  # example data
+from widgets import TreeBox
+from tree import Tree
+from decoration import CollapsibleArrowTree
+
+
+# define selectable urwid.Text widgets to display paths
+class FocusableText(urwid.WidgetWrap):
+    """Widget to display paths lines"""
+    def __init__(self, txt):
+        t = urwid.Text(txt)
+        w = urwid.AttrMap(t, 'body', 'focus')
+        urwid.WidgetWrap.__init__(self, w)
+
+    def selectable(self):
+        return True
+
+    def keypress(self, size, key):
+        return key
+
+# define Tree that can walk your filesystem
+
+
+class DirectoryTree(Tree):
+    """
+    A custom Tree representing our filesystem structure.
+    This implementation is rather inefficient: basically every position-lookup
+    will call `os.listdir`.. This makes navigation in the tree quite slow.
+    In real life you'd want to do some caching.
+
+    As positions we use absolute path strings.
+    """
+    # determine dir separator and form of root node
+    pathsep = os.path.sep
+    drive, _ = os.path.splitdrive(pathsep)
+
+    # define root node This is part of the Tree API!
+    root = drive + pathsep
+
+    def __getitem__(self, pos):
+        return FocusableText(pos)
+
+    # generic helper
+    def _list_dir(self, path):
+        """returns absolute paths for all entries in a directory"""
+        try:
+            elements = [os.path.join(
+                path, x) for x in os.listdir(path) if os.path.isdir(path)]
+            elements.sort()
+        except OSError:
+            elements = None
+        return elements
+
+    def _get_siblings(self, pos):
+        """lists the parent directory of pos """
+        parent = self.parent_position(pos)
+        siblings = [pos]
+        if parent is not None:
+            siblings = self._list_dir(parent)
+        return siblings
+
+    # Tree API
+    def parent_position(self, pos):
+        parent = None
+        if pos != '/':
+            parent = os.path.split(pos)[0]
+        return parent
+
+    def first_child_position(self, pos):
+        candidate = None
+        if os.path.isdir(pos):
+            children = self._list_dir(pos)
+            if children:
+                candidate = children[0]
+        return candidate
+
+    def last_child_position(self, pos):
+        candidate = None
+        if os.path.isdir(pos):
+            children = self._list_dir(pos)
+            if children:
+                candidate = children[-1]
+        return candidate
+
+    def next_sibling_position(self, pos):
+        candidate = None
+        siblings = self._get_siblings(pos)
+        myindex = siblings.index(pos)
+        if myindex + 1 < len(siblings):  # pos is not the last entry
+            candidate = siblings[myindex + 1]
+        return candidate
+
+    def prev_sibling_position(self, pos):
+        candidate = None
+        siblings = self._get_siblings(pos)
+        myindex = siblings.index(pos)
+        if myindex > 0:  # pos is not the first entry
+            candidate = siblings[myindex - 1]
+        return candidate
+
+if __name__ == "__main__":
+    cwd = os.getcwd()  # get current working directory
+    dtree = DirectoryTree()  # get a directory walker
+
+    # Use CollapsibleArrowTree for decoration.
+    # define initial collapse:
+    as_deep_as_cwd = lambda pos: dtree.depth(pos) >= dtree.depth(cwd)
+
+    # We hide the usual arrow tip and use a customized collapse-icon.
+    decorated_tree = CollapsibleArrowTree(dtree,
+                                          is_collapsed=as_deep_as_cwd,
+                                          arrow_tip_char=None,
+                                          icon_frame_left_char=None,
+                                          icon_frame_right_char=None,
+                                          icon_collapsed_char=u'\u25B6',
+                                          icon_expanded_char=u'\u25B7',)
+
+    # stick it into a TreeBox and use 'body' color attribute for gaps
+    tb = TreeBox(decorated_tree, focus=cwd)
+    root_widget = urwid.AttrMap(tb, 'body')
+    urwid.MainLoop(root_widget, palette).run()  # go
diff --git a/alot/foreign/urwidtrees/example5.nested.py b/alot/foreign/urwidtrees/example5.nested.py
new file mode 100755
index 00000000..d6c07659
--- /dev/null
+++ b/alot/foreign/urwidtrees/example5.nested.py
@@ -0,0 +1,82 @@
+#!/usr/bin/python
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+from example1 import palette, construct_example_tree  # example data
+from example1 import FocusableText  # Selectable Text used for nodes
+from widgets import TreeBox
+from tree import SimpleTree
+from nested import NestedTree
+from decoration import ArrowTree, CollapsibleArrowTree  # decoration
+import urwid
+import logging
+
+
+if __name__ == "__main__":
+    #logging.basicConfig(filename='example.log',level=logging.DEBUG)
+    # Take some Arrow decorated Tree that we later stick inside another tree.
+    innertree = ArrowTree(construct_example_tree())
+    # Some collapsible, arrow decorated tree with extra indent
+    anotherinnertree = CollapsibleArrowTree(construct_example_tree(),
+                                            indent=10)
+
+    # A SimpleTree, that contains the two above
+    middletree = SimpleTree(
+        [
+            (FocusableText('Middle ROOT'),
+             [
+                 (FocusableText('Mid Child One'), None),
+                 (FocusableText('Mid Child Two'), None),
+                 (innertree, None),
+                 (FocusableText('Mid Child Three'),
+                  [
+                      (FocusableText('Mid Grandchild One'), None),
+                      (FocusableText('Mid Grandchild Two'), None),
+                  ]
+                  ),
+                 (anotherinnertree,
+                  # middletree defines a childnode here. This is usually
+                  # covered by the tree 'anotherinnertree', unless the
+                  # interepreting NestedTree's constructor gets parameter
+                  # interpret_covered=True..
+                  [
+                      (FocusableText('XXX I\'m invisible!'), None),
+
+                  ]),
+             ]
+             )
+        ]
+    )  # end SimpleTree constructor for middletree
+    # use customized arrow decoration for middle tree
+    middletree = ArrowTree(middletree,
+                           arrow_hbar_char=u'\u2550',
+                           arrow_vbar_char=u'\u2551',
+                           arrow_tip_char=u'\u25B7',
+                           arrow_connector_tchar=u'\u2560',
+                           arrow_connector_lchar=u'\u255A')
+
+    # define outmost tree
+    outertree = SimpleTree(
+        [
+            (FocusableText('Outer ROOT'),
+             [
+                 (FocusableText('Child One'), None),
+                 (middletree, None),
+                 (FocusableText('last outer child'), None),
+             ]
+             )
+        ]
+    )  # end SimpleTree constructor
+
+    # add some Arrow decoration
+    outertree = ArrowTree(outertree)
+    # wrap the whole thing into a Nested Tree
+    outertree = NestedTree(outertree,
+                           # show covered nodes like  XXX
+                           interpret_covered=False
+                           )
+
+    # put it into a treebox and run
+    treebox = TreeBox(outertree)
+    rootwidget = urwid.AttrMap(treebox, 'body')
+    urwid.MainLoop(rootwidget, palette).run()  # go
diff --git a/alot/foreign/urwidtrees/lru_cache.py b/alot/foreign/urwidtrees/lru_cache.py
new file mode 100644
index 00000000..1d87a485
--- /dev/null
+++ b/alot/foreign/urwidtrees/lru_cache.py
@@ -0,0 +1,141 @@
+# This is a backport of functools.lru_cache, which is part of the stdlib =>v3.3.
+# http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/
+
+from collections import namedtuple
+from functools import update_wrapper
+from threading import Lock
+
+_CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])
+
+def lru_cache(maxsize=100, typed=False):
+    """Least-recently-used cache decorator.
+
+    If *maxsize* is set to None, the LRU features are disabled and the cache
+    can grow without bound.
+
+    If *typed* is True, arguments of different types will be cached separately.
+    For example, f(3.0) and f(3) will be treated as distinct calls with
+    distinct results.
+
+    Arguments to the cached function must be hashable.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.cache_info().  Clear the cache and statistics with f.cache_clear().
+    Access the underlying function with f.__wrapped__.
+
+    See:  http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
+
+    """
+
+    # Users should only access the lru_cache through its public API:
+    #       cache_info, cache_clear, and f.__wrapped__
+    # The internals of the lru_cache are encapsulated for thread safety and
+    # to allow the implementation to change (including a possible C version).
+
+    def decorating_function(user_function):
+
+        cache = dict()
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+        kwd_mark = (object(),)          # separate positional and keyword args
+        cache_get = cache.get           # bound method to lookup key or return None
+        _len = len                      # localize the global len() function
+        lock = Lock()                   # because linkedlist updates aren't threadsafe
+        root = []                       # root of the circular doubly linked list
+        nonlocal_root = [root]                  # make updateable non-locally
+        root[:] = [root, root, None, None]      # initialize by pointing to self
+        PREV, NEXT, KEY, RESULT = 0, 1, 2, 3    # names for the link fields
+
+        def make_key(args, kwds, typed, tuple=tuple, sorted=sorted, type=type):
+            # helper function to build a cache key from positional and keyword args
+            key = args
+            if kwds:
+                sorted_items = tuple(sorted(kwds.items()))
+                key += kwd_mark + sorted_items
+            if typed:
+                key += tuple(type(v) for v in args)
+                if kwds:
+                    key += tuple(type(v) for k, v in sorted_items)
+            return key
+
+        if maxsize == 0:
+
+            def wrapper(*args, **kwds):
+                # no caching, just do a statistics update after a successful call
+                result = user_function(*args, **kwds)
+                stats[MISSES] += 1
+                return result
+
+        elif maxsize is None:
+
+            def wrapper(*args, **kwds):
+                # simple caching without ordering or size limit
+                key = make_key(args, kwds, typed) if kwds or typed else args
+                result = cache_get(key, root)   # root used here as a unique not-found sentinel
+                if result is not root:
+                    stats[HITS] += 1
+                    return result
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                stats[MISSES] += 1
+                return result
+
+        else:
+
+            def wrapper(*args, **kwds):
+                # size limited caching that tracks accesses by recency
+                key = make_key(args, kwds, typed) if kwds or typed else args
+                with lock:
+                    link = cache_get(key)
+                    if link is not None:
+                        # record recent use of the key by moving it to the front of the list
+                        root, = nonlocal_root
+                        link_prev, link_next, key, result = link
+                        link_prev[NEXT] = link_next
+                        link_next[PREV] = link_prev
+                        last = root[PREV]
+                        last[NEXT] = root[PREV] = link
+                        link[PREV] = last
+                        link[NEXT] = root
+                        stats[HITS] += 1
+                        return result
+                result = user_function(*args, **kwds)
+                with lock:
+                    root = nonlocal_root[0]
+                    if _len(cache) < maxsize:
+                        # put result in a new link at the front of the list
+                        last = root[PREV]
+                        link = [last, root, key, result]
+                        cache[key] = last[NEXT] = root[PREV] = link
+                    else:
+                        # use root to store the new key and result
+                        root[KEY] = key
+                        root[RESULT] = result
+                        cache[key] = root
+                        # empty the oldest link and make it the new root
+                        root = nonlocal_root[0] = root[NEXT]
+                        del cache[root[KEY]]
+                        root[KEY] = None
+                        root[RESULT] = None
+                    stats[MISSES] += 1
+                return result
+
+        def cache_info():
+            """Report cache statistics"""
+            with lock:
+                return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        def cache_clear():
+            """Clear the cache and cache statistics"""
+            with lock:
+                cache.clear()
+                root = nonlocal_root[0]
+                root[:] = [root, root, None, None]
+                stats[:] = [0, 0]
+
+        wrapper.__wrapped__ = user_function
+        wrapper.cache_info = cache_info
+        wrapper.cache_clear = cache_clear
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
diff --git a/alot/foreign/urwidtrees/nested.py b/alot/foreign/urwidtrees/nested.py
new file mode 100644
index 00000000..3c7035b3
--- /dev/null
+++ b/alot/foreign/urwidtrees/nested.py
@@ -0,0 +1,358 @@
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+from tree import Tree
+from decoration import DecoratedTree, CollapseMixin
+
+
+class NestedTree(Tree):
+    """
+    A Tree that wraps around Trees that may contain list walkers or other
+    trees.  The wrapped tree may contain normal widgets as well. List walkers
+    and subtree contents will be expanded into the tree presented by this
+    wrapper.
+
+    This wrapper's positions are tuples of positions of the original and
+    subtrees: For example, `(X,Y,Z)` points at position Z in tree/list at
+    position Y in tree/list at position X in the original tree.
+
+    NestedTree transparently behaves like a collapsible DecoratedTree.
+    """
+    @property
+    def root(self):
+        root = (self._tree.root,)
+        rcontent = self._tree[self._tree.root]
+        if isinstance(rcontent, Tree):
+            root = root + (rcontent.root,)
+        return root
+
+    def _sanitize_position(self, pos, tree=None):
+        """
+        Ensure a position tuple until the result does not
+        point to a :class:`Tree` any more.
+        """
+        if pos is not None:
+            tree = tree or self._tree
+            entry = self._lookup_entry(tree, pos)
+            if isinstance(entry, Tree):
+                pos = pos + self._sanitize_position((entry.root,), tree=entry)
+        return pos
+
+    def __init__(self, tree, interpret_covered=False):
+        self._tree = tree
+        self._interpret_covered = interpret_covered
+
+    def _lookup_entry(self, tree, pos):
+        if len(pos) == 0:
+            entry = tree[tree.root]
+        else:
+            entry = tree[pos[0]]
+            if len(pos) > 1 and isinstance(entry, Tree):
+                subtree = entry
+                entry = self._lookup_entry(subtree, pos[1:])
+        return entry
+
+    def _depth(self, tree, pos, outmost_only=True):
+        depth = self._tree.depth(pos[1:])
+        if not outmost_only:
+            entry = self._tree[pos[0]]
+            if isinstance(entry, Tree) and len(pos) > 1:
+                depth += self._depth(entry, pos[1:], outmost_only=False)
+        return depth
+
+    def depth(self, pos, outmost=True):
+        return self._depth(self._tree, pos)
+
+    def __getitem__(self, pos):
+        return self._lookup_entry(self._tree, pos)
+
+    # DecoratedTree API
+    def _get_decorated_entry(self, tree, pos, widget=None, is_first=True):
+        entry = tree[pos[0]]
+        if len(pos) > 1 and isinstance(entry, Tree):
+            subtree = entry
+            entry = self._get_decorated_entry(
+                subtree, pos[1:], widget, is_first)
+        else:
+            entry = widget or entry
+        if isinstance(tree, (DecoratedTree, NestedTree)):  # has decorate-API
+            isf = len(pos) < 2
+            if not isf and isinstance(tree[pos[0]], Tree):
+                isf = (tree[pos[0]].parent_position(pos[1])
+                       is None) or not is_first
+            entry = tree.decorate(pos[0], entry, is_first=isf)
+        return entry
+
+    def get_decorated(self, pos):
+        return self._get_decorated_entry(self._tree, pos)
+
+    def decorate(self, pos, widget, is_first=True):
+        return self._get_decorated_entry(self._tree, pos, widget, is_first)
+
+    # Collapse API
+    def _get_subtree_for(self, pos):
+        """returns Tree that manages pos[-1]"""
+        res = self._tree
+        candidate = self._lookup_entry(self._tree, pos[:-1])
+        if isinstance(candidate, Tree):
+            res = candidate
+        return res
+
+    def collapsible(self, pos):
+        res = False
+        subtree = self._get_subtree_for(pos)
+        if isinstance(subtree, (CollapseMixin, NestedTree)):
+            res = subtree.collapsible(pos[-1])
+        return res
+
+    def is_collapsed(self, pos):
+        res = False
+        subtree = self._get_subtree_for(pos)
+        if isinstance(subtree, (CollapseMixin, NestedTree)):
+            res = subtree.is_collapsed(pos[-1])
+        return res
+
+    def toggle_collapsed(self, pos):
+        subtree = self._get_subtree_for(pos)
+        if isinstance(subtree, (CollapseMixin, NestedTree)):
+            subtree.toggle_collapsed(pos)
+
+    def collapse(self, pos):
+        subtree = self._get_subtree_for(pos)
+        if isinstance(subtree, (CollapseMixin, NestedTree)):
+            subtree.collapse(pos[-1])
+
+    def collapse_all(self):
+        self._collapse_all(self._tree, self.root)
+
+    def _collapse_all(self, tree, pos=None):
+        if pos is not None:
+            if isinstance(tree, (CollapseMixin, NestedTree)):
+                tree.expand_all()
+
+            if len(pos) > 1:
+                self._collapse_all(tree[pos[0]], pos[1:])
+            nextpos = tree.next_position(pos[0])
+            if nextpos is not None:
+                nentry = tree[nextpos]
+                if isinstance(nentry, Tree):
+                    self._collapse_all(nentry, (nentry.root,))
+                self._collapse_all(tree, (nextpos,))
+            if isinstance(tree, (CollapseMixin, NestedTree)):
+                tree.collapse_all()
+
+    def expand(self, pos):
+        subtree = self._get_subtree_for(pos)
+        if isinstance(subtree, (CollapseMixin, NestedTree)):
+            subtree.expand(pos[-1])
+
+    def expand_all(self):
+        self._expand_all(self._tree, self.root)
+
+    def _expand_all(self, tree, pos=None):
+        if pos is not None:
+            if isinstance(tree, (CollapseMixin, NestedTree)):
+                tree.expand_all()
+            if len(pos) > 1:
+                self._expand_all(tree[pos[0]], pos[1:])
+            nextpos = tree.next_position(pos[0])
+            if nextpos is not None:
+                nentry = tree[nextpos]
+                if isinstance(nentry, Tree):
+                    self._expand_all(nentry, (nentry.root,))
+                self._expand_all(tree, (nextpos,))
+            if isinstance(tree, (CollapseMixin, NestedTree)):
+                tree.expand_all()
+
+    def is_leaf(self, pos, outmost_only=False):
+        return self.first_child_position(pos, outmost_only) is None
+
+    ################################################
+    # Tree API
+    ################################################
+    def parent_position(self, pos):
+        candidate_pos = self._parent_position(self._tree, pos)
+        # return sanitized path (ensure it points to content, not a subtree)
+        return self._sanitize_position(candidate_pos)
+
+    def _parent_position(self, tree, pos):
+        candidate_pos = None
+        if len(pos) > 1:
+            # get the deepest subtree
+            subtree_pos = pos[:-1]
+            subtree = self._lookup_entry(tree, subtree_pos)
+            # get parent for our position in this subtree
+            least_pos = pos[-1]
+            subparent_pos = subtree.parent_position(least_pos)
+            if subparent_pos is not None:
+                # in case there is one, we are done, the position we look for
+                # is the path up to the subtree plus the local parent position.
+                candidate_pos = subtree_pos + (subparent_pos,)
+            else:
+                # otherwise we recur and look for subtree's parent in the next
+                # outer tree
+                candidate_pos = self._parent_position(self._tree, subtree_pos)
+        else:
+            # there is only one position in the path, we return its parent in
+            # the outmost tree
+            outer_parent = self._tree.parent_position(pos[0])
+            if outer_parent is not None:
+                # result needs to be valid position (tuple of local positions)
+                candidate_pos = outer_parent,
+        return candidate_pos
+
+    def first_child_position(self, pos, outmost_only=False):
+        childpos = self._first_child_position(self._tree, pos, outmost_only)
+        return self._sanitize_position(childpos, self._tree)
+
+    def _first_child_position(self, tree, pos, outmost_only=False):
+        childpos = None
+        # get content at first path element in outmost tree
+        entry = tree[pos[0]]
+        if isinstance(entry, Tree) and not outmost_only and len(pos) > 1:
+            # this points to a tree and we don't check the outmost tree only
+            # recur: get first child in the subtree for remaining path
+            subchild = self._first_child_position(entry, pos[1:])
+            if subchild is not None:
+                # found a childposition, re-append the path up to this subtree
+                childpos = (pos[0],) + subchild
+                return childpos
+            else:
+                # continue in the next outer tree only if we do not drop
+                # "covered" parts and the position path points to a parent-less
+                # position in the subtree.
+                if (entry.parent_position(pos[1]) is not None or not
+                        self._interpret_covered):
+                    return None
+
+        # return the first child of the outmost tree
+        outerchild = tree.first_child_position(pos[0])
+        if outerchild is not None:
+            childpos = outerchild,
+        return childpos
+
+    def last_child_position(self, pos, outmost_only=False):
+        childpos = self._last_child_position(self._tree, pos, outmost_only)
+        return self._sanitize_position(childpos, self._tree)
+
+    def _last_child_position(self, tree, pos, outmost_only=False):
+        childpos = None
+        # get content at first path element in outmost tree
+        entry = tree[pos[0]]
+        if isinstance(entry, Tree) and not outmost_only and len(pos) > 1:
+            # this points to a tree and we don't check the outmost tree only
+
+            # get last child in the outmost tree if we do not drop "covered"
+            # parts and the position path points to a root of the subtree.
+            if self._interpret_covered:
+                if entry.parent_position(pos[1]) is None:
+                    # return the last child of the outmost tree
+                    outerchild = tree.last_child_position(pos[0])
+                    if outerchild is not None:
+                        childpos = outerchild,
+
+            # continue as if we have not found anything yet
+            if childpos is None:
+                # recur: get last child in the subtree for remaining path
+                subchild = self._last_child_position(entry, pos[1:])
+                if subchild is not None:
+                    # found a childposition, re-prepend path up to this subtree
+                    childpos = (pos[0],) + subchild
+        else:
+            # outmost position element does not point to a tree:
+            # return the last child of the outmost tree
+            outerchild = tree.last_child_position(pos[0])
+            if outerchild is not None:
+                childpos = outerchild,
+        return childpos
+
+    def _next_sibling_position(self, tree, pos):
+        candidate = None
+        if len(pos) > 1:
+            # if position path does not point to position in outmost tree,
+            # first get the subtree as pointed out by first dimension, recur
+            # and check if some inner tree already returns a sibling
+            subtree = tree[pos[0]]
+            subsibling_pos = self._next_sibling_position(subtree, pos[1:])
+            if subsibling_pos is not None:
+                # we found our sibling, prepend the path up to the subtree
+                candidate = pos[:1] + subsibling_pos
+            else:
+                # no deeper tree has sibling. If inner position is root node
+                # the sibling in the outer tree is a valid candidate
+                subparent = subtree.parent_position(pos[1])
+                if subparent is None:
+                    # check if outer tree defines sibling
+                    next_sib = tree.next_sibling_position(pos[0])
+                    if next_sib is not None:
+                        # it has, we found our candidate
+                        candidate = next_sib,
+                # if the inner position has depth 1, then the first child
+                # of its parent in the outer tree can be seen as candidate for
+                # this position next sibling. Those live in the shadow of the
+                # inner tree and are hidden unless requested otherwise
+                elif subtree.parent_position(subparent) is None and \
+                        self._interpret_covered:
+                    # we respect "covered" stuff and inner position has depth 1
+                    # get (possibly nested) first child in outer tree
+                    candidate = self._first_child_position(tree, pos[:1])
+
+        else:
+            # the position path points to the outmost tree
+            # just return its next sibling in the outmost tree
+            next_sib = tree.next_sibling_position(pos[0])
+            if next_sib is not None:
+                candidate = next_sib,
+        return candidate
+
+    def next_sibling_position(self, pos):
+        candidate = self._next_sibling_position(self._tree, pos)
+        return self._sanitize_position(candidate, self._tree)
+
+    def _prev_sibling_position(self, tree, pos):
+        candidate = None
+        if len(pos) > 1:
+            # if position path does not point to position in outmost tree,
+            # first get the subtree as pointed out by first dimension, recur
+            # and check if some inner tree already returns a sibling
+            subtree = tree[pos[0]]
+            subsibling_pos = self._prev_sibling_position(subtree, pos[1:])
+            if subsibling_pos is not None:
+                # we found our sibling, prepend the path up to the subtree
+                candidate = pos[:1] + subsibling_pos
+            else:
+                # no deeper tree has sibling. If inner position is root node
+                # the sibling in the outer tree is a valid candidate
+                subparent = subtree.parent_position(pos[1])
+                if subparent is None:
+                    prev_sib = tree.prev_sibling_position(pos[0])
+                    if prev_sib is not None:
+                        candidate = prev_sib,
+                        return candidate
+            # my position could be "hidden" by being child of a
+            # position pointing to a Tree object (which is then unfolded).
+            if self._interpret_covered:
+                # we respect "covered" stuff:
+                # if parent is Tree, return last child of its (last) root
+                parent_pos = self._parent_position(tree, pos)
+                if parent_pos is not None:
+                    parent = self._lookup_entry(self._tree, parent_pos)
+                    if isinstance(parent, Tree):
+                        sib = parent.last_sibling_position(parent.root)
+                        candidate = parent.last_child_position(sib)
+                        if candidate is not None:
+                            candidate = parent_pos + (candidate,)
+        else:
+            # pos points to position in outmost tree
+            prev_sib = tree.prev_sibling_position(pos[0])
+            if prev_sib is not None:
+                candidate = prev_sib,
+        # In case our new candidate points to a Tree, pick its last root node
+        if candidate is not None:
+            entry = self._lookup_entry(tree, candidate)
+            if isinstance(entry, Tree):
+                candidate = (candidate) + (entry.last_sibling_position(entry.root),)
+        return candidate
+
+    def prev_sibling_position(self, pos):
+        candidate = self._prev_sibling_position(self._tree, pos)
+        return self._sanitize_position(candidate, self._tree)
diff --git a/alot/foreign/urwidtrees/tree.py b/alot/foreign/urwidtrees/tree.py
new file mode 100644
index 00000000..0058c177
--- /dev/null
+++ b/alot/foreign/urwidtrees/tree.py
@@ -0,0 +1,252 @@
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+import logging
+
+
+class Tree(object):
+    """
+    Base class for a tree strucures that can be displayed by :class:`TreeBox`
+    widgets. An instance defines a structure by defining local transformations
+    on positions. That is, by overwriting
+
+     * `next_sibling_position`
+     * `prev_sibling_position`
+     * `parent_position`
+     * `first_child_position`
+     * `last_child_position`
+
+    that compute the next position in the respective direction. Also, they need
+    to implement method `__getitem__` that returns a :class:`Widget` for a
+    given position.
+
+    The type of objects used as positions may vary in subclasses and is
+    deliberately unspecified for the base class.
+
+    This base class already implements methods based on the local
+    transformations above. These include :meth:`depth`, :meth:`last_decendant`
+    and :meth:`[next|prev]_position <next_position>` that computes
+    next/previous positions in depth-first order.
+    """
+    root = None
+
+    # local helper
+    def _get(self, pos):
+        """loads widget at given position; handling invalid arguments"""
+        res = None, None
+        if pos is not None:
+            try:
+                res = self[pos], pos
+            except (IndexError, KeyError):
+                pass
+        return res
+
+    def _next_of_kin(self, pos):
+        """
+        looks up the next sibling of the closest ancestor with not-None next
+        siblings.
+        """
+        candidate = None
+        parent = self.parent_position(pos)
+        if parent is not None:
+            candidate = self.next_sibling_position(parent)
+            if candidate is None:
+                candidate = self._next_of_kin(parent)
+        return candidate
+
+    def _last_in_direction(self, starting_pos, direction):
+        """
+        recursively move in the tree in given direction
+        and return the last position.
+
+        :param starting_pos: position to start at
+        :param direction: callable that transforms a position into a position.
+        """
+        next_pos = direction(starting_pos)
+        if next_pos is None:
+            return starting_pos
+        else:
+            return self._last_in_direction(next_pos, direction)
+
+    def depth(self, pos):
+        """determine depth of node at pos"""
+        parent = self.parent_position(pos)
+        if parent is None:
+            return 0
+        else:
+            return self.depth(parent) + 1
+
+    def is_leaf(self, pos):
+        """checks if given position has no children"""
+        return self.first_child_position(pos) is None
+
+    def first_ancestor(self, pos):
+        """
+        position of pos's ancestor with depth 0. Usually, this should return
+        the root node, but a :class:`Tree` might represent a forrest - have
+        multiple nodes without parent.
+        """
+        return self._last_in_direction(pos, self.parent_position)
+
+    def last_decendant(self, pos):
+        """position of last (in DFO) decendant of pos"""
+        return self._last_in_direction(pos, self.last_child_position)
+
+    def last_sibling_position(self, pos):
+        """position of last sibling of pos"""
+        return self._last_in_direction(pos, self.next_sibling_position)
+
+    def first_sibling_position(self, pos):
+        """position of first sibling of pos"""
+        return self._last_in_direction(pos, self.prev_sibling_position)
+
+    def next_position(self, pos):
+        """returns the next position in depth-first order"""
+        candidate = None
+        if pos is not None:
+            candidate = self.first_child_position(pos)
+            if candidate is None:
+                candidate = self.next_sibling_position(pos)
+                if candidate is None:
+                    candidate = self._next_of_kin(pos)
+        return candidate
+
+    def prev_position(self, pos):
+        """returns the previous position in depth-first order"""
+        candidate = None
+        if pos is not None:
+            prevsib = self.prev_sibling_position(pos)  # is None if first
+            if prevsib is not None:
+                candidate = self.last_decendant(prevsib)
+            else:
+                parent = self.parent_position(pos)
+                if parent is not None:
+                    candidate = parent
+        return candidate
+
+    def positions(self, reverse=False):
+        """returns a generator that walks the positions of this tree in DFO"""
+        def Posgen(reverse):
+            if reverse:
+                lastrootsib = self.last_sibling_position(self.root)
+                current = self.last_decendant(lastrootsib)
+                while current is not None:
+                    yield current
+                    current = self.prev_position(current)
+            else:
+                current = self.root
+                while current is not None:
+                    yield current
+                    current = self.next_position(current)
+        return Posgen(reverse)
+
+    ####################################################################
+    # End of high-level helper implementation. The following need to be
+    # overwritten by subclasses
+    ####################################################################
+    def parent_position(self, pos):
+        """returns the position of the parent node of the node at `pos`
+        or `None` if none exists."""
+        return None
+
+    def first_child_position(self, pos):
+        """returns the position of the first child of the node at `pos`,
+        or `None` if none exists."""
+        return None
+
+    def last_child_position(self, pos):
+        """returns the position of the last child of the node at `pos`,
+        or `None` if none exists."""
+        return None
+
+    def next_sibling_position(self, pos):
+        """returns the position of the next sibling of the node at `pos`,
+        or `None` if none exists."""
+        return None
+
+    def prev_sibling_position(self, pos):
+        """returns the position of the previous sibling of the node at `pos`,
+        or `None` if none exists."""
+        return None
+
+
+class SimpleTree(Tree):
+    """
+    Walks on a given fixed acyclic structure given as a list of nodes; every
+    node is a tuple `(content, children)`, where `content` is a `urwid.Widget`
+    to be displayed at that position and `children` is either `None` or a list
+    of nodes.
+
+    Positions are lists of integers determining a path from the root node with
+    position `(0,)`.
+    """
+    def __init__(self, treelist):
+        self._treelist = treelist
+        self.root = (0,) if treelist else None
+        Tree.__init__(self)
+
+    # a few local helper methods
+    def _get_substructure(self, treelist, pos):
+        """recursive helper to look up node-tuple for `pos` in `treelist`"""
+        subtree = None
+        if len(pos) > 1:
+            subtree = self._get_substructure(treelist[pos[0]][1], pos[1:])
+        else:
+            try:
+                subtree = treelist[pos[0]]
+            except (IndexError, TypeError):
+                pass
+        return subtree
+
+    def _get_node(self, treelist, pos):
+        """
+        look up widget at `pos` of `treelist`; default to None if
+        nonexistent.
+        """
+        node = None
+        if pos is not None:
+            subtree = self._get_substructure(treelist, pos)
+            if subtree is not None:
+                node = subtree[0]
+        return node
+
+    def _confirm_pos(self, pos):
+        """look up widget for pos and default to None"""
+        candidate = None
+        if self._get_node(self._treelist, pos) is not None:
+            candidate = pos
+        return candidate
+
+    # Tree API
+    def __getitem__(self, pos):
+        return self._get_node(self._treelist, pos)
+
+    def parent_position(self, pos):
+        parent = None
+        if pos is not None:
+            if len(pos) > 1:
+                parent = pos[:-1]
+        return parent
+
+    def first_child_position(self, pos):
+        return self._confirm_pos(pos + (0,))
+
+    def last_child_position(self, pos):
+        candidate = None
+        subtree = self._get_substructure(self._treelist, pos)
+        if subtree is not None:
+            children = subtree[1]
+            if children is not None:
+                candidate = pos + (len(children) - 1,)
+        return candidate
+
+    def next_sibling_position(self, pos):
+        return self._confirm_pos(pos[:-1] + (pos[-1] + 1,))
+
+    def prev_sibling_position(self, pos):
+        return pos[:-1] + (pos[-1] - 1,) if (pos[-1] > 0) else None
+
+    # optimizations
+    def depth(self, pos):
+        """more performant implementation due to specific structure of pos"""
+        return len(pos) - 1
diff --git a/alot/foreign/urwidtrees/widgets.py b/alot/foreign/urwidtrees/widgets.py
new file mode 100644
index 00000000..7a9d96e0
--- /dev/null
+++ b/alot/foreign/urwidtrees/widgets.py
@@ -0,0 +1,243 @@
+# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
+# This file is released under the GNU GPL, version 3 or a later revision.
+
+import urwid
+import logging
+from urwid import WidgetWrap, ListBox
+from urwid import signals
+from decoration import DecoratedTree, CollapseMixin
+from nested import NestedTree
+from lru_cache import lru_cache
+
+# The following are used to check dynamically if a tree offers sub-APIs
+
+
+def implementsDecorateAPI(tree):
+    """determines if given tree offers line decoration"""
+    return isinstance(tree, (DecoratedTree, NestedTree))
+
+
+def implementsCollapseAPI(tree):
+    """determines if given tree can collapse positions"""
+    res = False
+    if isinstance(tree, (CollapseMixin, NestedTree)):
+        res = True
+    return res
+
+
+class TreeListWalker(urwid.ListWalker):
+    """
+    ListWalker to walk through a class:`Tree`.
+
+    This translates a :class:`Tree` into a :class:`urwid.ListWalker` that is
+    digestible by :class:`urwid.ListBox`.
+    It uses :meth:`Tree.[next|prev]_position <Tree.next_position>` to determine
+    the next/previous position in depth first order.
+    """
+    def __init__(self, tree, focus=None):
+        """
+        :param tree: the tree to be displayed
+        :type tree: Tree
+        :param focus: position of node to be focussed initially.
+            This has to be a valid position in the Tree.
+            It defaults to the value of `Tree.root`.
+        """
+        self._tree = tree
+        self._focus = focus or tree.root
+        self.root = tree.root
+
+    @lru_cache()
+    def __getitem__(self, pos):
+        """gets (possibly decorated) line widget at given position"""
+        if implementsDecorateAPI(self._tree):
+            entry = self._tree.get_decorated(pos)
+        else:
+            entry = self._tree[pos]
+        return entry
+
+    def clear_cache(self):
+        """removes all cached lines"""
+        self.__getitem__.cache_clear()
+
+    def _get(self, pos):
+        """looks up widget for given position; handling invalid arguments"""
+        res = None, None
+        if pos is not None:
+            try:
+                res = self[pos], pos
+            except (IndexError, KeyError):
+                pass
+        return res
+
+    # List Walker API.
+    def get_focus(self):
+        return self._get(self._focus)
+
+    def set_focus(self, pos):
+        self._focus = pos
+
+    def get_next(self, pos):
+        return self._get(self._tree.next_position(pos))
+
+    def get_prev(self, pos):
+        return self._get(self._tree.prev_position(pos))
+
+    def positions(self, reverse=False):
+        """returns a generator that walks the tree's positions"""
+        return self._tree.positions(reverse)
+    # end of List Walker API
+
+
+class TreeBox(WidgetWrap):
+    """
+    A widget that displays a given :class:`Tree`.
+    This is essentially a :class:`ListBox` with the ability to move the focus
+    based on directions in the Tree and to collapse/expand subtrees if
+    possible.
+
+    TreeBox interprets `left/right` as well as `page up/`page down` to move the
+    focus to parent/first child and next/previous sibling respectively. All
+    other keys are passed to the underlying ListBox.
+    """
+
+    def __init__(self, tree, focus=None):
+        """
+        :param tree: tree of widgets to be displayed.
+        :type tree: Tree
+        :param focus: initially focussed position
+        """
+        self._tree = tree
+        self._walker = TreeListWalker(tree)
+        self._outer_list = ListBox(self._walker)
+        if focus is not None:
+            self._outer_list.set_focus(focus)
+        self.__super.__init__(self._outer_list)
+
+    # Widget API
+    def get_focus(self):
+        return self._outer_list.get_focus()
+
+    def set_focus(self, pos):
+        return self._outer_list.set_focus(pos)
+
+    def refresh(self):
+        self._walker.clear_cache()
+        signals.emit_signal(self._walker, "modified")
+
+    def keypress(self, size, key):
+        key = self._outer_list.keypress(size, key)
+        if key in ['left', 'right', '[', ']', '-', '+', 'C', 'E', ]:
+            if key == 'left':
+                self.focus_parent()
+            elif key == 'right':
+                self.focus_first_child()
+            elif key == '[':
+                self.focus_prev_sibling()
+            elif key == ']':
+                self.focus_next_sibling()
+            elif key == '-':
+                self.collapse_focussed()
+            elif key == '+':
+                self.expand_focussed()
+            elif key == 'C':
+                self.collapse_all()
+            elif key == 'E':
+                self.expand_all()
+            # This is a hack around ListBox misbehaving:
+            # it seems impossible to set the focus without calling keypress as
+            # otherwise the change becomes visible only after the next render()
+            return self._outer_list.keypress(size, None)
+        else:
+            return self._outer_list.keypress(size, key)
+
+    # Collapse operations
+    def collapse_focussed(self):
+        """
+        Collapse currently focussed position; works only if the underlying
+        tree allows it.
+        """
+        if implementsCollapseAPI(self._tree):
+            w, focuspos = self.get_focus()
+            self._tree.collapse(focuspos)
+            self._walker.clear_cache()
+            self.refresh()
+
+    def expand_focussed(self):
+        """
+        Expand currently focussed position; works only if the underlying
+        tree allows it.
+        """
+        if implementsCollapseAPI(self._tree):
+            w, focuspos = self.get_focus()
+            self._tree.expand(focuspos)
+            self._walker.clear_cache()
+            self.refresh()
+
+    def collapse_all(self):
+        """
+        Collapse all positions; works only if the underlying tree allows it.
+        """
+        if implementsCollapseAPI(self._tree):
+            self._tree.collapse_all()
+            self.set_focus(self._tree.root)
+            self._walker.clear_cache()
+            self.refresh()
+
+    def expand_all(self):
+        """
+        Expand all positions; works only if the underlying tree allows it.
+        """
+        if implementsCollapseAPI(self._tree):
+            self._tree.expand_all()
+            self._walker.clear_cache()
+            self.refresh()
+
+    # Tree based focus movement
+    def focus_parent(self):
+        """move focus to parent node of currently focussed one"""
+        w, focuspos = self.get_focus()
+        parent = self._tree.parent_position(focuspos)
+        if parent is not None:
+            self.set_focus(parent)
+
+    def focus_first_child(self):
+        """move focus to first child of currently focussed one"""
+        w, focuspos = self.get_focus()
+        child = self._tree.first_child_position(focuspos)
+        if child is not None:
+            self.set_focus(child)
+
+    def focus_last_child(self):
+        """move focus to last child of currently focussed one"""
+        w, focuspos = self.get_focus()
+        child = self._tree.last_child_position(focuspos)
+        if child is not None:
+            self.set_focus(child)
+
+    def focus_next_sibling(self):
+        """move focus to next sibling of currently focussed one"""
+        w, focuspos = self.get_focus()
+        sib = self._tree.next_sibling_position(focuspos)
+        if sib is not None:
+            self.set_focus(sib)
+
+    def focus_prev_sibling(self):
+        """move focus to previous sibling of currently focussed one"""
+        w, focuspos = self.get_focus()
+        sib = self._tree.prev_sibling_position(focuspos)
+        if sib is not None:
+            self.set_focus(sib)
+
+    def focus_next(self):
+        """move focus to next position (DFO)"""
+        w, focuspos = self.get_focus()
+        next = self._tree.next_position(focuspos)
+        if next is not None:
+            self.set_focus(next)
+
+    def focus_prev(self):
+        """move focus to previous position (DFO)"""
+        w, focuspos = self.get_focus()
+        prev = self._tree.prev_position(focuspos)
+        if prev is not None:
+            self.set_focus(prev)