test/hotspot/jtreg/vmTestbase/gc/gctests/gctest03/Tree.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2002, 2018, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 package gc.gctests.gctest03;

 class DataNodeException extends Exception
 {
 }


 class DataNode  {
   int key;
   int buf[];
   static int dataNodeCount = 0;
   static int dataNodeLimit;

   static synchronized void incDataNodeCount()
   {
     dataNodeCount++;
   }

   static synchronized int getDataNodeCount()
   {
     return dataNodeCount;
   }

   static synchronized void setDataNodeLimit(int newLimit)
   {
     dataNodeLimit = newLimit;
   }

   static synchronized int getDataNodeLimit()
   {
     return dataNodeLimit;
   }

   static synchronized void clearDataNodeCount()
   {
         dataNodeCount = 0;
   }
   DataNode(int key) throws DataNodeException
   {

     incDataNodeCount();
     if (getDataNodeCount() > getDataNodeLimit())
     {
         throw (new DataNodeException());
     }

     this.key = key;
     try {
       buf = new int[key];
     }
     catch ( OutOfMemoryError e )
       {
         System.out.println(Thread.currentThread().getName() + " : outofmemory");
       }
   }

   public void print()
   {
     System.out.println(key);
   }

   public boolean equals(DataNode d)
   {
     int k = d.getkey();

     return ( key == k);
   }

   public boolean large(DataNode d)
   {
     int k = d.getkey();

     return ( key > k);
   }

  public boolean less(DataNode d)

   {
     int k = d.getkey();

     return ( key < k);
   }

   public int getkey()
   { return key; }
 }


 class TreeNode {
   DataNode  data;
   TreeNode  parent;
   TreeNode  left;
   TreeNode  right;

   TreeNode(DataNode key)
   {
     this.data = key;
     parent = null;
     left = null;
     right = null;
   }

   public void print()
   {
     data.print();
   }

   public TreeNode getleft()
   {
     return left;
   }

   public TreeNode getright()
   {
     return right;
   }

   public TreeNode getparent()
   {
     return parent;
   }

   public synchronized void setleft(TreeNode left)
   {
     this.left = left;
   }

   public synchronized void setright(TreeNode right)
   {
     this.right = right;
   }

   public synchronized void setparent(TreeNode parent)
   {
     this.parent = parent;
   }

   public DataNode getData()
   {
     return data;
   }

   // print it out in order of a large one first
   public void sprint()
   {
     //print itself
     if ( left != null )  left.sprint();
     System.out.println(data.getkey());
     if ( right != null )  right.sprint();
   }

    // print it out in order of a small one first
   public void lprint()
   {
     if (right != null ) right.lprint();
     System.out.println(data.getkey());
     if ( left != null ) left.lprint();
   }

   public synchronized TreeNode duplicate()
   {
     TreeNode tp = new TreeNode(data);

     if ( left != null )
       {
         tp.left = left.duplicate();
       }
     if ( right != null )
       {
         tp.right = right.duplicate();
       }
     return tp;
   }

   public TreeNode search(DataNode d)
   {
     TreeNode tp = this;
     DataNode k;

     while ( tp != null )
       {
         k = tp.getData();
         if ( k.equals(d) )
           {
             return tp;
           }
         else
           if ( d.large(k) )
             tp = tp.getright();
         else
           tp = tp.getleft();
       }
     return null;
   }

   public synchronized void insert(TreeNode t)
   {
     DataNode d = t.getData();

     TreeNode tp = this;
     TreeNode tp1 = tp;
     DataNode d0;

     while ( true )
       {
         d0 = tp.getData();

         if ( d.large(d0) )
           {
             tp1 = tp;
             tp = tp.getright();
             if ( tp == null )
               {
                 tp1.setright(t);
                 t.setparent(tp1);
                 break;
               }
           }
         else
           {
             tp1 = tp;
             tp = tp.getleft();
             if (tp == null )
               {
                 tp1.setleft(t);
                 t.setparent(tp1);
                 break;
               }
           }
       }

   }


 }


 class Tree {
   TreeNode root = null;

   Tree()
   {
     root = null;
   }

   Tree(TreeNode root)
   {
     this.root = root;
   }

   public synchronized void insert(TreeNode t)
   {
     if ( root == null )
       {
         root = t;
         return;
       }

     root.insert(t);
   }


   public void sort1()
   {
     root.sprint();
   }

   public void sort2()
   {
     root.lprint();
   }

   public TreeNode search(DataNode d)
   {
     if ( root == null ) return null;
     else return root.search(d);
   }

   public synchronized boolean remove(DataNode d)
   {
     if ( root == null ) return false;

     TreeNode t = root.search(d);

         // data is not in a heap
     if ( t == null ) return false;

 /*
     if ( d.equals(t.getData()) == false )
       {
         System.out.println("failed");
         return false;
       }
  */

     TreeNode p = t.getparent();
     TreeNode l = t.getleft();
     TreeNode r = t.getright();

     // the removed node is a root
     if ( p == null )
       {
         if ( l == null && r != null )
           {
             r.setparent(null);
             root = r;
             return true;
           }
         if ( l != null && r == null )
           {
             l.setparent(null);
             root = l;
             return true;
           }
         if ( l == null && r == null )
           {
             root = null;
             return true;
           }

         if ( l != null && r != null )
           {
             r.setparent(null);
             r.insert(l);
             root = r;
             return true;
           }
       }

     // a leaf
     if ( r == null && l == null )
       {
         if ( p.getright() == t )
           {
             /* right child */
             p.setright(null);
           }
         else
           p.setleft(null);
         return true;
       }

     // a node without left child
     if ( r != null &&  l == null )
       {
         r.setparent(p);
         if ( t == p.getright() ) p.setright(r);
         if ( t == p.getleft() ) p.setleft(r);
         return true;
       }

     if ( r == null && l != null )
       {
         l.setparent(p);
         if ( t == p.getright() ) p.setright(l);
         if ( t == p.getleft() ) p.setleft(l);
         return true;
       }

     // a node with two children
     r.insert(l);
     r.setparent(p);
     if ( t == p.getright() ) p.setright(r);
     if ( t == p.getleft() ) p.setleft(r);
     return true;
    }

   public synchronized Tree copy()
   {
     if ( root == null ) return null;

     return(new Tree(root.duplicate()));
   }

   public synchronized boolean isempty()
   {
     return ( root == null );
   }


 }
	/*
	* Copyright (c) 2002, 2018, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package gc.gctests.gctest03;

	class DataNodeException extends Exception
	{
	}


	class DataNode {
	int key;
	int buf[];
	static int dataNodeCount = 0;
	static int dataNodeLimit;

	static synchronized void incDataNodeCount()
	{
	dataNodeCount++;
	}

	static synchronized int getDataNodeCount()
	{
	return dataNodeCount;
	}

	static synchronized void setDataNodeLimit(int newLimit)
	{
	dataNodeLimit = newLimit;
	}

	static synchronized int getDataNodeLimit()
	{
	return dataNodeLimit;
	}

	static synchronized void clearDataNodeCount()
	{
	dataNodeCount = 0;
	}
	DataNode(int key) throws DataNodeException
	{

	incDataNodeCount();
	if (getDataNodeCount() > getDataNodeLimit())
	{
	throw (new DataNodeException());
	}

	this.key = key;
	try {
	buf = new int[key];
	}
	catch ( OutOfMemoryError e )
	{
	System.out.println(Thread.currentThread().getName() + " : outofmemory");
	}
	}

	public void print()
	{
	System.out.println(key);
	}

	public boolean equals(DataNode d)
	{
	int k = d.getkey();

	return ( key == k);
	}

	public boolean large(DataNode d)
	{
	int k = d.getkey();

	return ( key > k);
	}

	public boolean less(DataNode d)

	{
	int k = d.getkey();

	return ( key < k);
	}

	public int getkey()
	{ return key; }
	}


	class TreeNode {
	DataNode data;
	TreeNode parent;
	TreeNode left;
	TreeNode right;

	TreeNode(DataNode key)
	{
	this.data = key;
	parent = null;
	left = null;
	right = null;
	}

	public void print()
	{
	data.print();
	}

	public TreeNode getleft()
	{
	return left;
	}

	public TreeNode getright()
	{
	return right;
	}

	public TreeNode getparent()
	{
	return parent;
	}

	public synchronized void setleft(TreeNode left)
	{
	this.left = left;
	}

	public synchronized void setright(TreeNode right)
	{
	this.right = right;
	}

	public synchronized void setparent(TreeNode parent)
	{
	this.parent = parent;
	}

	public DataNode getData()
	{
	return data;
	}

	// print it out in order of a large one first
	public void sprint()
	{
	//print itself
	if ( left != null ) left.sprint();
	System.out.println(data.getkey());
	if ( right != null ) right.sprint();
	}

	// print it out in order of a small one first
	public void lprint()
	{
	if (right != null ) right.lprint();
	System.out.println(data.getkey());
	if ( left != null ) left.lprint();
	}

	public synchronized TreeNode duplicate()
	{
	TreeNode tp = new TreeNode(data);

	if ( left != null )
	{
	tp.left = left.duplicate();
	}
	if ( right != null )
	{
	tp.right = right.duplicate();
	}
	return tp;
	}

	public TreeNode search(DataNode d)
	{
	TreeNode tp = this;
	DataNode k;

	while ( tp != null )
	{
	k = tp.getData();
	if ( k.equals(d) )
	{
	return tp;
	}
	else
	if ( d.large(k) )
	tp = tp.getright();
	else
	tp = tp.getleft();
	}
	return null;
	}

	public synchronized void insert(TreeNode t)
	{
	DataNode d = t.getData();

	TreeNode tp = this;
	TreeNode tp1 = tp;
	DataNode d0;

	while ( true )
	{
	d0 = tp.getData();

	if ( d.large(d0) )
	{
	tp1 = tp;
	tp = tp.getright();
	if ( tp == null )
	{
	tp1.setright(t);
	t.setparent(tp1);
	break;
	}
	}
	else
	{
	tp1 = tp;
	tp = tp.getleft();
	if (tp == null )
	{
	tp1.setleft(t);
	t.setparent(tp1);
	break;
	}
	}
	}

	}


	}


	class Tree {
	TreeNode root = null;

	Tree()
	{
	root = null;
	}

	Tree(TreeNode root)
	{
	this.root = root;
	}

	public synchronized void insert(TreeNode t)
	{
	if ( root == null )
	{
	root = t;
	return;
	}

	root.insert(t);
	}


	public void sort1()
	{
	root.sprint();
	}

	public void sort2()
	{
	root.lprint();
	}

	public TreeNode search(DataNode d)
	{
	if ( root == null ) return null;
	else return root.search(d);
	}

	public synchronized boolean remove(DataNode d)
	{
	if ( root == null ) return false;

	TreeNode t = root.search(d);

	// data is not in a heap
	if ( t == null ) return false;

	/*
	if ( d.equals(t.getData()) == false )
	{
	System.out.println("failed");
	return false;
	}
	*/

	TreeNode p = t.getparent();
	TreeNode l = t.getleft();
	TreeNode r = t.getright();

	// the removed node is a root
	if ( p == null )
	{
	if ( l == null && r != null )
	{
	r.setparent(null);
	root = r;
	return true;
	}
	if ( l != null && r == null )
	{
	l.setparent(null);
	root = l;
	return true;
	}
	if ( l == null && r == null )
	{
	root = null;
	return true;
	}

	if ( l != null && r != null )
	{
	r.setparent(null);
	r.insert(l);
	root = r;
	return true;
	}
	}

	// a leaf
	if ( r == null && l == null )
	{
	if ( p.getright() == t )
	{
	/* right child */
	p.setright(null);
	}
	else
	p.setleft(null);
	return true;
	}

	// a node without left child
	if ( r != null && l == null )
	{
	r.setparent(p);
	if ( t == p.getright() ) p.setright(r);
	if ( t == p.getleft() ) p.setleft(r);
	return true;
	}

	if ( r == null && l != null )
	{
	l.setparent(p);
	if ( t == p.getright() ) p.setright(l);
	if ( t == p.getleft() ) p.setleft(l);
	return true;
	}

	// a node with two children
	r.insert(l);
	r.setparent(p);
	if ( t == p.getright() ) p.setright(r);
	if ( t == p.getleft() ) p.setleft(r);
	return true;
	}

	public synchronized Tree copy()
	{
	if ( root == null ) return null;

	return(new Tree(root.duplicate()));
	}

	public synchronized boolean isempty()
	{
	return ( root == null );
	}


	}