io.pravega.common.util

Class AvlTreeIndex<V extends SortedIndex.IndexEntry>

java.lang.Object

io.pravega.common.util.AvlTreeIndex<V>

Type Parameters:

V - The type of the IndexEntries.

All Implemented Interfaces:

SortedIndex<V>

public class AvlTreeIndex<V extends SortedIndex.IndexEntry>
extends java.lang.Object
implements SortedIndex<V>

SortedIndex backed by an AVL Tree.

Note: This class is not thread-safe and requires external synchronization when in a multi-threaded environment.

Nested Class Summary

Nested classes/interfaces inherited from interface io.pravega.common.util.SortedIndex

SortedIndex.IndexEntry

Constructor Summary

Constructors

Constructor and Description
AvlTreeIndex() Creates a new instance of the AvlTreeIndex class.

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the contents of the Index.
void	forEach(java.util.function.Consumer<V> consumer) Iterates through each item in the Index, in natural order, and calls the given consumer on all of them.
V	get(long key) Gets an item with the given key.
V	getCeiling(long key) Gets the smallest item whose key is greater than or equal to the given key.
V	getFirst() Gets the smallest item in the index.
V	getFloor(long key) Gets the largest item whose key is smaller than or equal to the given key.
V	getLast() Gets the largest item in the index.
V	put(V item) Inserts the given item into the Index.
V	remove(long key) Removes any item with the given key from the Index.
int	size() Gets a value indicating the number of items in the Index.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AvlTreeIndex

public AvlTreeIndex()

Creates a new instance of the AvlTreeIndex class.

Method Detail

clear

public void clear()

Description copied from interface: SortedIndex

Clears the contents of the Index.

Specified by:

clear in interface SortedIndex<V extends SortedIndex.IndexEntry>

put

public V put(V item)

Description copied from interface: SortedIndex

Inserts the given item into the Index. If there already exists an item with the same key, it will be overridden.

Specified by:

put in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

item - The item to insert.

Returns:

The displaced item, if any.

remove

public V remove(long key)

Description copied from interface: SortedIndex

Removes any item with the given key from the Index.

Specified by:

remove in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

key - The key of the item to remove.

Returns:

The removed item, or null if nothing was removed.

size

public int size()

Description copied from interface: SortedIndex

Gets a value indicating the number of items in the Index.

Specified by:

size in interface SortedIndex<V extends SortedIndex.IndexEntry>

Returns:

Integer indicating the size or number of items in the Index.

get

public V get(long key)

Description copied from interface: SortedIndex

Gets an item with the given key.

Specified by:

get in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

key - The key to search by.

Returns:

The requested item, if it exists, or null if it doesn't.

getCeiling

public V getCeiling(long key)

Description copied from interface: SortedIndex

Gets the smallest item whose key is greater than or equal to the given key.

Specified by:

getCeiling in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

key - the Key to search by.

Returns:

The sought item, or null if it doesn't exist.

getFloor

public V getFloor(long key)

Description copied from interface: SortedIndex

Gets the largest item whose key is smaller than or equal to the given key.

Specified by:

getFloor in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

key - the Key to search by.

Returns:

The sought item, or null if it doesn't exist.

getFirst

public V getFirst()

Description copied from interface: SortedIndex

Gets the smallest item in the index.

Specified by:

getFirst in interface SortedIndex<V extends SortedIndex.IndexEntry>

Returns:

The sought item, or null (if no items in the index).

getLast

public V getLast()

Description copied from interface: SortedIndex

Gets the largest item in the index.

Specified by:

getLast in interface SortedIndex<V extends SortedIndex.IndexEntry>

Returns:

The sought item, or null (if no items in the index).

forEach

public void forEach(java.util.function.Consumer<V> consumer)

Description copied from interface: SortedIndex

Iterates through each item in the Index, in natural order, and calls the given consumer on all of them.

Specified by:

forEach in interface SortedIndex<V extends SortedIndex.IndexEntry>

Parameters:

consumer - The consumer to invoke.