哪種算法可以找到數字範圍內的空數字範圍？

Question

我正在做一些文件分析，在文件中標記探索區域。現在我想找到un探索區域，所以我知道接下來要看什麼。這非常類似於碎片整理軟件針對免費和使用區域顯示的內容。

例子：

在這張圖片中，讓我們說，探索區域是紅色的，未開發的區域是灰色的。我需要從這些紅色區域確定灰色區域邊界。

我當前的代碼，它記錄什麼已經讀過一個自定義的二進制讀者：

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

問題：

是否有一類算法或數據結構來解決此類問題（如樹或圖）？如果這樣的事情不存在，你可以給我一些方法或提示如何解決這個問題？

Answer 1

按位置順序對使用區域進行排序。 找到每個的上限爲position+length。 從那裏，每個開放區域從一個區域的上界開始，直到（但不包括）下一個區域的下界。

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立即告訴我我最終錯過了什麼:)