home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / Tree.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  16.5 KB  |  795 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * Tree is a red-black tree structure used as the underlying data structure by all
  8.  * all associative containers.
  9.  * <p>
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. final class TreeNode
  15.   {
  16.   public int color = Tree.BLACK;
  17.   public TreeNode parent;
  18.   public TreeNode left;
  19.   public TreeNode right;
  20.   public Object object;
  21.  
  22.   public TreeNode()
  23.     {
  24.     }
  25.  
  26.   public TreeNode( Object value )
  27.     {
  28.     object = value;
  29.     }
  30.   }
  31.  
  32. final class InsertResult
  33.   {
  34.   public boolean ok;
  35.   public TreeNode node;
  36.  
  37.   public InsertResult( TreeNode n, boolean b )
  38.     {
  39.     ok = b;
  40.     node = n;
  41.     }
  42.   }
  43.  
  44. final class Tree
  45.   {
  46.   public static final int RED = 1;
  47.   public static final int BLACK = 2;
  48.   static TreeNode NIL = new TreeNode();
  49.   int size;
  50.   boolean myInsertAlways;
  51.   boolean myIsMap;
  52.   BinaryPredicate myComparator;
  53.   Container myContainer;
  54.   TreeNode myHeader = new TreeNode(); // Note: myHeader == end, myHeader.left == begin
  55.  
  56.   Tree( boolean isMap, boolean always, Container container )
  57.     {
  58.     this( isMap, always, new HashComparator(), container );
  59.     }
  60.  
  61.   Tree( boolean isMap, boolean always, BinaryPredicate comparator, Container container )
  62.     {
  63.     myContainer = container;
  64.     myIsMap = isMap;
  65.     myInsertAlways = always;
  66.     myComparator = comparator;
  67.     myHeader.color = RED;
  68.     clear();
  69.     }
  70.  
  71.   Tree( Tree tree )
  72.     {
  73.     myContainer = tree.myContainer;
  74.     myIsMap = tree.myIsMap;
  75.     myInsertAlways = tree.myInsertAlways;
  76.     myComparator = tree.myComparator;
  77.     myHeader.color = RED;
  78.     copyTree( tree );
  79.     }
  80.  
  81.   boolean compare( Object first, Object second )
  82.     {
  83.     return myComparator.execute( first, second );
  84.     }
  85.  
  86.   Object key( Object object )
  87.     {
  88.     return myIsMap ? ((Pair) object).first : object;
  89.     }
  90.  
  91.   Object value( Object object )
  92.     {
  93.     if ( myIsMap )
  94.       {
  95.       if ( object == null )
  96.         return null;
  97.        
  98.       return ((Pair) object).second;
  99.       }
  100.     else
  101.       {
  102.       return object;
  103.       }
  104. //    return myIsMap ? ((Pair) object).second : object;
  105.     }
  106.  
  107.   void copy( Tree tree )
  108.     {
  109.     if( this != tree )
  110.       {
  111.       clear();
  112.       copyTree( tree );
  113.       }
  114.     }
  115.  
  116.   OrderedSetIterator beginSet()
  117.     {
  118.     return new OrderedSetIterator( this, myHeader.left, (OrderedSet)myContainer );
  119.     }
  120.  
  121.   OrderedSetIterator endSet()
  122.     {
  123.     return new OrderedSetIterator( this, myHeader, (OrderedSet)myContainer );
  124.     }
  125.  
  126.   OrderedMapIterator beginMap( int mode )
  127.     {
  128.     return new OrderedMapIterator( this, myHeader.left, (OrderedMap)myContainer, mode );
  129.     }
  130.  
  131.   OrderedMapIterator endMap( int mode )
  132.     {
  133.     return new OrderedMapIterator( this, myHeader, (OrderedMap)myContainer, mode );
  134.     }
  135.  
  136.   int maxSize()
  137.     {
  138.     return Allocator.maxSize();
  139.     }
  140.  
  141.   TreeNode insert( TreeNode pos, Object value )
  142.     {
  143.     if( pos == myHeader.left )
  144.       {
  145.       if( size > 0 && compare( key( value ), key( pos.object ) ) )
  146.         return insert( pos, pos, value );
  147.       else
  148.         return insert( value ).node;
  149.       }
  150.     else if( pos == myHeader ) 
  151.       {
  152.       if( compare( key( myHeader.right.object ), key( value ) ) )
  153.         return insert( NIL, myHeader.right, value );
  154.       else
  155.         return insert( value ).node;
  156.       }
  157.     else
  158.       {
  159.       TreeNode before = decrement( pos );
  160.  
  161.       if( compare( key( before.object ), key( value ) ) && compare( key( value ), key( pos.object ) ) )
  162.         if( before.right == NIL )
  163.           return insert( NIL, before, value );
  164.         else
  165.           return insert( pos, pos, value );
  166.       else
  167.         return insert( value ).node;
  168.       }
  169.     }
  170.  
  171.   void clear()
  172.     {
  173.     myHeader.parent = NIL;
  174.     myHeader.right = myHeader;
  175.     myHeader.left = myHeader;
  176.     size = 0;
  177.     }
  178.  
  179.   Object remove( Object key )
  180.     {
  181.     return remove( lowerBound( key ), upperBound( key ) );
  182.     }
  183.  
  184.   Object remove( TreeNode first, TreeNode last )
  185.     {
  186.     Object rvalue;
  187.     if( first == myHeader.left && last == myHeader && size != 0 )
  188.       { 
  189.       rvalue = value(first.object);     
  190.       clear();
  191.       }
  192.     else
  193.       {
  194.       TreeNode next;
  195.       rvalue = value( first.object );
  196.  
  197.       while( first != last )
  198.         {
  199.         next = increment( first ); 
  200.         remove( first );
  201.         first = next;
  202.         }
  203.       }
  204.  
  205.     return rvalue;
  206.     }
  207.  
  208.   TreeNode find( Object key )
  209.     {
  210.     TreeNode j = lowerBound( key );
  211.     return ( j == myHeader || compare( key, key( j.object ) ) ) ? myHeader : j;
  212.     }
  213.  
  214.   int count( Object key )
  215.     {
  216.     return distance( lowerBound( key ), upperBound( key ) );
  217.     }
  218.  
  219.   TreeNode lowerBound( Object key )
  220.     {
  221.     TreeNode y = myHeader;
  222.     TreeNode x = myHeader.parent;
  223.     boolean comp = false;
  224.  
  225.     while( x != NIL )
  226.       {
  227.       y = x;
  228.       comp = compare( key( x.object ), key );
  229.       x = comp ? x.right : x.left;
  230.       }
  231.  
  232.     return comp ? increment( y ) : y;
  233.     }
  234.  
  235.   TreeNode upperBound( Object key )
  236.     {
  237.     TreeNode y = myHeader;
  238.     TreeNode x = myHeader.parent;
  239.     boolean comp = true;
  240.  
  241.     while( x != NIL )
  242.       {
  243.       y = x;
  244.       comp = compare( key, key( x.object ) );
  245.       x = comp ? x.left : x.right;
  246.       }
  247.  
  248.     return comp ? y : increment( y );
  249.     }
  250.  
  251.   void insert( InputIterator first, InputIterator last )
  252.     {
  253.     InputIterator firstx = (InputIterator) first.clone();
  254.  
  255.     while( !firstx.equals( last ) )
  256.       insert( firstx.nextElement() );
  257.     }
  258.  
  259.   InsertResult insert( Object value )
  260.     {
  261.     TreeNode y = myHeader;
  262.     TreeNode x = myHeader.parent;
  263.     boolean comp = true;
  264.  
  265.     while( x != NIL )
  266.       {
  267.       y = x;
  268.       comp = compare( key( value ), key( x.object ) );
  269.       x = comp ? x.left : x.right;
  270.       }
  271.  
  272.     if( myInsertAlways )
  273.       return new InsertResult( insert( x, y, value ), true );
  274.  
  275.     TreeNode j = y;
  276.  
  277.     if( comp )
  278.       if ( j == myHeader.left )
  279.         return new InsertResult( insert( x, y, value ), true );
  280.       else   
  281.         j = decrement( j );
  282.  
  283.     if( compare( key( j.object ), key( value ) ) )
  284.       return new InsertResult( insert( x, y, value ), true );
  285.     else
  286.       return new InsertResult( j, false );
  287.     }
  288.  
  289.   InsertResult put( Object value )
  290.     {
  291.     TreeNode y = myHeader;
  292.     TreeNode x = myHeader.parent;
  293.     boolean comp = true;
  294.  
  295.     while( x != NIL )
  296.       {
  297.       y = x;
  298.       comp = compare( key( value ), key( x.object ) );
  299.       x = comp ? x.left : x.right;
  300.       }
  301.  
  302.     TreeNode j = y;
  303.  
  304.     if( comp )
  305.       if ( j == myHeader.left )
  306.         return new InsertResult( insert( x, y, value ), true );
  307.       else   
  308.         j = decrement( j );
  309.  
  310.     if( compare( key( j.object ), key( value ) ) )
  311.       return new InsertResult( insert( x, y, value ), true );
  312.     else
  313.       return new InsertResult( j, false );
  314.     }
  315.  
  316.   Object get( Object key )
  317.     {
  318.     TreeNode y = myHeader;
  319.     TreeNode x = myHeader.parent;
  320.     boolean comp = true;
  321.  
  322.     while( x != NIL )
  323.       {
  324.       y = x;
  325.       comp = compare( key, key( x.object ) );
  326.       x = comp ? x.left : x.right;
  327.       }
  328.  
  329.     TreeNode j = y;
  330.  
  331.     if( comp )
  332.       if ( j == myHeader.left )
  333.         return null;
  334.       else   
  335.         j = decrement( j );
  336.  
  337.     if( compare( key( j.object ), key ) )
  338.       return null;
  339.     else
  340.       return ((Pair) j.object).second;
  341.     }
  342.  
  343.   TreeNode insert( TreeNode x, TreeNode y, Object value )
  344.     {
  345.     ++size;
  346.     TreeNode z = new TreeNode( value );
  347.     boolean insertToLeft = ( y == myHeader || x != NIL || compare( key( value ), key( y.object ) ) );
  348.     insert( insertToLeft, x, y, z );
  349.     return z;
  350.     }
  351.  
  352.   static int distance( TreeNode first, TreeNode last )
  353.     {
  354.     int n = 0;
  355.  
  356.     while( first != last )
  357.       {
  358.       first = increment( first );
  359.       ++n;
  360.       }
  361.  
  362.     return n;
  363.     }
  364.  
  365.   TreeNode copyTree( TreeNode oldNode, TreeNode parent )
  366.     {
  367.     if( oldNode == NIL )
  368.       return NIL;
  369.  
  370.     TreeNode newNode = new TreeNode( oldNode.object );
  371.     newNode.color = oldNode.color;
  372.     newNode.left = copyTree( oldNode.left, newNode );
  373.     newNode.right = copyTree( oldNode.right, newNode );
  374.     newNode.parent = parent;
  375.     return newNode;
  376.     }
  377.  
  378.   void copyTree( Tree tree )
  379.     {
  380.     myHeader.parent = copyTree( tree.myHeader.parent, myHeader );
  381.     myHeader.left = minimum( myHeader.parent );
  382.     myHeader.right = maximum( myHeader.parent );
  383.     size = tree.size;
  384.     }
  385.  
  386.   Array keys()
  387.     {
  388.     Array array = new Array();
  389.     int i = 0;
  390.     TreeNode node = myHeader.left;
  391.  
  392.     while( node != myHeader )
  393.       {
  394.       array.add( ((Pair) node.object).first );
  395.       node = increment( node );
  396.       }
  397.  
  398.     return array;
  399.     }
  400.  
  401.   Array keys( Object value )
  402.     {
  403.     Array array = new Array();
  404.     int i = 0;
  405.     TreeNode node = myHeader.left;
  406.  
  407.     while( node != myHeader )
  408.       {
  409.       if( ((Pair) node.object).second.equals( value ) )
  410.         array.add( ((Pair) node.object).first );
  411.  
  412.       node = increment( node );
  413.       }
  414.  
  415.     return array;
  416.     }
  417.  
  418.  
  419.   Array values( Object key )
  420.     {
  421.     Array array = new Array();
  422.     int i = 0;
  423.     TreeNode node = myHeader.left;
  424.  
  425.     while( node != myHeader )
  426.       {
  427.       if( (((Pair) node.object).first).equals( key ) ) 
  428.         array.add( ((Pair) node.object).second );
  429.  
  430.       node = increment( node );
  431.       }
  432.  
  433.     return array;
  434.     }
  435.  
  436.   static TreeNode increment( TreeNode node )
  437.     {
  438.     if( node.right != NIL )
  439.       {
  440.       node = node.right;
  441.  
  442.       while( node.left != NIL )
  443.         node = node.left;
  444.  
  445.       return node;
  446.       }
  447.     else 
  448.       {
  449.       while( node == node.parent.right )
  450.         node = node.parent;
  451.  
  452.       return node.right == node.parent ? node : node.parent;
  453.       }
  454.     }
  455.  
  456.   static TreeNode decrement( TreeNode node )
  457.     {
  458.     if( node.color == RED && node.parent.parent == node )
  459.       {
  460.       return node.right;
  461.       }
  462.     else if( node.left != NIL )
  463.       {
  464.       node = node.left;
  465.  
  466.       while( node.right != NIL )
  467.         node = node.right;
  468.  
  469.       return node;
  470.       }
  471.     else 
  472.       {
  473.       while( node == node.parent.left )
  474.         node = node.parent;
  475.  
  476.       return node.parent;
  477.       }
  478.     }
  479.  
  480.   TreeNode minimum( TreeNode node )
  481.     {
  482.     if( node == NIL )
  483.       {
  484.       return myHeader;
  485.       }
  486.     else
  487.       {
  488.       while( node.left != NIL )
  489.         node = node.left;
  490.  
  491.       return node;
  492.       }
  493.     }
  494.  
  495.   TreeNode maximum( TreeNode node )
  496.     {
  497.     if( node == NIL )
  498.       {
  499.       return myHeader;
  500.       }
  501.     else
  502.       {
  503.       while( node.right != NIL )
  504.         node = node.right;
  505.  
  506.       return node;
  507.       }
  508.     }
  509.  
  510.   void rotateLeft( TreeNode x )
  511.     {
  512.     TreeNode y = x.right;
  513.     x.right = y.left;
  514.  
  515.     if( y.left != NIL )
  516.       y.left.parent = x;
  517.  
  518.     y.parent = x.parent;
  519.  
  520.     if( x == myHeader.parent )
  521.       myHeader.parent = y;
  522.     else if( x == x.parent.left )
  523.       x.parent.left = y;
  524.     else
  525.       x.parent.right = y;
  526.  
  527.     y.left = x;
  528.     x.parent = y;
  529.     }
  530.  
  531.   void rotateRight( TreeNode x )
  532.     {
  533.     TreeNode y = x.left;
  534.     x.left = y.right;
  535.  
  536.     if( y.right != NIL )
  537.       y.right.parent = x;
  538.  
  539.     y.parent = x.parent;
  540.  
  541.     if( x == myHeader.parent )
  542.       myHeader.parent = y;
  543.     else if( x == x.parent.right )
  544.       x.parent.right = y;
  545.     else
  546.       x.parent.left = y;
  547.  
  548.     y.right = x;
  549.     x.parent = y; 
  550.     }
  551.  
  552.   void insert( boolean insertToLeft, TreeNode x, TreeNode y, TreeNode z )
  553.     {
  554.     if( insertToLeft )
  555.       {
  556.       y.left = z;
  557.  
  558.       if( y == myHeader )
  559.         {
  560.         myHeader.parent = z;
  561.         myHeader.right = z;
  562.         }
  563.       else if( y == myHeader.left )
  564.         {
  565.         myHeader.left = z;
  566.         }
  567.       }
  568.     else
  569.       {
  570.       y.right = z;
  571.  
  572.       if( y == myHeader.right )
  573.         myHeader.right = z;
  574.       }
  575.  
  576.     z.parent = y;
  577.     z.left = NIL;
  578.     z.right = NIL;
  579.     x = z;
  580.     x.color = RED;
  581.  
  582.     while( x != myHeader.parent && x.parent.color == RED )
  583.       if( x.parent == x.parent.parent.left )
  584.         {
  585.         y = x.parent.parent.right;
  586.  
  587.         if( y.color == RED )
  588.           {
  589.           x.parent.color = BLACK;
  590.           y.color = BLACK;
  591.           x.parent.parent.color = RED;
  592.           x = x.parent.parent;
  593.           }
  594.         else
  595.           {
  596.           if( x == x.parent.right )
  597.             {
  598.             x = x.parent;
  599.             rotateLeft( x );
  600.             }
  601.  
  602.           x.parent.color = BLACK;
  603.           x.parent.parent.color = RED;
  604.           rotateRight( x.parent.parent );
  605.           }
  606.         }
  607.       else
  608.         {
  609.         y = x.parent.parent.left;
  610.  
  611.         if( y.color == RED )
  612.           {
  613.           x.parent.color = BLACK;
  614.           y.color = BLACK;
  615.           x.parent.parent.color = RED;
  616.           x = x.parent.parent;
  617.           }
  618.         else
  619.           {
  620.           if( x == x.parent.left )
  621.             {
  622.             x = x.parent;
  623.             rotateRight( x );
  624.             }
  625.  
  626.           x.parent.color = BLACK;
  627.           x.parent.parent.color = RED;
  628.           rotateLeft( x.parent.parent );
  629.           } 
  630.         }
  631.  
  632.       myHeader.parent.color = BLACK;
  633.     }
  634.  
  635.   TreeNode remove( TreeNode z )
  636.     {
  637.     TreeNode y = z;
  638.     TreeNode x;
  639.  
  640.     if( y.left == NIL )
  641.       {
  642.       x = y.right;
  643.       }
  644.     else if( y.right == NIL )
  645.       {
  646.       x = y.left;
  647.       }
  648.     else
  649.       {
  650.       y = y.right;
  651.  
  652.       while( y.left != NIL )
  653.         y = y.left;
  654.  
  655.       x = y.right;
  656.       }
  657.  
  658.     if( y != z )
  659.       {
  660.       z.left.parent = y;
  661.       y.left = z.left;
  662.  
  663.       if( y != z.right )
  664.         {
  665.         x.parent = y.parent;
  666.         y.parent.left = x;
  667.         y.right = z.right;
  668.         z.right.parent = y;
  669.         }
  670.       else
  671.         {
  672.         x.parent = y;
  673.         }
  674.  
  675.       if( myHeader.parent == z )
  676.         myHeader.parent = y;
  677.       else if( z.parent.left == z )
  678.         z.parent.left = y;
  679.       else
  680.         z.parent.right = y;
  681.  
  682.       y.parent = z.parent;
  683.  
  684.       // Swap color of y and z.
  685.       int tmp = y.color;
  686.       y.color = z.color;
  687.       z.color = tmp;
  688.  
  689.       y = z;
  690.       }
  691.     else
  692.       {
  693.       x.parent = y.parent;
  694.  
  695.       if( myHeader.parent == z )
  696.         myHeader.parent = x;
  697.       else if( z.parent.left == z )
  698.         z.parent.left = x;
  699.       else
  700.         z.parent.right = x;
  701.  
  702.       if( myHeader.left == z )
  703.         if( z.right == NIL )
  704.           myHeader.left = z.parent;
  705.         else
  706.           myHeader.left = minimum( x );
  707.  
  708.       if( myHeader.right == z )
  709.         if( z.left == NIL )
  710.           myHeader.right = z.parent;
  711.         else
  712.           myHeader.right = maximum( x );
  713.       }
  714.  
  715.     if( y.color != RED )
  716.       {
  717.       while( x != myHeader.parent && x.color == BLACK )
  718.         if( x == x.parent.left )
  719.           {
  720.           TreeNode w = x.parent.right;
  721.  
  722.           if( w.color == RED )
  723.             {
  724.             w.color = BLACK;
  725.             x.parent.color = RED;
  726.             rotateLeft( x.parent );
  727.             w = x.parent.right;
  728.             }
  729.  
  730.           if( w.left.color == BLACK && w.right.color == BLACK )
  731.             {
  732.             w.color = RED;
  733.             x = x.parent;
  734.             }
  735.           else
  736.             {
  737.             if( w.right.color == BLACK )
  738.               {
  739.               w.left.color = BLACK;
  740.               w.color = RED;
  741.               rotateRight( w );
  742.               w = x.parent.right;
  743.               }
  744.  
  745.             w.color = x.parent.color;
  746.             x.parent.color = BLACK;
  747.             w.right.color = BLACK;
  748.             rotateLeft( x.parent );
  749.             break;
  750.             }
  751.           }
  752.         else
  753.           {
  754.           TreeNode w = x.parent.left;
  755.  
  756.           if( w.color == RED )
  757.             {
  758.             w.color = BLACK;
  759.             x.parent.color = RED;
  760.             rotateRight( x.parent );
  761.             w = x.parent.left;
  762.             }
  763.   
  764.           if( w.right.color == BLACK && w.left.color == BLACK )
  765.             {
  766.             w.color = RED;
  767.             x = x.parent;
  768.             }
  769.           else
  770.             {
  771.             if( w.left.color == BLACK )
  772.               {
  773.               w.right.color = BLACK;
  774.               w.color = RED;
  775.               rotateLeft( w );
  776.               w = x.parent.left;
  777.               }
  778.  
  779.             w.color = x.parent.color;
  780.             x.parent.color = BLACK;
  781.             w.left.color = BLACK;
  782.             rotateRight( x.parent );
  783.             break;
  784.             }
  785.           }
  786.  
  787.       x.color = BLACK;
  788.       }
  789.  
  790.     --size;
  791.     return y;
  792.     }
  793.   }
  794.  
  795.