JuliaCollections / JuliaCollections/AbstractTrees.jl

Result of children required to be Indexable, not just Iterable

Open
#15 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Julia
Stars
243
Forks
67
PR merge metrics
No merged PRs in 30d

Description

I tried to model my own tree upon the concepts introduced in this package by simply defining children as a function that returns an iterator over the children of a given node. This immediately enabled print_tree. I was not able to use e.g. 'Leaves'. The problem seems to be that the children collection should be indexable as opposed to be merely iterable. Also the supplied example demonstrating directory traversal suffers from this:

include("examples/fstree.jl")
ns = collect(Leaves(Directory(pwd())))

MethodError: no method matching getindex(::DirectoryListing, ::Int64)
in collect at base\array.jl:431
in _collect at base\array.jl:442
in start at AbstractTrees\src\AbstractTrees.jl:494 
in firststate at AbstractTrees\src\AbstractTrees.jl:398
in isempty at base\essentials.jl:358 
in childstates at AbstractTrees\src\implicitstacks.jl:41
in getnode at AbstractTrees\src\implicitstacks.jl:2

I was able to fix this by defining

Base.getindex(dl::DirectoryListing, i::Int) = dl.names[i]
AbstractTrees.nextind(dl::DirectoryListing, i::Int) = i+1

This fix, however is does not work as in my implementation there is no easy way to predict the location of the i-th sibling in the underlying buffer.

What are the ambitions of this package? Does it aspire to define the vocabulary and interface for all tree implementations (as AbstractArrays tries to accomplish for Indexables)? Or would you advise to start a separate package. I would like to avoid proliferation of the package ecosystem with similar but different concepts if possible...

Is this framework written for convenience or is it also suitable for high performance large scale trees? If all nodes are of the same type, will the framework take advantage of this?

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the traversal code in AbstractTrees/src/AbstractTrees.jl around the reported collect, start, childstates, and getnode calls, then inspect examples/fstree.jl and DirectoryListing. Determine which child-collection interface Leaves requires and whether iterable-only children are intended to work. Done should include a documented interface decision and a verified outcome for the directory example and custom tree case.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
devtools
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.