Popularity
2.1
Declining
Activity
0.0
Stable
19
1
0

Monthly Downloads: 14
Programming language: Elixir
License: Do What The F*ck You Want To Public License
Latest version: v0.1.1

zipper_tree alternatives and similar packages

Based on the "Algorithms and Data structures" category.
Alternatively, view zipper_tree alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of zipper_tree or a related project?

Add another 'Algorithms and Data structures' Package

README

ZipperTree

Provides traversal and modification methods for variadic arity tree's. All methods maintain an active 'cursor' or focus in the tree. The methods will also technically work for lists too - I guess, if you're into that sorta thing.

All traversal and insertion methods happen in constant time with exception to up, which is porportional to how many nodes were junior to the current subtree.

This is an implementation of Gérard Huet's tree with a zipper (originally published in Functional Pearl: The Zipper), essentially a direct conversion of the published oocaml code to elixir.

WTF is a Zipper

A zipper is a novel method for encoding a focus, or position state of a collection in purely functional languages. The zipper is an analogy for the process of moving up and down the structure and how it can be thought of as opening and closing a zipper. For a better description of the data structure I recommend you read the paper linked above, although usage does not necessarily require you understand it's implementation.

Usage

Just add {:zipper_tree, "~> 0.1.1"} to your dependencies.

The implementation provided works for trees of variadic arity, simply define a tree using nested lists

iex(3)> import ZipperTree

iex(4)> tree = [
  1,
  2,
  [
    3,
    4
  ]
]

[1, 2, [3, 4]]

iex(5)> tree
  |> nth(3)
%ZipperTree.Loc{loc: [3, 4],
 path: %ZipperTree.Node{left: [2, 1], right: [], up: Top}}

iex(6)> tree
  |> nth(3)
  |> right
{:error, "right of last"}

iex(7)> tree
  |> nth(3)
  |> down
%ZipperTree.Loc{loc: 3,
 path: %ZipperTree.Node{left: [], right: [4],
  up: %ZipperTree.Node{left: [2, 1], right: [], up: Top}}}

iex(8)> tree
  |> nth(3)
  |> down
  |> right
%ZipperTree.Loc{loc: 4,
 path: %ZipperTree.Node{left: [3], right: [],
  up: %ZipperTree.Node{left: [2, 1], right: [], up: Top}}}

iex(9)> tree
  |> nth(3)
  |> down
  |> right
  |> top
%ZipperTree.Loc{loc: [1, 2, [3, 4]], path: Top}

iex(10)> tree
  |> nth(3)
  |> down
  |> right
  |> change(:sup)
  |> top
%ZipperTree.Loc{loc: [1, 2, [3, :sup]], path: Top}

iex(11)> tree
  |> nth(3)
  |> down
  |> right
  |> insert_left(:over_here_now)
  |> top
%ZipperTree.Loc{loc: [1, 2, [3, :over_here_now, 4]], path: Top}

Then move around the tree using down, left, right, up, nth, top and make modifications with change, insert_down, insert_left, insert_right.

For specific method examples check the tests.

Road map

  • [x] traversal
  • [x] modification and insertion
  • [ ] implement protocols (Enum, etc.)
  • [ ] various search strategies
  • [ ] ???