Back to index

wims  3.65+svn20090927
Node.java
Go to the documentation of this file.
00001 /*
00002 $Id: Node.java,v 1.3 2003/02/18 11:48:47 sander Exp $
00003 */
00004 
00005 
00006 /*
00007 Copyright (C) 2001-2002 Mainline Project (I3S - ESSI - CNRS -UNSA)
00008 
00009 This library is free software; you can redistribute it and/or
00010 modify it under the terms of the GNU Lesser General Public
00011 License as published by the Free Software Foundation; either
00012 version 2.1 of the License, or (at your option) any later version.
00013 
00014 This library is distributed in the hope that it will be useful,
00015 but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017 Lesser General Public License for more details.
00018 
00019 You should have received a copy of the GNU Lesser General Public
00020 License along with this library; if not, write to the Free Software
00021 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022 
00023 For further information on the GNU Lesser General Public License,
00024 see: http://www.gnu.org/copyleft/lesser.html
00025 For further information on this library, contact: mainline@essi.fr
00026 */
00027 
00028 
00029 package fr.ove.openmath.jome.model;
00030 
00031 import java.util.*;
00032 import java.io.Serializable;
00033 
00034 
00041 public abstract class Node implements Serializable, Cloneable {
00045     private Node father;
00046 
00050     private Vector children;
00051 
00055     private int rank;
00056     
00060     private int nbStrahler;
00061     
00066     private int depth;
00067     
00068 
00072     public Node() {
00073         father = null;
00074         rank = 0;
00075         nbStrahler = 1;
00076         depth = 0;
00077     }
00078 
00079     // ### The Accessors ###
00080 
00086     public Node getFather() {
00087         return father;
00088     }
00089 
00095     public int getRank() {
00096         return rank;
00097     }
00098 
00105     public Node getChild(int rank) {
00106         Node child = null;
00107         
00108         if (children != null) {
00109             try {
00110                 child = (Node) children.elementAt(rank);
00111             }
00112             catch (ArrayIndexOutOfBoundsException e) {
00113                 return null;
00114             }
00115         }
00116         
00117         return child;
00118     }
00119 
00123     public int getNbChildren() {
00124         int size = 0;
00125         
00126         if (children != null)
00127             size = children.size();
00128             
00129         return size;
00130     }
00131 
00137     public Vector getChildren() {
00138         return children;
00139     }
00140 
00141     // ### The Modifiers ###
00142 
00148     public void setFather(Node father) {
00149         this.father = father;
00150         depth = father.depth + 1;
00151         
00152         // On met à jour maintenant la profondeur des fils éventuels.
00153         if (children != null)
00154             adjustChildrenDepth();
00155     }
00156 
00163     public void addChild(Node child) {
00164         if (children == null)
00165             children = new Vector(0, 1);
00166             
00167         children.addElement(child);
00168         child.setFather(this);
00169         adjustRank();
00170     }
00171 
00179     public void addChild(Node child, int rank) {
00180         if (children == null)
00181             children = new Vector(0, 1);
00182             
00183         children.insertElementAt(child, rank);
00184         child.setFather(this);
00185         adjustRank();
00186     }
00187     
00193     public void removeChild(int rank) {
00194         if (children != null) {
00195             children.removeElementAt(rank);
00196             adjustRank();
00197         }
00198     }
00199 
00205     public void removeChild(Node node) {
00206         if (children != null) {
00207             children.removeElement(node);
00208             adjustRank();
00209         }
00210     }
00211     
00215     public void removeAll() {
00216         if (children != null) {
00217             int count = children.size();
00218             for (int i = 0; i < count; i++)
00219                 ((Node) children.elementAt(rank)).father = null;
00220                 
00221             children.setSize(0);
00222             children.trimToSize();
00223         }
00224     }
00225     
00229     private void adjustRank() {
00230         int i = 0;
00231 
00232         for (Enumeration e = children.elements(); e.hasMoreElements(); i++)
00233             ((Node) e.nextElement()).rank  = i;
00234     }
00235     
00241     private void changeRank(int rank) {
00242         int oldRank = this.rank;
00243         //Node father = this.father;
00244 
00245         if (rank > father.getNbChildren()) {
00246             rank = father.getNbChildren() + 1;
00247             father.addChild(this);  // On ajoute en dernier
00248         }
00249         else {
00250             if (rank < 0)
00251                 rank = 0;
00252             father.addChild(this, rank);
00253         }
00254 
00255         // On élimine le noeud courant situé à l'ancienne position
00256         if (rank < oldRank)
00257             father.removeChild(oldRank + 1);  // l'insertion s'est faite avant, donc le fils courant est décalé de 1
00258         else
00259             father.removeChild(oldRank);
00260     }
00261     
00269     public void moveChildren(Vector list, int rank) {
00270         // Puisque list contient des fils de l'instance, on peut partir du prérequis que
00271         // children est non null.
00272         int NbChildren = children.size();
00273         Node child = null;
00274         Node first = null;
00275         
00276         for (int i = 0; i < list.size(); i++) {
00277             child = (Node) list.elementAt(i);
00278             if (i == 0)
00279                 first = child;
00280             if (rank > NbChildren)
00281                 child.changeRank(rank + (i+1));
00282             else {
00283                 child.changeRank(rank);
00284                 rank = first.getRank() + (i+1);
00285             }
00286         }
00287     }
00288     
00295     public boolean hasChild(Node node) {
00296         boolean hasChild = false;
00297         
00298         if (children != null) 
00299             hasChild = children.contains(node);
00300             
00301         return hasChild;
00302     }
00303     
00309     public synchronized Object clone(){
00310         Node theClone = null;
00311         try {
00312             //return super.clone();
00313             
00314             // On clone l'instance.
00315             theClone = (Node) super.clone();
00316             // Le père du clone est null
00317             theClone.father = null;
00318             if (children != null) {
00319                 // On clone les enfants
00320                 Vector theChildren = new Vector();
00321                 int count = children.size();
00322                 for (int i = 0; i < count; i++)
00323                     theChildren.addElement(((Node) children.elementAt(i)).clone());
00324                 theClone.children = theChildren;
00325             }
00326             
00327         } catch (CloneNotSupportedException e) {
00328             System.out.println("clone failed !!");
00329         }
00330         
00331         return theClone;
00332     }
00333     
00339     public synchronized Object duplicate(){
00340         Node theClone = null;
00341         try {
00342             // On clone l'instance.
00343             theClone = (Node) super.clone();
00344             // Le père du clone est null
00345             theClone.father = null;
00346             // Pas de fils
00347             theClone.children = new Vector();
00348         } catch (CloneNotSupportedException e) {
00349             System.out.println("duplicate failed !!");
00350         }
00351         
00352         return theClone;
00353     }
00354     
00355     
00356     /*
00357     * ############################################
00358     * ### Les différents paramètres de l'arbre ###
00359     * ############################################
00360     */
00361     
00362     /*
00363     * La profondeur de l'arbre
00364     */
00365     
00369     public int getDepth() {
00370         return depth;
00371     }
00372     
00376     public void computeDepth() {
00377         int theDepth = 0;
00378         Node theFather = father;
00379         
00380         while (theFather != null) {
00381             theDepth++;
00382             theFather = theFather.father;
00383         }
00384         
00385         depth = theDepth;
00386         
00387         // On met à jour maintenant la profondeur des fils éventuels.
00388         if (children != null)
00389             adjustChildrenDepth();
00390     }
00391     
00395     private void adjustChildrenDepth() {
00396         Node child = null;
00397         int count = children.size();
00398         for (int i = 0; i < count; i++) {
00399             child = (Node) children.elementAt(i);
00400             //child.depth++;
00401             child.depth = depth + 1;
00402             
00403             // On met à jour maintenant la profondeur des fils éventuels.
00404             if (child.children != null)
00405                 child.adjustChildrenDepth();
00406         }
00407     }
00408     
00409     /*
00410     * Le nombre de Strahler
00411     */
00412     
00416     public int getNbStrahler() {
00417         return nbStrahler;
00418     }
00419     
00426     public void setNbStrahler(int nbStrahler) {
00427         this.nbStrahler = nbStrahler;
00428     }
00429     
00434     private void computeNodeNbStrahler() {
00435         // Si children == null, alors ça veut dire que l'instance est une feuille, et donc le
00436         // Strahler est déjà initialisé à 1.
00437         if (children != null) {
00438             int count = children.size();
00439             if (count == 0)
00440                 // ça c'est au cas où des manipulations sur l'arbre, mais normalement, pas de soucis.
00441                 nbStrahler = 1;
00442             else if (count == 1)
00443                 nbStrahler = ((Node) children.elementAt(0)).nbStrahler;
00444             else {
00445                 int max = 0;
00446                 int min = Integer.MAX_VALUE;
00447                 
00448                 int tmpStrahler;
00449                 
00450                 for (int i = 0; i < count; i++) {
00451                     tmpStrahler = ((Node) children.elementAt(i)).nbStrahler;
00452                     min = (min < tmpStrahler) ? min : tmpStrahler;
00453                     max = (max > tmpStrahler) ? max : tmpStrahler;
00454                 }
00455                 
00456                 int tabLength = max - min + 1;
00457                 int tabValue[] = new int[tabLength];
00458                 
00459                 for (int i = 0; i < tabLength; i++) 
00460                     tabValue[i] = 0;
00461                     
00462                 for (int i = 0; i < count; i++)
00463                     tabValue[((Node) children.elementAt(i)).nbStrahler - min] += 1;
00464                     
00465                 int free = max - 1;
00466                 tmpStrahler = max + tabValue[tabLength - 1] - 1;
00467                 
00468                 int requiered;
00469                 for (int i = tabLength - 2; i >= 0; i--) {
00470                     if (tabValue[i] == 0)
00471                         continue;
00472                         
00473                     requiered = i + min +  tabValue[i] - 1;
00474                     
00475                     if (free > requiered)
00476                         free -= tabValue[i];
00477                     else {
00478                         tmpStrahler += requiered - free;
00479                         free = i + min - 1;
00480                     }
00481                 }
00482                 
00483                 nbStrahler = tmpStrahler;
00484             }
00485         }
00486     }
00487     
00491     public void computeNbStrahler() {
00492         if (children != null) {
00493             int count = children.size();
00494             for (int i = 0; i < count; i++)
00495                 ((Node) children.elementAt(i)).computeNbStrahler();
00496                 
00497             computeNodeNbStrahler();
00498         }
00499     }
00500 }