All Packages This Package Class Hierarchy Class Search Index
Class grendel.storage.NewsSet
java.lang.Object | +----grendel.storage.NewsSet
- strictly increasing;
- large subsequences of monotonically increasing ranges;
- gaps in the set are usually small, but not always;
- consecutive ranges tend to be large.
This class represents a set of integers. It uses a highly compressed encoding, taking advantage of the assumption that many of the integers are consecutive. This is intended for representing lines from the .newsrc file, which have lists of message-numbers lists like
1-29627,29635,29658,32861-32863
so the data has these properties:
public class NewsSet
extends java.lang.Object
{
// Fields 5
private long cached_value;
private int cached_value_index;
private long[] data;
private int data_length;
private int data_size;
// Constructors 4
public NewsSet();
public NewsSet(byte[], int, int);
public NewsSet(ByteBuf);
public NewsSet(String);
// Methods 38
public long countMissingInRange(long, long);
public boolean delete(long);
public boolean delete(long, long);
private final int emit_range(long[], int, long, long);
public long firstNonMember();
public long firstNonMember(long, long);
private void grow();
public boolean insert(long);
public boolean insert(long, long);
protected boolean isEmpty();
public long lastNonMember(long, long);
public static void main(String[]);
public void markDirty();
public long max();
public boolean member(long);
public long min();
public long nextMember(long);
private void optimize();
public long previousMember(long);
protected static void self_test();
protected static void self_test_adder();
protected static void self_test_adder(NewsSet, boolean, long, String);
protected static void self_test_decoder();
protected static void self_test_decoder(String, String);
protected static void self_test_first_nonmember(boolean);
protected static void self_test_first_nonmember(NewsSet, boolean, long, long, long);
protected static void self_test_last_nonmember(boolean);
protected static void self_test_last_nonmember(NewsSet, boolean, long, long, long);
protected static void self_test_member(boolean);
protected static void self_test_member(NewsSet, boolean, long, boolean);
protected static void self_test_next_member(boolean);
protected static void self_test_next_member(NewsSet, boolean, long, long);
protected static void self_test_prev_member(boolean);
protected static void self_test_prev_member(NewsSet, boolean, long, long);
protected static void self_test_ranges();
protected static void self_test_ranges(NewsSet, long, long, String);
public String toString();
public void write(ByteBuf);
}
Fields
• cached_value
private long cached_value
• cached_value_index
private int cached_value_index
• data_length
private int data_length
• data_size
private int data_size
• data
private long[] data
Constructors
• NewsSet
public NewsSet()
• NewsSet
public NewsSet(String chars)
• NewsSet
public NewsSet(ByteBuf chars)
• NewsSet
public NewsSet(byte[] chars,
int start,
int end)
Methods
• grow
private void grow()
• firstNonMember
public long firstNonMember()
Returns the lowest non-member of the set greater than 0. Note that this never returns -1, since a NewsSet can't hold the set of positive integers.
• min
public long min()
Returns the smallest element of the set. Returns -1 if the set is empty.
• max
public long max()
Returns the largest element of the set. Returns -1 if the set is empty.
• member
public boolean member(long number)
Returns whether the number is a member of the set.
• insert
public boolean insert(long number)
Cause the number to be a member of the set. Returns false if the number was already a member of the set, true otherwise.
• delete
public boolean delete(long number)
Cause the number to not be a member of the set. Returns true if the number had been a member of the set, false otherwise.
• emit_range
private final int emit_range(long[] out,
int i,
long a,
long b)
• insert
public boolean insert(long start,
long end)
Cause the numbers in the range [start, end) to be members of the set. Returns false if all of the numbers were already members of the set, true otherwise.
• delete
public boolean delete(long start,
long end)
Cause the numbers in the range [start, end) to not be members of the set. Returns true if any of the numbers had been members of the set, false otherwise.
• countMissingInRange
public long countMissingInRange(long range_start,
long range_end)
Returns the number of elements in the range [start, end) which are not members of the set.
• firstNonMember
public long firstNonMember(long min,
long max)
Returns the first number which is not a member of the set, which falls in the range [min, max). Returns -1 if all numbers in the range are members.
• lastNonMember
public long lastNonMember(long min,
long max)
Returns the last number which is not a member of the set, which falls in the range [min, max). If all numbers in that range are members of the set, returns -1.
• nextMember
public long nextMember(long after)
Returns the first number which is in the set, and which is greater than the given value. Returns -1 if no number greater than the given value is in the set.
• previousMember
public long previousMember(long after)
Returns the last number which is in the set, and which is less than the given value. Returns -1 if the smallest member of the set is greater than or equal to the given value.
• optimize
private void optimize()
Re-compresses the data in the set.
The assumption is made that the data in the set is syntactically correct (all ranges have a length of at least 1, and all values are non-decreasing) but we can optimize the compression, for example, merging consecutive literals or ranges into one range.
• isEmpty
protected boolean isEmpty()
True if there are no elements in the set.
• markDirty
public void markDirty()
Called when a change is made to the set. This method does nothing, but is provided for the benefit of subclasses.
• write
public void write(ByteBuf out)
Converts a printed representation of the numbers in the set. This will be something like "1-29627,29635,29658,32861-32863", which is the same representation that new NewsSet() expects.
• toString
public String toString()
• self_test_decoder
protected static void self_test_decoder(String s, String target)
Self tests
• self_test_decoder
protected static void self_test_decoder()
• self_test_adder
protected static void self_test_adder(NewsSet set, boolean add_p, long value, String target)
• self_test_adder
protected static void self_test_adder()
• self_test_ranges
protected static void self_test_ranges(NewsSet set, long start, long end, String target)
• self_test_ranges
protected static void self_test_ranges()
• self_test_member
protected static void self_test_member(NewsSet set, boolean cache, long elt, boolean target)
• self_test_first_nonmember
protected static void self_test_first_nonmember(NewsSet set, boolean cache, long start, long end, long target)
• self_test_last_nonmember
protected static void self_test_last_nonmember(NewsSet set, boolean cache, long start, long end, long target)
• self_test_next_member
protected static void self_test_next_member(NewsSet set, boolean cache, long elt, long target)
• self_test_prev_member
protected static void self_test_prev_member(NewsSet set, boolean cache, long elt, long target)
• self_test_member
protected static void self_test_member(boolean cache)
• self_test_first_nonmember
protected static void self_test_first_nonmember(boolean cache)
• self_test_last_nonmember
protected static void self_test_last_nonmember(boolean cache)
• self_test_next_member
protected static void self_test_next_member(boolean cache)
• self_test_prev_member
protected static void self_test_prev_member(boolean cache)
• self_test
protected static void self_test()
• main
public static void main(String[] args)
All Packages This Package Class Hierarchy Class Search IndexFreshly brewed Java API Documentation automatically generated with polardoc Version 1.0.4