|
Java example source code file (AVLTreeTest.java)
The AVLTreeTest.java Java example source code/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.math3.geometry.partitioning.utilities; import org.apache.commons.math3.geometry.partitioning.utilities.AVLTree; import org.junit.Assert; import org.junit.Test; @Deprecated public class AVLTreeTest { @Test public void testInsert() { // this array in this order allows to pass in all branches // of the insertion algorithm int[] array = { 16, 13, 15, 14, 2, 0, 12, 9, 8, 5, 11, 18, 19, 17, 4, 7, 1, 3, 6, 10 }; AVLTree<Integer> tree = buildTree(array); Assert.assertEquals(array.length, tree.size()); for (int i = 0; i < array.length; ++i) { Assert.assertEquals(array[i], value(tree.getNotSmaller(new Integer(array[i])))); } checkOrder(tree); } @Test public void testDelete1() { int[][][] arrays = { { { 16, 13, 15, 14, 2, 0, 12, 9, 8, 5, 11, 18, 19, 17, 4, 7, 1, 3, 6, 10 }, { 11, 10, 9, 12, 16, 15, 13, 18, 5, 0, 3, 2, 14, 6, 19, 17, 8, 4, 7, 1 } }, { { 16, 13, 15, 14, 2, 0, 12, 9, 8, 5, 11, 18, 19, 17, 4, 7, 1, 3, 6, 10 }, { 0, 17, 14, 15, 16, 18, 6 } }, { { 6, 2, 7, 8, 1, 4, 3, 5 }, { 8 } }, { { 6, 2, 7, 8, 1, 4, 5 }, { 8 } }, { { 3, 7, 2, 1, 5, 8, 4 }, { 1 } }, { { 3, 7, 2, 1, 5, 8, 6 }, { 1 } } }; for (int i = 0; i < arrays.length; ++i) { AVLTree<Integer> tree = buildTree(arrays[i][0]); Assert.assertTrue(! tree.delete(new Integer(-2000))); for (int j = 0; j < arrays[i][1].length; ++j) { Assert.assertTrue(tree.delete(tree.getNotSmaller(new Integer(arrays[i][1][j])).getElement())); Assert.assertEquals(arrays[i][0].length - j - 1, tree.size()); } } } @Test public void testNavigation() { int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; AVLTree<Integer> tree = buildTree(array); AVLTree<Integer>.Node node = tree.getSmallest(); Assert.assertEquals(array[0], value(node)); for (int i = 0; i < array.length; ++i) { Assert.assertEquals(array[i], value(node)); node = node.getNext(); } Assert.assertNull(node); node = tree.getLargest(); Assert.assertEquals(array[array.length - 1], value(node)); for (int i = array.length - 1; i >= 0; --i) { Assert.assertEquals(array[i], value(node)); node = node.getPrevious(); } Assert.assertNull(node); checkOrder(tree); } @Test public void testSearch() { int[] array = { 2, 4, 6, 8, 10, 12, 14 }; AVLTree<Integer> tree = buildTree(array); Assert.assertNull(tree.getNotLarger(new Integer(array[0] - 1))); Assert.assertNull(tree.getNotSmaller(new Integer(array[array.length - 1] + 1))); for (int i = 0; i < array.length; ++i) { Assert.assertEquals(array[i], value(tree.getNotSmaller(new Integer(array[i] - 1)))); Assert.assertEquals(array[i], value(tree.getNotLarger(new Integer(array[i] + 1)))); } checkOrder(tree); } @Test public void testRepetition() { int[] array = { 1, 1, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7 }; AVLTree<Integer> tree = buildTree(array); Assert.assertEquals(array.length, tree.size()); AVLTree<Integer>.Node node = tree.getNotSmaller(new Integer(3)); Assert.assertEquals(3, value(node)); Assert.assertEquals(1, value(node.getPrevious())); Assert.assertEquals(3, value(node.getNext())); Assert.assertEquals(4, value(node.getNext().getNext())); node = tree.getNotLarger(new Integer(2)); Assert.assertEquals(1, value(node)); Assert.assertEquals(1, value(node.getPrevious())); Assert.assertEquals(3, value(node.getNext())); Assert.assertNull(node.getPrevious().getPrevious()); AVLTree<Integer>.Node otherNode = tree.getNotSmaller(new Integer(1)); Assert.assertTrue(node != otherNode); Assert.assertEquals(1, value(otherNode)); Assert.assertNull(otherNode.getPrevious()); node = tree.getNotLarger(new Integer(10)); Assert.assertEquals(7, value(node)); Assert.assertNull(node.getNext()); node = node.getPrevious(); Assert.assertEquals(7, value(node)); node = node.getPrevious(); Assert.assertEquals(7, value(node)); node = node.getPrevious(); Assert.assertEquals(7, value(node)); node = node.getPrevious(); Assert.assertEquals(7, value(node)); node = node.getPrevious(); Assert.assertEquals(6, value(node)); checkOrder(tree); } private AVLTree<Integer> buildTree(int[] array) { AVLTree<Integer> tree = new AVLTree Other Java examples (source code examples)Here is a short list of links related to this Java AVLTreeTest.java source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.