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