I work with my own geometry class, arcpy's geometry classes and more recently, I foolishly looked at geojson data structures. Nested objects are more common than you think, so I have time, so I messed around with recursive functions in python.
The get_keys function in my previous blog is a pure example of recursion, where the function calls itself.
Sometimes a recursive action can call a function nested within a main functions. Examples of both follow.
Let the nesting begin
Let's start with a simple example of a nested list which consists of nested lists, and simple lists of various sizes and depth.
Notes
-----
Array type and depth/size::
[] 1
[[]] 2, size 1
[[], []] 2, size 2
[[[]]] 3, size 1
[[[], []]] 3, size 2
Example
-------
>>> # input list nested_len
>>> lst = [ idx0, idx1, count
... [[1, 2, 3], [[0, 0, 3], two lists in list 0
... [4, 5]], [0, 1, 2],
... [[1, 2]], [1, 0, 2], one list in list 1
... [1, 2], [2, 0], [2, 1], no lists in list 2
... [[]], [3, 0, 0] one list in list 3
... [[1, 2, 3], [4, 0, 3], three lists in list 4
... [4, 5], [4, 1, 2],
... [6, 7, 8]], [4, 2, 3],
... [[[1, 2, 3], [5, 0, 2], two lists in list 5
... [4, 5]],
... [[6, 7, 8]]] [5, 1, 1]]
... ]
Hope the above is self-explanatory. Pay attention to the Notes section first, then try to follow the nested list object that contains other structures.
Ugly? Not really, I just pulled replaced real-world coordinate pairs with simple integers. to illustrate.
Here is a function that pulls out information from a nested iterable, in this example `target_cls` will use python list objects as the example
def nested_len(obj, out=[], target_cls=list):
"""Return the lengths of nested iterables.
Parameters
----------
obj : iterable
The iterable must be the same type as the `target_cls`.
out : list
The returned results in the form of a list of lists.
target_cls : class
A python, numpy class that is iterable.
"""
def _len(obj):
"""Object length."""
sub = len(obj) if isinstance(obj, target_cls) else 0
return sub
if not hasattr(obj, '__iter__'):
print("\nIterable required (e.g. list/tuple")
return None
#
for i, v0 in enumerate(obj):
num = _len(v0)
for j in range(0, num):
k = v0[j]
sub = [i, j]
if isinstance(k, target_cls):
s = _len(k)
sub.append(s)
out.append(sub)
return out
Running that function using the Example input list data results in
nl = nested_len(lst, out=[], target_cls=list)
nl
[[0, 0, 3],
[0, 1, 2],
[1, 0, 2],
[2, 0],
[2, 1],
[3, 0, 0],
[4, 0, 3],
[4, 1, 2],
[4, 2, 3],
[5, 0, 2],
[5, 1, 1]]
Which is the other half of the explanation section.
What if you just want to know how deep a nested structure is.
# -- input
lst
Out[113]:
[[[1, 2, 3], [4, 5]],
[[1, 2]],
[1, 2],
[[]],
[[1, 2, 3], [4, 5], [6, 7, 8]],
[[[1, 2, 3], [4, 5]], [[6, 7, 8]]]]
# -- the function
def depth(lst):
d = 0
for item in lst:
if isinstance(item, list):
d = max(depth(item), d)
return d + 1
# -- a call to it
depth(lst)
4
# -- four levels deep, max!!!
How about flattening a data structure and converting it to another one? In this case, recursively flatten `lst` to numpy arrays.
def flatten(arr, list_=None):
if list_ is None:
list_ = []
if isinstance(arr, list):
for i in arr:
if isinstance(i[0], list) and len(i) > 1:
flatten(i, list_)
else:
list_.append(np.array(i))
else:
list_.append(np.array(arr))
return list_
flatten(lst, list_=None)
[array([1, 2, 3]),
array([4, 5]),
array([[1, 2]]),
array([1, 2]),
array([], shape=(1, 0), dtype=float64),
array([1, 2, 3]),
array([4, 5]),
array([6, 7, 8]),
array([1, 2, 3]),
array([4, 5]),
array([[6, 7, 8]])]
Rather than grumbling about nested data structures, remember these few examples
