com.persistit

Class KeyFilter

java.lang.Object

com.persistit.KeyFilter

public class KeyFilter
extends Object

Specifies a subset of all possible keys values. A KeyFilter can be used with the Exchange.traverse(Key.Direction, KeyFilter, int) method to restrict the set of key values within a Persistit Tree that will actually be traversed.

A KeyFilter provides two primary methods:

• selected(Key) indicates whether the value of the specified Key is a member of the subset specified by this filter, and
• next(Key, Key.Direction) modifies the Key to the next larger or smaller key value that lies within the range specified by this filter.

These methods permit efficient traversal of a filtered subset of keys within a Tree.

KeyFilter Terms

A KeyFilter consists of an array of one or more terms. Each term corresponds to one segment in a key value that will be selected or excluded by this KeyFilter. The Kth term in the list applies to the Kth segment of a key.

There are three kinds of term:

SimpleTerm

Represents a single segment value. To match a SimpleTerm, the value of the key segment in the corresponding position must exactly match the SimpleTerm's value.

RangeTerm

Represents a range of values. To match a RangeTerm, the value of the key segment in the corresponding position must fall between the end points of the range according to the key ordering specification. RangeTerms can be defined to include or exclude either end point.

OrTerm

Represents alternatives. Each alternative is itself a SimpleTerm or a RangeTerm. To match an OrTerm, the value of the key segment in the corresponding position must match one of the alternative terms associated with the OrTerm.

The static methods simpleTerm(Object), rangeTerm(Object, Object), rangeTerm(Object, Object, CoderContext), rangeTerm(Object, Object, boolean, boolean), rangeTerm(Object, Object, boolean, boolean, CoderContext), and orTerm(com.persistit.KeyFilter.Term[]) produce these various kinds of Terms

For example, consider a key consisting of three segments: a last name, a first name and a person ID number for a person. Such a key value might be constructed with code such as this:

     key.clear().append("McDonald").append("Bob").append(12345);
 

Suppose we now want to enumerate all members of a tree having keys of this form with last names falling between "M" and "Q", and first names equal to either "Alice" or "Bob". The following code constructs a KeyFilter for this purpose:

     KeyFilter keyFilter = new KeyFilter();
     keyFilter = keyFilter.append(KeyFilter.rangeTerm("M", "Q"));
     keyFilter = keyFilter.append(KeyFilter.orTerm(new KeyFilter.Term[]{
         KeyFilter.simpleTerm("Alice"), KeyFilter.simpleTerm("Bob"))});
 

The first term specifies a range that includes any last name that sorts alphabetically between "M" and "Q" (inclusively). The second term is an OrTerm that selects the first names "Alice" or "Bob".

A RangeTerm optionally specifies whether the end-points are inclusive. For example, the term

     KeyFilter.rangeTerm("Jones", "Smith", true, false)
 

includes the name "Jones" and all names that follow up to, but not including, "Smith". If unspecified, the end-points of the range are included.

Minimum and Maximum Depth

A KeyFilter may also specify minimum depth, maximum depth, or both. These values control the number of segments that must be present in key value in order for it to be selected. A KeyFilter will select a key only if the number of segments in the key lies between the minimum depth and the maximum depth, inclusive.

String Representation

The toString() method returns a canonical String representation of the current terms for this KeyFilter. For example, the string representation of the filter constructed in above is

     {"M":"Q",{"Alice","Bob"}}
 

You can construct a KeyFilter from its string representation with the KeyParser.parseKeyFilter() method. For example, the following code generates an equivalent KeyFilter:

     KeyParser parser = new KeyParser("{\"M\":\"Q\",{\"Alice\",\"Bob\"}};
     KeyFilter filter = parser.parseKeyFilter();
 

As a convenience, the constructor KeyFilter(String) automatically creates and invokes a KeyParser to create a KeyFilter from its string representation.

Following is an informal grammar for the string representation of a key filter. See string representation in Key for information on how to specify a key segment value.

    keyFilter ::= '{' termElement [',' termElement]... '}'
    termElement ::= [ '>' ] term [ '<' ]
    term ::= segment | range | qualifiedRange | orTerm
    segment ::= see segment
    range ::= segment ':' segment | ':' segment | segment ':'
    qualifiedRange = ('(' | '[') range (')' | ']')
    orTerm ::= '{' term [',' term ]...'}'
 

A range may omit either the starting segment value or the ending segment value. When the starting segment value is omitted, the range starts before the first possible key value, and when the ending segment value is omitted, the range ends after the last possible key value. Thus the range specification

   {"Smith":}
 

include every key with a first segment value of "Smith" or above. Similarly,

   {:"Smith"}
 

includes all keys up to and including "Smith".

A qualifiedRange allows you to specify whether the end-points of a range are included or excluded from the selected subset. A square bracket indicates that the end-point is included, while a parenthesis indicates that it is excluded. For example

   {("Jones":"Smith"]}
 

does not include "Jones" but does include "Smith". An unqualified range specification such as

   {"Jones":"Smith"}
 

includes both end-points. It is equivelent to

   {["Jones":"Smith"]}
 

Within the string representation of a KeyFilter at most one term element may specify the prefix ">" (greater-than sign), and at most one term element may specify the suffix "<" (less-than sign). These denote the minimum and maximum depths of the KeyFilter, respectively. The minimum depth is the count of term elements up to and including the term marked with a ">" and the maximum depth is the count of terms up to and including the term marked with a ">". For example, in the KeyFilter represented by the string

   {*,>100:200,*<}
 

the minimum depth is 2 and the maximum depth is 3.

Building KeyFilters by Appending Terms

A KeyFilter is immutable. The methods append(KeyFilter), append(KeyFilter.Term), append(KeyFilter.Term[]), create new KeyFilters with additional terms supplied by the supplied KeyFilter, Term or array of Terms. The limit(int, int) method creates a new KeyFilter with modified minimum and maximum depth values. Each of these methods returns a new KeyFilter which results from combining the original KeyFilter with the supplied information.

Formal Specification of the next(Key, Key.Direction) Method

A KeyFilter defines a subset of the the set of all Key values: the Exchange.traverse(Key.Direction, KeyFilter, int) method returns only values in this subset. The following definitions are used in describing the behavior of the next(Key, Key.Direction) method.

Range

Let S be the ordered set of all possible key values. (Though large, this set is finite because a Keys have finite length.) The range R is the subset of keys in S selected by this KeyFilter.

Adjacent

Two keys K1 and K2 in this set are adjacent if K1 != K2 and there exists no other key value K such that K1 < K < K2. The terms left-adjacent and right-adjacent describe the precedence: K1 is left-adjacent to K2; K2 is right-adjacent to K1

Contiguous

Let C be a subset of R. Let Kmin and Kmax be the smallest and largest keys in C, respectively. Then C is contiguous if there is no key K not in R where Kmin < K < Kmax.

Direction

The Key.Direction is supplied to the Exchange.traverse(Key.Direction, KeyFilter, int) method to control navigation. There are five possible values:

• LT: the result key must be strictly less than the supplied key.
• LTEQ: the result key must be less than or equal to the supplied key.
• EQ: the result key must be equal to the supplied key.
• GTEQ: the result key must be greater than or equal to the supplied key.
• GT: the result key must be strictly greater than the supplied key.

LT and GT are called exclusive because the result of traverse excludes the supplied key. LTEQ and GTEQ are inclusive.

A KeyFilter defines the range R as zero or more contiguous subsets of S. The next method is used to assist the traverse method by skipping efficiently over keys that are not in contained in R. Given a Key K and a Key.Direction D, the method behaves as follows:

1. If K is in R (i.e., is selected) and either D is inclusive, or there exists a key value K' in R that is adjacent to K (where K' is larger than K if D is GT, or smaller than K if D is LT), then return true without modifying the K.
2. Otherwise attempt to modify K to a new value K' which is either adjacent to or in the next contiguous subset of R, and return true to indicate that more keys exist in the range. Specifically, for each Direction D, K' is defined as follows:
   • LT: find the largest key J in R where J < K. Then K' is the key right-adjacent to J.
   • LTEQ: find the largest key J in R where J < K. Then K' is J.
   • EQ: there is no K'
   • GTEQ: find the smallest key J in R where J > K. Then K' is J.
   • GT: find the smallest key J in R where J < K. Then K' is the key left-adjacent to J.
3. Otherwise, if there is no key K' that satisfies the requirements of #2, return false to indicate that the range has been exhausted.

Version:

1.0

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KeyFilter.Term Specifies criteria for selecting one segment of a Key value.

Field Summary

Fields

Modifier and Type	Field and Description
static KeyFilter.Term	ALL A KeyFilter.Term that matches all values.

Constructor Summary

Constructors

Constructor and Description
KeyFilter() Constructs an empty KeyFilter.
KeyFilter(Key key) Constructs a KeyFilter that selects the subset of all keys which are equal to, logical children of, or logical ancestors of the supplied Key.
KeyFilter(KeyFilter.Term[] terms) Constructs a KeyFilter that selects the subset of all keys whose segments are selected by the corresponding Terms of the supplied array.
KeyFilter(KeyFilter.Term[] terms, int minDepth, int maxDepth) Constructs a KeyFilter that selects the subset of all keys whose segments are selected by the corresponding Terms of the supplied array and whose depth is greater than or equal to the supplied minimum depth and less than or equal to the supplied maximum depth.
KeyFilter(Key key, int minDepth, int maxDepth) Constructs a KeyFilter that selects the subset of all key values that are equal to, logical children of, or logical ancestors of the supplied Key, and whose depth is greater than or equal to the supplied minimum depth and less than or equal to the supplied maximum depth.
KeyFilter(String string) Constructs a KeyFilter from its string representation.

Method Summary

Modifier and Type	Method and Description
KeyFilter	append(KeyFilter.Term term) Constructs and returns a new KeyFilter in which the supplied term is appended to the end of the array of terms in the current KeyFilter.
KeyFilter	append(KeyFilter.Term[] terms) Constructs and returns a new KeyFilter in which the supplied terms are appended to the array of terms in the current KeyFilter.
KeyFilter	append(KeyFilter filter) Constructs and returns a new KeyFilter in which the terms of the supplied filter are appended to the array of terms already present in this KeyFilter.
int	getMaximumDepth() Returns the maximum depth of a key value that will be selected by this KeyFilter.
int	getMinimumDepth() Returns the minimum depth of a key value that will be selected by this KeyFilter.
KeyFilter.Term	getTerm(int index) Returns the term at the specified index.
KeyFilter	limit(int minDepth, int maxDepth) Constructs and returns a new KeyFilter in which the minimum and maximum depth are set to the supplied values.
boolean	next(Key key, Key.Direction direction) Determine the next key value from which B-Tree traversal should proceed.
static KeyFilter.Term	orTerm(KeyFilter.Term[] terms) Returns a Term that selects a key segment value if and only if one of the members of the supplied terms array selects it.
static KeyFilter.Term	rangeTerm(Object fromValue, Object toValue) Returns a Term that accepts a range of values.
static KeyFilter.Term	rangeTerm(Object fromValue, Object toValue, boolean leftInclusive, boolean rightInclusive) Returns a Term that accepts a range of values.
static KeyFilter.Term	rangeTerm(Object fromValue, Object toValue, boolean leftInclusive, boolean rightInclusive, CoderContext context) Returns a Term that accepts a range of values.
static KeyFilter.Term	rangeTerm(Object fromValue, Object toValue, CoderContext context) Returns a Term that accepts a range of values.
boolean	selected(Key key) Indicates whether the supplied key is selected by this filter.
static KeyFilter.Term	simpleTerm(Object value) Returns a Term that matches a single value.
static KeyFilter.Term	simpleTerm(Object value, CoderContext context) Returns a Term that matches a single value.
int	size() Returns the current size of this KeyFilter's term array.
static KeyFilter.Term	termFromKeySegments(Key fromKey, Key toKey, boolean leftInclusive, boolean rightInclusive) Returns a Term that accepts a range of values.
String	toString() Returns a string representation of this KeyFilter

Methods inherited from class java.lang.Object

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

Field Detail

ALL

public static final KeyFilter.Term ALL

A KeyFilter.Term that matches all values.

Constructor Detail

KeyFilter

public KeyFilter()

Constructs an empty KeyFilter. This KeyFilter implicitly selects all key values.

KeyFilter

public KeyFilter(String string)

Constructs a KeyFilter from its string representation.

Parameters:

string - The string representation

Throws:

IllegalArgumentException - if the string is not valid

KeyFilter

public KeyFilter(Key key)

Constructs a KeyFilter that selects the subset of all keys which are equal to, logical children of, or logical ancestors of the supplied Key.

Parameters:

key - The Key

KeyFilter

public KeyFilter(Key key,
                 int minDepth,
                 int maxDepth)

Constructs a KeyFilter that selects the subset of all key values that are equal to, logical children of, or logical ancestors of the supplied Key, and whose depth is greater than or equal to the supplied minimum depth and less than or equal to the supplied maximum depth. Suppose the supplied key value has M segments and some other Key value K has N segments. Then K is a member of the subset selected by this KeyFilter if and only if N>=minDepth and N<= maxDepth and each of the first min(M, N) segments match.

Parameters:

key - The Key

minDepth - The minimum depth

maxDepth - The maximum depth

KeyFilter

public KeyFilter(KeyFilter.Term[] terms)

Constructs a KeyFilter that selects the subset of all keys whose segments are selected by the corresponding Terms of the supplied array. Suppose a Key K has N segments and the supplied array of terms has length M. Then K is a member of the key value subset selected by this KeyFilter if and only if each of the first min(M, N) segments of K is selected by the corresponding member of the terms array.

Parameters:

terms -

KeyFilter

public KeyFilter(KeyFilter.Term[] terms,
                 int minDepth,
                 int maxDepth)

Constructs a KeyFilter that selects the subset of all keys whose segments are selected by the corresponding Terms of the supplied array and whose depth is greater than or equal to the supplied minimum depth and less than or equal to the supplied maximum depth. Suppose some Key K has N segments and the supplied array of terms has length M. Then K is a member of the key value subset selected by this KeyFilter if and only if and only if N>=minDepth and N<=maxDepth and each of the first min(M, N) segments of K is selected by the corresponding member of the terms array.

Parameters:

terms - The Term array

minDepth - The minimum depth

maxDepth - The maximum depth

Method Detail

append

public KeyFilter append(KeyFilter filter)

Constructs and returns a new KeyFilter in which the terms of the supplied filter are appended to the array of terms already present in this KeyFilter. In addition, the minimum and maximum depths of the newly created KeyFilter are computed from the supplied filter value. Let M be the number of terms in this KeyFilter. The the minimum and maximum depth parameters for the newly created KeyFilter will be filter.getMinimumDepth()+M and filter.getMaximumDepth()+M, respectively.

Parameters:

filter - The KeyFilter to append

Returns:

The newly constructed KeyFilter.

append

public KeyFilter append(KeyFilter.Term term)

Constructs and returns a new KeyFilter in which the supplied term is appended to the end of the array of terms in the current KeyFilter.

Parameters:

term - The Term to append

Returns:

The newly constructed KeyFilter

append

public KeyFilter append(KeyFilter.Term[] terms)

Constructs and returns a new KeyFilter in which the supplied terms are appended to the array of terms in the current KeyFilter.

Parameters:

terms - The array of Term to append

Returns:

The newly constructed KeyFilter

limit

public KeyFilter limit(int minDepth,
                       int maxDepth)

Constructs and returns a new KeyFilter in which the minimum and maximum depth are set to the supplied values.

Parameters:

minDepth - The minimum depth

maxDepth - The maximum depth

Returns:

The newly constructed KeyFilter.

simpleTerm

public static KeyFilter.Term simpleTerm(Object value)

Returns a Term that matches a single value. The value is interpreted in the same manner and has the same restrictions as described for the Key class.

Parameters:

value - The value

Returns:

The Term.

simpleTerm

public static KeyFilter.Term simpleTerm(Object value,
                                        CoderContext context)

Returns a Term that matches a single value. The value is interpreted in the same manner and has the same restrictions as described for the Key class.

Parameters:

value - The value

context - A CoderContext supplied to any registered KeyCoder used in encoding the fromValue or toValue. May be null.

Returns:

The Term.

rangeTerm

public static KeyFilter.Term rangeTerm(Object fromValue,
                                       Object toValue)

Returns a Term that accepts a range of values. The range includes these two values and all values that lie between them according to the key ordering specification.

Parameters:

fromValue - The first value that will be selected by this term

toValue - The last value that will be selected by this term

Returns:

The term

Throws:

IllegalArgumentException - if fromValue follows toValue.

rangeTerm

public static KeyFilter.Term rangeTerm(Object fromValue,
                                       Object toValue,
                                       CoderContext context)

Returns a Term that accepts a range of values. The range includes these two values and all values that lie between them according to the key ordering specification.

Parameters:

fromValue - The first value that will be selected by this term

toValue - The last value that will be selected by this term

context - A CoderContext supplied to any registered KeyCoder used in encoding the fromValue or toValue. May be null.

Returns:

The term

Throws:

IllegalArgumentException - if fromValue follows toValue.

rangeTerm

public static KeyFilter.Term rangeTerm(Object fromValue,
                                       Object toValue,
                                       boolean leftInclusive,
                                       boolean rightInclusive)

Returns a Term that accepts a range of values. The range optionally includes these two values and all values that lie between them according to the key ordering specification.

Parameters:

fromValue - The first value that will be selected by this term

toValue - The last value that will be selected by this term

leftInclusive - Indicates whether a value exactly matching fromValue should be selected by this Term.

rightInclusive - Indicates whether a value exactly matching toValue should be selected by this Term.

Returns:

The term

Throws:

IllegalArgumentException - if fromValue follows toValue.

rangeTerm

public static KeyFilter.Term rangeTerm(Object fromValue,
                                       Object toValue,
                                       boolean leftInclusive,
                                       boolean rightInclusive,
                                       CoderContext context)

Returns a Term that accepts a range of values. The range optionally includes these two values and all values that lie between them according to the key ordering specification.

Parameters:

fromValue - The first value that will be selected by this term

toValue - The last value that will be selected by this term

leftInclusive - Indicates whether a value exactly matching fromValue should be selected by this Term.

rightInclusive - Indicates whether a value exactly matching toValue should be selected by this Term.

context - A CoderContext supplied to any registered KeyCoder used in encoding the fromValue or toValue. May be null.

Returns:

The term

Throws:

IllegalArgumentException - if fromValue follows toValue.

termFromKeySegments

public static KeyFilter.Term termFromKeySegments(Key fromKey,
                                                 Key toKey,
                                                 boolean leftInclusive,
                                                 boolean rightInclusive)

Returns a Term that accepts a range of values. The range is specified by values already encoded in two supplied Keys. The index of each Key object should be set on entry to the segment to be used in constructing the RangeTerm. As a side-effect, the index of each key is advanced to the next segment. If the two key segments are identical and if both leftInclusive and rightInclusive are true, this method returns a SimpleTerm containing the segment.

Parameters:

fromKey - A Key

toKey - A Key

leftInclusive - Indicates whether a value exactly matching fromValue should be selected by this Term.

rightInclusive - Indicates whether a value exactly matching toValue should be selected by this Term.

Returns:

The term

orTerm

public static KeyFilter.Term orTerm(KeyFilter.Term[] terms)

Returns a Term that selects a key segment value if and only if one of the members of the supplied terms array selects it. The terms array may not include a nested OrTerm.

Parameters:

terms - Array of RangeTerms or SimpleTerms.

Returns:

The term

Throws:

IllegalArgumentException - if any member of the terms array is itself an OrTerm or if the end points of the terms in that array are not strictly increasing in key order.

size

public int size()

Returns the current size of this KeyFilter's term array.

Returns:

The size.

getMinimumDepth

public int getMinimumDepth()

Returns the minimum depth of a key value that will be selected by this KeyFilter.

Returns:

The minimum depth

getMaximumDepth

public int getMaximumDepth()

Returns the maximum depth of a key value that will be selected by this KeyFilter.

Returns:

The maximum depth

getTerm

public KeyFilter.Term getTerm(int index)

Returns the term at the specified index.

Parameters:

index - The index of the term to be returned.

Returns:

The Term.

Throws:

ArrayIndexOutOfBoundsException - if index is less than zero or greater than or equal to the number of terms in the term array.

toString

public String toString()

Returns a string representation of this KeyFilter

Overrides:

toString in class Object

Returns:

The canonical string representation

selected

public boolean selected(Key key)

Indicates whether the supplied key is selected by this filter.

Parameters:

key - The Key value to test.

Returns:

true if the supplied Key state satisfies the constraints of this filter, otherwise false.

next

public boolean next(Key key,
                    Key.Direction direction)

Determine the next key value from which B-Tree traversal should proceed.

A KeyFilter defines a subset of the the set of all Key values: the Exchange.traverse(Key.Direction, KeyFilter, int) method returns only values in this subset. The following definitions are used in describing the behavior of this method.

Range

Let S be the ordered set of all possible key values. (Though large, this set is finite because of maximum length of a key.) T range R is the subset of S selected by this KeyFilter.

Adjacent

Two keys K1 and K2 in this set are adjacent if K1 != K2 and there exists no other key value K such that K1 < K < k2.

Contiguous

Let C be a subset of R. Let Kmin and Kmax be the smallest and largest keys in C, respectively. Then C is contiguous if there is no key K where K1 < K < K2 and K is not in R.

A KeyFilter defines a subset of S

This method modifies the supplied key as needed so that only key values in the range are traversed. For example suppose the KeyFilter admits key values between {5} and {10} (inclusive) and suppose the key currently contains {3}. Then if the traversal direction is GTEQ, this method modifies key to {5}, which is the next smallest memory of the range. If the direction is GT, this method modifies the value of key to {5}-, which is a pseudo-value immediately before {5}.

In most cases, if the supplied key is selected (in the range) then this method returns true and does not modify the key. The exception is that if the current key is selected, the direction is LT or GT, and there is no adjacent key in the range, this method w

Similarly, if key is {12} and then the directions LTEQ and LT result in key values {10} and {10}+, respectively.

The return value indicates whether there exist any remaining values in the range. For example, if the value of key is {10} and the direction is GT, then this method returns false.

Parameters:

key - The Key

direction - Direction specified in the traverse method using this KeyFilter

Returns:

true if a successor (or predecessor) key exists, otherwise false.