Advertisement
aaaaaa123456789

UnlimitedMatrix C# implementation

Apr 2nd, 2015
371
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.    This code is hereby released to the public domain.
  3.    ~aaaaaa123456789, 2015-04-02 (last updated 2015-04-07)
  4. */
  5.  
  6. using System.Collections;
  7. using System.Collections.Generic;
  8.  
  9. public class UnlimitedMatrix<T> : IEnumerable, IEnumerable<long[]> {
  10.   private object[] quadrants;
  11.   private byte[] depths;
  12.   private bool is_value_type;
  13.  
  14.   public UnlimitedMatrix () {
  15.     quadrants = new object[4];
  16.     depths = new byte[4];
  17.     is_value_type = typeof(T).IsValueType;
  18.   }
  19.  
  20.   private bool is_default (T value) {
  21.     if (is_value_type) return value.Equals(default(T));
  22.     return (object) value == null;
  23.   }
  24.  
  25.   private int quadrant_for (ref long x, ref long y) {
  26.     int result = 0;
  27.     if (x < 0) {
  28.       x = ~x;
  29.       result ++;
  30.     }
  31.     if (y < 0) {
  32.       y = ~y;
  33.       result += 2;
  34.     }
  35.     return result;
  36.   }
  37.  
  38.   private long max_index (byte depth) {
  39.     if (depth >= 20) return 9223372036854775807;
  40.     return (8L << (3 * depth)) - 1;
  41.   }
  42.  
  43.   private byte depth_of (long index) {
  44.     if (index < 0) return 255;
  45.     byte current_depth = 0;
  46.     while (index > 7) {
  47.       current_depth ++;
  48.       index >>= 3;
  49.     }
  50.     return current_depth;
  51.   }
  52.  
  53.   private object retrieve (object array, byte depth, long x, long y) {
  54.     if (depth > 0) {
  55.       array = this.retrieve(array, (byte) (depth - 1), x >> 3, y >> 3);
  56.       x &= 7;
  57.       y &= 7;
  58.     }
  59.     if (array == null) return null;
  60.     return ((object[]) array)[(x << 3) | y];
  61.   }
  62.  
  63.   private void increase_depth (int quadrant, byte depth) {
  64.     if (depth > 20) throw new System.ArgumentOutOfRangeException();
  65.     if (this.quadrants[quadrant] == null) {
  66.       this.quadrants[quadrant] = new T[64];
  67.     }
  68.     while (this.depths[quadrant] < depth) {
  69.       object[] new_array = new object[65];
  70.       new_array[0] = this.quadrants[quadrant];
  71.       new_array[64] = 1;
  72.       this.quadrants[quadrant] = new_array;
  73.       this.depths[quadrant] ++;
  74.     }
  75.   }
  76.  
  77.   private byte[] get_coords (long x, long y, byte depth) {
  78.     byte[] coords = new byte[21];
  79.     byte current_depth;
  80.     for (current_depth = 0; current_depth <= depth; current_depth ++) {
  81.       coords[current_depth] = (byte) (((x & 7) << 3) + (y & 7));
  82.       x >>= 3;
  83.       y >>= 3;
  84.     }
  85.     return coords;
  86.   }
  87.  
  88.   private bool is_empty (T[] array) {
  89.     int p;
  90.     for (p = 0; p < 64; p ++) if (!is_default(array[p])) return false;
  91.     return true;
  92.   }
  93.  
  94.   private void reduce (object[] locations, byte[] coords, int quadrant) {
  95.     int depth = 0;
  96.     object[] p;
  97.     while (true) {
  98.       if (locations[depth + 1] == null) {
  99.         this.quadrants[quadrant] = null;
  100.         this.depths[quadrant] = 0;
  101.         return;
  102.       }
  103.       p = (object[]) locations[depth + 1];
  104.       p[coords[depth]] = null;
  105.       p[64] = (int) p[64] - 1;
  106.       if (((int) p[64]) != 0) break;
  107.       depth ++;
  108.     }
  109.     while (this.depths[quadrant] > 0) {
  110.       p = (object[]) this.quadrants[quadrant];
  111.       if (((int) p[64]) != 1) return;
  112.       if (p[0] == null) return;
  113.       this.quadrants[quadrant] = p[0];
  114.       this.depths[quadrant] --;
  115.     }
  116.   }
  117.  
  118.   private void set (int quadrant, long x, long y, T value) {
  119.     byte current_depth = this.depths[quadrant];
  120.     byte[] coords = get_coords(x, y, current_depth);
  121.     object location = this.quadrants[quadrant];
  122.     object[] p;
  123.     for (; current_depth > 0; current_depth --) {
  124.       p = (object[]) location;
  125.       if (p[coords[current_depth]] == null) {
  126.         if (current_depth == 1)
  127.           p[coords[current_depth]] = new T[64];
  128.         else {
  129.           object[] vr = new object[65];
  130.           vr[64] = 0;
  131.           p[coords[current_depth]] = vr;
  132.         }
  133.         p[64] = (int) p[64] + 1;
  134.       }
  135.       location = p[coords[current_depth]];
  136.     }
  137.     ((T[]) location)[coords[0]] = value;
  138.   }
  139.  
  140.   public void unset (long x, long y) {
  141.     if (is_default(this[x, y])) return;
  142.     int quadrant = quadrant_for(ref x, ref y);
  143.     byte current_depth = this.depths[quadrant];
  144.     byte[] coords = get_coords(x, y, current_depth);
  145.     object[] locations = new object[22];
  146.     locations[current_depth] = this.quadrants[quadrant];
  147.     while (current_depth > 0) {
  148.       locations[current_depth - 1] = ((object[]) locations[current_depth])[coords[current_depth]];
  149.       current_depth --;
  150.     }
  151.     ((T[]) locations[0])[coords[0]] = default(T);
  152.     if (is_empty((T[]) locations[0])) this.reduce(locations, coords, quadrant);
  153.   }
  154.  
  155.   public T this [long x, long y] {
  156.     get {
  157.       int quad = quadrant_for(ref x, ref y);
  158.       if (this.quadrants[quad] == null) return default(T);
  159.       long rv = max_index(this.depths[quad]);
  160.       if ((x > rv) || (y > rv)) return default(T);
  161.       T[] array;
  162.       if (this.depths[quad] > 0) {
  163.         array = (T[]) this.retrieve(this.quadrants[quad], (byte) (this.depths[quad] - 1), x >> 3, y >> 3);
  164.         if (array == null) return default(T);
  165.         x &= 7;
  166.         y &= 7;
  167.       } else {
  168.         array = (T[]) this.quadrants[quad];
  169.       }
  170.       return array[(x << 3) | y];
  171.     }
  172.     set {
  173.       if (is_default(value)) {
  174.         this.unset(x, y);
  175.         return;
  176.       }
  177.       int quad = quadrant_for(ref x, ref y);
  178.       byte depth = depth_of(x);
  179.       byte t = depth_of(y);
  180.       if (t > depth) depth = t;
  181.       if ((this.quadrants[quad] == null) || (this.depths[quad] < depth))
  182.         this.increase_depth(quad, depth);
  183.       this.set(quad, x, y, value);
  184.     }
  185.   }
  186.  
  187.   public T this [int x, int y] {
  188.     set {
  189.       this[(long) x, (long) y] = value;
  190.     }
  191.     get {
  192.       return this[(long) x, (long) y];
  193.     }
  194.   }
  195.  
  196.   public void clear () {
  197.     this.quadrants = new object[4];
  198.     this.depths = new byte[4];
  199.     System.GC.Collect();
  200.   }
  201.  
  202.   private IEnumerable<long[]> enumerate_direct (T[] array, bool ascending, long x, long y, int quadrant) {
  203.     x <<= 3;
  204.     y <<= 3;
  205.     int pos, index;
  206.     long effectiveX, effectiveY;
  207.     for (pos = 0; pos < 64; pos ++) {
  208.       index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
  209.       if (!ascending) index ^= 63;
  210.       if (is_default(array[index])) continue;
  211.       effectiveX = x + (index >> 3);
  212.       effectiveY = y + (index & 7);
  213.       if ((quadrant & 1) == 1) effectiveX = ~effectiveX;
  214.       if ((quadrant & 2) == 2) effectiveY = ~effectiveY;
  215.       yield return new long[] {effectiveX, effectiveY};
  216.     }
  217.   }
  218.  
  219.   private IEnumerable<long[]> enumerate_indirect (object[] array, bool ascending, byte depth, long x, long y, int quadrant) {
  220.     depth --;
  221.     x <<= 3;
  222.     y <<= 3;
  223.     int pos, index;
  224.     for (pos = 0; pos < 64; pos ++) {
  225.       index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
  226.       if (!ascending) index ^= 63;
  227.       if (array[index] == null) continue;
  228.       if (depth == 0)
  229.         foreach (long[] current in enumerate_direct((T[]) array[index], ascending, x + (index >> 3), y + (index & 7), quadrant))
  230.           yield return current;
  231.       else
  232.         foreach (long[] current in enumerate_indirect(
  233.           (object[]) array[index],
  234.           ascending,
  235.           depth,
  236.           x + (index >> 3),
  237.           y + (index & 7),
  238.           quadrant
  239.         )) yield return current;
  240.     }
  241.   }
  242.  
  243.   private IEnumerable<long[]> enumerate_quadrant (int quadrant, bool ascending) {
  244.     if (quadrants[quadrant] == null) yield break;
  245.     if (depths[quadrant] == 0) {
  246.       foreach (long[] current in enumerate_direct(
  247.         (T[]) quadrants[quadrant], ascending, 0, 0, quadrant
  248.       )) yield return current;
  249.       yield break;
  250.     }
  251.     foreach (long[] current in enumerate_indirect(
  252.       (object[]) quadrants[quadrant], ascending, depths[quadrant], 0, 0, quadrant
  253.     )) yield return current;
  254.   }
  255.  
  256.   public IEnumerator<long[]> GetEnumerator () {
  257.     foreach (long[] current in enumerate_quadrant(1, false)) yield return current;
  258.     foreach (long[] current in enumerate_quadrant(0, true)) yield return current;
  259.     foreach (long[] current in enumerate_quadrant(3, false)) yield return current;
  260.     foreach (long[] current in enumerate_quadrant(2, true)) yield return current;
  261.   }
  262.  
  263.   IEnumerator IEnumerable.GetEnumerator () {
  264.     return GetEnumerator();
  265.   }
  266. }
Advertisement
RAW Paste Data Copied
Advertisement