Created
September 9, 2018 19:58
-
-
Save josgraha/98fef89c367b627844871891f88e1699 to your computer and use it in GitHub Desktop.
Zipper in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const lastIndex = list => ( | |
list && list.length > 0 ? list.length - 1 : 0); | |
const isNone = val => val === null || typeof val === 'undefined'; | |
const asList = list => (isNone(list) ? [] : list); | |
const isEmptyList = list => list && list.length <= 0; | |
const isLastIndex = (lst, index) => (asList(lst).length - 1) === index; | |
const append = (list, elem) => (isNone(elem) ? | |
list : [...asList(list), elem]); | |
const dropLast = list => asList(list).slice(0, lastIndex(list)); | |
const excludeRoot = paths => asList(paths).filter(path => path !== 'root'); | |
const clone = obj => JSON.parse(JSON.stringify(obj)); | |
const setPathValue = (obj, paths, newValue) => { | |
const newObj = clone(obj); | |
paths.reduce((val, key, index) => { | |
if (isLastIndex(paths, index)) { | |
const node = val; | |
node[key] = newValue; | |
return node; | |
} | |
return val[key]; | |
}, newObj); | |
return newObj; | |
}; | |
const pathValue = (obj, paths) => paths.reduce( | |
(val, key) => val[key], obj | |
); | |
const createContainer = ContainerClass => (tree, paths) => { | |
if (isEmptyList(paths)) { | |
return null; | |
} | |
return new ContainerClass(tree, paths); | |
}; | |
const createSetter = withContainer => (ctx, paths, value) => { | |
const tree = setPathValue(ctx, | |
excludeRoot(paths), value); | |
return withContainer(tree, paths); | |
}; | |
class Zipper { | |
constructor(tree, paths = ['root']) { | |
this.tree = tree; | |
this.paths = paths; | |
} | |
pushFocusNode(path) { | |
const paths = append(this.paths, path); | |
const nodeVal = pathValue(this.tree, excludeRoot(paths)); | |
if (isNone(nodeVal)) { | |
return nodeVal; | |
} | |
return this.asZipper(paths); | |
} | |
up() { | |
return this.asZipper(dropLast(this.paths)); | |
} | |
left() { | |
return this.pushFocusNode('left'); | |
} | |
right() { | |
return this.pushFocusNode('right'); | |
} | |
value() { | |
return pathValue(this.tree, | |
excludeRoot(append(this.paths, 'value')) | |
); | |
} | |
delete() { | |
return Zipper.setAttribute(this.tree, this.paths, undefined); | |
} | |
setValue(value) { | |
return Zipper.setAttribute( | |
this.tree, | |
append(this.paths, 'value'), | |
value | |
); | |
} | |
setLeft(value) { | |
return Zipper.setAttribute( | |
this.tree, | |
append(this.paths, 'left'), | |
value | |
); | |
} | |
setRight(value) { | |
return Zipper.setAttribute( | |
this.tree, | |
append(this.paths, 'right'), | |
value | |
); | |
} | |
asZipper(paths) { | |
return Zipper.asZipper(this.tree, paths); | |
} | |
toTree() { | |
return this.tree; | |
} | |
} | |
Zipper.asZipper = createContainer(Zipper); | |
Zipper.setAttribute = createSetter(Zipper.asZipper); | |
Zipper.fromTree = t => new Zipper(t); | |
export default Zipper; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Zipper from './zipper'; | |
// tests adapted from `problem-specifications/zipper/canonical-data.json` @ v1.0.0 | |
function bt(value, left, right) { | |
return { | |
value, | |
left, | |
right, | |
}; | |
} | |
function leaf(value) { | |
return bt(value, null, null); | |
} | |
describe('Zipper', () => { | |
const t1 = bt(1, bt(2, null, leaf(3)), leaf(4)); | |
const t2 = bt(1, bt(5, null, leaf(3)), leaf(4)); | |
const t3 = bt(1, bt(2, leaf(5), leaf(3)), leaf(4)); | |
const t4 = bt(1, leaf(2), leaf(4)); | |
const t5 = bt(1, bt(2, null, leaf(3)), bt(6, leaf(7), leaf(8))); | |
const t6 = bt(1, bt(2, null, leaf(5)), leaf(4)); | |
const t7 = bt(1, bt(2, null, leaf(3))); | |
let zipper; | |
beforeEach(() => { | |
zipper = Zipper.fromTree(t1); | |
}); | |
test('data is retained', () => { | |
expect(zipper.toTree(t1)).toEqual(t1); | |
}); | |
test('left, right and value', () => { | |
expect(zipper.left().right().value()).toEqual(3); | |
}); | |
test('dead end', () => { | |
expect(zipper.left().left()).toBe(null); | |
}); | |
test('tree from deep focus', () => { | |
expect(zipper.left().right().toTree()).toEqual(t1); | |
}); | |
test('traversing up from top', () => { | |
expect(zipper.up()).toEqual(null); | |
}); | |
test('left, right and up', () => { | |
expect(zipper.left().up().right().up().left().right().value()).toEqual(3); | |
}); | |
test('setValue', () => { | |
expect(zipper.left().setValue(5).toTree()).toEqual(t2); | |
}); | |
test('setValue after traversing up', () => { | |
expect(zipper.left().right().up().setValue(5).toTree()).toEqual(t2); | |
}); | |
test('setLeft with leaf', () => { | |
expect(zipper.left().setLeft(leaf(5)).toTree()).toEqual(t3); | |
}); | |
test('setRight with null', () => { | |
expect(zipper.left().setRight(null).toTree()).toEqual(t4); | |
}); | |
test('setRight with subtree', () => { | |
expect(zipper.setRight(bt(6, leaf(7), leaf(8))).toTree()).toEqual(t5); | |
}); | |
test('setValue on deep focus', () => { | |
expect(zipper.left().right().setValue(5).toTree()).toEqual(t6); | |
}); | |
test('delete on deep focus', () => { | |
expect(zipper.right().delete().toTree()).toEqual(t7); | |
}); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Zipper
Creating a zipper for a binary tree.
Zippers are
a purely functional way of navigating within a data structure and
manipulating it. They essentially contain a data structure and a
pointer into that data structure (called the focus).
For example given a rose tree (where each node contains a value and a
list of child nodes) a zipper might support these operations:
from_tree
(get a zipper out of a rose tree, the focus is on the root node)to_tree
(get the rose tree out of the zipper)value
(get the value of the focus node)prev
(move the focus to the previous child of the same parent,returns a new zipper)
next
(move the focus to the next child of the same parent, returns anew zipper)
up
(move the focus to the parent, returns a new zipper)set_value
(set the value of the focus node, returns a new zipper)insert_before
(insert a new subtree before the focus node, itbecomes the
prev
of the focus node, returns a new zipper)insert_after
(insert a new subtree after the focus node, it becomesthe
next
of the focus node, returns a new zipper)delete
(removes the focus node and all subtrees, focus moves to thenext
node if possible otherwise to theprev
node if possible,otherwise to the parent node, returns a new zipper)