{"id":82,"date":"2009-01-30T23:02:57","date_gmt":"2009-01-31T06:02:57","guid":{"rendered":"http:\/\/www.connorgarvey.com\/blog\/?p=82"},"modified":"2010-02-12T09:23:32","modified_gmt":"2010-02-12T16:23:32","slug":"a-recursive-tostring-method-for-trees","status":"publish","type":"post","link":"https:\/\/connorgarvey.com\/blog\/?p=82","title":{"rendered":"A recursive toString method for trees"},"content":{"rendered":"

While working on a project that uses Hibernate, my team was getting a little frustrated while trying to interrogate a tree structure in our data model since all collections are mapped as java.util.HashSets.\u00a0 We wanted a simple function that could print the tree to the log, so I took a free hour and wrote this.\u00a0 It was a little more complicated than I anticipated because it had to handle situations like these.<\/p>\n

root\r\n   |\r\n   |- child\r\n   |\r\n   |- child\r\n\r\nroot\r\n   |\r\n   |- child\r\n      |\r\n      |- child<\/pre>\n
and the infamous (to me) …<\/p>\n
root\r\n   |\r\n   |- child\r\n   |   |\r\n   |   |- child\r\n   |       |\r\n   |       |- child\r\n   |\r\n   |- child<\/pre>\n
There’s a subtle difference.\u00a0 Notice that in the middle one, the line for the first child stops because there aren’t any more children, but in the last one, the line continues?\u00a0 I could have created some kind of 2D text buffer and gone back to draw the line, but that would be boring.\u00a0 Here’s what I came up with.  I don’t know whether it’s pretty, but it works!<\/p>\n
<\/a>Code block<\/a><\/td><\/a> <\/a> <\/a> <\/td><\/tr><\/table><\/div>
\/**\n * Creates a tree representation of the node\n * @param node The node, which may not be null\n * @return A string containing the formatted tree\n *\/<\/span>\npublic<\/span> static<\/span> String<\/span><\/a> toStringTree(<\/span>Node node)<\/span> {<\/span>\n  final<\/span> StringBuilder buffer =<\/span> new<\/span> StringBuilder(<\/span>)<\/span>;<\/span>\n  return<\/span> toStringTreeHelper(<\/span>node, buffer, new<\/span> LinkedList<<\/span>Iterator<<\/span>Node>><\/span>(<\/span>)<\/span>)<\/span>.toString<\/span>(<\/span>)<\/span>;<\/span>\n}<\/span>\n \nprivate<\/span> static<\/span> void<\/span> toStringTreeDrawLines(<\/span>List<<\/span>Iterator<<\/span>Node>><\/span> parentIterators, boolean<\/span> amLast)<\/span> {<\/span>\n  StringBuilder result =<\/span> new<\/span> StringBuilder(<\/span>)<\/span>;<\/span>\n  Iterator<<\/span>Iterator<<\/span>Node>><\/span> it =<\/span> parentIterators.iterator<\/span>(<\/span>)<\/span>;<\/span>\n  while<\/span> (<\/span>it.hasNext<\/span>(<\/span>)<\/span>)<\/span> {<\/span>\n    Iterator<<\/span>Node><\/span> anIt =<\/span> it.next<\/span>(<\/span>)<\/span>;<\/span>\n    if<\/span> (<\/span>anIt.hasNext<\/span>(<\/span>)<\/span> ||<\/span> (<\/span>!<\/span>it.hasNext<\/span>(<\/span>)<\/span> &&<\/span> amLast)<\/span>)<\/span> {<\/span>\n      result.append<\/span>(<\/span>"   |"<\/span>)<\/span>;<\/span>\n    }<\/span>\n    else<\/span> {<\/span>\n      result.append<\/span>(<\/span>"    "<\/span>)<\/span>;<\/span>\n    }<\/span>\n  }<\/span>\n  return<\/span> result.toString<\/span>(<\/span>)<\/span>;<\/span>\n}<\/span>\n \nprivate<\/span> static<\/span> StringBuilder toStringTreeHelper(<\/span>Node node, StringBuilder buffer, List<<\/span>Iterator<<\/span>Node>><\/span>\n    parentIterators)<\/span> {<\/span>\n  if<\/span> (<\/span>!<\/span>parentIterators.isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>\n    boolean<\/span> amLast =<\/span> !<\/span>parentIterators.get<\/span>(<\/span>parentIterators.size<\/span>(<\/span>)<\/span> -<\/span> 1)<\/span>.hasNext<\/span>(<\/span>)<\/span>;<\/span>\n    buffer.append<\/span>(<\/span>"\\n<\/span>"<\/span>)<\/span>;<\/span>\n    String<\/span><\/a> lines =<\/span> toStringTreeDrawLines(<\/span>parentIterators, amLast)<\/span>;<\/span>\n    buffer.append<\/span>(<\/span>lines)<\/span>;<\/span>\n    buffer.append<\/span>(<\/span>"\\n<\/span>"<\/span>)<\/span>;<\/span>\n    buffer.append<\/span>(<\/span>lines)<\/span>;<\/span>\n    buffer.append<\/span>(<\/span>"- "<\/span>)<\/span>;<\/span>\n  }<\/span>\n  buffer.append<\/span>(<\/span>node.toString<\/span>(<\/span>)<\/span>)<\/span>;<\/span>\n  if<\/span> (<\/span>node.hasChildren<\/span>(<\/span>)<\/span>)<\/span> {<\/span>\n    Iterator<<\/span>Node><\/span> it =<\/span> node.getChildNodes<\/span>(<\/span>)<\/span>.iterator<\/span>(<\/span>)<\/span>;<\/span>\n    parentIterators.add<\/span>(<\/span>it)<\/span>;<\/span>\n    while<\/span> (<\/span>it.hasNext<\/span>(<\/span>)<\/span>)<\/span> {<\/span>\n      Node child =<\/span> it.next<\/span>(<\/span>)<\/span>;<\/span>\n      toStringTreeHelper(<\/span>child, buffer, parentIterators)<\/span>;<\/span>\n    }<\/span>\n    parentIterators.remove<\/span>(<\/span>it)<\/span>;<\/span>\n  }<\/span>\n  return<\/span> buffer;<\/span>\n}<\/span><\/pre><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
While working on a project that uses Hibernate, my team was getting a little frustrated while trying to interrogate a tree structure in our data model since all collections are mapped as java.util.HashSets.\u00a0 We wanted a simple function that could print the tree to the log, so I took a free hour and wrote this.\u00a0 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false},"version":2}},"categories":[59],"tags":[4,22,7,21],"class_list":["post-82","post","type-post","status-publish","format-standard","hentry","category-java","tag-java","tag-recursive","tag-redpoint","tag-tree"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1ql2n-1k","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=82"}],"version-history":[{"count":13,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/82\/revisions"}],"predecessor-version":[{"id":84,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/82\/revisions\/84"}],"wp:attachment":[{"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/connorgarvey.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}