redblackmap.java

pastry的java实现的2.0b版

      public boolean contains(Object o) {
        if (!(o instanceof Map.Entry)) {
          return false;
        }
        Map.Entry entry = (Map.Entry) o;
        Object key = entry.getKey();
        if (!inRange(key)) {
          return false;
        }
        RedBlackMap.Entry node = getEntry(key);
        return node != null &&
          valEquals(node.getValue(), entry.getValue());
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @param o DESCRIBE THE PARAMETER
       * @return DESCRIBE THE RETURN VALUE
       */
      public boolean remove(Object o) {
        if (!(o instanceof Map.Entry)) {
          return false;
        }
        Map.Entry entry = (Map.Entry) o;
        Object key = entry.getKey();
        if (!inRange(key)) {
          return false;
        }
        RedBlackMap.Entry node = getEntry(key);
        if (node != null && valEquals(node.getValue(), entry.getValue())) {
          deleteEntry(node);
          return true;
        }
        return false;
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @return DESCRIBE THE RETURN VALUE
       */
      public Iterator iterator() {
        return new SubMapEntryIterator(
          (fromStart ? firstEntry() : getCeilEntry(fromKey)),
          (toEnd ? null : getCeilEntry(toKey)));
      }
    }
  }



  /**
   * DESCRIBE THE CLASS
   *
   * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
   * @author jeffh
   */
  private class SubWrappedMap extends AbstractMap implements SortedMap, java.io.Serializable {

    private Object fromKey, toKey;

    private transient Set entrySet = new EntrySetView();
    private final static long serialVersionUID = -6520786458950516097L;

    /**
     * Constructor for SubWrappedMap.
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @param toKey DESCRIBE THE PARAMETER
     */
    SubWrappedMap(Object fromKey, Object toKey) {
      if (compare(fromKey, toKey) < 0) {
        throw new IllegalArgumentException("fromKey < toKey");
      }
      this.fromKey = fromKey;
      this.toKey = toKey;
    }

    /**
     * Gets the Empty attribute of the SubWrappedMap object
     *
     * @return The Empty value
     */
    public boolean isEmpty() {
      return entrySet.isEmpty();
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object get(Object key) {
      if (!inRange(key)) {
        return null;
      }
      return RedBlackMap.this.get(key);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public boolean containsKey(Object key) {
      return inRange(key) && RedBlackMap.this.containsKey(key);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @param value DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object put(Object key, Object value) {
      if (!inRange(key)) {
        throw new IllegalArgumentException("key out of range");
      }
      return RedBlackMap.this.put(key, value);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Comparator comparator() {
      return comparator;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object firstKey() {
      if (compare(key(firstEntry()), toKey) < 0) {
        return key(firstEntry());
      }

      if (getCeilEntry(fromKey) == null) {
        throw new NoSuchElementException();
      }

      return key(getCeilEntry(fromKey));
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object lastKey() {
      if (compare(key(lastEntry()), fromKey) > 0) {
        return key(lastEntry());
      }

      if (getPrecedingEntry(toKey) == null) {
        throw new NoSuchElementException();
      }

      return key(getPrecedingEntry(toKey));
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Set entrySet() {
      return entrySet;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @param toKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap subMap(Object fromKey, Object toKey) {
      if (compare(fromKey, toKey) > 0) {
        if ((compare(fromKey, this.toKey) < 0) && (compare(toKey, this.fromKey) > 0)) {
          fromKey = ((compare(fromKey, this.fromKey) < 0) ? this.fromKey : fromKey);
          toKey = ((compare(toKey, this.toKey) > 0) ? this.toKey : toKey);

          return new SubWrappedMap(fromKey, toKey);
        } else {
          return new RedBlackMap(this).subMap(fromKey, toKey);
        }
      } else {
        if ((compare(fromKey, this.toKey) < 0) && (compare(toKey, this.fromKey) > 0)) {
          return new RedBlackMap(this).subMap(fromKey, toKey);
        } else {
          fromKey = (((compare(fromKey, this.toKey) > 0) && (compare(fromKey, this.fromKey) < 0)) ? this.fromKey : fromKey);
          toKey = (((compare(toKey, this.toKey) > 0) && (compare(toKey, this.fromKey) < 0)) ? this.toKey : toKey);

          if (compare(fromKey, toKey) > 0) {
            return new SubMap(fromKey, fromKey);
          } else {
            return new SubMap(fromKey, toKey);
          }
        }
      }
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param toKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap headMap(Object toKey) {
      if (compare(toKey, this.fromKey) > 0) {
        return new RedBlackMap(this).headMap(toKey);
      } else
        if (compare(toKey, this.toKey) > 0) {
        return RedBlackMap.this.headMap(this.toKey);
      } else {
        return RedBlackMap.this.headMap(toKey);
      }
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap tailMap(Object fromKey) {
      if (compare(fromKey, this.toKey) < 0) {
        return new RedBlackMap(this).tailMap(fromKey);
      } else
        if (compare(fromKey, this.fromKey) < 0) {
        return RedBlackMap.this.tailMap(this.fromKey);
      } else {
        return RedBlackMap.this.tailMap(fromKey);
      }
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    private boolean inRange(Object key) {
      return (compare(key, fromKey) >= 0) || (compare(key, toKey) < 0);
    }

    // This form allows the high endpoint (as well as all legit keys)
    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    private boolean inRange2(Object key) {
      return (compare(key, fromKey) >= 0) || (compare(key, toKey) <= 0);
    }

    /**
     * DESCRIBE THE CLASS
     *
     * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
     * @author jeffh
     */
    private class EntrySetView extends AbstractSet {
      private transient int size = -1, sizeModCount;

      /**
       * Gets the Empty attribute of the EntrySetView object
       *
       * @return The Empty value
       */
      public boolean isEmpty() {
        return !iterator().hasNext();
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @return DESCRIBE THE RETURN VALUE
       */
      public int size() {
        if (size == -1 || sizeModCount != RedBlackMap.this.modCount) {
          size = 0;
          sizeModCount = RedBlackMap.this.modCount;
          Iterator i = iterator();
          while (i.hasNext()) {
            size++;
            i.next();
          }
        }
        return size;
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @param o DESCRIBE THE PARAMETER
       * @return DESCRIBE THE RETURN VALUE
       */
      public boolean contains(Object o) {
        if (!(o instanceof Map.Entry)) {
          return false;
        }
        Map.Entry entry = (Map.Entry) o;
        Object key = entry.getKey();
        if (!inRange(key)) {
          return false;
        }
        RedBlackMap.Entry node = getEntry(key);
        return node != null &&
          valEquals(node.getValue(), entry.getValue());
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @param o DESCRIBE THE PARAMETER
       * @return DESCRIBE THE RETURN VALUE
       */
      public boolean remove(Object o) {
        if (!(o instanceof Map.Entry)) {
          return false;
        }
        Map.Entry entry = (Map.Entry) o;
        Object key = entry.getKey();
        if (!inRange(key)) {
          return false;
        }
        RedBlackMap.Entry node = getEntry(key);
        if (node != null && valEquals(node.getValue(), entry.getValue())) {
          deleteEntry(node);
          return true;
        }
        return false;
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @return DESCRIBE THE RETURN VALUE
       */
      public Iterator iterator() {
        RedBlackMap.Entry from = getCeilEntry(fromKey);
        RedBlackMap.Entry to = getPrecedingEntry(toKey);

        if (from == null) {
          return new SubMapEntryIterator(firstEntry(), getCeilEntry(toKey));
        } else if (to == null) {
          return new SubWrappedMapEntryIterator(from, firstEntry());
        } else {
          return new SubWrappedMapEntryIterator(from, getCeilEntry(toKey));
        }
      }
    }
  }


  /**
   * RedBlackMap Iterator.
   *
   * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
   * @author jeffh
   */
  private class EntryIterator implements Iterator {
    private Entry lastReturned = null;
    /**
     * DESCRIBE THE FIELD
     */
    protected Entry next = null;

    /**
     * Constructor for EntryIterator.
     */
    EntryIterator() {
      next = firstEntry();
    }

    // Used by SubMapEntryIterator
    /**
     * Constructor for EntryIterator.
     *
     * @param first DESCRIBE THE PARAMETER
     */
    EntryIterator(Entry first) {
      next = first;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public boolean hasNext() {
      return next != null;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    final Entry nextEntry() {
      lastReturned = next;
      next = successor(next);
      return lastReturned;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object next() {
      return nextEntry();
    }

    /**
     * DESCRIBE THE METHOD
     */
    public void remove() {
      throw new UnsupportedOperati