12

Suppose I have a huge Boolean array flags:

Boolean[] flags = { true, false, true };    // 3 means "many"

I want to do two things on flags:

  • check whether all the elements are true and return an indicator;
  • reset all the elements to false.

Using lambda expression of Java 8, I can do them as follows:

indicator = Arrays.stream(flags).allMatch(flag -> flag);
Arrays.stream(flags).forEach(flag -> flag = false);
return indicator;

However this implementation scans flags twice. Since flags is huge, I don't want this. In addition, I do prefer the lambda way. Is there any way of implementing this checkIfAllTrueAndReset semantics with (one-liner) lambda expression which scans flags only once?

Related but not the same: What is the most elegant way to check if all values in a boolean array are true?

Note: I learn a lot from comments and answers. Thank you all!

  1. Stream is cool, but it is not for this.
  2. BitSet (and its bit-wisely atomic counterpart AtomicBitSet) is more suitable for this (so accepted as the answer; thank others).
  3. Side-effects in map (Stream or generally functional programming) are discouraged.
  4. Arrays.stream(flags).forEach(flag -> flag = false) (in my code) does not set anything!
Community
  • 1
  • 1
hengxin
  • 1,867
  • 2
  • 21
  • 42
  • 2
    Don't. Use a 32-bit integer (int) to do this and perform bitwise operations toggling 0s and 1s. – Stephan Bijzitter Dec 28 '15 at 12:37
  • 3
    Or, use a Bitset. Also note that your forEach loop is a noop. It doesn't modify the values in the array. – JB Nizet Dec 28 '15 at 12:40
  • @StephanBijzitter instead of Boolean[]? What about boolean[]? I use Boolean[] (instead of boolean[]) to avoid `Arrays.asList()` in this example. My point is to combine `allMatch` and `forEach`. – hengxin Dec 28 '15 at 12:41
  • 2
    @hengxin [This answer](http://stackoverflow.com/a/22753957/4216641) might be related. In short: `Stream`s are not designed to change the underlying datastructure. – Turing85 Dec 28 '15 at 12:43
  • 3
    Well, any integer can be used as an array of booleans in a sense. The integer is a series of 1s and 0s (trues and falses). A 32-bit integer then basically contains the same data as a boolean array with a length of 32, with much less overhead. Many large applications (especially games) use this technique because it's much more performant. You're asking for optimisation, yet you limit yourself to calling streaming functions, which is simply not needed. – Stephan Bijzitter Dec 28 '15 at 12:43
  • @JBNizet In my real code, I am using `AtomicBoolean[]` for thread-safety. In this post, I have abstracted this out and focus on how to combine `allMatch` and `forEach`. Is `BitSet` thread-safe? Or does it have a thread-safe counterpart? Well, the thread-safety may be another issue. `BitSet` is good for performance. – hengxin Dec 28 '15 at 12:45
  • 2
    No, it's not thread-safe. But if clearing all the bits is supposed to be an atomic operation, using an array of AtomicBooleans is not thread-safe either. – JB Nizet Dec 28 '15 at 12:48
  • @JBNizet I only require each (bit) element be accessed atomically (just like the semantics `AtomicBoolean[]` or `AtomicIntegerArray` provides). Then does `BitSet` have such an alternative? – hengxin Dec 28 '15 at 12:58
  • 1
    AFAIK, no, but you can encapsulate it inside an object and synchronize every access to it. If you really want to stick to an array of AtomicBoolean, then just don't use streams to modify it. That's not what streams are for. – JB Nizet Dec 28 '15 at 13:01
  • @JBNizet Thanks for suggestion. `That's not what streams are for.` This sentence is also helpful (also thank @Turing85). – hengxin Dec 28 '15 at 13:05
  • 2
    `Arrays.stream(flags).forEach(flag -> flag = false)` doesn't set anything. – Kirill Rakhman Dec 29 '15 at 00:05
  • @cypressious Great thanks. I have tested it, and you are right. A big mistake in my code. – hengxin Dec 29 '15 at 01:43

4 Answers4

16

Classic example for using the BitSet class:

This class implements a vector of bits that grows as needed. Each component of the bit set has a boolean value.

In complexity terms, BitSet uses ~1 bit for each boolean value, which is way better than using big array of Boolean objects.

Regarding checking of all bits are set or not (true or false), the API provides many useful methods - and they're really efficient.

Maroun
  • 94,125
  • 30
  • 188
  • 241
  • Thanks. BTW: As mentioned in the comments, I am also interested in thread-safe counterpart to `BitSet`. I googled and found [this](https://code.google.com/p/pitestrunner/source/browse/pitest/src/main/java/org/pitest/boot/AtomicBitSet.java?spec=svncc600208506a965a870ed6dc8a04a81c3c3b1b03&r=cc600208506a965a870ed6dc8a04a81c3c3b1b03). – hengxin Dec 28 '15 at 13:23
5

This is a bad match for streams and lambdas and there is no really nice way to do it.

The problem is that steams work with the elements of a collection, but you need to modify the actual collection.

I think you are best of using an old-school for-loop for this.

One not-so-nice solution is to get a stream over the indices of the array and use a forEach of that to loop over the array. An AtomicBoolean could be used to store if all elements are true. This can be run in parallel, but I think an ordinary for-loop is better.

Example:

Boolean[] flags = { true, true, true };  

AtomicBoolean allTrue = new AtomicBoolean(true);
IntStream.range(0, flags.length)
    .forEach(ix -> {
        if (!flags[ix]) allTrue.set(false);
        flags[ix] = false;
    });

Solution with atomic boolean

In in the comments of the question it was mentioned that it might be interesting with a solution for AtomicBoolean. In that case a solution with streams is possible, since an element can be reset without modifying the original collection.

The solution is really questionably however, so it's probably best to not use it. The problem is that map is used both for a side effect (resetting the value) and a mapping operation (extracting the old value). I think it is possible to run it in parallel but it's probably slower than a normal for-loop since the operation on each element is so tiny.

Also note that allMatch cannot be used since that operation is short-circuiting and if it finds a false it will terminate and subsequent elements will not be reset.

AtomicBoolean[] flags = { new AtomicBoolean(true), new AtomicBoolean(false), new AtomicBoolean(true) };  

boolean allTrue = Stream.of(flags)
    .map(b -> b.getAndSet(false))
    .reduce(true, (a, b) -> a && b);
Lii
  • 11,553
  • 8
  • 64
  • 88
  • 1
    Yes. I learn it today: although `Stream` is cool, it is not for this. Thanks. – hengxin Dec 28 '15 at 13:30
  • 1
    @hengxin: I added a really awkward solution for `AtomicBooleans`. – Lii Dec 28 '15 at 13:43
  • It urges me to re-check my existing code that how many times I have modified the original collection in `map`. A big lesson. – hengxin Dec 28 '15 at 13:54
  • 1
    You should use `AtomicBoolean`'s `getAndSet(false)` method within the `map` operation. – fps Dec 28 '15 at 13:56
  • 2
    @FedericoPeraltaSchaffner: Of course! That is much better, thanks! – Lii Dec 28 '15 at 13:58
  • 2
    @hengxin: *"how many times I have modified the original collection in map"* It is not that it is absolutely forbidden, but it goes against the functional idea of the stream library. The [documentation of `map`](https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#map-java.util.function.Function-) says that the operation should be *[non-interfering*](https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html#NonInterference) and [*stateless*](https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html#Statelessness). – Lii Dec 28 '15 at 14:29
5

If you really want to do this with streams in one line, then you can do something like this

boolean allTrue = IntStream.range(0, flags.length).reduce(0,
    (result, i) -> flags[i] ^ (flags[i] = false) ? result : 1) == 0;

However this does not look like a good idea, and I would lean towards using a BitSet as suggested by @MarounMaroun

SamYonnou
  • 2,068
  • 1
  • 19
  • 23
0

If you know the size of the array in advance, you can check in O(1) time if all the flags are true. Store the size of the array in a variable arraySize and set an additional variable indexCount to 0. Instead of changing the flags within the array to true/false, increment/decrement the indexCount variable. If you want to know whether all flags are true, simply check arraySize == indexCount. If you do not need to know the current flag of specific items, you can completely dispense with the array.

This is also applicable, if you have to check whether a specific amount of flags is true.

Rolch2015
  • 1,354
  • 1
  • 14
  • 20