Logo Search packages:      
Sourcecode: f-spot version File versions

Util.cs

using System;
using System.Collections;

using SemWeb;

namespace SemWeb.Util {

      internal class ResSet : ICollection {
            Hashtable items = new Hashtable();
            ICollection keys;
            
            public ResSet() {
            }
            
            public ResSet(ICollection items) {
                  AddRange(items);
            }

            private ResSet(Hashtable items) {
                  this.items = items;
            }

            public void Add(Resource res) {
                  items[res] = items;
                  keys = null;
            }
            
            public void AddRange(ICollection items) {
                  if (items == null) return;
                  foreach (Resource r in items)
                        Add(r);
            }
                  
            public void Remove(Resource res) {
                  items.Remove(res);
                  keys = null;
            }
            
            public bool Contains(Resource res) {
                  return items.ContainsKey(res);
            }
            
            public ICollection Items {
                  get {
                        if (keys == null)
                              keys = items.Keys;
                        return keys;
                  }
            }
            
            public void AddRange(ResSet set) {
                  if (set == null) return;
                  foreach (Resource r in set.Items) {
                        Add(r);
                  }
            }
            
            public void Clear() {
                  items.Clear();
                  keys = null;
            }
            
            public ResSet Clone() {
                  return new ResSet((Hashtable)items.Clone());
            }
            
            public int Count { get { return items.Count; } }
            
            public IEnumerator GetEnumerator() { return items.Keys.GetEnumerator(); }
            
            bool ICollection.IsSynchronized { get { return false; } }
            object ICollection.SyncRoot { get { return null; } }
            
            public void CopyTo(System.Array array, int index) {
                  foreach (Resource r in this)
                        array.SetValue(r, index++);
            }
            
            public Resource[] ToArray() {
                  Resource[] ret = new Resource[Count];
                  CopyTo(ret, 0);
                  return ret;
            }
            
            public Entity[] ToEntityArray() {
                  Entity[] ret = new Entity[Count];
                  CopyTo(ret, 0);
                  return ret;
            }
            
            public void RetainAll(ResSet set) {
                  foreach (Resource r in new ArrayList(this))
                        if (!set.Contains(r))
                              Remove(r);
            }

            /*Hashtable Intersect(Hashtable x, Hashtable y) {
                  Hashtable a, b;
                  if (x.Count < y.Count) { a = x; b = y; }
                  else { b = x; a = y; }
                  Hashtable c = new Hashtable();
                  foreach (Resource r in a)
                        if (b.ContainsKey(r))
                              c[r] = c;
                  return c;
            }*/         
      }
      
      public class DistinctStatementsSink : StatementSink {
            StatementSink sink;
            StatementMap hash;
            bool resetMeta;
            public DistinctStatementsSink(StatementSink sink, bool resetMeta) {
                  this.sink = sink;
                  hash = new StatementMap();
                  this.resetMeta = resetMeta;
            }
            public bool Add(Statement s) {
                  if (resetMeta) s.Meta = Statement.DefaultMeta;
                  if (hash.ContainsKey(s)) return true;
                  hash[s] = hash;
                  return sink.Add(s);
            }
      }
      

      public class StatementList : ICollection {
            private const int DefaultInitialCapacity = 0x10;
            private int _size;
            private Statement[] _items;

            public StatementList() {
                  _items = new Statement[DefaultInitialCapacity];
            }           

            public StatementList(Statement[] statements) {
                  _items = (Statement[])statements.Clone();
                  _size = _items.Length;
            }           

            public Statement this[int index] { 
                  get { return _items[index]; }
                  set { _items[index] = value; } 
            }

            public int Count { get { return _size; } }

            private void EnsureCapacity(int count) { 
                  if (count <= _items.Length) return; 
                  int newLength;
                  Statement[] newData;
                  newLength = _items.Length << 1;
                  if (newLength == 0)
                        newLength = DefaultInitialCapacity;
                  while (newLength < count) 
                        newLength <<= 1;
                  newData = new Statement[newLength];
                  Array.Copy(_items, 0, newData, 0, _items.Length);
                  _items = newData;
            }
            
            private void Shift(int index, int count) { 
                  if (count > 0) { 
                        if (_size + count > _items.Length) { 
                              int newLength;
                              Statement[] newData;
                              newLength = (_items.Length > 0) ? _items.Length << 1 : 1;
                              while (newLength < _size + count) 
                                    newLength <<= 1;
                              newData = new Statement[newLength];
                              Array.Copy(_items, 0, newData, 0, index);
                              Array.Copy(_items, index, newData, index + count, _size - index);
                              _items = newData;
                        } else {
                              Array.Copy(_items, index, _items, index + count, _size - index);
                        }
                  } else if (count < 0) {
                        int x = index - count ;
                        Array.Copy(_items, x, _items, index, _size - x);
                  }
            }

            public int Add(Statement value) { 
                  if (_items.Length <= _size /* same as _items.Length < _size + 1) */) 
                        EnsureCapacity(_size + 1);
                  _items[_size] = value;
                  return _size++;
            }
            
            public void Remove(Statement s) {
                  if (_size == 0) return;
                  int index = Array.IndexOf(_items, s, 0, _size);
                  if (index < 0) return;
                  RemoveAt(index);
            }

            public virtual void Clear() { 
                  Array.Clear(_items, 0, _size);
                  _size = 0;
            }

            public virtual void RemoveAt(int index) { 
                  if (index < 0 || index >= _size) 
                        throw new ArgumentOutOfRangeException("index", index,
                              "Less than 0 or more than list count.");
                  Shift(index, -1);
                  _size--;
            }

            public void Reverse() {
                  for (int i = 0; i <= Count / 2; i++) {
                        Statement t = this[i];
                        this[i] = this[Count-i-1];
                        this[Count-i-1] = t;
                  }                       
            }
            
            public Statement[] ToArray() {
                  Statement[] ret = new Statement[_size];
                  Array.Copy(_items, ret, _size);
                  return ret;
            }
            
            internal Statement[] ToArray(Type t) {
                  return ToArray();
            }
            
            public static implicit operator Statement[](StatementList list) {
                  return list.ToArray();
            }
            
            public IEnumerator GetEnumerator() { return new Enumer(this); }
            
            public void CopyTo(Array dest, int start) {
                  _items.CopyTo(dest, start);
            }
            
            public object SyncRoot { get { return null; } }
            
            public bool IsSynchronized { get { return false; } }
            
            public void Sort() {
                  Array.Sort(_items, 0, _size);
            }
            
            class Enumer : IEnumerator {
                  StatementList list;
                  int index;
                  public Enumer(StatementList list) { this.list = list; index = -1; }
                  public void Reset() { index = -1; }
                  public bool MoveNext() {
                        if (index == list.Count - 1)
                              return false;
                        index++;
                        return true;
                  }
                  public object Current { get { return list[index]; } }
            }
      }


      // This is based on Mono's Hashtable implementation:
      // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
      public class StatementMap {

            struct Slot {
                  internal bool used, removed;
                  internal Statement key;
                  internal Object value;
                  internal int hashMix;
            }

            const int CHAIN_MARKER  = ~Int32.MaxValue;
            private readonly static string xstr = "Hashtable.Enumerator: snapshot out of sync.";

            private int inUse;
            private int modificationCount;
            private float loadFactor;
            private Slot [] table;
            private int threshold;
      
            private StatementList hashKeys;
            private HashValues hashValues;

            private static readonly int [] primeTbl = {
                  11,
                  19,
                  37,
                  73,
                  109,
                  163,
                  251,
                  367,
                  557,
                  823,
                  1237,
                  1861,
                  2777,
                  4177,
                  6247,
                  9371,
                  14057,
                  21089,
                  31627,
                  47431,
                  71143,
                  106721,
                  160073,
                  240101,
                  360163,
                  540217,
                  810343,
                  1215497,
                  1823231,
                  2734867,
                  4102283,
                  6153409,
                  9230113,
                  13845163
            };

            public StatementMap () : this (0, 1.0f) {}

            public StatementMap (int capacity, float loadFactor) {
                  if (capacity<0)
                        throw new ArgumentOutOfRangeException ("capacity", "negative capacity");

                  if (loadFactor < 0.1f || loadFactor > 1.0f || Single.IsNaN (loadFactor))
                        throw new ArgumentOutOfRangeException ("loadFactor", "load factor");

                  if (capacity == 0) ++capacity;
                  this.loadFactor = 0.75f*loadFactor;
                  double tableSize = capacity / this.loadFactor;

                        if (tableSize > Int32.MaxValue)
                                throw new ArgumentException ("Size is too big");

                        int size = (int) tableSize;
                  size = ToPrime (size);
                  this.SetTable (new Slot [size]);

                  this.inUse = 0;
                  this.modificationCount = 0;
            }

            public int Count {
                  get {
                        return inUse;
                  }
            }

            public StatementList Keys {
                  get {
                        if (this.hashKeys == null) {
                              this.hashKeys = new StatementList ();
                              Enumerator e = new Enumerator(this);
                              while (e.MoveNext())
                                    hashKeys.Add(e.Key);
                        }
                        return this.hashKeys;
                  }
            }
            
            public IEnumerable Values {
                  get {
                        if (this.hashValues == null)
                              this.hashValues = new HashValues (this);
                        return this.hashValues;
                  }
            }

            public Object this [Statement key] {
                  get {
                        Slot [] table = this.table;
                        uint size = (uint) table.Length;
                        int h = key.GetHashCode() & Int32.MaxValue;
                        uint indx = (uint)h;
                        uint step = (uint) ((h >> 5)+1) % (size-1)+1;
                        
                        for (uint i = size; i > 0; i--) {
                              indx %= size;
                              Slot entry = table [indx];
                              if (!entry.used)
                                    break;
                              
                              Statement k = entry.key;
                              
                              if ((entry.hashMix & Int32.MaxValue) == h
                                  && k == key) {
                                    return entry.value;
                              }
      
                              if ((entry.hashMix & CHAIN_MARKER) == 0)
                                    break;
      
                              indx += step;
                        }
                        
                        return null;
                  }
                  
                  set {
                        PutImpl (key, value, true);
                  }
            }

            public virtual void Clear ()
            {
                  for (int i = 0;i<table.Length;i++) {
                        table [i].used = false;
                        table [i].removed = false;
                        table [i].key = Statement.All;
                        table [i].value = null;
                        table [i].hashMix = 0;
                  }

                  inUse = 0;
                  modificationCount++;
            }

            public bool ContainsKey (Statement key)
            {
                  return (Find (key) >= 0);
            }

            public virtual void Remove (Statement key)
            {
                  int i = Find (key);
                  if (i >= 0) {
                        Slot [] table = this.table;
                        int h = table [i].hashMix;
                        h &= CHAIN_MARKER;
                        table [i].hashMix = h;
                        table [i].key = Statement.All;
                        if (h != 0) table [i].removed = true;
                        else table [i].used = false;
                        table [i].value = null;
                        --inUse;
                        ++modificationCount;
                  }
            }

            private void AdjustThreshold ()
            {
                  int size = table.Length;

                  threshold = (int) (size*loadFactor);
                  if (this.threshold >= size)
                        threshold = size-1;
            }

            private void SetTable (Slot [] table)
            {
                  if (table == null)
                        throw new ArgumentNullException ("table");

                  this.table = table;
                  AdjustThreshold ();
            }

            private int Find (Statement key)
            {
                  Slot [] table = this.table;
                  uint size = (uint) table.Length;
                  int h = key.GetHashCode() & Int32.MaxValue;
                  uint indx = (uint)h;
                  uint step = (uint) ((h >> 5)+1) % (size-1)+1;
                  
                  for (uint i = size; i > 0; i--) {
                        indx %= size;
                        Slot entry = table [indx];
                        if (!entry.used)
                              break;
                        
                        Statement k = entry.key;
                        
                        if ((entry.hashMix & Int32.MaxValue) == h
                            && k == key) {
                              return (int) indx;
                        }

                        if ((entry.hashMix & CHAIN_MARKER) == 0)
                              break;

                        indx += step;
                  }
                  return -1;
            }


            private void Rehash ()
            {
                  int oldSize = this.table.Length;

                  // From the SDK docs:
                  //   Hashtable is automatically increased
                  //   to the smallest prime number that is larger
                  //   than twice the current number of Hashtable buckets
                  uint newSize = (uint)ToPrime ((oldSize<<1)|1);


                  Slot [] newTable = new Slot [newSize];
                  Slot [] table = this.table;

                  for (int i = 0;i<oldSize;i++) {
                        Slot s = table [i];
                        if (s.used) {
                              int h = s.hashMix & Int32.MaxValue;
                              uint spot = (uint)h;
                              uint step = ((uint) (h>>5)+1)% (newSize-1)+1;
                              for (uint j = spot%newSize;;spot+= step, j = spot%newSize) {
                                    // No check for KeyMarker.Removed here,
                                    // because the table is just allocated.
                                    if (!newTable [j].used) {
                                          newTable [j].used = s.used;
                                          newTable [j].removed = s.removed;
                                          newTable [j].key = s.key;
                                          newTable [j].value = s.value;
                                          newTable [j].hashMix |= h;
                                          break;
                                    } else {
                                          newTable [j].hashMix |= CHAIN_MARKER;
                                    }
                              }
                        }
                  }

                  ++this.modificationCount;

                  this.SetTable (newTable);
            }


            private void PutImpl (Statement key, Object value, bool overwrite)
            {
                  uint size = (uint)this.table.Length;
                  if (this.inUse >= this.threshold) {
                        this.Rehash ();
                        size = (uint)this.table.Length;
                  }

                  int h = key.GetHashCode() & Int32.MaxValue;
                  uint spot = (uint)h;
                  uint step = (uint) ((spot>>5)+1)% (size-1)+1;
                  Slot [] table = this.table;
                  Slot entry;

                  int freeIndx = -1;
                  for (int i = 0; i < size; i++) {
                        int indx = (int) (spot % size);
                        entry = table [indx];

                        if (freeIndx == -1
                            && entry.removed
                            && (entry.hashMix & CHAIN_MARKER) != 0)
                              freeIndx = indx;

                        if (!entry.used ||
                            (entry.removed
                             && (entry.hashMix & CHAIN_MARKER) == 0)) {

                              if (freeIndx == -1)
                                    freeIndx = indx;
                              break;
                        }

                        if ((entry.hashMix & Int32.MaxValue) == h && key == entry.key) {
                              if (overwrite) {
                                    table [indx].value = value;
                                    ++this.modificationCount;
                              } else {
                                    // Handle Add ():
                                    // An entry with the same key already exists in the Hashtable.
                                    throw new ArgumentException (
                                                "Key duplication when adding: " + key);
                              }
                              return;
                        }

                        if (freeIndx == -1) {
                              table [indx].hashMix |= CHAIN_MARKER;
                        }

                        spot+= step;

                  }

                  if (freeIndx!= -1) {
                        table [freeIndx].used = true;
                        table [freeIndx].removed = false;
                        table [freeIndx].key = key;
                        table [freeIndx].value = value;
                        table [freeIndx].hashMix |= h;

                        ++this.inUse;
                        ++this.modificationCount;
                  }

            }

            //
            // Private static methods
            //
            internal static bool TestPrime (int x)
            {
                  if ((x & 1) != 0) {
                        for (int n = 3; n< (int)Math.Sqrt (x); n += 2) {
                              if ((x % n) == 0)
                                    return false;
                        }
                        return true;
                  }
                  // There is only one even prime - 2.
                  return (x == 2);
            }

            internal static int CalcPrime (int x)
            {
                  for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
                        if (TestPrime (i)) return i;
                  }
                  return x;
            }

            internal static int ToPrime (int x)
            {
                  for (int i = 0; i < primeTbl.Length; i++) {
                        if (x <= primeTbl [i])
                              return primeTbl [i];
                  }
                  return CalcPrime (x);
            }

            private sealed class Enumerator : IEnumerator {

                  private StatementMap host;
                  private int stamp;
                  private int pos;
                  private int size;

                  private bool hasCurrentKey;
                  private Statement currentKey;
                  private Object currentValue;

                  public Enumerator (StatementMap host) {
                        this.host = host;
                        stamp = host.modificationCount;
                        size = host.table.Length;
                        Reset ();
                  }

                  private void FailFast ()
                  {
                        if (host.modificationCount != stamp) {
                              throw new InvalidOperationException (xstr);
                        }
                  }

                  public void Reset ()
                  {
                        FailFast ();

                        pos = -1;
                        hasCurrentKey = false;
                        currentKey = Statement.All;
                        currentValue = null;
                  }

                  public bool MoveNext ()
                  {
                        FailFast ();

                        if (pos < size) {
                              while (++pos < size) {
                                    Slot entry = host.table [pos];

                                    if (entry.used && !entry.removed) {
                                          currentKey = entry.key;
                                          currentValue = entry.value;
                                          return true;
                                    }
                              }
                        }

                        hasCurrentKey = false;
                        currentKey = Statement.All;
                        currentValue = null;
                        return false;
                  }

                  public DictionaryEntry Entry
                  {
                        get {
                              if (!hasCurrentKey) throw new InvalidOperationException ();
                              FailFast ();
                              return new DictionaryEntry (currentKey, currentValue);
                        }
                  }

                  public Statement Key {
                        get {
                              if (!hasCurrentKey) throw new InvalidOperationException ();
                              FailFast ();
                              return currentKey;
                        }
                  }
                  
                  public Object Value {
                        get {
                              if (!hasCurrentKey) throw new InvalidOperationException ();
                              FailFast ();
                              return currentValue;
                        }
                  }

                  public Object Current {
                        get {
                              if (!hasCurrentKey) throw new InvalidOperationException ();
                              return currentValue;
                        }
                  }
            }

            private class HashValues : IEnumerable {
                  private StatementMap host;

                  public HashValues (StatementMap host) {
                        if (host == null)
                              throw new ArgumentNullException ();

                        this.host = host;
                  }

                  public virtual IEnumerator GetEnumerator ()
                  {
                        return new Enumerator (host);
                  }
            }
      }

      internal class MultiMap {
            Hashtable items = new Hashtable();
            
            public MultiMap() {
            }
            
            public void Put(object key, object value) {
                  object entry = items[key];
                  if (entry == null) {
                        items[key] = value;
                  } else if (entry is ArrayList) {
                        ((ArrayList)entry).Add(value);
                  } else {
                        ArrayList list = new ArrayList();
                        list.Add(entry);
                        list.Add(value);
                        items[key] = list;
                  }
            }

            public void Clear() {
                  items.Clear();
            }
            
            public IList Get(object key) {
                  object ret = items[key];
                  if (ret == null) return null;
                  if (ret is ArrayList) return (ArrayList)ret;
                  ArrayList list = new ArrayList();
                  list.Add(ret);
                  return list;
            }
            
            public IEnumerable Keys {
                  get {
                        return items.Keys;
                  }
            }
      }
      
      internal class Permutation {
            int[] state;
            int[] max;
            public Permutation(int n) : this(n, 2) {
            }
            public Permutation(int n, int e) {
                  state = new int[n];
                  max = new int[n];
                  for (int i = 0; i < n; i++)
                        max[i] = e;
            }
            public Permutation(int[] choices) {
                  state = new int[choices.Length];
                  max = choices;
            }
            public int[] Next() {
                  if (state == null) return null;
            
                  int[] ret = (int[])state.Clone();
                  
                  state[0]++;
                  for (int i = 0; i < max.Length; i++) { // use max.Length because state becomes null
                        if (state[i] < max[i]) break;
                        state[i] = 0;
                        if (i == state.Length-1) // done the next time around
                              state = null;
                        else // carry
                              state[i+1]++;
                  }

                  return ret;
            }
            public void Reset() {
                  state = new int[state.Length];
            }
      }
}

Generated by  Doxygen 1.6.0   Back to index