variable length FIFO Queue with constant total element value.

[worli]

Hi All,
I have a strange requirement.
I have a dynamic input numeric data stream e.g. 2, 2, 4, 5 etc....
( each input number range from 1 to 10 ).

lets take a simple case where all inputs will have same value = 1 (
which may not be the case )
I need to create a FIFO queue in which at any given time I need the
total element value = 10. ( not the size of array ).
say if the data stream is all 1 e.g. 1,1,1,1,1,1,1,1,1
in this case the queue should accomodate 10 elements and than start
removing one element from the front as a one element with value = 1
gets added to the queue end.

if the data stream = 2,2,2,4,5 .. etc in this case the queue should get
filled til 2 + 2 + 2 + 4 ( which = 10 ) than when 5 is added to queue
then elemeent totalling to 5 should be removed from the front of the
queue. e.g in this scenario after adding 5 to the end of queue , the
queue should look 1, 4, 5 ( notice the first and the second 2 were
removed and one was substracted from the third 2 which left us with 1 )

basicallly at any given time the total value of all elements in the
queue should be exactly = 10.

any C# solution will be good , or worst case stl soultion might do as
well.

Regards,
Manish

 

[Bruce Wood]

How about something like this?

public class ConstantTotalNumberStream
{
private int target;
private int total;
private int[] stream;
private int startIndex;
private int endIndex;
private bool streamChanged;

public ConstantTotalNumberStream(int totalToMaintain)
{
this.target = totalToMaintain;
this.stream = new int[totaltoMaintain];
for (int i = 0; i < totalToMaintain; i++)
{
this.stream = 0;
}
this.total = 0;
this.startIndex = 0;
this.endIndex = 0;
this.streamChanged = false;
}

public AddNumber(int newNumber)
{
if (newNumber <= 0 || newNumber > this.total)
{
throw new ArgumentException(String.Format("Number to add must
be between 1 and {0}, not {1}", this.total, newNumber));
}
Push(newNumber);
while (this.total > this.target)
{
if (this.total - this.stream[this.startIndex] >= this.target)
{
Pop();
}
else
{
this.stream[this.startIndex] -= this.total - this.target;
this.total = this.target;
}
}
}

private void Push(int newNumber)
{
this.endIndex = (this.endIndex + 1) % this.total;
if (this.endIndex == this.startIndex)
{
// Array is full... have to pop one element in order to make
room
Pop();
}
this.stream[this.endIndex] = newNumber;
this.total += newNumber;
}

public void Pop()
{
if (this.startIndex != this.endIndex)
{
this.total -= this.stream[this.startIndex];
this.startIndex = (this.startIndex + 1) % this.target;
}
}

public int Total
{
get { return this.total; }
}

public int Count
{
get
{
int count = this.endIndex - this.startIndex;
if (count < 0)
{
count += this.target;
}
return count;
}
}

public int this[int index]
{
get
{
if (this.startIndex == this.endIndex)
{
throw new IndexOutOfRangeException("Cannot index stream
because it contains no numbers");
}
else if (index < 0 || index >= this.Count)
{
throw new IndexOutOfRangeException(String.Format("Index {0}
is outside valid range 0 to {1}", index, this.Count - 1));
}
int trueIndex = (index + startIndex) % this.target;
return this.stream[trueIndex];
}
}
}

 

[Bruce Wood]

Of course, that should have been:

private void Pop()
....