-module(zlists). -export([list_to_zlist/1, zlist_to_list/1, prev/1, next/1, current/1, replace/2, insert/2, delete/1, map/2, rmap/2]). %% A zlist, or zipper list, allows to 'browse' a list %% in two directions, much like a doubly-linked list. %% Access to the next and previous element are both %% constant time, and so is the cost of insertion and %% deletion. %% Lookups remain O(n). %% {Previous, [Current | Next]}. -type zlist() :: {list(), list()}. %% Most zippers data structures wouldn't really need to convert between %% types, but lists are kind of ubiquitous in usage, so it might be %% proper to convert them. %% Convert from standard list to zlist -spec list_to_zlist(list()) -> zlist(). list_to_zlist(L) when is_list(L) -> {[], L}. -spec zlist_to_list(zlist()) -> list(). zlist_to_list({Pre, Post}) -> lists:reverse(Pre) ++ Post. %% Zipper lists can be moved inside in both direction, much like a %% doubly-linked list in languages that support them. The functions %% prev/1 and next/1 allow to move in such a manner. They crash whenever %% you reach the end or the beginning of the zlist, exactly like the %% functions erlang:hd/1 and erlang:tl/1 do. -spec prev(zlist()) -> zlist(). prev({[H|T], Post}) -> {T, [H|Post]}. -spec next(zlist()) -> zlist(). next({Pre, [H|T]}) -> {[H|Pre], T}. %% current/1 allows to read the value of the list. fails on empty %% zlists, exactly the way erlang:hd/1 does. Also fails on lists where %% the end has been reached. -spec current(zlist()) -> term(). current({_, [Current|_]}) -> Current. %% Replace changes the value of the current zlist item. -spec replace(term(), zlist()) -> zlist(). replace(Val, {Pre, [_|Post]}) -> {Pre, [Val|Post]}. -spec insert(term(), zlist()) -> zlist(). insert(Val, {Pre, Post}) -> {Pre, [Val|Post]}. -spec delete(zlist()) -> zlist(). delete({Pre, [_|Post]}) -> {Pre, Post}. %% Map and reverse maps as an example of potentially %% useful functions map(_, L = {_, []}) -> L; map(F, {P, [H|T]}) -> map(F, {[F(H)|P], T}). rmap(_, L = {[], _}) -> L; rmap(F, {[H|T], N}) -> rmap(F, {T, [F(H)|N]}).