+++ /dev/null
-/*--------------------------------------------------------------------------\r
- * Copyright 2008 Taro L. Saito\r
- *\r
- * Licensed under the Apache License, Version 2.0 (the "License");\r
- * you may not use this file except in compliance with the License.\r
- * You may obtain a copy of the License at\r
- *\r
- * http://www.apache.org/licenses/LICENSE-2.0\r
- *\r
- * Unless required by applicable law or agreed to in writing, software\r
- * distributed under the License is distributed on an "AS IS" BASIS,\r
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
- * See the License for the specific language governing permissions and\r
- * limitations under the License.\r
- *--------------------------------------------------------------------------*/\r
-//--------------------------------------\r
-// XerialJ\r
-//\r
-// RedBlackTree.java\r
-// Since: Dec 5, 2008 5:12:11 PM\r
-//\r
-// $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/RedBlackTree.java $\r
-// $Author: leo $\r
-//--------------------------------------\r
-package org.xerial.util;\r
-\r
-import java.util.Collection;\r
-import java.util.Map;\r
-import java.util.Set;\r
-\r
-/**\r
- * Red-Black tree implementation using Left-Leaning Red-Black Tree (LLRB)\r
- * \r
- * @author leo\r
- * \r
- * @param <Key>\r
- * @param <Value>\r
- */\r
-public class RedBlackTree<Key extends Comparable<Key>, Value> implements Map<Key, Value>\r
-{\r
- private final static boolean RED = true;\r
- private final static boolean BLACK = false;\r
-\r
- private class Node\r
- {\r
- Key key;\r
- Value value;\r
- Node left;\r
- Node right;\r
- boolean color;\r
-\r
- public Node(Key key, Value value)\r
- {\r
- this.key = key;\r
- this.value = value;\r
- this.color = RED; // default is RED\r
- }\r
-\r
- public Node(Key key, Value value, boolean color)\r
- {\r
- this.key = key;\r
- this.value = value;\r
- this.color = color;\r
- }\r
- }\r
-\r
- private Node root;\r
- private int size = 0;\r
- private Value previousValue; // not thread-safe\r
-\r
- public RedBlackTree()\r
- {\r
- clear();\r
- }\r
-\r
- @SuppressWarnings("unchecked")\r
- public Value get(Object key)\r
- {\r
- return get(root, (Key) key);\r
- }\r
-\r
- public Value get(Node current, Key key)\r
- {\r
- if (current == null)\r
- return null;\r
-\r
- int cmp = key.compareTo(current.key);\r
- if (cmp == 0)\r
- return current.value;\r
- else if (cmp < 0)\r
- return get(current.left, key);\r
- else\r
- return get(current.right, key);\r
- }\r
-\r
- public boolean containsKey(Object key)\r
- {\r
- return get(key) != null;\r
- }\r
-\r
- public Value put(Key key, Value value)\r
- {\r
- previousValue = null;\r
- root = insert(root, key, value);\r
- root.color = BLACK;\r
- return previousValue;\r
- }\r
-\r
- private Node insert(Node current, Key key, Value value)\r
- {\r
- // insert at the bottom\r
- if (current == null)\r
- {\r
- previousValue = null;\r
- size++;\r
- return new Node(key, value);\r
- }\r
-\r
- // split 4-nodes (both of left and right edges are red) on the way down\r
- if (isRed(current.left) && isRed(current.right))\r
- flipColor(current);\r
-\r
- int cmp = key.compareTo(current.key);\r
- if (cmp == 0)\r
- {\r
- previousValue = current.value;\r
- current.value = value; // previous value is overwritten because no duplicate keys are allowed\r
- }\r
- else if (cmp < 0)\r
- current.left = insert(current.left, key, value);\r
- else\r
- current.right = insert(current.right, key, value);\r
-\r
- // enforce the left-leaning condition\r
- if (isRed(current.right))\r
- current = rotateLeft(current);\r
-\r
- // balance 4-node (two reds in the left)\r
- if (isRed(current.left) && isRed(current.left.left))\r
- current = rotateRight(current);\r
-\r
- return current;\r
- }\r
-\r
- private boolean isRed(Node node)\r
- {\r
- return node == null ? false : node.color == RED;\r
- }\r
-\r
- private void flipColor(Node node)\r
- {\r
- node.color = !node.color;\r
- node.left.color = !node.left.color;\r
- node.right.color = !node.right.color;\r
- }\r
-\r
- /**\r
- * before:\r
- * \r
- * <pre>\r
- * |\r
- * | c.color\r
- * c\r
- * / \\r
- * / \ x.color\r
- * c.left c.right (x)\r
- * / \\r
- * x.left x.right\r
- * \r
- * </pre>\r
- * \r
- * after:\r
- * \r
- * <pre>\r
- * | \r
- * x\r
- * x.color / \ \r
- * c x.right\r
- * / \\r
- * / \ \r
- * c.left x.left\r
- * </pre>\r
- * \r
- * \r
- * @param c\r
- * @return\r
- */\r
- private Node rotateLeft(Node c)\r
- {\r
- Node x = c.right;\r
- c.right = x.left;\r
- x.left = c;\r
- x.color = x.left.color;\r
- c.color = RED;\r
- return x;\r
- }\r
-\r
- /**\r
- * before:\r
- * \r
- * <pre>\r
- * c.color| \r
- * c\r
- * x.color / \ \r
- * c.left (x) c.right\r
- * / \\r
- * / \ \r
- * x.left x.right\r
- * </pre>\r
- * \r
- * after:\r
- * \r
- * <pre>\r
- * |\r
- * | x.color\r
- * x (c.left)\r
- * / \\r
- * / \ c.color \r
- * x.left c\r
- * / \\r
- * x.right c.right\r
- * \r
- * </pre>\r
- * \r
- * @param c\r
- * @return\r
- */\r
- private Node rotateRight(Node c)\r
- {\r
- Node x = c.left;\r
- c.left = x.right;\r
- x.right = c;\r
- x.color = c.color;\r
- c.color = RED;\r
- return x;\r
- }\r
-\r
- /**\r
- * invariant: curent node (c) is not a 2-node\r
- * \r
- * @param c\r
- * @return\r
- */\r
- private Node fixUp(Node c)\r
- {\r
- if (isRed(c.right))\r
- c = rotateLeft(c);\r
- if (isRed(c.left) && isRed(c.left.left))\r
- c = rotateRight(c);\r
-\r
- // eliminate 4-nodes on the way up\r
- if (isRed(c.left) && isRed(c.right))\r
- flipColor(c);\r
-\r
- return c;\r
- }\r
-\r
- public void clear()\r
- {\r
- root = null;\r
- previousValue = null;\r
- size = 0;\r
- }\r
-\r
- public Node delete(Node c, Key key)\r
- {\r
- int cmp = key.compareTo(c.key);\r
- if (cmp < 0)\r
- {\r
- // delete from the left\r
- c.left = delete(c.left, key);\r
- }\r
- else\r
- {\r
- // TODO impl\r
- }\r
-\r
- return null;\r
- }\r
-\r
- private Node deleteMin(Node c)\r
- {\r
- if (c.left == null)\r
- return null;\r
-\r
- if (!isRed(c.left) && !isRed(c.left.left))\r
- {\r
- // TODO impl\r
- }\r
-\r
- return null;\r
-\r
- }\r
-\r
- public Set<java.util.Map.Entry<Key, Value>> entrySet()\r
- {\r
- // TODO Auto-generated method stub\r
- return null;\r
- }\r
-\r
- public boolean isEmpty()\r
- {\r
- return size == 0;\r
- }\r
-\r
- public Set<Key> keySet()\r
- {\r
- // TODO Auto-generated method stub\r
- return null;\r
- }\r
-\r
- public void putAll(Map< ? extends Key, ? extends Value> newEntries)\r
- {\r
- for (Entry< ? extends Key, ? extends Value> each : newEntries.entrySet())\r
- {\r
- put(each.getKey(), each.getValue());\r
- }\r
-\r
- }\r
-\r
- @SuppressWarnings("unchecked")\r
- public Value remove(Object key)\r
- {\r
- root = delete(root, (Key) key);\r
- root.color = BLACK;\r
- return previousValue;\r
- }\r
-\r
- public int size()\r
- {\r
- return size;\r
- }\r
-\r
- public boolean containsValue(Object arg0)\r
- {\r
- // TODO Auto-generated method stub\r
- return false;\r
- }\r
-\r
- public Collection<Value> values()\r
- {\r
- // TODO Auto-generated method stub\r
- return null;\r
- }\r
-\r
-}\r
OSDN Git Service
