redblackmap.java

pastry的java实现的2.0b版

/*************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate 

Copyright 2002, Rice University. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither  the name  of Rice  University (RICE) nor  the names  of its
contributors may be  used to endorse or promote  products derived from
this software without specific prior written permission.

This software is provided by RICE and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall RICE or contributors be liable
for any direct, indirect, incidental, special, exemplary, or
consequential damages (including, but not limited to, procurement of
substitute goods or services; loss of use, data, or profits; or
business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even
if advised of the possibility of such damage.

********************************************************************************/
/*
 *  @(#)RedBlackMap.java	1.56 03/01/23
 *
 *  Copyright 2003 Sun Microsystems, Inc. All rights reserved.
 *  SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package rice.p2p.util;

import java.util.*;

/**
 * This class is a modification of the RedBlackMap java class, with the added
 * benefit that iterators do not throw a ConcurrentModificationException when
 * the backing tree changes. The iterator is guaranteed to walk through some
 * version of the tree, and may show nodes which were deleted or which were
 * subsequently added, but it will not die.
 *
 * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
 * @author jeffh
 */

public class RedBlackMap extends AbstractMap implements SortedMap, Cloneable, java.io.Serializable {
  /**
   * The Comparator used to maintain order in this RedBlackMap, or null if this
   * RedBlackMap uses its elements natural ordering.
   *
   * @serial
   */
  private Comparator comparator = null;

  private transient Entry root = null;

  /**
   * The number of entries in the tree
   */
  private transient int size = 0;

  /**
   * The number of structural modifications to the tree.
   */
  private transient int modCount = 0;

  // Views

  /**
   * This field is initialized to contain an instance of the entry set view the
   * first time this view is requested. The view is stateless, so there's no
   * reason to create more than one.
   */
  private transient volatile Set entrySet = null;
  private transient volatile Set keySet = null;
  private transient volatile Collection values = null;

  private final static boolean RED = false;
  private final static boolean BLACK = true;

  private final static long serialVersionUID = 919286545866124006L;

  /**
   * Constructs a new, empty map, sorted according to the keys' natural order.
   * All keys inserted into the map must implement the <tt>Comparable</tt>
   * interface. Furthermore, all such keys must be <i>mutually comparable</i> :
   * <tt>k1.compareTo(k2)</tt> must not throw a ClassCastException for any
   * elements <tt>k1</tt> and <tt>k2</tt> in the map. If the user attempts to
   * put a key into the map that violates this constraint (for example, the user
   * attempts to put a string key into a map whose keys are integers), the <tt>
   * put(Object key, Object value)</tt> call will throw a <tt>ClassCastException
   * </tt>.
   *
   * @see Comparable
   */
  public RedBlackMap() {
  }

  /**
   * Constructs a new, empty map, sorted according to the given comparator. All
   * keys inserted into the map must be <i>mutually comparable</i> by the given
   * comparator: <tt>comparator.compare(k1, k2)</tt> must not throw a <tt>
   * ClassCastException</tt> for any keys <tt>k1</tt> and <tt>k2</tt> in the
   * map. If the user attempts to put a key into the map that violates this
   * constraint, the <tt>put(Object key, Object value)</tt> call will throw a
   * <tt>ClassCastException</tt> .
   *
   * @param c the comparator that will be used to sort this map. A <tt>null</tt>
   *      value indicates that the keys' <i>natural ordering</i> should be used.
   */
  public RedBlackMap(Comparator c) {
    this.comparator = c;
  }

  /**
   * Constructs a new map containing the same mappings as the given map, sorted
   * according to the keys' <i>natural order</i> . All keys inserted into the
   * new map must implement the <tt>Comparable</tt> interface. Furthermore, all
   * such keys must be <i>mutually comparable</i> : <tt>k1.compareTo(k2)</tt>
   * must not throw a <tt>ClassCastException</tt> for any elements <tt>k1</tt>
   * and <tt>k2</tt> in the map. This method runs in n*log(n) time.
   *
   * @param m the map whose mappings are to be placed in this map.
   * @throws ClassCastException the keys in t are not Comparable, or are not
   *      mutually comparable.
   * @throws NullPointerException if the specified map is null.
   */
  public RedBlackMap(Map m) {
    putAll(m);
  }

  /**
   * Constructs a new map containing the same mappings as the given <tt>
   * SortedMap</tt> , sorted according to the same ordering. This method runs in
   * linear time.
   *
   * @param m the sorted map whose mappings are to be placed in this map, and
   *      whose comparator is to be used to sort this map.
   * @throws NullPointerException if the specified sorted map is null.
   */
  public RedBlackMap(SortedMap m) {
    comparator = m.comparator();
    try {
      buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
  }

  /**
   * Returns the value to which this map maps the specified key. Returns <tt>
   * null</tt> if the map contains no mapping for this key. A return value of
   * <tt>null</tt> does not <i>necessarily</i> indicate that the map contains no
   * mapping for the key; it's also possible that the map explicitly maps the
   * key to <tt>null</tt> . The <tt>containsKey</tt> operation may be used to
   * distinguish these two cases.
   *
   * @param key key whose associated value is to be returned.
   * @return the value to which this map maps the specified key, or <tt>null
   *      </tt> if the map contains no mapping for the key.
   * @throws ClassCastException key cannot be compared with the keys currently
   *      in the map.
   * @throws NullPointerException key is <tt>null</tt> and this map uses natural
   *      ordering, or its comparator does not tolerate <tt>null</tt> keys.
   * @see #containsKey(Object)
   */
  public synchronized Object get(Object key) {
    Entry p = getEntry(key);
    return (p == null ? null : p.value);
  }

  /**
   * Returns this map's entry for the given key, or <tt>null</tt> if the map
   * does not contain an entry for the key.
   *
   * @param key DESCRIBE THE PARAMETER
   * @return this map's entry for the given key, or <tt>null</tt> if the map
   *      does not contain an entry for the key.
   * @throws ClassCastException if the key cannot be compared with the keys
   *      currently in the map.
   * @throws NullPointerException key is <tt>null</tt> and this map uses natural
   *      order, or its comparator does not tolerate * <tt>null</tt> keys.
   */
  private synchronized Entry getEntry(Object key) {
    Entry p = root;
    while (p != null) {
      int cmp = compare(key, p.key);
      if (cmp == 0) {
        return p;
      } else if (cmp < 0) {
        p = p.left;
      } else {
        p = p.right;
      }
    }
    return null;
  }

  /**
   * Gets the entry corresponding to the specified key; if no such entry exists,
   * returns the entry for the least key greater than the specified key; if no
   * such entry exists (i.e., the greatest key in the Tree is less than the
   * specified key), returns <tt>null</tt> .
   *
   * @param key DESCRIBE THE PARAMETER
   * @return The CeilEntry value
   */
  private synchronized Entry getCeilEntry(Object key) {
    Entry p = root;
    if (p == null) {
      return null;
    }

    while (true) {
      int cmp = compare(key, p.key);
      if (cmp == 0) {
        return p;
      } else if (cmp < 0) {
        if (p.left != null) {
          p = p.left;
        } else {
          return p;
        }
      } else {
        if (p.right != null) {
          p = p.right;
        } else {
          Entry parent = p.parent;
          Entry ch = p;
          while (parent != null && ch == parent.right) {
            ch = parent;
            parent = parent.parent;
          }
          return parent;
        }
      }
    }
  }

  /**
   * Returns the entry for the greatest key less than the specified key; if no
   * such entry exists (i.e., the least key in the Tree is greater than the
   * specified key), returns <tt>null</tt> .
   *
   * @param key DESCRIBE THE PARAMETER
   * @return The PrecedingEntry value
   */
  private synchronized Entry getPrecedingEntry(Object key) {
    Entry p = root;
    if (p == null) {
      return null;
    }

    while (true) {
      int cmp = compare(key, p.key);
      if (cmp > 0) {
        if (p.right != null) {
          p = p.right;
        } else {
          return p;
        }
      } else {
        if (p.left != null) {
          p = p.left;
        } else {
          Entry parent = p.parent;
          Entry ch = p;
          while (parent != null && ch == parent.left) {
            ch = parent;
            parent = parent.parent;
          }
          return parent;
        }
      }
    }
  }

  /**
   * Gets the Key attribute of the RedBlackMap object
   *
   * @param key DESCRIBE THE PARAMETER
   * @return The Key value
   */
  public Object getKey(Object key) {
    if (key == null) {
      return null;
    }

    Entry p = getEntry(key);
    if (p == null) {
      return null;
    }

    return p.key;
  }

  /**
   * DESCRIBE THE METHOD
   */
  private void incrementSize() {
    modCount++;
    size++;
  }

  /**
   * DESCRIBE THE METHOD
   */
  private void decrementSize() {
    modCount++;
    size--;
  }


  // Query Operations

  /**
   * Returns the number of key-value mappings in this map.
   *
   * @return the number of key-value mappings in this map.
   */
  public int size() {
    return size;
  }

  /**
   * Returns <tt>true</tt> if this map contains a mapping for the specified key.
   *
   * @param key key whose presence in this map is to be tested.
   * @return <tt>true</tt> if this map contains a mapping for the specified key.
   * @throws ClassCastException if the key cannot be compared with the keys
   *      currently in the map.
   * @throws NullPointerException key is <tt>null</tt> and this map uses natural
   *      ordering, or its comparator does not tolerate <tt>null</tt> keys.
   */
  public synchronized boolean containsKey(Object key) {
    return getEntry(key) != null;
  }

  /**
   * Returns <tt>true</tt> if this map maps one or more keys to the specified
   * value. More formally, returns <tt>true</tt> if and only if this map
   * contains at least one mapping to a value <tt>v</tt> such that <tt>
   * (value==null ? v==null : value.equals(v))</tt> . This operation will
   * probably require time linear in the Map size for most implementations of
   * Map.
   *
   * @param value value whose presence in this Map is to be tested.
   * @return <tt>true</tt> if a mapping to <tt>value</tt> exists; <tt>false</tt>
   *      otherwise.
   * @since 1.2
   */
  public synchronized boolean containsValue(Object value) {
    return (root == null ? false :
      (value == null ? valueSearchNull(root)
      : valueSearchNonNull(root, value)));
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param n DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private boolean valueSearchNull(Entry n) {
    if (n.value == null) {
      return true;
    }

    // Check left and right subtrees for value
    return (n.left != null && valueSearchNull(n.left)) ||
      (n.right != null && valueSearchNull(n.right));
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param n DESCRIBE THE PARAMETER
   * @param value DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private boolean valueSearchNonNull(Entry n, Object value) {
    // Check this node for the value
    if (value.equals(n.value)) {
      return true;
    }

    // Check left and right subtrees for value
    return (n.left != null && valueSearchNonNull(n.left, value)) ||
      (n.right != null && valueSearchNonNull(n.right, value));
  }

  /**
   * Returns the comparator used to order this map, or <tt>null</tt> if this map
   * uses its keys' natural order.
   *
   * @return the comparator associated with this sorted map, or <tt>null</tt> if
   *      it uses its keys' natural sort method.
   */
  public Comparator comparator() {
    return comparator;
  }

  /**
   * Returns the first (lowest) key currently in this sorted map.
   *
   * @return the first (lowest) key currently in this sorted map.
   * @throws NoSuchElementException Map is empty.
   */
  public synchronized Object firstKey() {
    return key(firstEntry());
  }

  /**
   * Returns the last (highest) key currently in this sorted map.
   *
   * @return the last (highest) key currently in this sorted map.
   * @throws NoSuchElementException Map is empty.
   */
  public synchronized Object lastKey() {
    return key(lastEntry());
  }