Algorithm for performing a rollup

[Chris Uppal]

Don't all the other solutions shown so far in this discussion require
maintaining all the elements in memory?
No.

It's a rhetorical question: of
course they do.

Oh no, they don't !

-- chris

 

[Lew]

Oh no, they don't !

OK, so the use of arrays in every example cited was not the use of in-memory
constructs.

-- Lew

 

[Lew]

Oh no, they don't !

Oh, I see. I was misled by the fact that every example in this thread did
maintain all the elements in memory, starting with the OP's.

The "lookahead" algorithm does not require all elements to be in memory.

-- Lew

 

[Stefan Ram]

I do not like the »while( true ){ ... break; ... }«-style
myself, but sometimes it is the last ressort, when the loop
control logic is too complex to fit into the parentheses.

The next version:

class Source
implements java.util.Iterator<java.lang.String>
{ private final java.lang.String source[] =
{ "A", "A", "A", "B", "B", "C", "D", "D" };
private int position;
public Source()
{ this.position = 0; }
public java.lang.String next(){ return source[ position++ ]; }
public boolean hasNext(){ return position < source.length; }
public void remove(){ throw new java.lang.UnsupportedOperationException(); }}

/** For an Iterator<E> object delivering components, allow to count how many
components appear in a sequence of consecutive equal components.
@param E the type of the components */

class Counter<E>
{
/** Initialize a new Counter object for a source.
@param source an iterator delivering each component of the source in turn */

public Counter( final java.util.Iterator<E> source )
{ first = null;
next = null;
this.source = source; }

/** Advance the Counter object to the beginning of the next
sequence of consecutive equal components.
A true result indicates success.
This might be called directly after object creation.
Between a call of this and the next call there
must be exactly one call of "count". */

public boolean advance()
{ final boolean advanced;
if( next != null )
{ first = next; next = null; advanced = true; }
else if( source.hasNext() )
{ first = source.next(); advanced = true; }
else advanced = false;
return advanced; }

/** After a succesful "advance",
count the number of consecutive equal source components.
This must be called exactly once after a successful call of "advance". */

public int count()
{ int count = 1; while( this.isExtendable() )++count;
return count; }

/** The current value of the component, valid after a successful
advance operation */

public E value()
{ return first; }

/** Is the next component equal to the first?
side-effect: advance the (perceived) position to the next component if it is
equal to the first */
private boolean isExtendable()
{ final boolean result;
if( !source.hasNext() ){ next = null; result = false; }
else result = first.equals( next = source.next() );
return result; }

/** The first component in a sequence of consecutive
equal source components */
private E first;

/** The next component as just read from the source */
private E next;

/** The component source for this Counter */
private final java.util.Iterator<E> source; }

public class Main
{
public static void main( final java.lang.String[] args )
{ Source source = new Source();
Counter<java.lang.String> counter = new Counter<java.lang.String>( source );
while( counter.advance() )
{ java.lang.System.out.println
( "\"" + counter.value() + "\", " + counter.count() ); }}}

 

[Chris]

Remember the original problem statement started with sorted data. It

Here is the original statement of the inputs:

This puts all the elements in memory at once. The OP then went on to
show code using an array kept entire in memory.

For the input, that was just an example. For the output, no, my code did
not store everything in memory. It streamed out the results as they were
discovered.

 

[Stefan Ram]

Between a call of this and the next call there
must be exactly one call of "count".

This burden placed on the client has been removed in the
following version, where the client is free to call »value«
and »count« an arbitrary number of times and in an arbitrary
order after each successful »advance«.

class Source
implements java.util.Iterator<java.lang.String>
{ private final java.lang.String source[] =
{ "A", "A", "A", "B", "B", "C", "D", "D" };
private int position;
public Source()
{ this.position = 0; }
public java.lang.String next(){ return source[ position++ ]; }
public boolean hasNext(){ return position < source.length; }
public void remove(){ throw new java.lang.UnsupportedOperationException(); }}

/** For an Iterator<E> object delivering components, allow to count how many
components appear in a sequence of consecutive equal components.
@param E the type of the components */

class Counter<E>
{
/** Initialize a new Counter object for a source.
@param source an iterator delivering each component of the source in turn */

public Counter( final java.util.Iterator<E> source )
{ this.first = null;
this.next = null;
this.count = -1;
this.source = source; }

/** Advance the Counter object to the beginning of the next
sequence of consecutive equal components.
A true result indicates success. */

public boolean advance()
{ this.first = null;
this.count = -1;
final boolean advanced;
if( next != null )
{ first = next; next = null; advanced = true; }
else if( source.hasNext() )
{ first = source.next(); advanced = true; }
else advanced = false;
if( advanced )doCount();
return advanced; }

/** The current value of the component, valid after a successful
advance operation */

public E value()
{ return first; }

/** The current value of the counter, valid after a successful
advance operation */

public int count()
{ return count; }

/** count the number of consecutive equal source components */
private void doCount()
{ count = 1; while( this.isExtendable() )++count; }

/** Is the next component equal to the first?
side-effect: advance the (perceived) position to the next component if it is
equal to the first */
private boolean isExtendable()
{ final boolean result;
if( !source.hasNext() ){ next = null; result = false; }
else result = first.equals( next = source.next() );
return result; }

/** The first component in a sequence of consecutive
equal source components */
private E first;

/** The next component as just read from the source */
private E next;

/** The component source for this Counter */
private final java.util.Iterator<E> source;

/** The last count */
private int count = -1; }

public class Main
{
public static void main( final java.lang.String[] args )
{ Source source = new Source();
Counter<java.lang.String> counter = new Counter<java.lang.String>( source );
while( counter.advance() )
{ java.lang.System.out.println
( "\"" + counter.value() + "\", " + counter.count() ); }}}