com.netflix.nfgraph.compressed

Class CompactOrdinalSet

java.lang.Object

com.netflix.nfgraph.OrdinalSet

com.netflix.nfgraph.compressed.CompactOrdinalSet

public class CompactOrdinalSet
extends OrdinalSet

An implementation of OrdinalSet, returned for connections represented as variable-byte deltas in an NFCompressedGraph.

A variable-byte delta representation contains between one and five bytes per connection. The ordinals in the set are sorted ascending, then encoded as the difference between each ordinal and the last ordinal.

For example, the values [ 7, 11, 13, 21 ] will be encoded as [ 7, 4, 2, 8 ].

This is done because smaller values can be represented in fewer bytes.

Because each value can only be derived using the previous value, contains() is an O(n) operation.

This representation for a connection set can be configured for an NFPropertySpec using NFPropertySpec.COMPACT.

See Also:

The Netflix Tech Blog, Variable-length quantity, Compact Representations

Field Summary

Fields inherited from class com.netflix.nfgraph.OrdinalSet

EMPTY_SET

Constructor Summary

Constructors

Constructor and Description
CompactOrdinalSet(com.netflix.nfgraph.util.ByteArrayReader reader)

Method Summary

Modifier and Type	Method and Description
boolean	contains(int value) Returns true when the specified value is contained in this set.
boolean	containsAll(int... values) Returns true when all specified values are contained in this set.
OrdinalIterator	iterator()
int	size()

Methods inherited from class com.netflix.nfgraph.OrdinalSet

asArray

Methods inherited from class java.lang.Object

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

Constructor Detail

CompactOrdinalSet

public CompactOrdinalSet(com.netflix.nfgraph.util.ByteArrayReader reader)

Method Detail

contains

public boolean contains(int value)

Description copied from class: OrdinalSet

Returns true when the specified value is contained in this set. Depending on the implementation, this operation will have one of two performance characteristics:

O(1) for HashSetOrdinalSet and BitSetOrdinalSet
O(n) for CompactOrdinalSet and NFBuildGraphOrdinalSet

Specified by:

contains in class OrdinalSet

containsAll

public boolean containsAll(int... values)

Description copied from class: OrdinalSet

Returns true when all specified values are contained in this set. Depending on the implementation, this operation will have one of two performance characteristics:

O(m) for HashSetOrdinalSet and BitSetOrdinalSet, where m is the number of specified elements.
O(n) for CompactOrdinalSet, where n is the number of elements in the set.
O(n * m) for NFBuildGraphOrdinalSet.

Overrides:

containsAll in class OrdinalSet

iterator

public OrdinalIterator iterator()

Specified by:

iterator in class OrdinalSet

Returns:

an OrdinalIterator over this set.

size

public int size()

Specified by:

size in class OrdinalSet

Returns:

the number of ordinals in this set.