001/* FixedHeightLayoutCache.java -- Fixed cell height tree layout cache
002Copyright (C) 2002, 2004, 2006,  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038package javax.swing.tree;
039
040import gnu.javax.swing.tree.GnuPath;
041
042import java.awt.Rectangle;
043import java.util.Enumeration;
044import java.util.HashSet;
045import java.util.Hashtable;
046import java.util.LinkedList;
047import java.util.Set;
048import java.util.Vector;
049
050import 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 */
063public 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<Object> lpath = new LinkedList<Object>();
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<Object> expanded = new HashSet<Object>();
177  
178  /**
179   * Maps nodes to the row numbers.
180   */
181  Hashtable<Object,NodeRecord> nodes = new Hashtable<Object,NodeRecord>();
182  
183  /**
184   * Maps row numbers to nodes.
185   */
186  Hashtable<Integer,Object> row2node = new Hashtable<Integer,Object>();
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 = 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 = 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 = 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<NodeRecord> en = nodes.elements();
417    
418    int dist = Integer.MAX_VALUE;
419
420    while (en.hasMoreElements() && dist > 0)
421      {
422        r = 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 paths 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 = 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<NodeRecord> en = nodes.elements();
587    while (en.hasMoreElements())
588      {
589        NodeRecord nr = 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<NodeRecord> en = nodes.elements();
606    while (en.hasMoreElements())
607      {
608        NodeRecord nr = 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}