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) { // Nested lists are easier to write, but less detailed. 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)) } //d3.shuffle(this.children) } else if (input instanceof GeoOrdering) { super() this['name'] = input.name this['aliases'] = input['aliases'] this.properties = input.properties this['children'] = input.children } else { // Initialize from an object. 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) { } }