Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- This code is hereby released to the public domain.
- ~aaaaaa123456789, 2015-04-02 (last updated 2015-04-07)
- */
- using System.Collections;
- using System.Collections.Generic;
- public class UnlimitedMatrix<T> : IEnumerable, IEnumerable<long[]> {
- private object[] quadrants;
- private byte[] depths;
- private bool is_value_type;
- public UnlimitedMatrix () {
- quadrants = new object[4];
- depths = new byte[4];
- is_value_type = typeof(T).IsValueType;
- }
- private bool is_default (T value) {
- if (is_value_type) return value.Equals(default(T));
- return (object) value == null;
- }
- private int quadrant_for (ref long x, ref long y) {
- int result = 0;
- if (x < 0) {
- x = ~x;
- result ++;
- }
- if (y < 0) {
- y = ~y;
- result += 2;
- }
- return result;
- }
- private long max_index (byte depth) {
- if (depth >= 20) return 9223372036854775807;
- return (8L << (3 * depth)) - 1;
- }
- private byte depth_of (long index) {
- if (index < 0) return 255;
- byte current_depth = 0;
- while (index > 7) {
- current_depth ++;
- index >>= 3;
- }
- return current_depth;
- }
- private object retrieve (object array, byte depth, long x, long y) {
- if (depth > 0) {
- array = this.retrieve(array, (byte) (depth - 1), x >> 3, y >> 3);
- x &= 7;
- y &= 7;
- }
- if (array == null) return null;
- return ((object[]) array)[(x << 3) | y];
- }
- private void increase_depth (int quadrant, byte depth) {
- if (depth > 20) throw new System.ArgumentOutOfRangeException();
- if (this.quadrants[quadrant] == null) {
- this.quadrants[quadrant] = new T[64];
- }
- while (this.depths[quadrant] < depth) {
- object[] new_array = new object[65];
- new_array[0] = this.quadrants[quadrant];
- new_array[64] = 1;
- this.quadrants[quadrant] = new_array;
- this.depths[quadrant] ++;
- }
- }
- private byte[] get_coords (long x, long y, byte depth) {
- byte[] coords = new byte[21];
- byte current_depth;
- for (current_depth = 0; current_depth <= depth; current_depth ++) {
- coords[current_depth] = (byte) (((x & 7) << 3) + (y & 7));
- x >>= 3;
- y >>= 3;
- }
- return coords;
- }
- private bool is_empty (T[] array) {
- int p;
- for (p = 0; p < 64; p ++) if (!is_default(array[p])) return false;
- return true;
- }
- private void reduce (object[] locations, byte[] coords, int quadrant) {
- int depth = 0;
- object[] p;
- while (true) {
- if (locations[depth + 1] == null) {
- this.quadrants[quadrant] = null;
- this.depths[quadrant] = 0;
- return;
- }
- p = (object[]) locations[depth + 1];
- p[coords[depth]] = null;
- p[64] = (int) p[64] - 1;
- if (((int) p[64]) != 0) break;
- depth ++;
- }
- while (this.depths[quadrant] > 0) {
- p = (object[]) this.quadrants[quadrant];
- if (((int) p[64]) != 1) return;
- if (p[0] == null) return;
- this.quadrants[quadrant] = p[0];
- this.depths[quadrant] --;
- }
- }
- private void set (int quadrant, long x, long y, T value) {
- byte current_depth = this.depths[quadrant];
- byte[] coords = get_coords(x, y, current_depth);
- object location = this.quadrants[quadrant];
- object[] p;
- for (; current_depth > 0; current_depth --) {
- p = (object[]) location;
- if (p[coords[current_depth]] == null) {
- if (current_depth == 1)
- p[coords[current_depth]] = new T[64];
- else {
- object[] vr = new object[65];
- vr[64] = 0;
- p[coords[current_depth]] = vr;
- }
- p[64] = (int) p[64] + 1;
- }
- location = p[coords[current_depth]];
- }
- ((T[]) location)[coords[0]] = value;
- }
- public void unset (long x, long y) {
- if (is_default(this[x, y])) return;
- int quadrant = quadrant_for(ref x, ref y);
- byte current_depth = this.depths[quadrant];
- byte[] coords = get_coords(x, y, current_depth);
- object[] locations = new object[22];
- locations[current_depth] = this.quadrants[quadrant];
- while (current_depth > 0) {
- locations[current_depth - 1] = ((object[]) locations[current_depth])[coords[current_depth]];
- current_depth --;
- }
- ((T[]) locations[0])[coords[0]] = default(T);
- if (is_empty((T[]) locations[0])) this.reduce(locations, coords, quadrant);
- }
- public T this [long x, long y] {
- get {
- int quad = quadrant_for(ref x, ref y);
- if (this.quadrants[quad] == null) return default(T);
- long rv = max_index(this.depths[quad]);
- if ((x > rv) || (y > rv)) return default(T);
- T[] array;
- if (this.depths[quad] > 0) {
- array = (T[]) this.retrieve(this.quadrants[quad], (byte) (this.depths[quad] - 1), x >> 3, y >> 3);
- if (array == null) return default(T);
- x &= 7;
- y &= 7;
- } else {
- array = (T[]) this.quadrants[quad];
- }
- return array[(x << 3) | y];
- }
- set {
- if (is_default(value)) {
- this.unset(x, y);
- return;
- }
- int quad = quadrant_for(ref x, ref y);
- byte depth = depth_of(x);
- byte t = depth_of(y);
- if (t > depth) depth = t;
- if ((this.quadrants[quad] == null) || (this.depths[quad] < depth))
- this.increase_depth(quad, depth);
- this.set(quad, x, y, value);
- }
- }
- public T this [int x, int y] {
- set {
- this[(long) x, (long) y] = value;
- }
- get {
- return this[(long) x, (long) y];
- }
- }
- public void clear () {
- this.quadrants = new object[4];
- this.depths = new byte[4];
- System.GC.Collect();
- }
- private IEnumerable<long[]> enumerate_direct (T[] array, bool ascending, long x, long y, int quadrant) {
- x <<= 3;
- y <<= 3;
- int pos, index;
- long effectiveX, effectiveY;
- for (pos = 0; pos < 64; pos ++) {
- index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
- if (!ascending) index ^= 63;
- if (is_default(array[index])) continue;
- effectiveX = x + (index >> 3);
- effectiveY = y + (index & 7);
- if ((quadrant & 1) == 1) effectiveX = ~effectiveX;
- if ((quadrant & 2) == 2) effectiveY = ~effectiveY;
- yield return new long[] {effectiveX, effectiveY};
- }
- }
- private IEnumerable<long[]> enumerate_indirect (object[] array, bool ascending, byte depth, long x, long y, int quadrant) {
- depth --;
- x <<= 3;
- y <<= 3;
- int pos, index;
- for (pos = 0; pos < 64; pos ++) {
- index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
- if (!ascending) index ^= 63;
- if (array[index] == null) continue;
- if (depth == 0)
- foreach (long[] current in enumerate_direct((T[]) array[index], ascending, x + (index >> 3), y + (index & 7), quadrant))
- yield return current;
- else
- foreach (long[] current in enumerate_indirect(
- (object[]) array[index],
- ascending,
- depth,
- x + (index >> 3),
- y + (index & 7),
- quadrant
- )) yield return current;
- }
- }
- private IEnumerable<long[]> enumerate_quadrant (int quadrant, bool ascending) {
- if (quadrants[quadrant] == null) yield break;
- if (depths[quadrant] == 0) {
- foreach (long[] current in enumerate_direct(
- (T[]) quadrants[quadrant], ascending, 0, 0, quadrant
- )) yield return current;
- yield break;
- }
- foreach (long[] current in enumerate_indirect(
- (object[]) quadrants[quadrant], ascending, depths[quadrant], 0, 0, quadrant
- )) yield return current;
- }
- public IEnumerator<long[]> GetEnumerator () {
- foreach (long[] current in enumerate_quadrant(1, false)) yield return current;
- foreach (long[] current in enumerate_quadrant(0, true)) yield return current;
- foreach (long[] current in enumerate_quadrant(3, false)) yield return current;
- foreach (long[] current in enumerate_quadrant(2, true)) yield return current;
- }
- IEnumerator IEnumerable.GetEnumerator () {
- return GetEnumerator();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement