在一定范围内查找数字空缺的算法是什么？

Question

我正在进行一些文件分析，其中我会标记文件中已探索过的区域。现在我想要找到未探索过的区域，以便知道下一步需要查看什么。这很像磁盘碎片整理软件显示空闲和已用区域的方式。

示例：

在此图片中，假设红色区域为已探索区域，灰色区域为未探索区域。我需要确定从这些红色区域中得出灰色区域边界的方法。

我的当前代码是自定义二进制读取器，记录了已读内容：

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();
    }
}

这是定义区域的类型：

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

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

问题：

是否有一类算法或数据结构可以解决这样的问题（如树或图）？如果不存在这样的东西，您能给我一些方法或提示来解决这个问题吗？

- aybe

---

基于图像还是原始数据？ - stelioslogothetis

它将基于一个具有两个成员的结构体：position和length。 - aybe

我看不出这里有什么难度。你有原始数据，对吧？你将已使用的块列表排序，合并相邻块，然后使用剩余边界作为空区域的边界。 - Prune

如果您有答案，最好将其发布为答案，而不是将其编辑到问题中，即使它基于已发布的答案。 - Bernhard Barker

是的，完成了，谢谢！ - aybe

Answer 1

按位置顺序对已使用区域进行排序。 查找每个区域的上限为position+length。 从那里开始，每个开放区域都从一个区域的上限开始，直到下一个区域的下限（不包括它）。

- Prune

Answer 2

以下是完整实现，来自@Prune的答案：

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using JetBrains.Annotations;

namespace Whatever
{
    public sealed class LoggedBinaryReader : BinaryReader
    {
        [UsedImplicitly]
        public LoggedBinaryReader([NotNull] Stream input) : this(input, Encoding.Default)
        {
        }

        public LoggedBinaryReader(Stream input, Encoding encoding, bool leaveOpen = true) : base(input, encoding, leaveOpen)
        {
            Journal = new LoggedBinaryReaderJournal(this);
        }

        private LoggedBinaryReaderJournal Journal { get; }

        public override int Read()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.Read();
        }

        public override int Read(byte[] buffer, int index, int count)
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.Read(buffer, index, count);
        }

        public override int Read(char[] buffer, int index, int count)
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.Read(buffer, index, count);
        }

        public override char ReadChar()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadChar();
        }

        public override char[] ReadChars(int count)
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadChars(count);
        }

        public override string ReadString()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadString();
        }

        public override bool ReadBoolean()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadBoolean();
        }

        public override byte ReadByte()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadByte();
        }

        public override sbyte ReadSByte()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadSByte();
        }

        public override short ReadInt16()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadInt16();
        }

        public override int ReadInt32()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadInt32();
        }

        public override long ReadInt64()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadInt64();
        }

        public override ushort ReadUInt16()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadUInt16();
        }

        public override uint ReadUInt32()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadUInt32();
        }

        public override ulong ReadUInt64()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadUInt64();
        }

        public override byte[] ReadBytes(int count)
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadBytes(count);
        }

        public override float ReadSingle()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadSingle();
        }

        public override double ReadDouble()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadDouble();
        }

        public override decimal ReadDecimal()
        {
            using (new LoggedBinaryReaderScope(Journal))
                return base.ReadDecimal();
        }

        public IEnumerable<LoggedBinaryReaderRegion> GetRegionsRead()
        {
            return Journal.GetRegions();
        }

        public IEnumerable<LoggedBinaryReaderRegion> GetRegionsUnread()
        {
            var blocks = new LinkedList<LoggedBinaryReaderRegion>(Journal.GetRegions());

            var curr = blocks.First;

            // nothing explored
            if (curr == null)
            {
                yield return new LoggedBinaryReaderRegion(0, BaseStream.Length);
                yield break;
            }

            // account for beginning of file
            if (curr.Value.Position > 0)
                yield return new LoggedBinaryReaderRegion(0, curr.Value.Position);

            // in-between
            while (true)
            {
                var next = curr.Next;
                if (next == null)
                    break;

                var position = curr.Value.Position + curr.Value.Length;
                var length = next.Value.Position - position;

                if (length > 0)
                    yield return new LoggedBinaryReaderRegion(position, length);

                curr = next;
            }

            // account for end of file
            if (curr.Value.Position + curr.Value.Length < BaseStream.Length)
                yield return new LoggedBinaryReaderRegion(
                    curr.Value.Position + curr.Value.Length,
                    BaseStream.Length - (curr.Value.Position + curr.Value.Length));
        }
    }

    public struct LoggedBinaryReaderRegion
    {
        internal LoggedBinaryReaderRegion(long position, long length)
        {
            Position = position;
            Length = length;
        }

        public long Position { get; }

        public long Length { get; }

        public override string ToString()
        {
            return $"{nameof(Position)}: {Position}, {nameof(Length)}: {Length}";
        }
    }

    internal class LoggedBinaryReaderJournal
    {
        internal LoggedBinaryReaderJournal([NotNull] LoggedBinaryReader reader)
        {
            if (reader == null)
                throw new ArgumentNullException(nameof(reader));

            Reader = reader;
            Regions = new List<LoggedBinaryReaderRegion>();
        }

        private long Position { get; set; }

        private LoggedBinaryReader Reader { get; }

        private List<LoggedBinaryReaderRegion> Regions { get; }

        internal void StartLogging()
        {
            Position = Reader.BaseStream.Position;
        }

        internal void StopLogging()
        {
            var length = Reader.BaseStream.Position - Position;
            var region = new LoggedBinaryReaderRegion(Position, length);
            Regions.Add(region);
        }

        public IEnumerable<LoggedBinaryReaderRegion> GetRegions()
        {
            return Regions.OrderBy(s => s.Position);
        }
    }

    internal struct LoggedBinaryReaderScope : IDisposable
    {
        private LoggedBinaryReaderJournal Journal { get; }

        internal LoggedBinaryReaderScope(LoggedBinaryReaderJournal journal)
        {
            Journal = journal;
            Journal.StartLogging();
        }

        public void Dispose()
        {
            Journal.StopLogging();
        }
    }
}

这是什么：

它记录BinaryReader读取的所有内容，并且可以返回已读或未读的区域。每个Read...方法都会被日志记录。

实际上，我需要它来解析一个古老的视频游戏格式，我编写了一个解析器，在十六进制编辑器中浏览了300Kb的数据并使用奇怪的结构体来确保我已经读取了整个文件，这太过繁琐，而LoggedBinaryReader立即告诉我我最终错过了什么 :)

- aybe