Which algorithm for finding empty ranges of numbers in a range of numbers?

Viewed 123

I'm doing some file analysis, where I mark explored regions in the file. Now I would like to find the unexplored regions, so I know what to look at next. This is much like what defragmentation software shows for free and used regions.

Example:

In this picture, let's say that explored regions are red, unexplored regions are gray. I need to determine the gray-region boundaries from these red regions.

enter image description here

My current code, a custom binary reader that logs what's been read:

public class CustomBinaryReader : BinaryReader {

    private readonly List<Block> _blocks;

    public CustomBinaryReader([NotNull] Stream input) : this(input, Encoding.Default) { }

    public CustomBinaryReader(Stream input, Encoding encoding, bool leaveOpen = true) : base(input, encoding, leaveOpen) {
        _blocks = new List<Block>();
    }

    public override byte[] ReadBytes(int count) {
        Log(count);
        return base.ReadBytes(count);
    }

    private void Log(int count) {
        _blocks.Add(new Block(BaseStream.Position, count));
    }

    private IEnumerable<Block> GetUnreadBlocks() {
        // how to get unread blocks in the stream, from read blocks ?
        throw new NotImplementedException();
    }
}

And the type that defines what a region is:

public class Block {
    public Block(long position, long length) {
        Position = position;
        Length = length;
    }

    public long Position { get; }
    public long Length { get; }
}

Question:

Is there a class of algorithms or data structures to solve such problem (like a tree or a graph) ? If such thing does not exist, can you give me some approach or tips on how to solve such problem?

2 Answers
Related