context: /*
      Copyright 2014-2017 Travel Modelling Group, Department of Civil Engineering, University of Toronto
  
      This file is part of XTMF.
  
      XTMF is free software: you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation, either version 3 of the License, or
      (at your option) any later version.
  
      XTMF is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.
  
      You should have received a copy of the GNU General Public License
      along with XTMF.  If not, see <http://www.gnu.org/licenses/>.
  */
  using System;
  using System.Collections.Generic;
  using System.IO;
  using System.Text;
  
  namespace Datastructure
  {
      public sealed class SparseArray<T>
      {
          internal SparseIndexing Indexing;
          private const int Version = 2;
          private T[] Data;
  
          public SparseArray(SparseIndexing indexing, T[] rawData = null)
          {
              Indexing = indexing;
              if(rawData != null)
              {
                  Data = rawData;
              }
              GenerateStructure();
          }
  
          public int Count => Data.Length;
  
          public int Top { get; private set; }
  
          public T this[int o]
          {
              get
              {
                  if(GetTransformedIndex(ref o))
                  {
                      return Data[o];
                  }
                  else
                  {
                      // return null / whatever the closest thing to null is
                      return default(T);
                  }
              }
  
              set
              {
                  var originalO = o;
                  if(GetTransformedIndex(ref o))
                  {
                      Data[o] = value;
                  }
                  else
                  {
                      throw new IndexOutOfRangeException(String.Format("The location {0} is invalid for this SparseArray Datastructure!", originalO));
                  }
              }
          }
  
          public static SparseArray<T> CreateSparseArray(int[] sparseSpace, IList<T> data)
          {
              var length = sparseSpace.Length;
              var indexes = new SortStruct[length];
              for(var i = 0; i < length; i++)
              {
                  indexes[i].SparseSpace = sparseSpace[i];
                  indexes[i].DataSpace = i;
              }
              return CreateSparseArray(data, length, indexes);
          }
  
          public static SparseArray<T> CreateSparseArray(Func<T, int> placeFunction, IList<T> data)
          {
              var length = data.Count;
              var indexes = new SortStruct[length];
              for(var i = 0; i < length; i++)
              {
                  indexes[i].SparseSpace = placeFunction(data[i]);
                  indexes[i].DataSpace = i;
              }
              return CreateSparseArray(data, length, indexes);
          }
  
          public bool ContainsIndex(int o)
          {
              return GetTransformedIndex(ref o);
          }
  
          public SparseArray<TKey> CreateSimilarArray<TKey>()
          {
              var ret = new SparseArray<TKey>(Indexing);
              return ret;
          }
  
          public SparseTwinIndex<TKey> CreateSquareTwinArray<TKey>()
          {
              SparseIndexing twinIndex;
              var length = Indexing.Indexes.Length;
              twinIndex.Indexes = new SparseSet[length];
              for(var i = 0; i < length; i++)
              {
                  twinIndex.Indexes[i].Start = Indexing.Indexes[i].Start;
                  twinIndex.Indexes[i].Stop = Indexing.Indexes[i].Stop;
                  twinIndex.Indexes[i].SubIndex = new SparseIndexing() { Indexes = new SparseSet[length] };
                  for(var j = 0; j < length; j++)
                  {
                      twinIndex.Indexes[i].SubIndex.Indexes[j] = Indexing.Indexes[j];
                  }
              }
              return new SparseTwinIndex<TKey>(twinIndex);
          }
  
          public T[] GetFlatData()
          {
              return Data;
          }
  
          public int GetFlatIndex(int sparseSpaceIndex)
          {
              if(GetTransformedIndex(ref sparseSpaceIndex))
              {
                  return sparseSpaceIndex;
              }
              return -1;
          }
  
          public int GetSparseIndex(int flatIndex)
          {
              var soFar = 0;
              for(var i = 0; i < Indexing.Indexes.Length; i++)
              {
                  var index = Indexing.Indexes[i];
                  var length = index.Stop - index.Start + 1;
                  if(soFar + length > flatIndex)
                  {
                      return index.Start + (flatIndex - soFar);
                  }
                  soFar += length;
              }
              return -1;
          }
  
          public void Save(string fileName, Func<T, float[]> decompose, int types)
          {
              using (var writer = new BinaryWriter(new
                  FileStream(fileName, FileMode.Create, FileAccess.Write,
                  FileShare.None, 0x8000, FileOptions.SequentialScan),
                  Encoding.Default))
              {
                  var dataLength = Data.Length;
                  var highestZone = 0;
  
                  for(var i = 0; i < dataLength; i++)
                  {
                      if(Data[i] != null) highestZone = i;
                  }
                  writer.Write(highestZone);
                  writer.Write(Version);
                  writer.Write(types);
                  WriteSparseIndexes(writer, types);
  
                  for(var i = 0; i < dataLength; i++)
                  {
                      if(Data[i] != null)
                      {
                          var data = decompose(Data[i]);
                          for(var j = 0; j < data.Length; j++)
                          {
                              writer.Write(data[j]);
                          }
                      }
                  }
              }
          }
  
          /// <summary>
          /// Get a copy of all of the valid indexes
          /// </summary>
          /// <returns>An array of all of the valid indexes</returns>
          public int[] ValidIndexArray()
          {
              var ret = new int[Data.Length];
              var pos = 0;
              var length = Indexing.Indexes.Length;
              for(var i = 0; i < length; i++)
              {
                  var stop = Indexing.Indexes[i].Stop;
                  for(var j = Indexing.Indexes[i].Start; j <= stop; j++)
                  {
                      ret[pos++] = j;
                  }
              }
              return ret;
          }
  
          /// <summary>
          /// Get an enumeration of all of the valid indexes in the sparse array
          /// </summary>
          /// <returns>An enumeration of the indexes</returns>
          public IEnumerable<int> ValidIndexies()
          {
              var length = Indexing.Indexes.Length;
              for(var i = 0; i < length; i++)
              {
                  var stop = Indexing.Indexes[i].Stop;
                  for(var j = Indexing.Indexes[i].Start; j <= stop; j++)
                  {
                      yield return j;
                  }
              }
          }
  
          private static SparseArray<T> CreateSparseArray(IList<T> data, int length, SortStruct[] indexes)
          {
              Array.Sort(indexes, new CompareSortStruct());
              var localData = new T[length];
              if (data != null)
              {
                  for (var i = 0; i < length; i++)
                  {
                      localData[i] = data[indexes[i].DataSpace];
                  }
              }
              return new SparseArray<T>(GenerateIndexes(indexes), localData);
          }
  
          private static SparseIndexing GenerateIndexes(SortStruct[] data)
          {
              var indexes = new SparseIndexing();
              var elements = new List<SparseSet>();
              var length = data.Length;
              var current = default(SparseSet);
              if(length == 0) return indexes;
              current.Start = data[0].SparseSpace;
              var expected = data[0].SparseSpace + 1;
              for(var i = 1; i < length; i++)
              {
                  if(data[i].SparseSpace != expected)
                  {
  
gt:                     current.Stop = data[i - 1].SparseSpace;