数字の範囲で空の数字の範囲を見つけるアルゴリズムはどれですか？

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です。 そこから、それぞれの空き領域は、次の領域の下限まで（ただしこれには含まれません）、1つの領域の上限で開始されます。 @Pruneの答えから

Answer 2

は、ここでの完全な実装です：

それはBinaryReader読み取りどんな記録し、読んでてきた領域を返したりすることはできません。これは何

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

。すべてのRead...メソッドはジャーナルによって記録されます。

実際に私はパーサーを書いた古いビデオゲームのあいまいなフォーマットのためにこれを必要としました。これはファイル全体を読み過ぎたことを確実にするために奇妙な構造の16進エディタで+ 300Kbのデータをブラウジングしていました。これはLoggedBinaryReader即座に私が最後に逃したものを教えてくれた:)