001    /* VariableHeightLayoutCache.java --
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.ArrayList;
044    import java.util.Enumeration;
045    import java.util.HashSet;
046    import java.util.Hashtable;
047    import java.util.LinkedList;
048    import java.util.Set;
049    import java.util.Vector;
050    
051    import 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     */
063    public 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    }