001    /* FixedHeightLayoutCache.java -- Fixed cell height tree layout cache
002    Copyright (C) 2002, 2004, 2006,  Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package javax.swing.tree;
039    
040    import gnu.javax.swing.tree.GnuPath;
041    
042    import java.awt.Rectangle;
043    import java.util.Enumeration;
044    import java.util.HashSet;
045    import java.util.Hashtable;
046    import java.util.LinkedList;
047    import java.util.Set;
048    import java.util.Vector;
049    
050    import javax.swing.event.TreeModelEvent;
051    
052    
053    /**
054     * The fixed height tree layout. This class assumes that all cells in the tree
055     * have the same fixed height. This may be not the case, for instance, if leaves
056     * and branches have different height, of if the tree rows may have arbitrary
057     * variable height. This class will also work if the NodeDimensions are not
058     * set.  
059     * 
060     * @author Audrius Meskauskas
061     * @author Andrew Selkirk 
062     */
063    public class FixedHeightLayoutCache
064                    extends VariableHeightLayoutCache
065    {
066      /**
067       * The cached node record.
068       */
069      class NodeRecord
070      {
071        NodeRecord(int aRow, int aDepth, Object aNode, Object aParent)
072        {
073          row = aRow;
074          depth = aDepth;
075          parent = aParent;
076          node = aNode;
077          
078          isExpanded = expanded.contains(aNode); 
079        }
080        
081        /**
082         * The row, where the tree node is displayed.
083         */
084        final int row;    
085        
086        /**
087         * The nesting depth
088         */
089        final int depth;
090        
091        /**
092         * The parent of the given node, null for the root node.
093         */
094        final Object parent;
095        
096        /**
097         * This node.
098         */
099        final Object node;
100        
101        /**
102         * True for the expanded nodes. The value is calculated in constructor.
103         * Using this field saves one hashtable access operation.
104         */
105        final boolean isExpanded;
106        
107        /**
108         * The cached bounds of the tree row.
109         */
110        Rectangle bounds;
111        
112        /**
113         * The path from the tree top to the given node (computed under first
114         * demand)
115         */
116        private TreePath path;
117        
118        /**
119         * Get the path for this node. The derived class is returned,
120         * making check for the last child of some parent easier.
121         */
122        TreePath getPath()
123        {
124          if (path == null)
125            {
126              boolean lastChild = false;
127              if (parent != null)
128                {
129                  int nc = treeModel.getChildCount(parent);
130                  if (nc > 0)
131                    {
132                      int n = treeModel.getIndexOfChild(parent, node);
133                      if (n == nc - 1)
134                        lastChild = true;
135                    }
136                }
137    
138              LinkedList lpath = new LinkedList();
139              NodeRecord rp = this;
140              while (rp != null)
141                {
142                  lpath.addFirst(rp.node);
143                  if (rp.parent != null)
144                    {
145                      Object parent = rp.parent;
146                      rp = (NodeRecord) nodes.get(parent);
147                      // Add the root node, even if it is not visible.
148                      if (rp == null)
149                        lpath.addFirst(parent);
150                    }
151                  else
152                    rp = null;
153                }
154              path = new GnuPath(lpath.toArray(), lastChild);
155            }
156          return path;
157        }
158        
159        /**
160         * Get the rectangle bounds (compute, if required).
161         */
162        Rectangle getBounds()
163        {
164          // This method may be called in the context when the tree rectangle is
165          // not known. To work around this, it is assumed near infinitely large.
166          if (bounds == null)
167            bounds = getNodeDimensions(node, row, depth, isExpanded, 
168                                       new Rectangle());
169          return bounds;      
170        }
171      }
172      
173      /**
174       * The set of all expanded tree nodes.
175       */
176      Set expanded = new HashSet();
177      
178      /**
179       * Maps nodes to the row numbers.
180       */
181      Hashtable nodes = new Hashtable();
182      
183      /**
184       * Maps row numbers to nodes.
185       */
186      Hashtable row2node = new Hashtable();
187      
188      /**
189       * If true, the row map must be recomputed before using.
190       */
191      boolean dirty;
192      
193      /**
194       * The cumulative height of all rows.
195       */
196      int totalHeight;
197      
198      /**
199       * The maximal width.
200       */
201      int maximalWidth;
202    
203      /**
204       * Creates the unitialised instance. Before using the class, the row height
205       * must be set with the {@link #setRowHeight(int)} and the model must be set
206       * with {@link #setModel(TreeModel)}. The node dimensions may not be set.
207       */
208      public FixedHeightLayoutCache()
209      {
210        // Nothing to do here.
211      } 
212    
213      /**
214       * Get the total number of rows in the tree. Every displayed node occupies the
215       * single row. The root node row is included if the root node is set as
216       * visible (false by default).
217       * 
218       * @return int the number of the displayed rows.
219       */
220      public int getRowCount()
221      {
222        if (dirty) update();
223        return row2node.size();
224      } 
225      
226      /**
227       * Refresh the row map.
228       */
229      private final void update()
230      {
231        nodes.clear();
232        row2node.clear();
233        
234        totalHeight = maximalWidth = 0;
235    
236        Object root = treeModel.getRoot();
237    
238        if (rootVisible)
239          {
240            countRows(root, null, 0);
241          }
242        else
243          {
244            int sc = treeModel.getChildCount(root);
245            for (int i = 0; i < sc; i++)
246              {
247                Object child = treeModel.getChild(root, i);
248                countRows(child, root, 0);
249              }
250          }
251        dirty = false;
252      }
253      
254      /**
255       * Recursively counts all rows in the tree.
256       */
257      private final void countRows(Object node, Object parent, int depth)
258      {
259        Integer n = new Integer(row2node.size());
260        row2node.put(n, node);
261        
262        NodeRecord nr = new NodeRecord(n.intValue(), depth, node, parent);
263        nodes.put(node, nr);
264         
265        // For expanded nodes and for the root node.
266        if (expanded.contains(node))
267          {
268            int sc = treeModel.getChildCount(node);
269            int deeper = depth + 1;
270            for (int i = 0; i < sc; i++)
271              {
272                Object child = treeModel.getChild(node, i);
273                countRows(child, node, deeper);
274              }
275          }
276      }
277    
278      /**
279       * Discard the bound information for the given path.
280       * 
281       * @param path the path, for that the bound information must be recomputed.
282       */
283      public void invalidatePathBounds(TreePath path)
284      {
285        NodeRecord r = (NodeRecord) nodes.get(path.getLastPathComponent());
286        if (r != null)
287          r.bounds = null;
288      } 
289    
290      /**
291       * Mark all cached information as invalid.
292       */
293      public void invalidateSizes()
294      {
295        dirty = true;
296      } 
297    
298      /**
299       * Set the expanded state of the given path. The expansion states must be
300       * always updated when expanding and colapsing the tree nodes. Otherwise 
301       * other methods will not work correctly after the nodes are collapsed or
302       * expanded.
303       *
304       * @param path the tree path, for that the state is being set.
305       * @param isExpanded the expanded state of the given path.
306       */
307      public void setExpandedState(TreePath path, boolean isExpanded)
308      {
309        if (isExpanded)
310          expanded.add(path.getLastPathComponent());
311        else
312          expanded.remove(path.getLastPathComponent());
313        
314        dirty = true;
315      }
316      
317      /**
318       * Get the expanded state for the given tree path.
319       * 
320       * @return true if the given path is expanded, false otherwise.
321       */
322      public boolean isExpanded(TreePath path)
323      {
324        return expanded.contains(path.getLastPathComponent());
325      } 
326    
327      /**
328       * Get bounds for the given tree path.
329       * 
330       * @param path the tree path
331       * @param rect the rectangle that will be reused to return the result.
332       * @return Rectangle the bounds of the last line, defined by the given path.
333       */
334      public Rectangle getBounds(TreePath path, Rectangle rect)
335      {
336        if (path == null)
337          return null;
338        if (dirty)
339          update();
340        Object last = path.getLastPathComponent();
341        NodeRecord r = (NodeRecord) nodes.get(last);
342        if (r == null)
343        // This node is not visible.
344          {
345            rect.x = rect.y = rect.width = rect.height = 0;
346          }
347        else
348          {
349            if (r.bounds == null)
350              {
351                Rectangle dim = getNodeDimensions(last, r.row, r.depth,
352                                                  r.isExpanded, rect);
353                r.bounds = dim;
354              }
355    
356            rect.setRect(r.bounds);
357          }
358        return rect;
359      } 
360    
361      /**
362       * Get the path, the last element of that is displayed in the given row.
363       * 
364       * @param row the row
365       * @return TreePath the path
366       */
367      public TreePath getPathForRow(int row)
368      {
369        if (dirty)
370          update();
371        Object last = row2node.get(new Integer(row));
372        if (last == null)
373          return null;
374        else
375          {
376            NodeRecord r = (NodeRecord) nodes.get(last);
377            return r.getPath();
378          }
379      } 
380    
381      /**
382       * Get the row, displaying the last node of the given path.
383       * 
384       * @param path the path
385       * @return int the row number or -1 if the end of the path is not visible.
386       */
387      public int getRowForPath(TreePath path)
388      {
389        if (path == null)
390          return -1;
391        
392        if (dirty) update();
393    
394        NodeRecord r = (NodeRecord) nodes.get(path.getLastPathComponent());
395        if (r == null)
396          return - 1;
397        else
398          return r.row;
399      } 
400    
401      /**
402       * Get the path, closest to the given point.
403       * 
404       * @param x the point x coordinate
405       * @param y the point y coordinate
406       * @return the tree path, closest to the the given point
407       */
408      public TreePath getPathClosestTo(int x, int y)
409      {
410        if (dirty)
411          update();
412    
413        // As the rows have arbitrary height, we need to iterate.
414        NodeRecord best = null;
415        NodeRecord r;
416        Enumeration en = nodes.elements();
417        
418        int dist = Integer.MAX_VALUE;
419    
420        while (en.hasMoreElements() && dist > 0)
421          {
422            r = (NodeRecord) en.nextElement();
423            if (best == null)
424              {
425                best = r;
426                dist = distance(r.getBounds(), x, y);
427              }
428            else
429              {
430                int rr = distance(r.getBounds(), x, y);
431                if (rr < dist)
432                  {
433                    best = r;
434                    dist = rr;
435                  }
436              }
437          }
438    
439        if (best == null)
440          return null;
441        else
442          return best.getPath();
443      } 
444      
445      /**
446       * Get the closest distance from this point till the given rectangle. Only
447       * vertical distance is taken into consideration.
448       */
449      int distance(Rectangle r, int x, int y)
450      {
451        if (y < r.y)
452          return r.y - y;
453        else if (y > r.y + r.height)
454          return y - (r.y + r.height);
455        else
456          return 0;
457      }
458    
459      /**
460       * Get the number of the visible childs for the given tree path. If the node
461       * is not expanded, 0 is returned. Otherwise, the number of children is
462       * obtained from the model as the number of children for the last path
463       * component.
464       * 
465       * @param path the tree path
466       * @return int the number of the visible childs (for row).
467       */
468      public int getVisibleChildCount(TreePath path)  
469      {
470        if (isExpanded(path))
471          return 0; 
472        else
473          return treeModel.getChildCount(path.getLastPathComponent());
474      } 
475    
476      /**
477       * Get the enumeration over all visible pathes that start from the given
478       * parent path.
479       * 
480       * @param parentPath the parent path
481       * @return the enumeration over pathes
482       */
483      public Enumeration<TreePath> getVisiblePathsFrom(TreePath parentPath)
484      {
485        if (dirty)
486          update();
487        Vector p = new Vector(parentPath.getPathCount());
488        Object node;
489        NodeRecord nr;
490    
491        for (int i = 0; i < parentPath.getPathCount(); i++)
492          {
493            node = parentPath.getPathComponent(i);
494            nr = (NodeRecord) nodes.get(node);
495            if (nr.row >= 0)
496              p.add(node);
497          }
498        return p.elements();
499      }
500    
501      /**
502       * Return the expansion state of the given tree path. The expansion state
503       * must be previously set with the 
504       * {@link #setExpandedState(TreePath, boolean)}
505       * 
506       * @param path the path being checked
507       * @return true if the last node of the path is expanded, false otherwise.
508       */
509      public boolean getExpandedState(TreePath path)
510      {
511        return expanded.contains(path.getLastPathComponent());
512      }
513    
514      /**
515       * The listener method, called when the tree nodes are changed.
516       * 
517       * @param event the change event
518       */
519      public void treeNodesChanged(TreeModelEvent event)
520      {
521        dirty = true;
522      } 
523    
524      /**
525       * The listener method, called when the tree nodes are inserted.
526       * 
527       * @param event the change event
528       */
529      public void treeNodesInserted(TreeModelEvent event)
530      {
531        dirty = true;
532      } 
533    
534      /**
535       * The listener method, called when the tree nodes are removed.
536       * 
537       * @param event the change event
538       */
539      public void treeNodesRemoved(TreeModelEvent event)
540      {
541        dirty = true;
542      } 
543    
544      /**
545       * Called when the tree structure has been changed. 
546       * 
547       * @param event the change event
548       */
549      public void treeStructureChanged(TreeModelEvent event)
550      {
551        dirty = true;
552      } 
553      
554      /**
555       * Set the tree model that will provide the data.
556       */
557      public void setModel(TreeModel newModel)
558      {
559        treeModel = newModel;
560        // The root node is expanded by default.
561        expanded.add(treeModel.getRoot());
562        dirty = true;
563      }
564      
565      /**
566       * Inform the instance if the tree root node is visible. If this method
567       * is not called, it is assumed that the tree root node is not visible.
568       * 
569       * @param visible true if the tree root node is visible, false
570       * otherwise.
571       */
572      public void setRootVisible(boolean visible)
573      {
574        rootVisible = visible;
575        dirty = true;
576      }
577    
578      /**
579       * Get the sum of heights for all rows.
580       */
581      public int getPreferredHeight()
582      {
583        if (dirty)
584          update();
585        totalHeight = 0;
586        Enumeration en = nodes.elements();
587        while (en.hasMoreElements())
588          {
589            NodeRecord nr = (NodeRecord) en.nextElement();
590            Rectangle r = nr.getBounds();
591            totalHeight += r.height;
592          }
593        return totalHeight;
594      }
595    
596      /**
597       * Get the maximal width.
598       */
599      public int getPreferredWidth(Rectangle value)
600      {
601        if (dirty)
602          update();
603        
604        maximalWidth = 0;
605        Enumeration en = nodes.elements();
606        while (en.hasMoreElements())
607          {
608            NodeRecord nr = (NodeRecord) en.nextElement();
609            Rectangle r = nr.getBounds();
610            if (r.x + r.width > maximalWidth)
611              maximalWidth = r.x + r.width;
612          }
613        return maximalWidth;
614      }
615      
616      /**
617       * Returns true if this layout supposes that all rows have the fixed
618       * height.
619       * 
620       * @return boolean true if all rows in the tree must have the fixed
621       * height (true by default).
622       */
623      protected boolean isFixedRowHeight()
624      {
625        return true; 
626      }
627      
628    }