src/main/java/irc/tree/SortedList.java

   1 /*****************************************************/\r
   2 /*          This java file is a part of the          */\r
   3 /*                                                   */\r
   4 /*           -  Plouf's Java IRC Client  -           */\r
   5 /*                                                   */\r
   6 /*   Copyright (C)  2002 - 2004 Philippe Detournay   */\r
   7 /*                                                   */\r
   8 /*         All contacts : theplouf@yahoo.com         */\r
   9 /*                                                   */\r
  10 /*  PJIRC is free software; you can redistribute     */\r
  11 /*  it and/or modify it under the terms of the GNU   */\r
  12 /*  General Public License as published by the       */\r
  13 /*  Free Software Foundation; version 2 or later of  */\r
  14 /*  the License.                                     */\r
  15 /*                                                   */\r
  16 /*  PJIRC is distributed in the hope that it will    */\r
  17 /*  be useful, but WITHOUT ANY WARRANTY; without     */\r
  18 /*  even the implied warranty of MERCHANTABILITY or  */\r
  19 /*  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU   */\r
  20 /*  General Public License for more details.         */\r
  21 /*                                                   */\r
  22 /*  You should have received a copy of the GNU       */\r
  23 /*  General Public License along with PJIRC; if      */\r
  24 /*  not, write to the Free Software Foundation,      */\r
  25 /*  Inc., 59 Temple Place, Suite 330, Boston,        */\r
  26 /*  MA  02111-1307  USA                              */\r
  27 /*                                                   */\r
  28 /*****************************************************/\r
  29 \r
  30 package irc.tree;\r
  31 \r
  32 import java.util.Enumeration;\r
  33 import java.util.Vector;\r
  34 \r
  35 //class GroupItem\r
  36 //{\r
  37 //  //private Hashtable t;\r
  38 //  //Object[] t;\r
  39 //  Object s;\r
  40 //\r
  41 //  public GroupItem(Object o)\r
  42 //  {\r
  43 //    //t=new Hashtable();\r
  44 //    //t=new Object\r
  45 //    //t=null;\r
  46 //    s=null;\r
  47 //    add(o);\r
  48 //  }\r
  49 //\r
  50 //  public void add(Object o)\r
  51 //  {\r
  52 //    if(s==null) s=o;\r
  53 //    else\r
  54 //    {\r
  55 //      /*if(t==null)\r
  56 //      {\r
  57 //        t=new Object[] {o};\r
  58 //      }\r
  59 //      else\r
  60 //      {\r
  61 //      }*/\r
  62 //      throw new RuntimeException("Didn't expect similar keys!!");\r
  63 //    }\r
  64 //    //t.put(o,o);\r
  65 //  }\r
  66 //\r
  67 //  public void remove(Object o)\r
  68 //  {\r
  69 //    //t.remove(o);\r
  70 //    s=null;\r
  71 //  }\r
  72 //\r
  73 //  public int size()\r
  74 //  {\r
  75 //    //return t.size();\r
  76 //    if(s==null) return 0;\r
  77 //    //if(t==null) return 1;\r
  78 //    return 1;\r
  79 //    //return t.length+1;\r
  80 //  }\r
  81 //\r
  82 //  public Object getFirstItem()\r
  83 //  {\r
  84 //    //return t.elements().nextElement();\r
  85 //    return s;\r
  86 //  }\r
  87 //\r
  88 //  //public Enumeration elements()\r
  89 //  //{\r
  90 //    //return t.elements();\r
  91 //  //}\r
  92 //}\r
  93 \r
  94 /**\r
  95  * TreeNode.\r
  96  */\r
  97 class TreeNode {\r
  98         /**\r
  99          * Left node.\r
 100          */\r
 101         public TreeNode left;\r
 102         /**\r
 103          * Right node.\r
 104          */\r
 105         public TreeNode right;\r
 106         // public GroupItem item;\r
 107         // public Object objects[];\r
 108         /**\r
 109          * Objects in this node.\r
 110          */\r
 111         public Vector objects;\r
 112         // private int count;\r
 113         private Comparator _comparator;\r
 114 \r
 115         /**\r
 116          * Create a new TreeNode\r
 117          * \r
 118          * @param itm\r
 119          *          first item.\r
 120          * @param comparator\r
 121          *          item comparator.\r
 122          */\r
 123         public TreeNode(Object itm, Comparator comparator) {\r
 124                 _comparator = comparator;\r
 125                 // item=itm;\r
 126                 objects = new Vector(1, 0);\r
 127                 objects.insertElementAt(itm, objects.size());\r
 128                 // count=1;\r
 129                 left = new TreeNode(comparator);\r
 130                 right = new TreeNode(comparator);\r
 131         }\r
 132 \r
 133         /**\r
 134          * Create a new TreeNode\r
 135          * \r
 136          * @param comparator\r
 137          *          comparator.\r
 138          */\r
 139         public TreeNode(Comparator comparator) {\r
 140                 _comparator = comparator;\r
 141                 // item=null;\r
 142                 objects = new Vector(1, 0);\r
 143                 left = null;\r
 144                 right = null;\r
 145                 // count=0;\r
 146         }\r
 147 \r
 148         /**\r
 149          * Returns true if node is external.\r
 150          * \r
 151          * @return true if node is external, false otherwise.\r
 152          */\r
 153         public boolean external() {\r
 154                 return ((left == null) || (right == null));\r
 155         }\r
 156 \r
 157         /**\r
 158          * Remove the given item.\r
 159          * \r
 160          * @param itm\r
 161          *          item to remove.\r
 162          * @return resulting tree node.\r
 163          * @throws Exception\r
 164          */\r
 165         public TreeNode remove(Object itm) throws Exception {\r
 166                 if (external())\r
 167                         throw new Exception();\r
 168 \r
 169                 int compare = _comparator.compare(itm,/* item.getFirstItem() */\r
 170                                 objects.elementAt(0));\r
 171                 if (compare == 0) {\r
 172                         // item.remove(itm);\r
 173                         objects.removeElement(itm);\r
 174                         // count--;\r
 175                         if (objects.size() == 0) {\r
 176                                 if (left.external())\r
 177                                         return right;\r
 178                                 if (right.external())\r
 179                                         return left;\r
 180                                 return right.addTree(left);\r
 181                         }\r
 182                         return this;\r
 183                 } else if (compare < 0) {\r
 184                         left = left.remove(itm);\r
 185                         return this;\r
 186                 } else {\r
 187                         right = right.remove(itm);\r
 188                         return this;\r
 189                 }\r
 190         }\r
 191 \r
 192         private TreeNode addTree(TreeNode tree) throws Exception {\r
 193                 if (external())\r
 194                         return tree;\r
 195                 if (tree.external())\r
 196                         return this;\r
 197 \r
 198                 int compare = _comparator.compare(tree.objects.elementAt(0), objects.elementAt(0));\r
 199                 if (compare == 0) {\r
 200                         throw new Exception();\r
 201                 } else if (compare < 0) {\r
 202                         left = left.addTree(tree);\r
 203                         return this;\r
 204                 } else {\r
 205                         right = right.addTree(tree);\r
 206                         return this;\r
 207                 }\r
 208         }\r
 209 \r
 210         /**\r
 211          * Add an object.\r
 212          * \r
 213          * @param itm\r
 214          *          object to tadd.\r
 215          * @return resulting tree node.\r
 216          * @throws Exception\r
 217          */\r
 218         public TreeNode add(Object itm) throws Exception {\r
 219                 if (external()) {\r
 220                         return new TreeNode(itm, _comparator);\r
 221                 }\r
 222 \r
 223                 int compare = _comparator.compare(itm, objects.elementAt(0));\r
 224                 if (compare == 0) {\r
 225                         // item.add(itm);\r
 226                         objects.insertElementAt(itm, objects.size());\r
 227                         // throw new RuntimeException("Duplicate key");\r
 228                         return this;\r
 229                 } else if (compare < 0) {\r
 230                         left = left.add(itm);\r
 231                         return this;\r
 232                 } else {\r
 233                         right = right.add(itm);\r
 234                         return this;\r
 235                 }\r
 236         }\r
 237 \r
 238         /**\r
 239          * Start an inorder tree traversal.\r
 240          * \r
 241          * @param lis\r
 242          *          traversal listener.\r
 243          * @param param\r
 244          *          user parameter.\r
 245          */\r
 246         public void inorder(TreeTraversalListener lis, Object param) {\r
 247                 if (external())\r
 248                         return;\r
 249                 left.inorder(lis, param);\r
 250                 // Enumeration e=item.elements();\r
 251                 // while(e.hasMoreElements()) lis.nextItem(e.nextElement(),param);\r
 252                 // lis.nextItem(object,param);\r
 253                 for (int i = 0; i < objects.size(); i++)\r
 254                         lis.nextItem(objects.elementAt(i), param);\r
 255                 right.inorder(lis, param);\r
 256         }\r
 257 }\r
 258 \r
 259 /**\r
 260  * A Sorted List.\r
 261  */\r
 262 public class SortedList implements TreeTraversalListener {\r
 263         private TreeNode _root;\r
 264         private Vector _items;\r
 265         private Comparator _comparator;\r
 266         private boolean _upToDate;\r
 267 \r
 268         /**\r
 269          * Create a new SortedList, using the given Comparator for the order\r
 270          * definition.\r
 271          * \r
 272          * @param comparator\r
 273          *          comparator to be used for ordering.\r
 274          */\r
 275         public SortedList(Comparator comparator) {\r
 276                 _comparator = comparator;\r
 277                 _root = new TreeNode(_comparator);\r
 278                 _items = new Vector();\r
 279                 _upToDate = false;\r
 280         }\r
 281 \r
 282         /**\r
 283          * Get the amount of items in the list.\r
 284          * \r
 285          * @return list size.\r
 286          */\r
 287         public int getSize() {\r
 288                 if (!_upToDate)\r
 289                         computeVector();\r
 290                 return _items.size();\r
 291         }\r
 292 \r
 293         /**\r
 294          * Add an item in the list.\r
 295          * \r
 296          * @param item\r
 297          *          item to add.\r
 298          */\r
 299         public void add(Object item) {\r
 300                 try {\r
 301                         _root = _root.add(item);\r
 302                 } catch (Exception e) {\r
 303                 }\r
 304                 _upToDate = false;\r
 305         }\r
 306 \r
 307         /**\r
 308          * Remove the given item from the list.\r
 309          * \r
 310          * @param item\r
 311          *          item to remove from the list.\r
 312          */\r
 313         public void remove(Object item) {\r
 314                 try {\r
 315                         _root = _root.remove(item);\r
 316                 } catch (Exception e) {\r
 317                 }\r
 318                 _upToDate = false;\r
 319         }\r
 320 \r
 321         @Override\r
 322         public void begin(Object param) {\r
 323                 _items = new Vector();\r
 324         }\r
 325 \r
 326         @Override\r
 327         public void nextItem(Object item, Object param) {\r
 328                 _items.insertElementAt(item, _items.size());\r
 329         }\r
 330 \r
 331         @Override\r
 332         public void end(Object param) {\r
 333                 _upToDate = true;\r
 334         }\r
 335 \r
 336         private void computeVector() {\r
 337                 getItems(this, null);\r
 338         }\r
 339 \r
 340         /**\r
 341          * Get a sorted enumeration of items.\r
 342          * \r
 343          * @return a sorted enumeration of items in the list.\r
 344          */\r
 345         public Enumeration getItems() {\r
 346                 if (!_upToDate)\r
 347                         computeVector();\r
 348                 return _items.elements();\r
 349         }\r
 350 \r
 351         /**\r
 352          * Get the i'th element in the list. Index are ordered.\r
 353          * \r
 354          * @param i\r
 355          *          index.\r
 356          * @return object at i'th position.\r
 357          */\r
 358         public Object getItemAt(int i) {\r
 359                 if (!_upToDate)\r
 360                         computeVector();\r
 361                 return _items.elementAt(i);\r
 362         }\r
 363 \r
 364         /**\r
 365          * Begin a new traversal.\r
 366          * \r
 367          * @param lis\r
 368          *          traversal listener.\r
 369          * @param param\r
 370          *          user parameter.\r
 371          */\r
 372         public void getItems(TreeTraversalListener lis, Object param) {\r
 373                 lis.begin(param);\r
 374                 _root.inorder(lis, param);\r
 375                 lis.end(param);\r
 376         }\r
 377 \r
 378         /**\r
 379          * Clear the list.\r
 380          */\r
 381         public void clear() {\r
 382                 _root = new TreeNode(_comparator);\r
 383                 _items = new Vector();\r
 384                 _upToDate = false;\r
 385         }\r
 386 \r
 387 }\r