Module id.xfunction
Package id.xfunction.util

Class LongNumberSequence

Object
LongNumberSequence
public class LongNumberSequence extends Object
Collection which keeps track of incoming positive number sequence (1, 2, 3, 4, ...) and allows to query what numbers are missing in it.

When this collection initially created all numbers of it are missing.

This collection can keep track only of N last numbers of the sequence. All numbers less than "last added maximum number - N" are removed.

This collection is not thread safe.

Examples


 // empty sequence of numbers between [1, 10]
 LongNumberSequence seq = new LongNumberSequence(10);

 // prints "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]" since all numbers are missing
 System.out.println(seq.getMissing());

 // similarly all numbers between [1, 8] are missing so it prints "[1, 2, 3, 4, 5, 6, 7, 8]"
 System.out.println(seq.getMissing(1, 8));

 // adding few numbers
 seq.add(5);
 seq.add(4);

 // now 4 and 5 are not missing so it prints "[1, 2, 3, 6, 7, 8]"
 System.out.println(seq.getMissing(1, 8));

 // adding 13
 // since sequence size is 10 it cannot hold 13 numbers so it shifts
 // to the right to accommodate 13 and now it is a sequence between [4, 13]
 seq.add(13);

 // prints "[6, 7, 8, 9, 10, 11, 12]" (1, 2, 3 does not belong to the sequence anymore
 // since it is not sequence of numbers between [1, 10] but between [4, 13]
 System.out.println(seq.getMissing(1, 13));

  • Constructor Details

    • LongNumberSequence

      public LongNumberSequence(int size)
      Parameters:
      size - how many N last numbers to keep. All numbers less than "last added maximum number - N" are removed.

  • Method Details

    • size

      public int size()
      Returns:
      how many N last numbers can be queried for presence

    • hasMissing

      public boolean hasMissing()
      Returns whether there are any missing number of last N numbers or not

    • add

      public void add(long n)
      Add new number to the sequence.

      Complexity is log(N)

    • isMissing

      public boolean isMissing(long n)
      Check if certain number is missing

      Complexity is log(N)

    • getMissing

      public Collection<Long> getMissing()
      Returns unmodifiable collection of missing numbers from the sequence of numbers seen so far

    • getMissing

      public Collection<Long> getMissing(long first, long last)
      Returns unmodifiable collection of missing numbers between [first, last] from the sequence of numbers seen so far