001/* VariableHeightLayoutCache.java --
002   Copyright (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.ArrayList;
044import java.util.Enumeration;
045import java.util.HashSet;
046import java.util.Hashtable;
047import java.util.LinkedList;
048import java.util.Set;
049import java.util.Vector;
050
051import javax.swing.event.TreeModelEvent;
052
053/**
054 * The fixed height tree layout. This class requires the NodeDimensions to be
055 * set and ignores the row height property.
056 * 
057 * @specnote the methods, of this class, returning TreePath, actually returns
058 * the derived class GnuPath that provides additional information for optimized
059 * painting. See the GnuPath code for details.
060 * 
061 * @author Audrius Meskauskas
062 */
063public class VariableHeightLayoutCache
064  extends AbstractLayoutCache
065{
066
067  private static final Rectangle RECT_CACHE = new Rectangle();
068
069  /**
070   * The cached node record.
071   */
072  class NodeRecord
073  {
074    NodeRecord(int aRow, int aDepth, Object aNode, Object aParent)
075    {
076      row = aRow;
077      depth = aDepth;
078      parent = aParent;
079      node = aNode;
080      isExpanded = expanded.contains(aNode);
081      bounds = new Rectangle(0, -1, 0, 0);
082    }
083    
084    /**
085     * The row, where the tree node is displayed.
086     */
087    final int row;    
088    
089    /**
090     * The nesting depth
091     */
092    final int depth;
093    
094    /**
095     * The parent of the given node, null for the root node.
096     */
097    final Object parent;
098    
099    /**
100     * This node.
101     */
102    final Object node;
103    
104    /**
105     * True for the expanded nodes. The value is calculated in constructor.
106     * Using this field saves one hashtable access operation.
107     */
108    final boolean isExpanded;
109
110    /**
111     * The cached bounds of the tree row.
112     */
113    Rectangle bounds;
114    
115    /**
116     * The path from the tree top to the given node (computed under first
117     * demand)
118     */
119    private TreePath path;
120    
121    /**
122     * Get the path for this node. The derived class is returned, making check
123     * for the last child of some parent easier.
124     */
125    TreePath getPath()
126    {
127      if (path == null)
128        {
129          boolean lastChild = false;
130          if (parent != null)
131            {
132              int nc = treeModel.getChildCount(parent);
133              if (nc > 0)
134                {
135                  int n = treeModel.getIndexOfChild(parent, node);
136                  if (n == nc - 1)
137                    lastChild = true;
138                }
139            }
140
141          LinkedList<Object> lpath = new LinkedList<Object>();
142          NodeRecord rp = this;
143          while (rp != null)
144            {
145              lpath.addFirst(rp.node);
146              if (rp.parent != null)
147                {
148                  Object parent = rp.parent;
149                  rp = nodes.get(parent);
150                  // Add the root node, even if it is not visible.
151                  if (rp == null)
152                    lpath.addFirst(parent);
153                }
154              else
155                rp = null;
156            }
157          path = new GnuPath(lpath.toArray(), lastChild);
158        }
159      return path;
160    }
161    
162    /**
163     * Get the rectangle bounds (compute, if required).
164     */
165    Rectangle getBounds()
166    {
167      return bounds;      
168    }
169  }
170  
171  /**
172   * The set of all expanded tree nodes.
173   */
174  Set<Object> expanded = new HashSet<Object>();
175  
176  /**
177   * Maps nodes to the row numbers.
178   */
179  Hashtable<Object,NodeRecord> nodes = new Hashtable<Object,NodeRecord>();
180  
181  /**
182   * Maps row numbers to nodes.
183   */
184  ArrayList<Object> row2node = new ArrayList<Object>();
185  
186  /**
187   * If true, the row map must be recomputed before using.
188   */
189  boolean dirty;
190  
191  /**
192   * The cumulative height of all rows.
193   */
194  int totalHeight;
195  
196  /**
197   * The maximal width.
198   */
199  int maximalWidth;
200
201  /**
202   * Creates the unitialised instance. Before using the class, the row height
203   * must be set with the {@link #setRowHeight(int)} and the model must be set
204   * with {@link #setModel(TreeModel)}. The node dimensions may not be set.
205   */
206  public VariableHeightLayoutCache()
207  {
208    // Nothing to do here.
209  } 
210
211  /**
212   * Get the total number of rows in the tree. Every displayed node occupies the
213   * single row. The root node row is included if the root node is set as
214   * visible (false by default).
215   * 
216   * @return int the number of the displayed rows.
217   */
218  public int getRowCount()
219  {
220    if (dirty) update();
221    return row2node.size();
222  } 
223  
224  /**
225   * Refresh the row map.
226   */
227  private final void update()
228  {
229    nodes.clear();
230    row2node.clear();
231    
232    totalHeight = maximalWidth = 0;
233
234    if (treeModel == null)
235      return;
236
237    Object root = treeModel.getRoot();
238    countRows(root, null, 0, 0);
239    dirty = false;
240  }
241  
242  /**
243   * Recursively counts all rows in the tree.
244   */
245  private final int countRows(Object node, Object parent, int depth, int y)
246  {
247    boolean visible = node != treeModel.getRoot() || rootVisible;
248    int row = row2node.size();
249    if (visible)
250      {
251        row2node.add(node);
252      }
253    NodeRecord nr = new NodeRecord(row, depth, node, parent);
254    NodeDimensions d = getNodeDimensions();
255    Rectangle r = RECT_CACHE;
256    if (d != null)
257      r = d.getNodeDimensions(node, row, depth, nr.isExpanded, r);
258    else
259      r.setBounds(0, 0, 0, 0);
260
261    if (! visible)
262      r.y = -1;
263    else
264      r.y = Math.max(0, y);
265
266    if (isFixedRowHeight())
267      r.height = getRowHeight();
268
269    nr.bounds.setBounds(r);
270    nodes.put(node, nr);
271
272    if (visible)
273      y += r.height;
274
275    int sc = treeModel.getChildCount(node);
276    int deeper = depth + 1;
277    if (expanded.contains(node))
278      {
279        for (int i = 0; i < sc; i++)
280          {
281            Object child = treeModel.getChild(node, i);
282            y = countRows(child, node, deeper, y);
283          }
284      }
285    return y;
286  }
287
288  /**
289   * Discard the bound information for the given path.
290   * 
291   * @param path the path, for that the bound information must be recomputed.
292   */
293  public void invalidatePathBounds(TreePath path)
294  {
295    NodeRecord r = nodes.get(path.getLastPathComponent());
296    if (r != null)
297      r.bounds = null;
298  } 
299
300  /**
301   * Mark all cached information as invalid.
302   */
303  public void invalidateSizes()
304  {
305    dirty = true;
306  } 
307
308  /**
309   * Set the expanded state of the given path. The expansion states must be
310   * always updated when expanding and colapsing the tree nodes. Otherwise 
311   * other methods will not work correctly after the nodes are collapsed or
312   * expanded.
313   *
314   * @param path the tree path, for that the state is being set.
315   * @param isExpanded the expanded state of the given path.
316   */
317  public void setExpandedState(TreePath path, boolean isExpanded)
318  {
319    if (isExpanded)
320      {
321        int length = path.getPathCount();
322        for (int i = 0; i < length; i++)
323          expanded.add(path.getPathComponent(i));
324      }
325    else
326      expanded.remove(path.getLastPathComponent());
327
328    dirty = true;
329  }
330  
331  /**
332   * Get the expanded state for the given tree path.
333   * 
334   * @return true if the given path is expanded, false otherwise.
335   */
336  public boolean isExpanded(TreePath path)
337  {
338    return expanded.contains(path.getLastPathComponent());
339  } 
340
341  /**
342   * Get bounds for the given tree path.
343   * 
344   * @param path the tree path
345   * @param rect the rectangle that will be reused to return the result.
346   * @return Rectangle the bounds of the last line, defined by the given path.
347   */
348  public Rectangle getBounds(TreePath path, Rectangle rect)
349  {
350    if (path == null)
351      return null;
352    if (dirty)
353      update();
354
355    Object last = path.getLastPathComponent();
356    Rectangle result = null;
357    NodeRecord r = nodes.get(last);
358    if (r != null)
359      {
360        // The RI allows null arguments for rect, in which case a new Rectangle
361        // is created.
362        result = rect;
363        if (result == null)
364          result = new Rectangle(r.bounds);
365        else
366          result.setBounds(r.bounds);
367      }
368    return result;
369  } 
370
371  /**
372   * Get the path, the last element of that is displayed in the given row.
373   * 
374   * @param row the row
375   * @return TreePath the path
376   */
377  public TreePath getPathForRow(int row)
378  {
379    if (dirty)
380      update();
381
382    TreePath path = null;
383    // Search row in the nodes map. TODO: This is inefficient, optimize this.
384    Enumeration nodesEnum = nodes.elements();
385    while (nodesEnum.hasMoreElements() && path == null)
386      {
387        NodeRecord record = (NodeRecord) nodesEnum.nextElement();
388        if (record.row == row)
389          path = record.getPath();
390      }
391    return path;
392  } 
393
394  /**
395   * Get the row, displaying the last node of the given path.
396   * 
397   * @param path the path
398   * @return int the row number or -1 if the end of the path is not visible.
399   */
400  public int getRowForPath(TreePath path)
401  {
402    if (path == null)
403      return -1;
404
405    if (dirty)
406      update();
407
408    NodeRecord r = nodes.get(path.getLastPathComponent());
409    if (r == null)
410      return - 1;
411    else
412      return r.row;
413  } 
414
415  /**
416   * Get the path, closest to the given point.
417   * 
418   * @param x the point x coordinate
419   * @param y the point y coordinate
420   * @return the tree path, closest to the the given point
421   */
422  public TreePath getPathClosestTo(int x, int y)
423  {
424    if (dirty)
425      update();
426
427    // As the rows have arbitrary height, we need to iterate.
428    NodeRecord best = null;
429    NodeRecord r;
430    Enumeration<NodeRecord> en = nodes.elements();
431    
432    int dist = Integer.MAX_VALUE;
433
434    while (en.hasMoreElements() && dist > 0)
435      {
436        r = en.nextElement();
437        if (best == null)
438          {
439            best = r;
440            dist = distance(r.getBounds(), x, y);
441          }
442        else
443          {
444            int rr = distance(r.getBounds(), x, y);
445            if (rr < dist)
446              {
447                best = r;
448                dist = rr;
449              }
450          }
451      }
452
453    if (best == null)
454      return null;
455    else
456      return best.getPath();
457  } 
458  
459  /**
460   * Get the closest distance from this point till the given rectangle. Only
461   * vertical distance is taken into consideration.
462   */
463  int distance(Rectangle r, int x, int y)
464  {
465    if (y < r.y)
466      return r.y - y;
467    else if (y > r.y + r.height - 1)
468      return y - (r.y + r.height - 1);
469    else
470      return 0;
471  }
472
473  /**
474   * Get the number of the visible childs for the given tree path. If the node
475   * is not expanded, 0 is returned. Otherwise, the number of children is
476   * obtained from the model as the number of children for the last path
477   * component.
478   * 
479   * @param path the tree path
480   * @return int the number of the visible childs (for row).
481   */
482  public int getVisibleChildCount(TreePath path)  
483  {
484    if (! isExpanded(path) || treeModel == null)
485      return 0; 
486    else
487      return treeModel.getChildCount(path.getLastPathComponent());
488  } 
489
490  /**
491   * Get the enumeration over all visible paths that start from the given
492   * parent path.
493   * 
494   * @param parentPath the parent path
495   * @return the enumeration over pathes
496   */
497  public Enumeration<TreePath> getVisiblePathsFrom(TreePath parentPath)
498  {
499    if (dirty)
500      update();
501    Vector p = new Vector(parentPath.getPathCount());
502    Object node;
503    NodeRecord nr;
504
505    for (int i = 0; i < parentPath.getPathCount(); i++)
506      {
507        node = parentPath.getPathComponent(i);
508        nr = nodes.get(node);
509        if (nr != null && nr.row >= 0)
510          p.add(node);
511      }
512    return p.elements();
513  }
514
515  /**
516   * Return the expansion state of the given tree path. The expansion state
517   * must be previously set with the 
518   * {@link #setExpandedState(TreePath, boolean)}
519   * 
520   * @param path the path being checked
521   * @return true if the last node of the path is expanded, false otherwise.
522   */
523  public boolean getExpandedState(TreePath path)
524  {
525    return expanded.contains(path.getLastPathComponent());
526  }
527
528  /**
529   * The listener method, called when the tree nodes are changed.
530   * 
531   * @param event the change event
532   */
533  public void treeNodesChanged(TreeModelEvent event)
534  {
535    dirty = true;
536  } 
537
538  /**
539   * The listener method, called when the tree nodes are inserted.
540   * 
541   * @param event the change event
542   */
543  public void treeNodesInserted(TreeModelEvent event)
544  {
545    dirty = true;
546  } 
547
548  /**
549   * The listener method, called when the tree nodes are removed.
550   * 
551   * @param event the change event
552   */
553  public void treeNodesRemoved(TreeModelEvent event)
554  {
555    dirty = true;
556  } 
557
558  /**
559   * Called when the tree structure has been changed. 
560   * 
561   * @param event the change event
562   */
563  public void treeStructureChanged(TreeModelEvent event)
564  {
565    dirty = true;
566  } 
567  
568  /**
569   * Set the tree model that will provide the data.
570   */
571  public void setModel(TreeModel newModel)
572  {
573    treeModel = newModel;
574    dirty = true;
575    if (treeModel != null)
576      {
577        // The root node is expanded by default.
578        expanded.add(treeModel.getRoot());
579      }
580  }
581  
582  /**
583   * Inform the instance if the tree root node is visible. If this method
584   * is not called, it is assumed that the tree root node is not visible.
585   * 
586   * @param visible true if the tree root node is visible, false
587   * otherwise.
588   */
589  public void setRootVisible(boolean visible)
590  {
591    rootVisible = visible;
592    dirty = true;
593  }
594
595  /**
596   * Get the sum of heights for all rows.
597   */
598  public int getPreferredHeight()
599  {
600    if (dirty)
601      update();
602    int height = 0;
603    int rowCount = getRowCount();
604    if (rowCount > 0)
605      {
606        NodeRecord last = nodes.get(row2node.get(rowCount - 1));
607        height = last.bounds.y + last.bounds.height;
608      }
609    return height;
610  }
611
612  /**
613   * Get the maximal width.
614   */
615  public int getPreferredWidth(Rectangle value)
616  {
617    if (dirty)
618      update();
619    
620    maximalWidth = 0;
621    Enumeration<NodeRecord> en = nodes.elements();
622    while (en.hasMoreElements())
623      {
624        NodeRecord nr = en.nextElement();
625        if (nr != null)
626          {
627            Rectangle r = nr.getBounds();
628            int width = r.x + r.width;
629            if (width > maximalWidth)
630              maximalWidth = width;
631          }
632      }
633    return maximalWidth;
634  }
635
636  /**
637   * Sets the node dimensions and invalidates the cached layout.
638   *
639   * @param dim the dimensions to set
640   */
641  public void setNodeDimensions(NodeDimensions dim)
642  {
643    super.setNodeDimensions(dim);
644    dirty = true;
645  }
646
647  /**
648   * Sets the row height and marks the layout as invalid.
649   *
650   * @param height the row height to set
651   */
652  public void setRowHeight(int height)
653  {
654    super.setRowHeight(height);
655    dirty = true;
656  }
657}