Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## ix.isim.util
Class LongKeyTreeMap

    java.lang.Object
      ix.isim.util.LongKeyTreeMap

    public class LongKeyTreeMap

extends java.lang.Object

This is a Red-Black-Tree-based implementation of a sorted map, mapping `long`s to objects. This class guarantees that the map will be in ascending key order and the `Iterator` returned by `values()` will list the values (not the keys) in ascending key order.

This implementation provides guaranteed log(n) time cost for the `containsKey(...)`, `get(...)`, `put(...)` and `remove(...)` operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

This implementation should essentially behave like the one in the java.util package. The main difference is that keys are `long`s here which are not ojbects. The use of `long`s rather than `Double`s greatly improves the efficiency of the implementation.

Nested Class Summary
`(package private) static class` | `LongKeyTreeMap.Entry` A node in the tree.
`(package private) class` | `LongKeyTreeMap.LongKeyTreeMapIterator`

Field Summary
`protected LongKeyTreeMap.Entry` | `root` the root of the tree

Constructor Summary
`LongKeyTreeMap()` This constructor creates a new, empty map.

Method Summary
`void` | `clear()` This function removes all mappings from this map.
`protected java.lang.Object` | `clone()` This class does not support cloning and an exception will be thrown if this method is called.
`boolean` | `containsKey(long key)` This function returns `true` if this map contains a mapping for the specified key.
`long` | `firstKey()` This function returns the first (lowest) key currently in this sorted map.
`java.lang.Object` | `get(long key)` This function returns the value to which this map maps the specified key.
`long` | `lastKey()` This function returns the last (highest) key currently in this sorted map.
`java.lang.Object` | `put(long key, java.lang.Object value)` This function associates the specified value with the specified key in this map.
`java.lang.Object` | `remove(long key)` This function removes the mapping for this key from this map if it was present.
`int` | `size()` This function returns the number of key-value mappings in this map.
`java.util.Iterator` | `values()` This function returns an iterator for the objects in this map.

Methods inherited from class java.lang.Object
`equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### root

    protected LongKeyTreeMap.Entry root

  the root of the tree

Constructor Detail

### LongKeyTreeMap

    public LongKeyTreeMap()

  This constructor creates a new, empty map.

Method Detail

### clone

    protected java.lang.Object clone()
                              throws java.lang.CloneNotSupportedException

  This class does not support cloning and an exception will be thrown if this method is called.

  Overrides:
    `clone` in class `java.lang.Object`
  Returns:
    nothing
  Throws:
    `java.lang.CloneNotSupportedException` - will be thrown

### size

    public int size()

  This function returns the number of key-value mappings in this map.

  Returns:
    the number of key-value mappings in this map

### containsKey

    public boolean containsKey(long key)

  This function returns `true` if this map contains a mapping for the specified key.

  Parameters:
    `key` - the key whose presence in this map is to be tested
  Returns:
    `true` if this map contains a mapping for the specified key

### get

    public java.lang.Object get(long key)

  This function returns the value to which this map maps the specified key. It returns `null` if the map contains no mapping for this key. A return value of `null` does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to `null`. The `containsKey(...)` operation may be used to distinguish these two cases.

  Parameters:
    `key` - key whose associated value is to be returned
  Returns:
    the value to which this map maps the specified key, or `null` if the map contains no mapping for the key

### firstKey

    public long firstKey()
                  throws java.util.NoSuchElementException

  This function returns the first (lowest) key currently in this sorted map.

  Returns:
    the first (lowest) key currently in this sorted map
  Throws:
    `NoSuchElementException` - if the map is empty

### lastKey

    public long lastKey()
                 throws java.util.NoSuchElementException

  This function returns the last (highest) key currently in this sorted map.

  Returns:
    the last (highest) key currently in this sorted map
  Throws:
    `NoSuchElementException` - if the map is empty

### put

    public java.lang.Object put(long key,
                                java.lang.Object value)

  This function associates the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced. A `null` return may indicate that the map previously associated `null` with the specified key.

  Parameters:
    `key` - the key with which the specified value is to be associated
    `value` - the value to be associated with the specified key
  Returns:
    previous value associated with specified key, or `null` if there was no mapping for the key

### remove

    public java.lang.Object remove(long key)

  This function removes the mapping for this key from this map if it was present. A `null` return may indicate that the map previously associated `null` with the specified key.

  Parameters:
    `key` - the key to the mapping that is to be removed
  Returns:
    the previous value associated with specified key, or `null` if there was no mapping for the key

### clear

    public void clear()

  This function removes all mappings from this map.

### values

    public java.util.Iterator values()

  This function returns an iterator for the objects in this map. They will be returned in the (ascending) order of their keys.

  Returns:
    an ordered `Iterator` of the values (not keys) in this map

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD