1 /* (This is the new BSD license.)
  2 * Copyright (c) 2012-2014, Chris Culy
  3 * All rights reserved.
  4 *
  5 * Redistribution and use in source and binary forms, with or without
  6 * modification, are permitted provided that the following conditions are met:
  7 *     * Redistributions of source code must retain the above copyright
  8 *       notice, this list of conditions and the following disclaimer.
  9 *     * Redistributions in binary form must reproduce the above copyright
 10 *       notice, this list of conditions and the following disclaimer in the
 11 *       documentation and/or other materials provided with the distribution.
 12 *     * Neither the name of the Chris Culy nor the 
 13 *		names of its contributors may be used to endorse or promote 
 14 *		products from this software without specific prior written permission.
 15 *
 16 * THIS SOFTWARE IS PROVIDED BY Chris Culy
 17 * ``AS IS'' AND ANY OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
 18 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 19 * ARE DISCLAIMED. IN NO EVENT SHALL Chris Culy
 20 * BE LIABLE FOR ANY, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 21 * CONSEQUENTIAL DAMAGES INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 
 22 * GOODS OR SERVICES; OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
 23 * CAUSED AND ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR 
 24 * TORT INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 
 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 26 */
 27 "use strict";
 28 /**
 29  @namespace doubletree
 30  All of the functionality is in the doubletree namespace
 31 */
 32 var doubletree = {};
 33 
 34 (function(){
 35   
 36   //TBD what about visWidth? to be fixed visWidth is really width and width is really just the width of one side of the doubletree
 37   
 38   /**
 39     @class doubletree.DoubleTree
 40     This is the class for the DoubleTree visualization
 41   */
 42   doubletree.DoubleTree = function() {
 43     var containers = []; //nominally for allowing the same tree in multiple places, but not tested and probably doesn't work right (e.g. for search)
 44     //defaults. see below for getter/setters
 45     var visWidth = 600;
 46     var visHt; //calculated, not settable
 47     var filters = {"left":[], "right":[]};
 48     var handlers = {"alt":noOp, "shift":noOp};
 49     var showTokenExtra = true;
 50     var scaleLabels = true;
 51     var sortFun = doubletree.sortByStrFld("token");
 52     var nodeText = doubletree.tokenText; //default
 53     var tokenExtraText = function(info) {
 54       return doubletree.fieldText(info, "POS");
 55     };
 56     var rectColor = function(info) {
 57       return "rgba(255,255,255,0)"; //transparent white
 58     };
 59     var rectBorderColor = function(info) {
 60       return "rgba(255,255,255,0)"; //transparent white
 61     };
 62     var continuationColor = function(info) {
 63 	 return "red";
 64     }
 65     var basicStyles = {"node":{"fill":"white", "stroke":"steelblue", "stroke-width":"1.5px"}, "branch":{"stroke":"#aaa", "stroke-width":"1.5px"}};
 66     
 67     
 68     
 69     var succeeded = false; //did we succeed in building a DoubleTree? we need this flag, since we no longer return true/false from setupFromX (since we do chaining)
 70     
 71     var dispatch = d3.dispatch("idsUpdated");
 72     dispatch.on("idsUpdated", function() {
 73 	if (this == leftTree) {
 74 	  rtTree.setIds( leftTree.continuationIDs );
 75 	  rtTree.updateContinuations();
 76 	} else if (this == rtTree) {
 77 	  leftTree.setIds( rtTree.continuationIDs );
 78 	  leftTree.updateContinuations();
 79 	}	 
 80     });
 81   
 82     var leftTrie, rtTrie, leftTree, rtTree;
 83     var visibleIDs; //the ids of the results that are showing
 84     
 85     //tmp, until we can do sizing right. the font sizes are specified in doubletree.css and manually copied here
 86     var kFontSize = 14; //normal
 87     var kBigFontSize = 1.15*kFontSize; //for found text and continuations (was 18) NB: this is 0.05 bigger than in doubletree.css
 88     var kMinFontSize = 8; //smallest that we'll scale to
 89     var textScale;
 90     
 91     /** @exports mine as doubletree.DoubleTree */
 92     /** @ignore */
 93     function mine(selection) {
 94       // generate container and data independent part of chart here, using `width` and `height` etc
 95       
 96       selection.each(function(d, i) {
 97 	//generate chart here; `d` is the data and `this` is the element
 98 	//really, storing containers. Use updateData and redraw to really do the generation
 99 	containers.push(this[i]);
100       });
101     
102     }
103     
104     /**
105      * initialize the visualization in one or more html containers
106      * <p>
107      * @param containerPattern CSS selector for the containers
108      */
109     mine.init = function(containerPattern) {
110       d3.select(d3.selectAll(containerPattern)).call(this);
111       return mine;
112     }
113     
114     /**
115      * redraw the visualization
116      */
117     mine.redraw = function() {
118       mine.setupFromTries(leftTrie, rtTrie);
119       
120       return mine;
121     }
122     
123 
124     /**
125      * set up the visualization using 2 {@link doubletree.Trie}s
126      * @param leftOne the left {@link doubletree.Trie}
127      * @param rtOne the right {@link doubletree.Trie}
128      */
129     mine.setupFromTries = function(leftOne, rtOne) {
130       leftTrie = leftOne.getUniqRoot();
131       rtTrie = rtOne.getUniqRoot();
132       
133       
134       
135       var leftTrieTree =  leftTrie.toTree(filters.left);
136       var rtTrieTree =  rtTrie.toTree(filters.right);
137      
138       var copyIDs = true;
139       if (Object.keys(rtTrieTree.pruned).length > 0) {
140         new_pruneTree(rtTrieTree, rtTrieTree.pruned, copyIDs);
141         new_pruneTree(leftTrieTree, rtTrieTree.pruned, copyIDs);
142         copyIDs = false;
143       }
144       
145       if (Object.keys(leftTrieTree.pruned).length > 0 ) {
146         new_pruneTree(leftTrieTree, leftTrieTree.pruned, copyIDs);
147         new_pruneTree(rtTrieTree, leftTrieTree.pruned, copyIDs);
148       }
149       
150       
151       //combine the info's from the two trees
152       var newInfo = {}; //rtTrieTree.info;
153       
154       for(var k in rtTrieTree.info) {
155         if (k != "continuations" && k != "ids" && k != "count") {
156           newInfo[k] = rtTrieTree.info[k];
157         }
158       }
159      
160       newInfo["right continuations"] = rtTrieTree.info.continuations;
161       newInfo["left continuations"] = leftTrieTree.info.continuations;
162       
163      
164       newInfo.ids = {};
165       addTo(newInfo.ids, rtTrieTree.info.ids);
166       addTo(newInfo.ids, leftTrieTree.info.ids);
167       newInfo.count = Object.keys(newInfo.ids).length;
168       visibleIDs = Object.keys(newInfo.ids);
169      
170       if (rtTrieTree.info.origIDs || leftTrieTree.info.origIDs) {
171         newInfo.origIDs = {};
172         addTo(newInfo.origIDs, rtTrieTree.info.origIDs);
173         addTo(newInfo.origIDs, leftTrieTree.info.origIDs);
174         newInfo.origCount = Object.keys(newInfo.origIDs).length;
175       }
176      
177      
178       rtTrieTree.info = newInfo;
179       leftTrieTree.info = newInfo;
180       
181       
182       
183       var maxChildren = Math.max(leftTrieTree.maxChildren, rtTrieTree.maxChildren);
184       if (isNaN(maxChildren) || maxChildren == 0 ) {
185         succeeded = false;
186         return mine;
187       }
188       
189       if (scaleLabels) {
190         textScale = d3.scale.log().range([kMinFontSize, kFontSize]);
191       } else {
192         textScale = function() {return kFontSize;}
193         textScale.domain = function(){};
194       }
195       
196       visHt = Math.max(200, maxChildren * (kBigFontSize-2));//TBD ?? fix was 16; 18 is the continuation font size
197       
198       var maxLen = Math.max(leftTrieTree.maxLen, rtTrieTree.maxLen);
199       var brLen = Math.max(80, maxLen*0.6*kBigFontSize); //TBD ?? fix was 10.5; 18 is the continuation font size
200       if (brLen > 200) {
201 	brLen = 200;
202       }
203       
204       var minCount = Math.min(leftTrieTree.minCount, rtTrieTree.minCount);
205       textScale.domain([minCount, leftTrieTree.info.count]);
206       
207       //TBD ?? margin, width, height, duplicated in Tree
208       var margin = {top: 20, right: 20, bottom: 20, left: 20},
209       width = visWidth - margin.right - margin.left,
210       height = visHt - margin.top - margin.bottom;
211       
212       containers[0].forEach(function(d,i) {
213 	var thisContainer = d;
214 	var thisVis;
215      
216      function zoomF() {
217       if (d3.event.sourceEvent.type !== 'mousemove') {
218           return;
219         }
220         d3.select(thisContainer).select("svg > g").attr("transform", "translate(" + d3.event.translate + ")"); //scale(" + d3.event.scale + ") //don't zoom
221      }
222        
223 	var tmp = d3.select(thisContainer).select("svg");
224 	if (tmp[0][0] == null) {
225 	  thisVis = d3.select(thisContainer).append("svg")
226 	    .attr("width", width + margin.right + margin.left)
227 	    .attr("height", height + margin.top + margin.bottom)
228          .attr("cursor", "move")
229           //should use drag, but didn't work right -- keeps bouncing back
230           /*
231           .call(d3.behavior.drag()
232             .origin(function() {return {'x':width/2, 'y':height/2}})
233             .on("drag", function() {
234                  var delta = [d3.event.dx, d3.event.dy];
235                  thisVis.attr("transform", "translate(" + delta + ")");
236               }));
237           */
238           .call(d3.behavior.zoom()
239             .on("zoom", function() {
240               if (d3.event.sourceEvent.type !== 'mousemove') {
241                 return;
242               }
243               d3.select(thisContainer).select("svg > g").attr("transform", "translate(" + d3.event.translate + ")"); //scale(" + d3.event.scale + ") //don't zoom
244             }));
245          
246 	  thisVis.append("g"); //container for both trees
247        
248          
249 	} else {
250 	  thisVis = tmp;
251 	  thisVis.attr("width", width + margin.right + margin.left)
252 	    .attr("height", height + margin.top + margin.bottom);
253 	  thisVis.selectAll("g *").remove(); //clear previous 
254 	}
255 	
256 	leftTree = new doubletree.Tree(thisVis.select("g"), visWidth, visHt, brLen, leftTrieTree, true, sortFun, dispatch, textScale, showTokenExtra, nodeText, tokenExtraText, rectColor, rectBorderColor, continuationColor, basicStyles);
257 	rtTree = new doubletree.Tree(thisVis.select("g"), visWidth, visHt, brLen, rtTrieTree, false, sortFun, dispatch, textScale, showTokenExtra, nodeText, tokenExtraText, rectColor, rectBorderColor, continuationColor, basicStyles);
258       });
259       
260       leftTree.handleAltPress = handlers.alt;
261       rtTree.handleAltPress = handlers.alt;
262     
263       leftTree.handleShiftPress = handlers.shift;
264       rtTree.handleShiftPress = handlers.shift;
265 	
266       succeeded = true;
267       return mine;
268     }
269     
270     //hitArray is an array of items, prefixArray and suffixArray are arrays of arrays of items
271     /**
272      * set up the visualization from arrays corresponding to the hit, the prefix, and the suffix of a key word in context result.
273      * <p>
274      * The ith elements should correspond with each other.
275      * Each item consists of fields separated by a field delimiter.
276      * For example we might have word/tag (with / as the delimiter) or word\tlemma\tauthor (with tab (\t) as the delimiter)
277      * Only certain fields are relevant for deciding whether two items are to be considered the same (e.g. we might ignore an author field)
278      * @param prefixArray the array of arrays of the prefixes of the hits
279      * @param hitArray the array of the hits
280      * @param suffixArray the array of arrays of the suffixes of the hits
281      * @param idArray the array of ids of the hits (or null, if there are no ids for the hits)
282      * @param caseSensitive are the hits case sensitive
283      * @param fieldNames the names of the fields
284      * @param fieldDelim the field delimiter
285      * @param distinguishingFieldsArray the fields that determine identity
286      */
287     mine.setupFromArrays = function(prefixArray, hitArray, suffixArray, idArray, caseSensitive, fieldNames, fieldDelim, distinguishingFieldsArray) {
288       
289       if (undefined == caseSensitive && leftTrie) {
290 	caseSensitive = leftTrie.caseSensitive();
291       }
292       if (undefined == fieldNames  && leftTrie) {
293 	fieldNames = leftTrie.fieldNames();
294       }
295       if (undefined == fieldDelim  && leftTrie) {
296 	fieldDelim = leftTrie.fieldDelim();
297       }
298       if (undefined == distinguishingFieldsArray  && leftTrie) {
299 	distinguishingFieldsArray = leftTrie.distinguishingFieldsArray();
300       }
301       
302       leftTrie = new doubletree.Trie(caseSensitive, fieldNames, fieldDelim, distinguishingFieldsArray);
303       rtTrie = new doubletree.Trie(caseSensitive, fieldNames, fieldDelim, distinguishingFieldsArray);
304       
305       var n = hitArray.length;
306       for(var i=0;i<n;i++) {
307         var thisID = idArray ? idArray[i] : i;
308         var thisHit = hitArray[i];
309 	   var thesePrefixes = prefixArray[i].slice();
310 	   thesePrefixes.push(thisHit);
311 	   thesePrefixes.reverse();
312 	   leftTrie.addNgram( thesePrefixes, thisID);
313 	   
314 	   var theseSuffixes = suffixArray[i].slice();
315 	   theseSuffixes.unshift(thisHit);
316 	   rtTrie.addNgram( theseSuffixes, thisID);
317       }
318       
319       mine.setupFromTries(leftTrie, rtTrie);
320       return mine;
321     }
322     
323     /**
324      * @returns just the <em>ids</em> of the data that satisfies the current filters
325      */
326     mine.filteredIDs = function() {
327       return visibleIDs;
328     }
329     
330     //return how many found
331     /**
332      * search the nodes of the visualization for a pattern
333      * <p>
334      * The found nodes will get the CSS class foundText
335      * @param searchRE the regular expression to look for
336      * @returns how many nodes were found
337      */
338     mine.search = function(searchRE) {
339       leftTree.search(searchRE);
340       rtTree.search(searchRE);
341       
342       var thisVis = d3.select(containers[0][0]);
343       var found = thisVis.selectAll("text.foundText");
344       
345       if (found.empty()) { return 0;}
346       
347       var what = found[0].length;
348      
349       var foundRt = thisVis.selectAll("text.rtNdText.foundText");
350       
351       if (foundRt[0][0] != null) {
352 	what--; //root node, and we have 2 of those, so subtract one from the count
353       }
354       return what;
355     }
356 
357     /**
358      * clear the visualization of the search results
359      * <p>
360      * the CSS class foundText is removed
361      */
362     mine.clearSearch = function() {
363 	leftTree.clearSearch();
364 	rtTree.clearSearch();
365 	return mine;
366     }
367     
368     /**
369      * update the showing/hiding of extra information associated with the basic item, e.g. part of speech information
370      * <p>
371      * Notes:
372      * 	<ul>
373      * 		<li>This <em>DOES</em> redraw the visualization.</li>
374      * 		<li>Safari does not update the visualization correctly by itself, so we force it to rebuild the entire visualization, unlike in other browsers.</li>
375      * 	</ul>
376      */
377     mine.updateTokenExtras = function() {
378       leftTree.showTokenExtras(showTokenExtra);
379       rtTree.showTokenExtras(showTokenExtra);
380       
381       //Safari doesn't update reshowing correctly, so we'll force it to build this again :(    (Chrome works correctly, so it's not a webkit issue)
382       var thisVis = d3.select(containers[0][0]);
383       var tokExtra = thisVis.select('.tokenExtra[display="inline"]');
384       if (! tokExtra.empty()) {
385 	var ht = tokExtra.style("height");
386 	if (ht == "0px") {
387 	  mine.redraw();
388 	}
389       }
390 
391       return mine;
392     }
393   
394     //////////// getter/setters
395     /**
396      * Getter/setter for the maximum width of the DoubleTree area
397      * @param value the maximum width
398      */
399     mine.visWidth = function(value) {
400       if (!arguments.length) return visWidth;
401       visWidth = value;
402       return mine;
403     }
404     
405     //NB: doesn't redraw
406     /**
407      * Getter/setter for the filter functions.
408      *<p>
409      * The filter functions get an information object as their argument, and return true/false.
410      * Each position away from the root has its own filter, and the left and right sides also have their own filters.
411      * The filters are specified via an object with "left" and "right" keys whose values are arrays of functions
412      * The function at index <em>i</em> filters position <em>i + 1</em> away from the root.
413      * Default is no filtering (via empty arrays)
414      * <p>
415      * Note: setting the filters does <em>not</em> redraw the visualization. See {@link #redraw}
416      * @param value an object containing the filters
417      */ 
418     mine.filters = function(value) {
419       if (!arguments.length) return filters;
420       filters = value;
421       return mine;
422     }
423     
424     /**
425      * Getter/setter for the handlers for alt-click and shift-click on the nodes.
426      * <p>
427      * The handlers get an information object as their argument.
428      * The handlers are specified via an object with "alt" and "shift" keys whose values are functions
429      * The default is no handlers, i.e. <em>NO</em> interaction
430      * @param value an object containing the handlers
431      */
432     mine.handlers = function(value) {
433       if (!arguments.length) return handlers;
434       handlers = value;
435       return mine;
436     }
437     
438     //NB: doesn't redraw
439     /**
440      * Getter/setter for showing/hiding extra information associated with the main value, e.g. part of speech information.
441      * <p>
442      * Note: setting this value does <em>not</em> redraw the visualization. See {@link #redraw}
443      * Default is true
444      * @param value a boolean specifying whether to show the information or not
445      */
446     mine.showTokenExtra = function(value) {
447       if (!arguments.length) return showTokenExtra;
448       showTokenExtra = value;
449       return mine;
450     }
451     
452     /**
453      * Getter/setter for scaling the node labels by their frequency.
454      * <p>
455      * Default is true
456      * @param value a boolean specifying whether to scale the labels or not
457      */
458     mine.scaleLabels = function(value) {
459       if (!arguments.length) return scaleLabels;
460       scaleLabels = value;
461       return mine;
462     }
463     
464     //succeeded is read only
465     /**
466      * Reports whether the DoubleTree was constructed successfully
467      * <p>
468      * @returns true if the DoubleTree was constructed successfully and false otherwise
469      */
470     mine.succeeded = function() {
471       return succeeded;
472     }
473     
474     /**
475      * Getter/setter for the function determining the sort order of sibling nodes.
476      * <p>
477      * The function gets an information object as its argument, and should return -1 for precedes, 1 for follows and 0 for don't care
478      * The nodes are displayed in "preceding" (i.e. ascending) order, from top to bottom.
479      * The default is alphabetical by a "token" field if there is one: doubletree.sortByStrFld("token")
480      * @param the sort order function
481      */
482     mine.sortFun = function(value) {
483       if (!arguments.length) return sortFun;
484       sortFun = value;
485       return mine;
486     }
487     
488     /**
489      * Getter/setter for the function determining the content of the node labels.
490      * <p>
491      * The function gets an information object as its first argument and a boolean indicating whether the node is the root or not as its second argument. The function should return a string.
492      * The default is {@link #tokenText}
493      * @param the content function
494      */
495     mine.nodeText = function(value) {
496       if (!arguments.length) return nodeText;
497       nodeText = value;
498       return mine;
499     }
500     
501     /**
502      * Getter/setter for the function determining the content of the "extra" information for the labels labels
503      * <p>
504      * The function gets an information object as its first argument and a boolean indicating whether the node is the root or not as its second argument. The function should return a string.
505      * The default is the POS field of the information object
506      * @param the content function
507      */
508     mine.tokenExtraText = function(value) {
509       if (!arguments.length) return tokenExtraText;
510       tokenExtraText = value;
511       return mine;
512     }
513     
514     /**
515      * Getter/setter for the function determining the color of the background rectangles for the nodes.
516      * <p>
517      * The function gets an information object as its argument, and should return a CSS color in a string, e.g. "rgba(255,128,0,0.5)"
518      * The default is transparent white (i.e., effectively no color);
519      * @param value the background color function
520      */
521     mine.rectColor = function(value) {
522       if (!arguments.length) return rectColor;
523       rectColor = value;
524       return mine;
525     }
526     
527      /**
528      * Getter/setter for the function determining the color of the borders of the background rectangles for the nodes.
529      * <p>
530      * The function gets an information object as its argument, and should return a CSS color in a string, e.g. "rgba(255,128,0,0.5)"
531      * The default is transparent white (i.e., effectively no color);
532      * @param value the border color function
533      */
534     mine.rectBorderColor = function(value) {
535       if (!arguments.length) return rectBorderColor;
536       rectBorderColor = value;
537       return mine;
538     }
539     
540     /**
541      * Getter/setter for the function determining the color of the text of the nodes that are continuations of the clicked node.
542      * <p>
543      * The function gets an information object as its argument, and should return a CSS color in a string, e.g. "rgba(255,128,0,0.5)"
544      * The default is transparent white (i.e., effectively no color);
545      * @param value the border color function
546      */
547     mine.continuationColor = function(value) {
548       if (!arguments.length) return continuationColor;
549       continuationColor = value;
550       return mine;
551     }
552     
553     /**
554      * Getter/setter for the styles of the nodes and branches. For now these are constant throughout the tree.
555      * Takes an object of the form: {"node":{"fill":cssColor, "stroke":cssColor, "stroke-width":cssWidth}, "branch":{"stroke":cssColor, "stroke-width":cssWidth}}
556      * All of the attributes are optional
557      * Defaults are: {"node":{"fill":"white", "stroke":"steelblue", "stroke-width":"1.5px"}, "branch":{"stroke":"#777", "stroke-width":"1.5px"}};
558      */
559     mine.basicStyles = function(stylesObj) {
560       if (!arguments.length) return basicStyles;
561       
562       Object.keys(basicStyles).forEach(function(aspect){
563         if (aspect in stylesObj) {
564           Object.keys(basicStyles[aspect]).forEach(function(attr){
565             if (attr in stylesObj[aspect]) {
566               basicStyles[aspect][attr] = stylesObj[aspect][attr];
567             }
568           });
569         }
570       });
571       return mine;
572     }
573     
574     return mine;
575   }
576   
577   //////// tree for doubletree
578   /** @private */
579   doubletree.Tree = function(vis, visWidth, visHt, branchW, data, toLeft, sortFun, dispatch, textScale, showTokenXtra, nodeTextFun, tokenExtraTextFun, rectColorFun, rectBorderFun, contColorFun, baseStyles) {
580     var branchWidth = branchW;
581     var showTokenExtra = false || showTokenXtra;
582     var continuationIDs = {};
583     var clickedNode;
584     var nodeText = nodeTextFun;
585     var tokenExtraText = tokenExtraTextFun;
586     var rectColor = rectColorFun;
587     var rectBorderColor = rectBorderFun;
588     var continuationColor = contColorFun;
589     var basicStyles = baseStyles;
590     
591     var margin = {top: 20, right: 20, bottom: 20, left: 20},
592       width = visWidth - margin.right - margin.left,
593       height = visHt - margin.top - margin.bottom,
594       i = 0,
595       duration = 200,
596       root;
597     var dx;
598   
599     if (! sortFun ) {
600       sortFun = doubletree.sortByStrFld("token");
601     }
602     
603     var tree = d3.layout.tree()
604 	.size([height, width])
605 	.sort( sortFun )
606 	;
607     
608     var diagonal = d3.svg.diagonal()
609 	//.projection(function(d) { return [d.y, d.x]; }); //CC orig
610 	.projection(function(d) { return [positionX(d.y), positionY(d.x)]; });
611     
612     vis = vis.append("g")
613 	.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
614     
615     
616     ////////
617     this.readJSONTree = function(json) {
618       root = json;
619       root.x0 = height / 2;  
620       root.y0 = width / 2; //CC orig was 0
621     
622       root.children.forEach(collapse);
623       this.update(root);
624     }
625     
626     //CC had been inside readJSONTree
627     function collapse(d) {
628       if (d.children) {
629 	d._children = d.children;
630 	d._children.forEach(collapse);
631 	d.children = null;
632       }
633     }
634     
635     //CC new
636     function collapseSiblings(nd) {
637       if (nd.parent) {
638 	nd.parent.children.forEach(function(d) {
639 	    if (d != nd) {
640 	      collapse(d);
641 	    }
642 	});
643       }  
644     }
645     
646     var that = this;
647 
648     this.update = function(source) {      
649       if (! source ) {
650 	source = root;
651       }
652   
653       // Compute the new tree layout.
654       var nodes = tree.nodes(root).reverse(); //CC orig why reverse?
655       //var nodes = tree.nodes(root);
656       
657       //we don't want the root to change position, so we need to compensate
658       dx = root.x - height/2;     
659     
660     
661       // Normalize for fixed-depth.
662       nodes.forEach(function(d) { d.y = d.depth * branchWidth; }); //TBD paramaterize -- this is the length of the branch ??
663     
664       // Update the nodes…
665       var node = vis.selectAll("g.node_" + toLeft)
666 	  .data(nodes, function(d) { return d.id || (d.id = ++i); });
667     
668       // Enter any new nodes at the parent's previous position.
669       var nodeEnter = node.enter().append("g")
670 	  .attr("class", "node node_" + toLeft)	
671 	  .attr("transform", function(d) { return "translate(" + positionX(source.y0) + "," + positionY(source.x0) + ")"; })
672 	  /* doesn't work for webkit; svg really wants the title as separate element, see below
673 	   .attr("title", function(d) {
674 	    var what = doubletree.infoToText(d.info);
675 	    return what;})
676 	  */
677 	  .on("click", click);
678     
679       nodeEnter.append("title")
680 	.text(function(d) {
681 	    var what = doubletree.infoToText(d.info);
682 	    return what;}
683       );
684     
685       nodeEnter.append("circle")
686 	  .attr("r", 1e-6)	  
687 	  .style("fill", function(d) { return d._children ? "#fff" : basicStyles.node.fill; })
688 	  .style("stroke", function(d) { return basicStyles.node.stroke});
689     
690       var txtNode = nodeEnter.append("text")
691 	  .attr("class", function(d){
692 	      if (d.depth == 0) {
693 		return "rtNdText";
694 	      } else {
695 		return "";
696 	      }
697 	    })	
698 	  .attr("x", function(d) {
699 	    if (d.children || d._children) {	      	      
700 	      return 0;
701 	    } else {
702 	      return toLeft ? 10 : -10;
703 	    }	    
704 	  })
705 	  .attr("text-anchor", function(d) {
706 	    if (! d.parent) {
707 	      return "middle";
708 	    }
709 	    if (d.children || d._children) {
710 	      return toLeft ? "end" : "start";	      
711 	    } else {
712 	      return toLeft ? "start" : "end";
713 	    }	    
714 	  })
715 	  .style("font-size", function(d) {
716             /*
717             if (d.depth == 0 && toLeft) {
718               return 0; //suppress left side root -- do this because of differences in counts when filtering
719             }
720             */
721 	      return textScale(d.info.count) + "pt";
722 	    });
723 	  
724       txtNode.append("tspan")
725 	  .attr("dy", ".35em")
726 	  .attr("class", "tokenText")
727 	  .text(function(d) {
728 		return nodeText(d.info, d.depth < 1); })
729 	  .style("fill-opacity", 1e-6);
730       
731 	txtNode.append("tspan")
732 	  .attr("dx", ".35em")
733 	  .attr("class", "tokenExtra")
734 	  .text(function(d) {return tokenExtraText(d.info, d.depth < 1); })
735 	  .style("fill-opacity", 1e-6);
736       
737       this.drawRects = function() {
738 	var which = showTokenExtra ? "inline" : "none";
739 	vis.selectAll(".tokenExtra").attr("display",which);
740 	
741 	node.selectAll("rect").remove(); //remove previous rects
742 
743 	var nodeRect = node.append("rect")
744 	    .attr("class", "nodeRect")
745 	   .attr("height", function(){
746 	      return this.parentElement.getBBox().height -6;
747 	   })
748 	   .attr("y", function(d){
749 	      if (! d.parent) {
750 		return -0.5* this.parentElement.getBBox().height/2 -2;
751 	      } else {
752 		return -0.5* this.parentElement.getBBox().height/2 ;
753 	      }
754 	    })
755 	   .attr("width", function(){
756 	      return this.parentElement.getBBox().width;
757 	   })
758 	   .attr("x", function(d){
759 	      var parentW = this.parentElement.getBBox().width;
760 	      if (! d.parent) {
761 		return -0.33333 * parentW;
762 	      }
763 	      if (!toLeft) {
764 		return 0;
765 	      }
766 	      return -0.5 * parentW;
767 	   })	 
768 	   //.style("stroke-opacity", 1e-6)
769 	   .style("stroke-opacity", 1)
770 	   .style("stroke-width", 1)
771 	   .style("stroke", function(d){
772 	      return rectBorderColor(d.info);
773 	    })
774 	   .style("fill", function(d) {
775 	      return rectColor(d.info);
776 	   })
777 	   .style("fill-opacity", function(d){
778 	      if (! d.parent && ! toLeft) {
779 		return 1e-6;
780 	      } else {
781 		return 1;
782 	      }
783 	    });
784       }
785       try {
786 	this.drawRects();
787       } catch (e) {
788 	//apparently we're in some version of Opera, which thinks "this" is the window, not the rect wh
789       }
790     
791       // Transition nodes to their new position.
792       var nodeUpdate = node.transition()	  
793 	  .duration(duration)
794 	  .attr("transform", function(d) { return "translate(" + positionX(d.y) + "," + positionY(d.x) + ")"; });
795     
796       nodeUpdate.select("circle")
797 	  //.attr("r", 4.5)
798 	  .attr("r", function(d) { return (d.children || d._children) ? 1e-6 : 4.5})
799 	  .style("fill", function(d) { return d._children ? "#fff" : basicStyles.node.fill; }) //function(d) { return d._children ? "lightsteelblue" : "#fff"; })
800 	  .style("stroke-width", basicStyles.node["stroke-width"]);
801     
802       nodeUpdate.select("text")
803 	    .attr("class", function(d) {
804 	    	var isContinuation = containedIn(that.continuationIDs, d.info.ids);
805 	    	//var classes = this.classList.toString(); //TBD ?? WARNING, classList is Firefox only
806 
807 			if (isContinuation || !d.parent) {
808 				//this.classList.add("continuation");
809 				classListAdd(this,"continuation");
810 			} else {
811 				//this.classList.remove("continuation");
812 				classListRemove(this,"continuation");
813 			}
814 			//return this.classList.toString();
815 			return classListToString(this);
816 	    })
817 	  .style("fill-opacity", 1)
818 	  .style("fill", function(d){
819 		if (classListContains(this,"continuation")) {
820 		  return continuationColor(d.info);
821 		}
822 		return "#444"; //default text color
823 	   }); //this is duplicate in updateContinuations
824 
825       nodeUpdate.selectAll("tspan")
826 	.style("fill-opacity", 1);
827 
828     
829       // Transition exiting nodes to the parent's new position.
830       var nodeExit = node.exit().transition()
831 	  .duration(duration)
832 	  .attr("transform", function(d) { return "translate(" + positionX(source.y) + "," + positionY(source.x) + ")"; })
833 	  .remove();
834     
835       nodeExit.select("circle")
836 	  .attr("r", 1e-6);
837     
838       //nodeExit.select("text")
839       nodeExit.selectAll("tspan")
840 	  .style("fill-opacity", 1e-6);
841     
842       // Update the links…
843       var link = vis.selectAll("path.link_" + toLeft)
844 	  .data(tree.links(nodes), function(d) { return d.target.id; });
845     
846       // Enter any new links at the parent's previous position.
847       link.enter().insert("path", "g")
848 	  .attr("class", "link link_" + toLeft)
849 	  .attr("d", function(d) {
850 	    var o = {x: source.x0, y: source.y0}; //CC orig	
851 	    return diagonal({source: o, target: o});
852 	  })
853 	  .style("fill", "none")
854 	  .style("stroke", basicStyles.branch.stroke)
855 	  .style("stroke-width",basicStyles.branch["stroke-width"]);
856     
857       // Transition links to their new position.
858       link.transition()
859 	  .duration(duration)
860 	  .attr("d", diagonal);
861     
862       // Transition exiting nodes to the parent's new position.
863       link.exit().transition()
864 	  .duration(duration)
865 	  .attr("d", function(d) {
866 	    var o = {x: source.x, y: source.y}; //CC orig	    
867 	    return diagonal({source: o, target: o}); //CC orig	  
868 	  })
869 	  .remove();
870     
871       // Stash the old positions for transition.
872       nodes.forEach(function(d) {
873 	d.x0 = d.x;
874 	d.y0 = d.y;
875       });
876       
877     }
878   
879     // Toggle children on click.
880     function click(d, i) {
881       if (d3.event.altKey) {
882 	that.handleAltPress(d,i);
883 	//that.showTokenExtras(showTokenExtra);
884 	return;
885       }
886       if (d3.event.shiftKey) {
887 	that.handleShiftPress(d,i);
888 	//that.showTokenExtras(showTokenExtra);
889 	return;
890       }
891       
892       if (! d.parent ) {
893 	return;
894       }
895       if (that.continuationIDs != d.info.ids) {
896 	that.setIds(d.info.ids);
897 	that.clickedNode = d.id;
898 	dispatch.idsUpdated.apply(that);
899       }
900       
901       collapseSiblings(d); //CC new    
902       /*
903       if (d.children) {
904 	d._children = d.children;
905 	d.children = null;
906       } else {
907 	d.children = d._children;
908 	d._children = null;
909       }
910       that.update(d);
911       */
912       toggleChildren(d, true);
913     }
914     
915     function toggleChildren(d, update) { //we only update the clicked node, not recursively
916       //collapseSiblings(d); //CC we don't do this here, since after the top level there's no point
917       
918       if (d.children) {
919         if (d.children && d.children.length == 1) {
920           toggleChildren(d.children[0], true); //need true to make sure we toggle all the way down
921         }
922         d._children = d.children;
923         d.children = null;
924         
925         
926       } else {
927         d.children = d._children;
928         d._children = null;
929        
930         //expand all if there is only one path
931         if (d.children && d.children.length == 1) {
932           toggleChildren(d.children[0], false);
933         }
934       }
935       if (update) {
936          that.update(d);
937       }
938     }
939     
940     this.setIds = function(ids) {
941       that.continuationIDs = ids;
942     }    
943     this.updateContinuations = function() {
944       vis.selectAll("g.node_" + toLeft + " text")
945 	.classed("continuation", function(d) {
946         var isContinuation = overlap(d.info.ids, that.continuationIDs);
947         if (isContinuation) {
948           classListAdd(this,"continuation");  //some day we can get rid of this ...
949         } else {
950           classListRemove(this, "continuation");
951         }
952 	   return isContinuation;
953 	})
954 	.style("fill", function(d){
955 		if (classListContains(this,"continuation")) {
956 		  return continuationColor(d.info);
957 		}
958 		return "#444"; //default text color
959 	 }); //this is duplicated from above, nodeUpdate
960     }
961     
962     this.search = function(searchRE) {
963       vis.selectAll("g.node text")
964 	.attr("class", function(d) {
965 	    var what = searchRE.test(nodeText(d.info));
966 	    if (what) {
967 		    //this.classList.add("continuation");
968 		    classListAdd(this,"foundText");
969 	    } else {
970 		    //this.classList.remove("continuation");
971 		    classListRemove(this,"foundText");
972 	    }
973 	    //return this.classList.toString();
974 	    return classListToString(this);	    
975 	})
976     }
977     
978     this.clearSearch = function() {
979       vis.selectAll("g.node text")
980 	.attr("class", function(d) {
981 	    classListRemove(this,"foundText");
982 	    return classListToString(this);	    
983 	});
984     }
985     
986     this.showTokenExtras = function(show) {
987       if (arguments.length == 0) {
988 	return showTokenExtra;
989       }
990       showTokenExtra = show;
991       
992       this.drawRects();
993       return this;
994     }
995     
996     this.setRectColor = function(rectColorFun) {
997       if (arguments.length == 0) {
998 	return rectColor;
999       }
1000       rectColor = rectColorFun;
1001       this.drawRects();
1002       return this;
1003     }
1004     
1005     ///////////////
1006     function positionX(x) {
1007       return toLeft ? width/2-x : width/2+ x;
1008     }
1009     function positionY(y) {
1010       return y -dx;
1011     }
1012     
1013     
1014     
1015     ////default modifier handlers
1016     this.handleAltPress = function() {};
1017     this.handleShifttPress = function() {};
1018     
1019     this.readJSONTree(data);
1020     return this;
1021   }
1022   
1023 
1024 
1025   ///////////////////////////////// tree sorting functions
1026   /**
1027    * function to sort the nodes (case insenstive) by a field in the information object
1028    * @param fld the field to sort by
1029    */
1030   doubletree.sortByStrFld = function(fld) {
1031     var field = fld;
1032     return function(a,b) {
1033 	var aUndefined = (undefined == a.info[field]);
1034 	var bUndefined = (undefined == b.info[field]);
1035 	if (aUndefined && bUndefined) {
1036 	  return 0;
1037 	} else if (aUndefined) {
1038 	  return -1;
1039 	} else if (bUndefined) {
1040 	  return 1;
1041 	}
1042 	var aVal = a.info[field].join(" ").toLowerCase();
1043 	var bVal = b.info[field].join(" ").toLowerCase();
1044 	  if (aVal < bVal) {
1045 	    return -1;
1046 	  } else if (aVal > bVal) {
1047 	    return 1;
1048 	  }
1049 	  return 0;
1050       }
1051   }
1052   /**
1053    * function to sort the nodes according to the count field in the information object
1054    */
1055   doubletree.sortByCount = function() {
1056     return function(a,b) {
1057 	return b.info.count - a.info.count;
1058     }
1059   }
1060   
1061   /**
1062    * function to sort the nodes according to the continuations field in the information object
1063    */
1064   doubletree.sortByContinuations = function() {
1065     return function(a,b) {
1066 	return b.info.continuations - a.info.continuations;
1067     }
1068   }
1069   
1070   
1071   ///////////////////////////////// some tree filtering functions
1072   /**
1073    * function to filter the nodes according to a minimum for the count field
1074    * @param n the minimum count to include
1075    */
1076   doubletree.filterByMinCount = function(n) {
1077       return function(inf) { return inf.count >= n;};
1078   }
1079   
1080   /**
1081    * function to filter the nodes according to a maximum for the count field
1082    * @param n the maximum count to include
1083    */
1084   doubletree.filterByMaxCount = function(n) {
1085       return function(inf) { return inf.count <= n;};
1086   }
1087   
1088   /**
1089    * function to filter the nodes according to the "POS" field (if it exists)
1090    * @param n a string for a regular expression of the POS values to include
1091    */
1092   doubletree.filterByPOS = function(pos) {
1093     var re = new RegExp(pos);
1094     return function(inf) {
1095       return inf["POS"] && inf["POS"].filter(function(p) {
1096 	  return p.search(re) > -1;
1097 	}).length > 0; //end of ng has no POS
1098       }
1099   }
1100   
1101   ///////////////////////////////// formatting functions
1102 
1103   //doubletree.nodeText = function(info) {
1104   //  return doubletree.tokenText(info); //default
1105   //}
1106   
1107   //extracts a field
1108   /**
1109    * return the value of a field in the provided information object
1110    * @param info the information object
1111    * @param the field to get
1112    * @returns the value of the field in the information object
1113    */
1114   doubletree.fieldText = function(info, fieldName) {
1115     return info[fieldName];
1116   }
1117   //extracts the "token" field
1118   /**
1119    * convenience function to return the value of the "token" field (if it exists). The same as doubletree.fieldText(info, "token")
1120    * @param info the information object
1121    * @returns the value of the "token" field of the information object
1122    */
1123   doubletree.tokenText = function(info) {
1124     return doubletree.fieldText(info, "token");
1125   }
1126   
1127   /**
1128    * converts an information object to a string
1129    * @param the information object
1130    * @returns a string with one key/value pair per line
1131    */
1132   doubletree.infoToText = function(info) {
1133       var what = "";
1134       for(var infp in info) {
1135 	if (infp == "ids" || infp == "origIDs") {
1136 	  what += infp + "\t:\t" + Object.keys( info[infp] ).join(",") + "\n";
1137 	} else {
1138 	  what += (infp + "\t:\t" + info[infp] + "\n");
1139 	}
1140       }
1141       return what;
1142   }
1143   ////////////////// internal utility functions
1144 
1145   function old_pruneTree(tree, ids) {
1146     
1147     if (! tree.children) {
1148         return;
1149     }
1150     
1151     var n = tree.children.length;
1152     for(var i=0;i<n;i++) {
1153         var c = tree.children[i];
1154         
1155         if (containedIn(c.info.ids, ids)) {
1156             tree.children[i] = null;
1157         } else {
1158             old_pruneTree(c, ids);
1159         }
1160     }
1161     tree.children = tree.children.filter(function(c) { return c != null});
1162     
1163     //recalculate maxChildren
1164     var cMax = d3.max( tree.children.map(function(c) {return c.maxChildren;}) );
1165     tree.maxChildren = Math.max(tree.children.length, cMax);
1166   }
1167   
1168   
1169   function new_pruneTree(tree, ids, copyIDs) {
1170     
1171     if (! tree.children) {
1172         return;
1173     }
1174     
1175     //copy over original ids
1176     if (copyIDs) {
1177       if (! tree.info.origIDs) {
1178         tree.info.origIDs = {};
1179         addTo(tree.info.origIDs, tree.info.ids);
1180         tree.info.origCount = Object.keys(tree.info.origIDs).length;
1181       } else {
1182         tree.info.ids = {};
1183         addTo(tree.info.ids, tree.info.origIDs);
1184         tree.info.count = Object.keys(tree.info.ids).length;
1185       }
1186     }
1187    
1188     
1189     //adjust IDs
1190     var idNums = Object.keys(ids)
1191     for(var i=0, n=idNums.length;i<n;i++) {
1192       var cid = idNums[i];
1193       delete tree.info.ids[cid];
1194     }
1195     tree.info.count = Object.keys(tree.info.ids).length;
1196     
1197     //recurse and prune
1198     var n = tree.children.length;
1199     for(var i=0;i<n;i++) {
1200         var c = tree.children[i];
1201         
1202         if (containedIn(c.info.ids, ids)) {
1203             tree.children[i] = null;
1204         } else {
1205             new_pruneTree(c, ids, false);
1206         }
1207     }
1208     tree.children = tree.children.filter(function(c) { return c != null});
1209     tree.info.continuations = tree.children.length;
1210     
1211     //recalculate maxChildren
1212     var cMax = d3.max( tree.children.map(function(c) {return c.maxChildren;}) );
1213     tree.maxChildren = Math.max(tree.children.length, cMax);
1214   }
1215   
1216   function restoreTree(tree) {
1217     
1218       if (tree.info.origCount) {  //otherwise tree was suppressed, so its ids never got switched around
1219         //restore originals
1220         tree.info.ids = {};
1221         addTo(tree.info.ids, tree.info.origIDs);
1222         //delete tree.info.origIDs;
1223         tree.info.count = tree.info.origCount;
1224         //delete tree.info.origCount;
1225         
1226         var n = tree.children.length;
1227         tree.info.continuations = n;
1228         for(var i=0;i<n;i++) {
1229             var c = tree.children[i];
1230             restoreTree(c);
1231         }
1232       }
1233   
1234   }
1235   
1236   //do the keys in o1 and o2 overlap
1237   function overlap(o1, o2) {
1238       for(var k in o1) {
1239 	  if (k in o2) {
1240 	      return true;
1241 	  }
1242       }
1243       return false;
1244   }
1245   //are all the keys in o1 also in o2
1246   function containedIn(o1, o2) {
1247       if (! o1 || ! o2) {
1248 	  return false;
1249       }
1250       for(var k in o1) {
1251 	  if (! (k in o2)) {
1252 	      return false;
1253 	  }
1254       }
1255       return true; 
1256   }
1257   
1258   //add key/vals of o2 to o1 and return o1; (top level key-value only, o2 values maintained over o1)
1259   //same as in Trie.js
1260   function addTo(o1, o2) {
1261       for(var k in o2) {
1262           o1[k] = o2[k];
1263       }
1264   }
1265 
1266   function noOp() {}
1267 
1268   
1269   //////////////////
1270 
1271 
1272 })();