class GeoOrdering extends Object {
constructor(input, lookup_maps = {}) {
if (typeof(input) == "string") {
super()
this.children = []
this.aliases = input.split(" AKA ")
this.name = this.aliases[0];
this.properties = {}
this.geometry = {}
} else if (input.length) {
super()
this.aliases = input[0].split("AKA")
this.name = this.aliases[0]
this.children = []
this.properties = {}
if (this.name.length && !typeof(this.name) == "string") {
this.name = input[0][0]
this.properties.aliases = input[0].slice(1, input[0].length)
}
for (let child of input.slice(1, input.length)) {
this.children.push(new GeoOrdering(child, lookup_maps))
}
} else if (input instanceof GeoOrdering) {
super()
this['name'] = input.name
this['aliases'] = input['aliases']
this.properties = input.properties
this['children'] = input.children
} else {
super()
this.properties = input.properties || {}
this.name = input.name
this.aliases = input.aliases
this.children = []
for (let [k, v] of Object.entries(this)) {
if (k != "children" &&
k != "name" &&
k != "properties" &&
k != "aliases") {
this[k] = v
}
}
if (self.children) {
self.children = self.children.map(
child => new GeoOrdering(child, lookup_maps)
)
}
}
for (const [key, val] of Object.entries(lookup_maps)) {
for (let name of this.aliases) {
const candidate = val.get(name)
if (candidate) {this.properties[key] = candidate}
}
}
this.backlink_parents()
}
alias_map() {
const aliases = new Map()
for (let child of this) {
for (let name of child.aliases) {
aliases.set(name, child.aliases)
}
}
return aliases
}
*[Symbol.iterator]() {
yield this
for (let child of this.children) {
for (let entry of child) {
yield entry
}
}
}
backlink_parents() {
for (let child of this.children) {
child.parent = this
child.backlink_parents()
}
}
object_repr() {
const { alias, name, geometry, properties } = this;
const children = this.children.map(d => d.object_repr())
return { alias, name, geometry,
properties, children }
}
compact_repr() {
// Return to the most compact possible form.
const val = []
val.push(this.aliases.join(" AKA "))
if (this.children.length == 0) {
return val[0]
}
for (let child of this.children) {
val.push(child.compact_repr())
}
return val
}
get array() {
let output = [...this.aliases]
for (let child of this.children) {
output = output.concat(child.array)
}
return output
}
get parent_tree() {
if (this._parent_tree) {return this._parent_tree}
this._parent_tree = []
let node = this;
while (node.parent) {
this._parent_tree.unshift(node.parent.name)
node = node.parent
}
return this._parent_tree
}
get objects() {
const output = []
for (let entry of this) {
output.push(entry)
}
return output
}
missing(l) {
// List missing keys from a passed list.
const current = new Set(this.array)
return new Set(l.filter(d => !current.has(d)))
}
get coords() {
let val;
if (this.properties.coords) {
// To ensure it always populates if it doesn't exist.
this.children.map(d => d.coords)
val = this.properties.coords
} else if (this.geometry) {
// Should just use d3.geoCentroid.
if (d3 === undefined || d3.geoCentroid === undefined) {
throw ("Must have d3 and d3-geo in the namespace.")
} else {
this.properties.coords = d3.geoCentroid(this.geometry);
val = this.properties.coords;
}
} else if (this.children) {
// Note--unweighted. Might be good to weight.
const points = []
for (let child of this.children) {
if (child.coords && child.coords[0]) {
// Could weight by overpushing points from some leaves.
points.push(child.coords)
}
}
this.properties.coords = d3.geoCentroid(
{
"type": "MultiPoint" ,
coordinates: points
})
val = this.properties.coords;
} else {
val = null
}
if (val.length && !isFinite(val[0])) {
val = null
}
if (val && val[0] === null) {val = null}
return val
}
leaves(only_those_with_coords = true) {
const leaves = [];
const break_function = d => d.children.length == 0;
for (let child of this) {
if (break_function(child)) {
if (only_those_with_coords && child.coords === null) {
continue
}
leaves.push(child)
}
}
return leaves
}
LineString(break_function = d => d.children.length == 0) {
const coords = []
for (let child of this) {
if (break_function(child)) {
coords.push(child.coords)
}
}
return {
"type": "LineString",
"coordinates": coords.filter(d => d && d.length == 2)
}
}
point() {
return {"type": "Point", "geometry": (this.coords)}
}
entrance_and_exit() {
if (this.parent === undefined) {
return [null, null]
}
let entrance = null;
let exit = null;
const index_of_this = this.parent.children
.map(d => d.name)
.indexOf(this.name)
if (index_of_this > 0) {
entrance = this.parent.children[index_of_this - 1].endpoints[1]
}
if (index_of_this < this.parent.children.length - 1) {
exit = this.parent.children[index_of_this + 1].endpoints[0]
}
return [entrance, exit]
}
distance() {
const [entrance, exit] = this.entrance_and_exit()
const coords = this.LineString().coordinates;
let cost;
if (coords.length <= 1) {
return 0
}
if (entrance !== null) {
cost = d3.geoDistance(entrance, coords[0])
} else {
cost = 0
}
let last;
let current
for (let i = 1; i < coords.length; i++) {
current = coords[i]
last = coords[i-1]
cost += d3.geoDistance(last, current);
}
if (exit != null) {
cost += d3.geoDistance(current, exit)
}
return cost;
}
shallow_distance() {
let accumulator = 0
let last = null
let current = null
const coords = this.children.map(d => d.coords);
const [start, end] = this.entrance_and_exit();
coords.push(end)
coords.shift(start)
for (let coord of coords) {
current = coord
if (last && current) {
accumulator += d3.geoDistance(last, current)
}
// If the current thing is undefined, stay at the last point.
if (current !== null) {last = current}
}
return accumulator
}
reverse() {
this.children.reverse()
for (let child of this.children) {
child.reverse()
}
}
get endpoints() {
if (this.children.length == 0) {
return [this.coords, this.coords]
}
const first = this.children[0].endpoints[0]
const last = this.children[this.children.length - 1].endpoints[1]
return [first, last]
}
two_opt(i, j) {
const { children } = this;
const switcheroo = [...this.children.slice(i, j)].reverse()
for (let m = 0; m < switcheroo.length; m++) {
children[i + m] = switcheroo[m]
// Need to flip the kids as well.
// in case i + 1 == j, simply reverses the single list.
children[i + m].reverse()
}
}
optimize_two_opts_once(metric = "shallow_distance", depth = 0, pin_start = false, pin_end = false) {
if (this.children.length == 0) {return false}
// console.log(this, metric, this[metric])
let delta = false
let best_distance = this[metric]()
for (let i = 0; i <= this.children.length - 2; i++) {
for (let j = i + 1; j < this.children.length; j++) {
this.two_opt(i, j)
if (depth > 0) {
this.children.forEach(child => child.optimize_two_opts_once(metric, depth - 1))
}
if (this[metric]() < best_distance) {
best_distance = this[metric]()
delta = true
} else {
// swap back.
this.two_opt(i, j)
}
}
}
// console.log(this.name, best_distance, delta)
return delta
}
stash_order() {
this.stash = this.stash || []
this.stash.push([...this.children])
this.children.forEach(child => child.stash_order())
}
revert_order() {
this.children = this.stash.pop()
this.children.forEach(child => child.revert_order())
}
confirm_order() {
this.stash.pop()
this.children.forEach(child => child.confirm_order())
}
optimize_swaps_on_children(entrance = null, exit = null) {
let last_enter = entrance;
let delta = false
this.children.forEach((child, i) => {
const next_exit = i < this.children.length - 1 ? this.children[i + 1].endpoints[0] : exit;
const delta_here = child.optimize_swaps(last_enter, next_exit)
if (delta_here) {
delta = true
}
last_enter = this.children[i].endpoints[1];
})
return delta
}
optimize_swaps(entrance = null, exit = null) {
let delta = true
if (this.children.length < 2) {
return false
}
const { children } = this;
let cost = this.distance(entrance, exit)
while (delta = true) {
delta = false
for (let i = 0; i < this.children.length; i++) {
for (let j = i + 1; j <= children.length; j++) {
this.stash_order()
// Special case here--you *can*
// swap a single item by reversing it in place.
this.two_opt(i, j);
this.optimize_swaps_on_children(entrance, exit);
const new_cost = this.distance(entrance, exit);
if (new_cost >= cost) {
// swap back.
this.revert_order()
} else {
delta = true
cost = new_cost
this.confirm_order()
}
}
}
}
this.optimize_swaps_on_children(entrance, exit);
return delta
}
update_editable_tree(parent = undefined) {
if (parent == undefined) {
parent = d3.select(DOM.element("div")).append("ul")
}
const tree = this
function move_up_or_down(event, d) {
const direction = d3.select(this).attr("class")
console.log("Moving", d.name, direction, "among", tree.children.map(d => d.name))
const ix = tree
.children
.map(d => d.name)
.indexOf(d.name)
const new_ix = ix + (direction == "up" ? -1 : 1)
if (new_ix < 0 || new_ix >= tree.children.length) {
return
}
[tree.children[new_ix], tree.children[ix]] = [tree.children[ix], tree.children[new_ix]]
tree.update_editable_tree(parent)
}
const lis = parent.selectAll("li")
.data(tree.children, d => d.name)
.join(
enter => {
const li = enter.append("li")
const label = li.append("span").attr("class", "label").text(d => d.name)
const up = li.append("span").attr("class", "up").text("⇧").on("click", move_up_or_down)
const down = li.append("span").attr("class", "down").text("⇩").on("click", move_up_or_down)
const reverse = li.append("span").attr("class", "down").text("⟳").on("click", function(event, d) {
d.reverse()
tree.update_editable_tree(parent)
})
const ul = li.append("ul").style("display", "none")
label.on("click", function (event, d) {
const child_list = d3.select(this.parentNode).select("ul")
child_list.style("display", child_list.style("display") == "none" ? "inline" : "none")
})
up.on("click", move_up_or_down)
down.on("click", move_up_or_down)
return li
})
.style("padding-left", "1em")
.each((d, i, group) => {
const node = group[i]
d.update_editable_tree(d3.select(node).select("ul"))
})
return parent
}
optimize(entrance = null, exit = null) {
}
}