All Packages  This Package  Class Hierarchy  Class Search  Index

Class grendel.storage.NewsSet

java.lang.Object
   |
   +----grendel.storage.NewsSet

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:

• strictly increasing;
• large subsequences of monotonically increasing ranges;
• gaps in the set are usually small, but not always;
• consecutive ranges tend to be large.

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);
}

• 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

• NewsSet

   public NewsSet() 

• NewsSet

   public NewsSet(String chars) 

• NewsSet

   public NewsSet(ByteBuf chars) 

• NewsSet

   public NewsSet(byte[] chars, 
                  int start, 
                  int end) 

• 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() 

Overrides:

toString in class Object

• 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  Index