lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [13/26] lucenenet git commit: first commit of facet porting, failing tests will be fixed in next commits.
Date Fri, 14 Nov 2014 11:59:28 GMT
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/TaxonomyReader.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/TaxonomyReader.cs b/Lucene.Net.Facet/Taxonomy/TaxonomyReader.cs
new file mode 100644
index 0000000..aaee8fe
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/TaxonomyReader.cs
@@ -0,0 +1,316 @@
+using System;
+using System.Diagnostics;
+using System.Collections.Generic;
+using System.Threading;
+using Lucene.Net.Support;
+
+namespace Lucene.Net.Facet.Taxonomy
+{
+
+
+    using AlreadyClosedException = Lucene.Net.Store.AlreadyClosedException;
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// TaxonomyReader is the read-only interface with which the faceted-search
+    /// library uses the taxonomy during search time.
+    /// <P>
+    /// A TaxonomyReader holds a list of categories. Each category has a serial
+    /// number which we call an "ordinal", and a hierarchical "path" name:
+    /// <UL>
+    /// <LI>
+    /// The ordinal is an integer that starts at 0 for the first category (which is
+    /// always the root category), and grows contiguously as more categories are
+    /// added; Note that once a category is added, it can never be deleted.
+    /// <LI>
+    /// The path is a CategoryPath object specifying the category's position in the
+    /// hierarchy.
+    /// </UL>
+    /// <B>Notes about concurrent access to the taxonomy:</B>
+    /// <P>
+    /// An implementation must allow multiple readers to be active concurrently
+    /// with a single writer. Readers follow so-called "point in time" semantics,
+    /// i.e., a TaxonomyReader object will only see taxonomy entries which were
+    /// available at the time it was created. What the writer writes is only
+    /// available to (new) readers after the writer's commit() is called.
+    /// <P>
+    /// In faceted search, two separate indices are used: the main Lucene index,
+    /// and the taxonomy. Because the main index refers to the categories listed
+    /// in the taxonomy, it is important to open the taxonomy *after* opening the
+    /// main index, and it is also necessary to reopen() the taxonomy after
+    /// reopen()ing the main index.
+    /// <P>
+    /// This order is important, otherwise it would be possible for the main index
+    /// to refer to a category which is not yet visible in the old snapshot of
+    /// the taxonomy. Note that it is indeed fine for the the taxonomy to be opened
+    /// after the main index - even a long time after. The reason is that once
+    /// a category is added to the taxonomy, it can never be changed or deleted,
+    /// so there is no danger that a "too new" taxonomy not being consistent with
+    /// an older index.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    public abstract class TaxonomyReader
+    {
+
+        /// <summary>
+        /// An iterator over a category's children. </summary>
+        public class ChildrenIterator
+        {
+
+            internal readonly int[] siblings;
+            internal int child;
+
+            internal ChildrenIterator(int child, int[] siblings)
+            {
+                this.siblings = siblings;
+                this.child = child;
+            }
+
+            /// <summary>
+            /// Return the next child ordinal, or <seealso cref="TaxonomyReader#INVALID_ORDINAL"/>
+            /// if no more children.
+            /// </summary>
+            public virtual int Next()
+            {
+                int res = child;
+                if (child != TaxonomyReader.INVALID_ORDINAL)
+                {
+                    child = siblings[child];
+                }
+                return res;
+            }
+
+        }
+
+        /// <summary>
+        /// Sole constructor. </summary>
+        public TaxonomyReader()
+        {
+        }
+
+        /// <summary>
+        /// The root category (the category with the empty path) always has the ordinal
+        /// 0, to which we give a name ROOT_ORDINAL. <seealso cref="#getOrdinal(FacetLabel)"/>
+        /// of an empty path will always return {@code ROOT_ORDINAL}, and
+        /// <seealso cref="#getPath(int)"/> with {@code ROOT_ORDINAL} will return the empty path.
+        /// </summary>
+        public const int ROOT_ORDINAL = 0;
+
+        /// <summary>
+        /// Ordinals are always non-negative, so a negative ordinal can be used to
+        /// signify an error. Methods here return INVALID_ORDINAL (-1) in this case.
+        /// </summary>
+        public const int INVALID_ORDINAL = -1;
+
+        /// <summary>
+        /// If the taxonomy has changed since the provided reader was opened, open and
+        /// return a new <seealso cref="TaxonomyReader"/>; else, return {@code null}. The new
+        /// reader, if not {@code null}, will be the same type of reader as the one
+        /// given to this method.
+        /// 
+        /// <para>
+        /// This method is typically far less costly than opening a fully new
+        /// <seealso cref="TaxonomyReader"/> as it shares resources with the provided
+        /// <seealso cref="TaxonomyReader"/>, when possible.
+        /// </para>
+        /// </summary>
+        public static T OpenIfChanged<T>(T oldTaxoReader) where T : TaxonomyReader
+        {
+            T newTaxoReader = (T)oldTaxoReader.DoOpenIfChanged();
+            Debug.Assert(newTaxoReader != oldTaxoReader);
+            return newTaxoReader;
+        }
+
+        private volatile bool Closed = false;
+
+        // set refCount to 1 at start
+        private readonly AtomicInteger refCount = new AtomicInteger(1);
+
+        /// <summary>
+        /// performs the actual task of closing the resources that are used by the
+        /// taxonomy reader.
+        /// </summary>
+        protected internal abstract void DoClose();
+
+        /// <summary>
+        /// Implements the actual opening of a new <seealso cref="TaxonomyReader"/> instance if
+        /// the taxonomy has changed.
+        /// </summary>
+        /// <seealso cref= #openIfChanged(TaxonomyReader) </seealso>
+        protected internal abstract TaxonomyReader DoOpenIfChanged();
+
+        /// <summary>
+        /// Throws <seealso cref="AlreadyClosedException"/> if this IndexReader is closed
+        /// </summary>
+        protected internal void EnsureOpen()
+        {
+            if (RefCount <= 0)
+            {
+                throw new AlreadyClosedException("this TaxonomyReader is closed");
+            }
+        }
+
+        public virtual void Dispose(bool disposing)
+        {
+            if (disposing)
+            {
+                lock (this)
+                {
+                    if (!Closed)
+                    {
+                        DecRef();
+                        Closed = true;
+                    }
+                }
+            }
+        }
+
+
+        /// <summary>
+        /// Expert: decreases the refCount of this TaxonomyReader instance. If the
+        /// refCount drops to 0 this taxonomy reader is closed.
+        /// </summary>
+        public void DecRef()
+        {
+            EnsureOpen();
+            int rc = refCount.DecrementAndGet();
+            if (rc == 0)
+            {
+                bool success = false;
+                try
+                {
+                    DoClose();
+                    Closed = true;
+                    success = true;
+                }
+                finally
+                {
+                    if (!success)
+                    {
+                        // Put reference back on failure
+                        refCount.IncrementAndGet();
+                    }
+                }
+            }
+            else if (rc < 0)
+            {
+                throw new ThreadStateException("too many decRef calls: refCount is " + rc + " after decrement");
+            }
+        }
+
+        /// <summary>
+        /// Returns a <seealso cref="ParallelTaxonomyArrays"/> object which can be used to
+        /// efficiently traverse the taxonomy tree.
+        /// </summary>
+        public abstract ParallelTaxonomyArrays ParallelTaxonomyArrays { get; }
+
+        /// <summary>
+        /// Returns an iterator over the children of the given ordinal. </summary>
+        public virtual ChildrenIterator GetChildren(int ordinal)
+        {
+            ParallelTaxonomyArrays arrays = ParallelTaxonomyArrays;
+            int child = ordinal >= 0 ? arrays.Children()[ordinal] : INVALID_ORDINAL;
+            return new ChildrenIterator(child, arrays.Siblings());
+        }
+
+        /// <summary>
+        /// Retrieve user committed data.
+        /// </summary>
+        /// <seealso cref= TaxonomyWriter#setCommitData(Map) </seealso>
+        public abstract IDictionary<string, string> CommitUserData { get; }
+
+        /// <summary>
+        /// Returns the ordinal of the category given as a path. The ordinal is the
+        /// category's serial number, an integer which starts with 0 and grows as more
+        /// categories are added (note that once a category is added, it can never be
+        /// deleted).
+        /// </summary>
+        /// <returns> the category's ordinal or <seealso cref="#INVALID_ORDINAL"/> if the category
+        ///         wasn't foun. </returns>
+        public abstract int GetOrdinal(FacetLabel categoryPath);
+
+        /// <summary>
+        /// Returns ordinal for the dim + path. </summary>
+        public virtual int GetOrdinal(string dim, string[] path)
+        {
+            string[] fullPath = new string[path.Length + 1];
+            fullPath[0] = dim;
+            Array.Copy(path, 0, fullPath, 1, path.Length);
+            return GetOrdinal(new FacetLabel(fullPath));
+        }
+
+        /// <summary>
+        /// Returns the path name of the category with the given ordinal. </summary>
+        public abstract FacetLabel GetPath(int ordinal);
+
+        /// <summary>
+        /// Returns the current refCount for this taxonomy reader. </summary>
+        public int RefCount
+        {
+            get
+            {
+                return refCount.Get();
+            }
+        }
+
+        /// <summary>
+        /// Returns the number of categories in the taxonomy. Note that the number of
+        /// categories returned is often slightly higher than the number of categories
+        /// inserted into the taxonomy; This is because when a category is added to the
+        /// taxonomy, its ancestors are also added automatically (including the root,
+        /// which always get ordinal 0).
+        /// </summary>
+        public abstract int Size { get; }
+
+        /// <summary>
+        /// Expert: increments the refCount of this TaxonomyReader instance. RefCounts
+        /// can be used to determine when a taxonomy reader can be closed safely, i.e.
+        /// as soon as there are no more references. Be sure to always call a
+        /// corresponding decRef(), in a finally clause; otherwise the reader may never
+        /// be closed.
+        /// </summary>
+        public void IncRef()
+        {
+            EnsureOpen();
+            refCount.IncrementAndGet();
+        }
+
+        /// <summary>
+        /// Expert: increments the refCount of this TaxonomyReader
+        ///  instance only if it has not been closed yet.  Returns
+        ///  true on success. 
+        /// </summary>
+        public bool TryIncRef()
+        {
+            int count;
+            while ((count = refCount.Get()) > 0)
+            {
+                if (refCount.CompareAndSet(count, count + 1))
+                {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/TaxonomyWriter.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/TaxonomyWriter.cs b/Lucene.Net.Facet/Taxonomy/TaxonomyWriter.cs
new file mode 100644
index 0000000..26a3e10
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/TaxonomyWriter.cs
@@ -0,0 +1,125 @@
+using System;
+using System.Collections.Generic;
+using Lucene.Net.Index;
+
+namespace Lucene.Net.Facet.Taxonomy
+{
+
+
+    using TwoPhaseCommit = Lucene.Net.Index.TwoPhaseCommit;
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// TaxonomyWriter is the interface which the faceted-search library uses
+    /// to dynamically build the taxonomy at indexing time.
+    /// <P>
+    /// Notes about concurrent access to the taxonomy:
+    /// <P>
+    /// An implementation must allow multiple readers and a single writer to be
+    /// active concurrently. Readers follow so-called "point in time" semantics,
+    /// i.e., a reader object will only see taxonomy entries which were available
+    /// at the time it was created. What the writer writes is only available to
+    /// (new) readers after the writer's commit() is called.
+    /// <P>
+    /// Faceted search keeps two indices - namely Lucene's main index, and this
+    /// taxonomy index. When one or more readers are active concurrently with the
+    /// writer, care must be taken to avoid an inconsistency between the state of
+    /// these two indices: When writing to the indices, the taxonomy must always
+    /// be committed to disk *before* the main index, because the main index
+    /// refers to categories listed in the taxonomy.
+    /// Such control can best be achieved by turning off the main index's
+    /// "autocommit" feature, and explicitly calling commit() for both indices
+    /// (first for the taxonomy, then for the main index).
+    /// In old versions of Lucene (2.2 or earlier), when autocommit could not be
+    /// turned off, a more complicated solution needs to be used. E.g., use
+    /// some sort of (possibly inter-process) locking to ensure that a reader
+    /// is being opened only right after both indices have been flushed (and
+    /// before anything else is written to them).
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    public interface TaxonomyWriter : IDisposable, TwoPhaseCommit
+    {
+
+        /// <summary>
+        /// addCategory() adds a category with a given path name to the taxonomy,
+        /// and returns its ordinal. If the category was already present in
+        /// the taxonomy, its existing ordinal is returned.
+        /// <P>
+        /// Before adding a category, addCategory() makes sure that all its
+        /// ancestor categories exist in the taxonomy as well. As result, the
+        /// ordinal of a category is guaranteed to be smaller then the ordinal of
+        /// any of its descendants. 
+        /// </summary>
+        int AddCategory(FacetLabel categoryPath);
+
+        /// <summary>
+        /// getParent() returns the ordinal of the parent category of the category
+        /// with the given ordinal.
+        /// <P>
+        /// When a category is specified as a path name, finding the path of its
+        /// parent is as trivial as dropping the last component of the path.
+        /// getParent() is functionally equivalent to calling getPath() on the
+        /// given ordinal, dropping the last component of the path, and then calling
+        /// getOrdinal() to get an ordinal back. 
+        /// <P>
+        /// If the given ordinal is the ROOT_ORDINAL, an INVALID_ORDINAL is returned.
+        /// If the given ordinal is a top-level category, the ROOT_ORDINAL is returned.
+        /// If an invalid ordinal is given (negative or beyond the last available
+        /// ordinal), an ArrayIndexOutOfBoundsException is thrown. However, it is
+        /// expected that getParent will only be called for ordinals which are
+        /// already known to be in the taxonomy.
+        /// TODO (Facet): instead of a getParent(ordinal) method, consider having a
+        /// <P>
+        /// getCategory(categorypath, prefixlen) which is similar to addCategory
+        /// except it doesn't add new categories; This method can be used to get
+        /// the ordinals of all prefixes of the given category, and it can use
+        /// exactly the same code and cache used by addCategory() so it means less code.
+        /// </summary>
+        int GetParent(int ordinal);
+
+        /// <summary>
+        /// getSize() returns the number of categories in the taxonomy.
+        /// <P>
+        /// Because categories are numbered consecutively starting with 0, it
+        /// means the taxonomy contains ordinals 0 through getSize()-1.
+        /// <P>
+        /// Note that the number returned by getSize() is often slightly higher
+        /// than the number of categories inserted into the taxonomy; This is
+        /// because when a category is added to the taxonomy, its ancestors
+        /// are also added automatically (including the root, which always get
+        /// ordinal 0).
+        /// </summary>
+        int Size { get; }
+
+        /// <summary>
+        /// Sets the commit user data map. That method is considered a transaction and
+        /// will be <seealso cref="#commit() committed"/> even if no other changes were made to
+        /// the writer instance.
+        /// <para>
+        /// <b>NOTE:</b> the map is cloned internally, therefore altering the map's
+        /// contents after calling this method has no effect.
+        /// </para>
+        /// </summary>
+        IDictionary<string, string> CommitData { set; get; }
+
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/CategoryPathUtils.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/CategoryPathUtils.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/CategoryPathUtils.cs
new file mode 100644
index 0000000..36e5db1
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/CategoryPathUtils.cs
@@ -0,0 +1,99 @@
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// Utilities for use of <seealso cref="FacetLabel"/> by <seealso cref="CompactLabelToOrdinal"/>. </summary>
+    internal class CategoryPathUtils
+    {
+
+        /// <summary>
+        /// Serializes the given <seealso cref="FacetLabel"/> to the <seealso cref="CharBlockArray"/>. </summary>
+        public static void Serialize(FacetLabel cp, CharBlockArray charBlockArray)
+        {
+            charBlockArray.Append((char)cp.length);
+            if (cp.length == 0)
+            {
+                return;
+            }
+            for (int i = 0; i < cp.length; i++)
+            {
+                charBlockArray.Append((char)cp.components[i].Length);
+                charBlockArray.Append(cp.components[i]);
+            }
+        }
+
+        /// <summary>
+        /// Calculates a hash function of a path that was serialized with
+        /// <seealso cref="#serialize(FacetLabel, CharBlockArray)"/>.
+        /// </summary>
+        public static int HashCodeOfSerialized(CharBlockArray charBlockArray, int offset)
+        {
+            int length = charBlockArray.CharAt(offset++);
+            if (length == 0)
+            {
+                return 0;
+            }
+
+            int hash = length;
+            for (int i = 0; i < length; i++)
+            {
+                int len = charBlockArray.CharAt(offset++);
+                hash = hash * 31 + charBlockArray.SubSequence(offset, offset + len).GetHashCode();
+                offset += len;
+            }
+            return hash;
+        }
+
+        /// <summary>
+        /// Check whether the <seealso cref="FacetLabel"/> is equal to the one serialized in
+        /// <seealso cref="CharBlockArray"/>.
+        /// </summary>
+        public static bool EqualsToSerialized(FacetLabel cp, CharBlockArray charBlockArray, int offset)
+        {
+            int n = charBlockArray.CharAt(offset++);
+            if (cp.length != n)
+            {
+                return false;
+            }
+            if (cp.length == 0)
+            {
+                return true;
+            }
+
+            for (int i = 0; i < cp.length; i++)
+            {
+                int len = charBlockArray.CharAt(offset++);
+                if (len != cp.components[i].Length)
+                {
+                    return false;
+                }
+
+                if (!cp.components[i].Equals(charBlockArray.SubSequence(offset, offset + len)))
+                {
+                    return false;
+                }
+                offset += len;
+            }
+            return true;
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/CharBlockArray.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/CharBlockArray.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/CharBlockArray.cs
new file mode 100644
index 0000000..4695eb0
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/CharBlockArray.cs
@@ -0,0 +1,234 @@
+using System;
+using System.Collections.Generic;
+using System.IO;
+using System.Text;
+using Lucene.Net.Store;
+using Lucene.Net.Support;
+
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// Similar to <seealso cref="StringBuilder"/>, but with a more efficient growing strategy.
+    /// This class uses char array blocks to grow.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    [Serializable]
+    public class CharBlockArray : ICharSequence
+    {
+
+        private const long serialVersionUID = 1L;
+
+        private const int DefaultBlockSize = 32 * 1024; // 32 KB default size
+
+        [Serializable]
+        internal sealed class Block : ICloneable
+        {
+            internal const long serialVersionUID = 1L;
+
+            internal readonly char[] chars;
+            internal int length;
+
+            internal Block(int size)
+            {
+                this.chars = new char[size];
+                this.length = 0;
+            }
+
+            public object Clone()
+            {
+                throw new NotImplementedException();
+            }
+        }
+
+        internal IList<Block> blocks;
+        internal Block current;
+        internal int blockSize;
+        internal int length_Renamed;
+
+        public CharBlockArray()
+            : this(DefaultBlockSize)
+        {
+        }
+
+        internal CharBlockArray(int blockSize)
+        {
+            this.blocks = new List<Block>();
+            this.blockSize = blockSize;
+            AddBlock();
+        }
+
+        private void AddBlock()
+        {
+            this.current = new Block(this.blockSize);
+            this.blocks.Add(this.current);
+        }
+
+        internal virtual int blockIndex(int index)
+        {
+            return index / blockSize;
+        }
+
+        internal virtual int IndexInBlock(int index)
+        {
+            return index % blockSize;
+        }
+
+        public CharBlockArray Append(ICharSequence chars)
+        {
+            return Append(chars, 0, chars.Length);
+        }
+
+        public CharBlockArray Append(char c)
+        {
+            if (this.current.length == this.blockSize)
+            {
+                AddBlock();
+            }
+            this.current.chars[this.current.length++] = c;
+            this.length_Renamed++;
+
+            return this;
+        }
+
+        public CharBlockArray Append(ICharSequence chars, int start, int length)
+        {
+            int end = start + length;
+            for (int i = start; i < end; i++)
+            {
+                Append(chars.CharAt(i));
+            }
+            return this;
+        }
+
+        public virtual CharBlockArray Append(char[] chars, int start, int length)
+        {
+            int offset = start;
+            int remain = length;
+            while (remain > 0)
+            {
+                if (this.current.length == this.blockSize)
+                {
+                    AddBlock();
+                }
+                int toCopy = remain;
+                int remainingInBlock = this.blockSize - this.current.length;
+                if (remainingInBlock < toCopy)
+                {
+                    toCopy = remainingInBlock;
+                }
+                Array.Copy(chars, offset, this.current.chars, this.current.length, toCopy);
+                offset += toCopy;
+                remain -= toCopy;
+                this.current.length += toCopy;
+            }
+
+            this.length_Renamed += length;
+            return this;
+        }
+
+        public virtual CharBlockArray Append(string s)
+        {
+            int remain = s.Length;
+            int offset = 0;
+            while (remain > 0)
+            {
+                if (this.current.length == this.blockSize)
+                {
+                    AddBlock();
+                }
+                int toCopy = remain;
+                int remainingInBlock = this.blockSize - this.current.length;
+                if (remainingInBlock < toCopy)
+                {
+                    toCopy = remainingInBlock;
+                }
+                s.CopyTo(offset, this.current.chars, this.current.length, offset + toCopy - offset);
+                offset += toCopy;
+                remain -= toCopy;
+                this.current.length += toCopy;
+            }
+
+            this.length_Renamed += s.Length;
+            return this;
+        }
+
+        public int Length
+        {
+            get
+            {
+                return this.length_Renamed;
+            }
+        }
+
+        public char CharAt(int index)
+        {
+            Block b = blocks[blockIndex(index)];
+            return b.chars[IndexInBlock(index)];
+        }
+
+        public ICharSequence SubSequence(int start, int end)
+        {
+            int remaining = end - start;
+            StringBuilder sb = new StringBuilder(remaining);
+            int blockIdx = blockIndex(start);
+            int indexInBlock = IndexInBlock(start);
+            while (remaining > 0)
+            {
+                Block b = blocks[blockIdx++];
+                int numToAppend = Math.Min(remaining, b.length - indexInBlock);
+                sb.Append(b.chars, indexInBlock, numToAppend);
+                remaining -= numToAppend;
+                indexInBlock = 0; // 2nd+ iterations read from start of the block
+            }
+            return new StringCharSequenceWrapper(sb.ToString());
+        }
+
+
+
+
+        public override string ToString()
+        {
+            StringBuilder sb = new StringBuilder();
+            foreach (Block b in blocks)
+            {
+                sb.Append(b.chars, 0, b.length);
+            }
+            return sb.ToString();
+        }
+
+        internal virtual void Flush(OutputStreamDataOutput @out)
+        {
+            
+            using (var ms = StreamUtils.SerializeToStream(this))
+            {
+                var bytes = ms.ToArray();
+                @out.WriteBytes(bytes, 0, bytes.Length);
+            }
+        }
+
+        public static CharBlockArray Open(BinaryReader @in)
+        {
+            return StreamUtils.DeserializeFromStream(@in) as CharBlockArray;
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/Cl2oTaxonomyWriterCache.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/Cl2oTaxonomyWriterCache.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/Cl2oTaxonomyWriterCache.cs
new file mode 100644
index 0000000..1b8f0c3
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/Cl2oTaxonomyWriterCache.cs
@@ -0,0 +1,123 @@
+using System.Threading;
+
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// <seealso cref="TaxonomyWriterCache"/> using <seealso cref="CompactLabelToOrdinal"/>. Although
+    /// called cache, it maintains in memory all the mappings from category to
+    /// ordinal, relying on that <seealso cref="CompactLabelToOrdinal"/> is an efficient
+    /// mapping for this purpose.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    public class Cl2oTaxonomyWriterCache : TaxonomyWriterCache
+    {
+        private const int LockTimeOut = 1000;
+        private readonly ReaderWriterLock @lock = new ReaderWriterLock();
+        private readonly int initialCapcity, numHashArrays;
+        private readonly float loadFactor;
+
+        private volatile CompactLabelToOrdinal cache;
+
+        /// <summary>
+        /// Sole constructor. </summary>
+        public Cl2oTaxonomyWriterCache(int initialCapcity, float loadFactor, int numHashArrays)
+        {
+            this.cache = new CompactLabelToOrdinal(initialCapcity, loadFactor, numHashArrays);
+            this.initialCapcity = initialCapcity;
+            this.numHashArrays = numHashArrays;
+            this.loadFactor = loadFactor;
+        }
+
+        public virtual void Clear()
+        {
+            @lock.AcquireWriterLock(LockTimeOut);
+            try
+            {
+                cache = new CompactLabelToOrdinal(initialCapcity, loadFactor, numHashArrays);
+            }
+            finally
+            {
+                @lock.ReleaseWriterLock();
+            }
+        }
+
+        public virtual void Close()
+        {
+            lock (this)
+            {
+                cache = null;
+            }
+        }
+
+        public virtual bool Full
+        {
+            get
+            {
+                // This cache is never full
+                return false;
+            }
+        }
+
+        public virtual int Get(FacetLabel categoryPath)
+        {
+            @lock.AcquireReaderLock(LockTimeOut);
+            try
+            {
+                return cache.GetOrdinal(categoryPath);
+            }
+            finally
+            {
+                @lock.ReleaseReaderLock();
+            }
+        }
+
+        public virtual bool Put(FacetLabel categoryPath, int ordinal)
+        {
+            @lock.AcquireWriterLock(LockTimeOut);
+            try
+            {
+                cache.AddLabel(categoryPath, ordinal);
+                // Tell the caller we didn't clear part of the cache, so it doesn't
+                // have to flush its on-disk index now
+                return false;
+            }
+            finally
+            {
+                @lock.ReleaseWriterLock();
+            }
+        }
+
+        /// <summary>
+        /// Returns the number of bytes in memory used by this object. </summary>
+        public virtual int MemoryUsage
+        {
+            get
+            {
+                return cache == null ? 0 : cache.MemoryUsage;
+            }
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/CollisionMap.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/CollisionMap.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/CollisionMap.cs
new file mode 100644
index 0000000..1adb7b3
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/CollisionMap.cs
@@ -0,0 +1,288 @@
+using System;
+using System.Collections.Generic;
+
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// HashMap to store colliding labels. See <seealso cref="CompactLabelToOrdinal"/> for
+    /// details.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    public class CollisionMap
+    {
+
+        private int capacity_Renamed;
+        private float loadFactor;
+        private int size_Renamed;
+        private int threshold;
+
+        public class Entry
+        {
+            internal int offset;
+            internal int cid;
+            internal Entry next;
+            internal int hash;
+
+            internal Entry(int offset, int cid, int h, Entry e)
+            {
+                this.offset = offset;
+                this.cid = cid;
+                this.next = e;
+                this.hash = h;
+            }
+        }
+
+        private CharBlockArray labelRepository;
+
+        private Entry[] entries;
+
+        internal CollisionMap(CharBlockArray labelRepository)
+            : this(16 * 1024, 0.75f, labelRepository)
+        {
+        }
+
+        internal CollisionMap(int initialCapacity, CharBlockArray labelRepository)
+            : this(initialCapacity, 0.75f, labelRepository)
+        {
+        }
+
+        private CollisionMap(int initialCapacity, float loadFactor, CharBlockArray labelRepository)
+        {
+            this.labelRepository = labelRepository;
+            this.loadFactor = loadFactor;
+            this.capacity_Renamed = CompactLabelToOrdinal.DetermineCapacity(2, initialCapacity);
+
+            this.entries = new Entry[this.capacity_Renamed];
+            this.threshold = (int)(this.capacity_Renamed * this.loadFactor);
+        }
+
+        /// <summary>
+        /// How many mappings. </summary>
+        public virtual int Size()
+        {
+            return this.size_Renamed;
+        }
+
+        /// <summary>
+        /// How many slots are allocated. </summary>
+        public virtual int capacity()
+        {
+            return this.capacity_Renamed;
+        }
+
+        private void Grow()
+        {
+            int newCapacity = this.capacity_Renamed * 2;
+            Entry[] newEntries = new Entry[newCapacity];
+            Entry[] src = this.entries;
+
+            for (int j = 0; j < src.Length; j++)
+            {
+                Entry e = src[j];
+                if (e != null)
+                {
+                    src[j] = null;
+                    do
+                    {
+                        Entry next = e.next;
+                        int hash = e.hash;
+                        int i = IndexFor(hash, newCapacity);
+                        e.next = newEntries[i];
+                        newEntries[i] = e;
+                        e = next;
+                    } while (e != null);
+                }
+            }
+
+            this.capacity_Renamed = newCapacity;
+            this.entries = newEntries;
+            this.threshold = (int)(this.capacity_Renamed * this.loadFactor);
+        }
+
+        /// <summary>
+        /// Return the mapping, or {@link
+        ///  LabelToOrdinal#INVALID_ORDINAL} if the label isn't
+        ///  recognized. 
+        /// </summary>
+        public virtual int Get(FacetLabel label, int hash)
+        {
+            int bucketIndex = IndexFor(hash, this.capacity_Renamed);
+            Entry e = this.entries[bucketIndex];
+
+            while (e != null && !(hash == e.hash && CategoryPathUtils.EqualsToSerialized(label, labelRepository, e.offset)))
+            {
+                e = e.next;
+            }
+            if (e == null)
+            {
+                return LabelToOrdinal.INVALID_ORDINAL;
+            }
+
+            return e.cid;
+        }
+
+        /// <summary>
+        /// Add another mapping. </summary>
+        public virtual int AddLabel(FacetLabel label, int hash, int cid)
+        {
+            int bucketIndex = IndexFor(hash, this.capacity_Renamed);
+            for (Entry e = this.entries[bucketIndex]; e != null; e = e.next)
+            {
+                if (e.hash == hash && CategoryPathUtils.EqualsToSerialized(label, labelRepository, e.offset))
+                {
+                    return e.cid;
+                }
+            }
+
+            // new string; add to label repository
+            int offset = labelRepository.Length;
+            CategoryPathUtils.Serialize(label, labelRepository);
+            AddEntry(offset, cid, hash, bucketIndex);
+            return cid;
+        }
+
+        /// <summary>
+        /// This method does not check if the same value is already in the map because
+        /// we pass in an char-array offset, so so we now that we're in resize-mode
+        /// here.
+        /// </summary>
+        public virtual void AddLabelOffset(int hash, int offset, int cid)
+        {
+            int bucketIndex = IndexFor(hash, this.capacity_Renamed);
+            AddEntry(offset, cid, hash, bucketIndex);
+        }
+
+        private void AddEntry(int offset, int cid, int hash, int bucketIndex)
+        {
+            Entry e = this.entries[bucketIndex];
+            this.entries[bucketIndex] = new Entry(offset, cid, hash, e);
+            if (this.size_Renamed++ >= this.threshold)
+            {
+                Grow();
+            }
+        }
+
+        internal virtual EntryIterator entryIterator()
+        {
+            return new EntryIterator(this, entries, size_Renamed);
+        }
+
+        /// <summary>
+        /// Returns index for hash code h. 
+        /// </summary>
+        internal static int IndexFor(int h, int length)
+        {
+            return h & (length - 1);
+        }
+
+        /// <summary>
+        /// Returns an estimate of the memory usage of this CollisionMap. </summary>
+        /// <returns> The approximate number of bytes used by this structure. </returns>
+        internal virtual int MemoryUsage
+        {
+            get
+            {
+                int memoryUsage = 0;
+                if (this.entries != null)
+                {
+                    foreach (Entry e in this.entries)
+                    {
+                        if (e != null)
+                        {
+                            memoryUsage += (4 * 4);
+                            for (Entry ee = e.next; ee != null; ee = ee.next)
+                            {
+                                memoryUsage += (4 * 4);
+                            }
+                        }
+                    }
+                }
+                return memoryUsage;
+            }
+        }
+
+        public class EntryIterator 
+        {
+            private readonly CollisionMap outerInstance;
+
+            internal Entry next_Renamed; // next entry to return
+            internal int index; // current slot
+            internal Entry[] ents;
+
+            internal EntryIterator(CollisionMap outerInstance, Entry[] entries, int size)
+            {
+                this.outerInstance = outerInstance;
+                this.ents = entries;
+                Entry[] t = entries;
+                int i = t.Length;
+                Entry n = null;
+                if (size != 0) // advance to first entry
+                {
+                    while (i > 0 && (n = t[--i]) == null)
+                    {
+                        // advance
+                    }
+                }
+                this.next_Renamed = n;
+                this.index = i;
+            }
+
+            public bool HasNext()
+            {
+                return this.next_Renamed != null;
+            }
+
+            public Entry Next()
+            {
+                Entry e = this.next_Renamed;
+                if (e == null)
+                {
+                    throw new IndexOutOfRangeException();
+                }
+
+                Entry n = e.next;
+                Entry[] t = ents;
+                int i = this.index;
+                while (n == null && i > 0)
+                {
+                    n = t[--i];
+                }
+                this.index = i;
+                this.next_Renamed = n;
+                return e;
+            }
+
+            public void Remove()
+            {
+                throw new System.NotSupportedException();
+            }
+
+            public Entry Current()
+            {
+                return ents[index];
+            }
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/CompactLabelToOrdinal.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/CompactLabelToOrdinal.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/CompactLabelToOrdinal.cs
new file mode 100644
index 0000000..9f73968
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/CompactLabelToOrdinal.cs
@@ -0,0 +1,521 @@
+using System;
+using System.Collections.Generic;
+using System.IO;
+using Lucene.Net.Store;
+
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+
+    /// <summary>
+    /// This is a very efficient LabelToOrdinal implementation that uses a
+    /// CharBlockArray to store all labels and a configurable number of HashArrays to
+    /// reference the labels.
+    /// <para>
+    /// Since the HashArrays don't handle collisions, a <seealso cref="CollisionMap"/> is used
+    /// to store the colliding labels.
+    /// </para>
+    /// <para>
+    /// This data structure grows by adding a new HashArray whenever the number of
+    /// collisions in the <seealso cref="CollisionMap"/> exceeds {@code loadFactor} * 
+    /// <seealso cref="#getMaxOrdinal()"/>. Growing also includes reinserting all colliding
+    /// labels into the HashArrays to possibly reduce the number of collisions.
+    /// 
+    /// For setting the {@code loadFactor} see 
+    /// <seealso cref="#CompactLabelToOrdinal(int, float, int)"/>. 
+    /// 
+    /// </para>
+    /// <para>
+    /// This data structure has a much lower memory footprint (~30%) compared to a
+    /// Java HashMap&lt;String, Integer&gt;. It also only uses a small fraction of objects
+    /// a HashMap would use, thus limiting the GC overhead. Ingestion speed was also
+    /// ~50% faster compared to a HashMap for 3M unique labels.
+    /// 
+    /// @lucene.experimental
+    /// </para>
+    /// </summary>
+    public class CompactLabelToOrdinal : LabelToOrdinal
+    {
+
+        /// <summary>
+        /// Default maximum load factor. </summary>
+        public const float DefaultLoadFactor = 0.15f;
+
+        internal const char TERMINATOR_CHAR = (char)0xffff;
+        private const int COLLISION = -5;
+
+        private HashArray[] hashArrays;
+        private CollisionMap collisionMap;
+        private CharBlockArray labelRepository;
+
+        private int capacity;
+        private int threshold;
+        private float loadFactor;
+
+        /// <summary>
+        /// How many labels. </summary>
+        public virtual int SizeOfMap()
+        {
+            return this.collisionMap.Size();
+        }
+
+        private CompactLabelToOrdinal()
+        {
+        }
+
+        /// <summary>
+        /// Sole constructor. </summary>
+        public CompactLabelToOrdinal(int initialCapacity, float loadFactor, int numHashArrays)
+        {
+
+            this.hashArrays = new HashArray[numHashArrays];
+
+            this.capacity = DetermineCapacity((int)Math.Pow(2, numHashArrays), initialCapacity);
+            Init();
+            this.collisionMap = new CollisionMap(this.labelRepository);
+
+            this.counter = 0;
+            this.loadFactor = loadFactor;
+
+            this.threshold = (int)(this.loadFactor * this.capacity);
+        }
+
+        internal static int DetermineCapacity(int minCapacity, int initialCapacity)
+        {
+            int capacity = minCapacity;
+            while (capacity < initialCapacity)
+            {
+                capacity <<= 1;
+            }
+            return capacity;
+        }
+
+        private void Init()
+        {
+            labelRepository = new CharBlockArray();
+            CategoryPathUtils.Serialize(new FacetLabel(), labelRepository);
+
+            int c = this.capacity;
+            for (int i = 0; i < this.hashArrays.Length; i++)
+            {
+                this.hashArrays[i] = new HashArray(c);
+                c /= 2;
+            }
+        }
+
+        public override void AddLabel(FacetLabel label, int ordinal)
+        {
+            if (collisionMap.Size() > threshold)
+            {
+                Grow();
+            }
+
+            int hash = CompactLabelToOrdinal.StringHashCode(label);
+            for (int i = 0; i < this.hashArrays.Length; i++)
+            {
+                if (AddLabel(this.hashArrays[i], label, hash, ordinal))
+                {
+                    return;
+                }
+            }
+
+            int prevVal = collisionMap.AddLabel(label, hash, ordinal);
+            if (prevVal != ordinal)
+            {
+                throw new System.ArgumentException("Label already exists: " + label + " prev ordinal " + prevVal);
+            }
+        }
+
+        public override int GetOrdinal(FacetLabel label)
+        {
+            if (label == null)
+            {
+                return LabelToOrdinal.INVALID_ORDINAL;
+            }
+
+            int hash = CompactLabelToOrdinal.StringHashCode(label);
+            for (int i = 0; i < this.hashArrays.Length; i++)
+            {
+                int ord = GetOrdinal(this.hashArrays[i], label, hash);
+                if (ord != COLLISION)
+                {
+                    return ord;
+                }
+            }
+
+            return this.collisionMap.Get(label, hash);
+        }
+
+        private void Grow()
+        {
+            HashArray temp = this.hashArrays[this.hashArrays.Length - 1];
+
+            for (int i = this.hashArrays.Length - 1; i > 0; i--)
+            {
+                this.hashArrays[i] = this.hashArrays[i - 1];
+            }
+
+            this.capacity *= 2;
+            this.hashArrays[0] = new HashArray(this.capacity);
+
+            for (int i = 1; i < this.hashArrays.Length; i++)
+            {
+                int[] sourceOffsetArray = this.hashArrays[i].offsets;
+                int[] sourceCidsArray = this.hashArrays[i].cids;
+
+                for (int k = 0; k < sourceOffsetArray.Length; k++)
+                {
+
+                    for (int j = 0; j < i && sourceOffsetArray[k] != 0; j++)
+                    {
+                        int[] targetOffsetArray = this.hashArrays[j].offsets;
+                        int[] targetCidsArray = this.hashArrays[j].cids;
+
+                        int newIndex = IndexFor(StringHashCode(this.labelRepository, sourceOffsetArray[k]), targetOffsetArray.Length);
+                        if (targetOffsetArray[newIndex] == 0)
+                        {
+                            targetOffsetArray[newIndex] = sourceOffsetArray[k];
+                            targetCidsArray[newIndex] = sourceCidsArray[k];
+                            sourceOffsetArray[k] = 0;
+                        }
+                    }
+                }
+            }
+
+            for (int i = 0; i < temp.offsets.Length; i++)
+            {
+                int offset = temp.offsets[i];
+                if (offset > 0)
+                {
+                    int hash = StringHashCode(this.labelRepository, offset);
+                    AddLabelOffset(hash, temp.cids[i], offset);
+                }
+            }
+
+            CollisionMap oldCollisionMap = this.collisionMap;
+            this.collisionMap = new CollisionMap(oldCollisionMap.capacity(), this.labelRepository);
+            this.threshold = (int)(this.capacity * this.loadFactor);
+
+            var it = oldCollisionMap.entryIterator();
+            while (it.HasNext())
+            {
+                var e = it.Current();
+                AddLabelOffset(StringHashCode(this.labelRepository, e.offset), e.cid, e.offset);
+            }
+        }
+
+        private bool AddLabel(HashArray a, FacetLabel label, int hash, int ordinal)
+        {
+            int index = CompactLabelToOrdinal.IndexFor(hash, a.offsets.Length);
+            int offset = a.offsets[index];
+
+            if (offset == 0)
+            {
+                a.offsets[index] = this.labelRepository.Length;
+                CategoryPathUtils.Serialize(label, labelRepository);
+                a.cids[index] = ordinal;
+                return true;
+            }
+
+            return false;
+        }
+
+        private void AddLabelOffset(int hash, int cid, int knownOffset)
+        {
+            for (int i = 0; i < this.hashArrays.Length; i++)
+            {
+                if (AddLabelOffsetToHashArray(this.hashArrays[i], hash, cid, knownOffset))
+                {
+                    return;
+                }
+            }
+
+            this.collisionMap.AddLabelOffset(hash, knownOffset, cid);
+
+            if (this.collisionMap.Size() > this.threshold)
+            {
+                Grow();
+            }
+        }
+
+        private bool AddLabelOffsetToHashArray(HashArray a, int hash, int ordinal, int knownOffset)
+        {
+
+            int index = CompactLabelToOrdinal.IndexFor(hash, a.offsets.Length);
+            int offset = a.offsets[index];
+
+            if (offset == 0)
+            {
+                a.offsets[index] = knownOffset;
+                a.cids[index] = ordinal;
+                return true;
+            }
+
+            return false;
+        }
+
+        private int GetOrdinal(HashArray a, FacetLabel label, int hash)
+        {
+            if (label == null)
+            {
+                return LabelToOrdinal.INVALID_ORDINAL;
+            }
+
+            int index = IndexFor(hash, a.offsets.Length);
+            int offset = a.offsets[index];
+            if (offset == 0)
+            {
+                return LabelToOrdinal.INVALID_ORDINAL;
+            }
+
+            if (CategoryPathUtils.EqualsToSerialized(label, labelRepository, offset))
+            {
+                return a.cids[index];
+            }
+
+            return COLLISION;
+        }
+
+        /// <summary>
+        /// Returns index for hash code h. </summary>
+        internal static int IndexFor(int h, int length)
+        {
+            return h & (length - 1);
+        }
+
+        // static int stringHashCode(String label) {
+        // int len = label.length();
+        // int hash = 0;
+        // int i;
+        // for (i = 0; i < len; ++i)
+        // hash = 33 * hash + label.charAt(i);
+        //
+        // hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+        // hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+        //
+        // return hash;
+        //
+        // }
+
+        internal static int StringHashCode(FacetLabel label)
+        {
+            int hash = label.GetHashCode();
+
+            hash = hash ^ (((int)((uint)hash >> 20)) ^ ((int)((uint)hash >> 12)));
+            hash = hash ^ ((int)((uint)hash >> 7)) ^ ((int)((uint)hash >> 4));
+
+            return hash;
+
+        }
+
+        internal static int StringHashCode(CharBlockArray labelRepository, int offset)
+        {
+            int hash = CategoryPathUtils.HashCodeOfSerialized(labelRepository, offset);
+            hash = hash ^ (((int)((uint)hash >> 20)) ^ ((int)((uint)hash >> 12)));
+            hash = hash ^ ((int)((uint)hash >> 7)) ^ ((int)((uint)hash >> 4));
+            return hash;
+        }
+
+        // public static boolean equals(CharSequence label, CharBlockArray array,
+        // int offset) {
+        // // CONTINUE HERE
+        // int len = label.length();
+        // int bi = array.blockIndex(offset);
+        // CharBlockArray.Block b = array.blocks.get(bi);
+        // int index = array.indexInBlock(offset);
+        //
+        // for (int i = 0; i < len; i++) {
+        // if (label.charAt(i) != b.chars[index]) {
+        // return false;
+        // }
+        // index++;
+        // if (index == b.length) {
+        // b = array.blocks.get(++bi);
+        // index = 0;
+        // }
+        // }
+        //
+        // return b.chars[index] == TerminatorChar;
+        // }
+
+        /// <summary>
+        /// Returns an estimate of the amount of memory used by this table. Called only in
+        /// this package. Memory is consumed mainly by three structures: the hash arrays,
+        /// label repository and collision map.
+        /// </summary>
+        internal virtual int MemoryUsage
+        {
+            get
+            {
+                int memoryUsage = 0;
+                if (this.hashArrays != null)
+                {
+                    // HashArray capacity is instance-specific.
+                    foreach (HashArray ha in this.hashArrays)
+                    {
+                        // Each has 2 capacity-length arrays of ints.
+                        memoryUsage += (ha.capacity * 2 * 4) + 4;
+                    }
+                }
+                if (this.labelRepository != null)
+                {
+                    // All blocks are the same size.
+                    int blockSize = this.labelRepository.blockSize;
+                    // Each block has room for blockSize UTF-16 chars.
+                    int actualBlockSize = (blockSize * 2) + 4;
+                    memoryUsage += this.labelRepository.blocks.Count * actualBlockSize;
+                    memoryUsage += 8; // Two int values for array as a whole.
+                }
+                if (this.collisionMap != null)
+                {
+                    memoryUsage += this.collisionMap.MemoryUsage;
+                }
+                return memoryUsage;
+            }
+        }
+
+        /// <summary>
+        /// Opens the file and reloads the CompactLabelToOrdinal. The file it expects
+        /// is generated from the <seealso cref="#flush(File)"/> command.
+        /// </summary>
+        internal static CompactLabelToOrdinal Open(string file, float loadFactor, int numHashArrays)
+        {
+            /// <summary>
+            /// Part of the file is the labelRepository, which needs to be rehashed
+            /// and label offsets re-added to the object. I am unsure as to why we
+            /// can't just store these off in the file as well, but in keeping with
+            /// the spirit of the original code, I did it this way. (ssuppe)
+            /// </summary>
+            CompactLabelToOrdinal l2o = new CompactLabelToOrdinal();
+            l2o.loadFactor = loadFactor;
+            l2o.hashArrays = new HashArray[numHashArrays];
+
+            BinaryReader dis = null;
+            try
+            {
+                dis = new BinaryReader(new FileStream(file,FileMode.Open,FileAccess.Read));
+
+                // TaxiReader needs to load the "counter" or occupancy (L2O) to know
+                // the next unique facet. we used to load the delimiter too, but
+                // never used it.
+                l2o.counter = dis.ReadInt32();
+
+                l2o.capacity = DetermineCapacity((int)Math.Pow(2, l2o.hashArrays.Length), l2o.counter);
+                l2o.Init();
+
+                // now read the chars
+                l2o.labelRepository = CharBlockArray.Open(dis);
+
+                l2o.collisionMap = new CollisionMap(l2o.labelRepository);
+
+                // Calculate hash on the fly based on how CategoryPath hashes
+                // itself. Maybe in the future we can call some static based methods
+                // in CategoryPath so that this doesn't break again? I don't like
+                // having code in two different places...
+                int cid = 0;
+                // Skip the initial offset, it's the CategoryPath(0,0), which isn't
+                // a hashed value.
+                int offset = 1;
+                int lastStartOffset = offset;
+                // This loop really relies on a well-formed input (assumes pretty blindly
+                // that array offsets will work).  Since the initial file is machine 
+                // generated, I think this should be OK.
+                while (offset < l2o.labelRepository.Length)
+                {
+                    // identical code to CategoryPath.hashFromSerialized. since we need to
+                    // advance offset, we cannot call the method directly. perhaps if we
+                    // could pass a mutable Integer or something...
+                    int length = (short)l2o.labelRepository.CharAt(offset++);
+                    int hash = length;
+                    if (length != 0)
+                    {
+                        for (int i = 0; i < length; i++)
+                        {
+                            int len = (short)l2o.labelRepository.CharAt(offset++);
+                            hash = hash * 31 + l2o.labelRepository.SubSequence(offset, offset + len).GetHashCode();
+                            offset += len;
+                        }
+                    }
+                    // Now that we've hashed the components of the label, do the
+                    // final part of the hash algorithm.
+                    hash = hash ^ (((int)((uint)hash >> 20)) ^ ((int)((uint)hash >> 12)));
+                    hash = hash ^ ((int)((uint)hash >> 7)) ^ ((int)((uint)hash >> 4));
+                    // Add the label, and let's keep going
+                    l2o.AddLabelOffset(hash, cid, lastStartOffset);
+                    cid++;
+                    lastStartOffset = offset;
+                }
+
+            }
+            catch (DllNotFoundException)
+            {
+                throw new IOException("Invalid file format. Cannot deserialize.");
+            }
+            finally
+            {
+                if (dis != null)
+                {
+                    dis.Dispose();
+                }
+            }
+
+            l2o.threshold = (int)(l2o.loadFactor * l2o.capacity);
+            return l2o;
+
+        }
+
+        internal virtual void Flush(Stream stream)
+        {
+
+            OutputStreamDataOutput dos = new OutputStreamDataOutput(stream);
+
+            try
+            {
+                dos.WriteInt(this.counter);
+
+                // write the labelRepository
+                this.labelRepository.Flush(dos);
+                // Closes the data output stream
+                dos.Dispose();
+
+            }
+            finally
+            {
+                dos.Dispose();
+            }
+        }
+
+        private sealed class HashArray
+        {
+            internal int[] offsets;
+            internal int[] cids;
+
+            internal int capacity;
+
+            internal HashArray(int c)
+            {
+                this.capacity = c;
+                this.offsets = new int[this.capacity];
+                this.cids = new int[this.capacity];
+            }
+        }
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/LabelToOrdinal.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/LabelToOrdinal.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/LabelToOrdinal.cs
new file mode 100644
index 0000000..495aa9b
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/LabelToOrdinal.cs
@@ -0,0 +1,83 @@
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+	/*
+	 * Licensed to the Apache Software Foundation (ASF) under one or more
+	 * contributor license agreements.  See the NOTICE file distributed with
+	 * this work for additional information regarding copyright ownership.
+	 * The ASF licenses this file to You under the Apache License, Version 2.0
+	 * (the "License"); you may not use this file except in compliance with
+	 * the License.  You may obtain a copy of the License at
+	 *
+	 *     http://www.apache.org/licenses/LICENSE-2.0
+	 *
+	 * Unless required by applicable law or agreed to in writing, software
+	 * distributed under the License is distributed on an "AS IS" BASIS,
+	 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+	 * See the License for the specific language governing permissions and
+	 * limitations under the License.
+	 */
+
+	/// <summary>
+	/// Abstract class for storing Label->Ordinal mappings in a taxonomy. 
+	/// 
+	/// @lucene.experimental
+	/// </summary>
+	public abstract class LabelToOrdinal
+	{
+
+	  /// <summary>
+	  /// How many ordinals we've seen. </summary>
+	  protected internal int counter;
+
+	  /// <summary>
+	  /// Returned by <seealso cref="#getOrdinal"/> when the label isn't
+	  ///  recognized. 
+	  /// </summary>
+	  public const int INVALID_ORDINAL = -2;
+
+	  /// <summary>
+	  /// Default constructor. </summary>
+	  public LabelToOrdinal()
+	  {
+	  }
+
+	  /// <summary>
+	  /// return the maximal Ordinal assigned so far
+	  /// </summary>
+	  public virtual int MaxOrdinal
+	  {
+		  get
+		  {
+			return this.counter;
+		  }
+	  }
+
+	  /// <summary>
+	  /// Returns the next unassigned ordinal. The default behavior of this method
+	  /// is to simply increment a counter.
+	  /// </summary>
+	  public virtual int NextOrdinal
+	  {
+		  get
+		  {
+			return this.counter++;
+		  }
+	  }
+
+	  /// <summary>
+	  /// Adds a new label if its not yet in the table.
+	  /// Throws an <seealso cref="IllegalArgumentException"/> if the same label with
+	  /// a different ordinal was previoulsy added to this table.
+	  /// </summary>
+	  public abstract void AddLabel(FacetLabel label, int ordinal);
+
+	  /// <summary>
+	  /// Returns the ordinal assigned to the given label, 
+	  /// or <seealso cref="#INVALID_ORDINAL"/> if the label cannot be found in this table.
+	  /// </summary>
+	  public abstract int GetOrdinal(FacetLabel label);
+
+	}
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/LruTaxonomyWriterCache.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/LruTaxonomyWriterCache.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/LruTaxonomyWriterCache.cs
new file mode 100644
index 0000000..74bf396
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/LruTaxonomyWriterCache.cs
@@ -0,0 +1,149 @@
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// LRU <seealso cref="TaxonomyWriterCache"/> - good choice for huge taxonomies.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    public class LruTaxonomyWriterCache : TaxonomyWriterCache
+    {
+
+        /// <summary>
+        /// Determines cache type.
+        /// For guaranteed correctness - not relying on no-collisions in the hash
+        /// function, LRU_STRING should be used.
+        /// </summary>
+        public enum LRUType
+        {
+            /// <summary>
+            /// Use the label's hash as the key; this can lead to
+            ///  silent conflicts! 
+            /// </summary>
+            LRU_HASHED,
+
+            /// <summary>
+            /// Use the label as the hash key; this is always
+            ///  correct but will usually use more RAM. 
+            /// </summary>
+            LRU_STRING
+        }
+
+        private NameIntCacheLRU cache;
+
+        /// <summary>
+        /// Creates this with <seealso cref="LRUType#LRU_HASHED"/> method. </summary>
+        public LruTaxonomyWriterCache(int cacheSize)
+            : this(cacheSize, LRUType.LRU_HASHED)
+        {
+            // TODO (Facet): choose between NameHashIntCacheLRU and NameIntCacheLRU.
+            // For guaranteed correctness - not relying on no-collisions in the hash
+            // function, NameIntCacheLRU should be used:
+            // On the other hand, NameHashIntCacheLRU takes less RAM but if there
+            // are collisions (which we never found) two different paths would be
+            // mapped to the same ordinal...
+        }
+
+        /// <summary>
+        /// Creates this with the specified method. </summary>
+        public LruTaxonomyWriterCache(int cacheSize, LRUType lruType)
+        {
+            // TODO (Facet): choose between NameHashIntCacheLRU and NameIntCacheLRU.
+            // For guaranteed correctness - not relying on no-collisions in the hash
+            // function, NameIntCacheLRU should be used:
+            // On the other hand, NameHashIntCacheLRU takes less RAM but if there
+            // are collisions (which we never found) two different paths would be
+            // mapped to the same ordinal...
+            if (lruType == LRUType.LRU_HASHED)
+            {
+                this.cache = new NameHashIntCacheLRU(cacheSize);
+            }
+            else
+            {
+                this.cache = new NameIntCacheLRU(cacheSize);
+            }
+        }
+
+        public virtual bool Full
+        {
+            get
+            {
+                lock (this)
+                {
+                    return cache.Size == cache.MaxSize;
+                }
+            }
+        }
+
+        public virtual void Clear()
+        {
+            lock (this)
+            {
+                cache.Clear();
+            }
+        }
+
+        public virtual void Close()
+        {
+            lock (this)
+            {
+                cache.Clear();
+                cache = null;
+            }
+        }
+
+        public virtual int Get(FacetLabel categoryPath)
+        {
+            lock (this)
+            {
+                int? res = cache.Get(categoryPath);
+                if (res == null)
+                {
+                    return -1;
+                }
+
+                return (int)res;
+            }
+        }
+
+        public virtual bool Put(FacetLabel categoryPath, int ordinal)
+        {
+            lock (this)
+            {
+                bool ret = cache.Put(categoryPath, new int?(ordinal));
+                // If the cache is full, we need to clear one or more old entries
+                // from the cache. However, if we delete from the cache a recent
+                // addition that isn't yet in our reader, for this entry to be
+                // visible to us we need to make sure that the changes have been
+                // committed and we reopen the reader. Because this is a slow
+                // operation, we don't delete entries one-by-one but rather in bulk
+                // (put() removes the 2/3rd oldest entries).
+                if (ret)
+                {
+                    cache.MakeRoomLRU();
+                }
+                return ret;
+            }
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/NameHashIntCacheLRU.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/NameHashIntCacheLRU.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/NameHashIntCacheLRU.cs
new file mode 100644
index 0000000..cf135ea
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/NameHashIntCacheLRU.cs
@@ -0,0 +1,49 @@
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+	/*
+	 * Licensed to the Apache Software Foundation (ASF) under one or more
+	 * contributor license agreements.  See the NOTICE file distributed with
+	 * this work for additional information regarding copyright ownership.
+	 * The ASF licenses this file to You under the Apache License, Version 2.0
+	 * (the "License"); you may not use this file except in compliance with
+	 * the License.  You may obtain a copy of the License at
+	 *
+	 *     http://www.apache.org/licenses/LICENSE-2.0
+	 *
+	 * Unless required by applicable law or agreed to in writing, software
+	 * distributed under the License is distributed on an "AS IS" BASIS,
+	 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+	 * See the License for the specific language governing permissions and
+	 * limitations under the License.
+	 */
+
+	/// <summary>
+	/// An an LRU cache of mapping from name to int.
+	/// Used to cache Ordinals of category paths.
+	/// It uses as key, hash of the path instead of the path.
+	/// This way the cache takes less RAM, but correctness depends on
+	/// assuming no collisions. 
+	/// 
+	/// @lucene.experimental
+	/// </summary>
+	public class NameHashIntCacheLRU : NameIntCacheLRU
+	{
+
+	  internal NameHashIntCacheLRU(int maxCacheSize) : base(maxCacheSize)
+	  {
+	  }
+
+	  internal override object Key(FacetLabel name)
+	  {
+		return new long?(name.LongHashCode());
+	  }
+
+	  internal override object Key(FacetLabel name, int prefixLen)
+	  {
+		return new long?(name.Subpath(prefixLen).LongHashCode());
+	  }
+
+	}
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs
new file mode 100644
index 0000000..cd01527
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs
@@ -0,0 +1,167 @@
+using System.Collections.Generic;
+
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// An an LRU cache of mapping from name to int.
+    /// Used to cache Ordinals of category paths.
+    /// 
+    /// @lucene.experimental
+    /// </summary>
+    // Note: Nothing in this class is synchronized. The caller is assumed to be
+    // synchronized so that no two methods of this class are called concurrently.
+    public class NameIntCacheLRU
+    {
+
+        private Dictionary<object, int?> cache;
+        internal long nMisses = 0; // for debug
+        internal long nHits = 0; // for debug
+        private int maxCacheSize;
+
+        internal NameIntCacheLRU(int maxCacheSize)
+        {
+            this.maxCacheSize = maxCacheSize;
+            CreateCache(maxCacheSize);
+        }
+
+        /// <summary>
+        /// Maximum number of cache entries before eviction. </summary>
+        public virtual int MaxSize
+        {
+            get
+            {
+                return maxCacheSize;
+            }
+        }
+
+        /// <summary>
+        /// Number of entries currently in the cache. </summary>
+        public virtual int Size
+        {
+            get
+            {
+                return cache.Count;
+            }
+        }
+
+        private void CreateCache(int maxSize)
+	  {
+        //if (maxSize < int.MaxValue)
+        //{
+        //    cache = new LRUHashMap<object,int?>(1000,true); //for LRU
+        //}
+        //else
+		{
+		  cache = new Dictionary<object, int?>(1000); //no need for LRU
+		}
+	  }
+
+        internal virtual int? Get(FacetLabel name)
+        {
+            int? res = cache[Key(name)];
+            if (res == null)
+            {
+                nMisses++;
+            }
+            else
+            {
+                nHits++;
+            }
+            return res;
+        }
+
+        /// <summary>
+        /// Subclasses can override this to provide caching by e.g. hash of the string. </summary>
+        internal virtual object Key(FacetLabel name)
+        {
+            return name;
+        }
+
+        internal virtual object Key(FacetLabel name, int prefixLen)
+        {
+            return name.Subpath(prefixLen);
+        }
+
+        /// <summary>
+        /// Add a new value to cache.
+        /// Return true if cache became full and some room need to be made. 
+        /// </summary>
+        internal virtual bool Put(FacetLabel name, int? val)
+        {
+            cache[Key(name)] = val;
+            return CacheFull;
+        }
+
+        internal virtual bool Put(FacetLabel name, int prefixLen, int? val)
+        {
+            cache[Key(name, prefixLen)] = val;
+            return CacheFull;
+        }
+
+        private bool CacheFull
+        {
+            get
+            {
+                return cache.Count > maxCacheSize;
+            }
+        }
+
+        internal virtual void Clear()
+        {
+            cache.Clear();
+        }
+
+        internal virtual string Stats()
+        {
+            return "#miss=" + nMisses + " #hit=" + nHits;
+        }
+
+        /// <summary>
+        /// If cache is full remove least recently used entries from cache. Return true
+        /// if anything was removed, false otherwise.
+        /// 
+        /// See comment in DirectoryTaxonomyWriter.addToCache(CategoryPath, int) for an
+        /// explanation why we clean 2/3rds of the cache, and not just one entry.
+        /// </summary>
+        internal virtual bool MakeRoomLRU()
+        {
+            if (!CacheFull)
+            {
+                return false;
+            }
+            int n = cache.Count - (2 * maxCacheSize) / 3;
+            if (n <= 0)
+            {
+                return false;
+            }
+            IEnumerator<object> it = cache.Keys.GetEnumerator();
+            int i = 0;
+            
+            while (i < n && it.MoveNext())
+            {
+                cache.Remove(it.Current);
+                i++;
+            }
+            return true;
+        }
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/Taxonomy/WriterCache/TaxonomyWriterCache.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/Taxonomy/WriterCache/TaxonomyWriterCache.cs b/Lucene.Net.Facet/Taxonomy/WriterCache/TaxonomyWriterCache.cs
new file mode 100644
index 0000000..a20dcd6
--- /dev/null
+++ b/Lucene.Net.Facet/Taxonomy/WriterCache/TaxonomyWriterCache.cs
@@ -0,0 +1,105 @@
+namespace Lucene.Net.Facet.Taxonomy.WriterCache
+{
+
+    using DirectoryTaxonomyWriter = Lucene.Net.Facet.Taxonomy.Directory.DirectoryTaxonomyWriter;
+
+    /*
+     * Licensed to the Apache Software Foundation (ASF) under one or more
+     * contributor license agreements.  See the NOTICE file distributed with
+     * this work for additional information regarding copyright ownership.
+     * The ASF licenses this file to You under the Apache License, Version 2.0
+     * (the "License"); you may not use this file except in compliance with
+     * the License.  You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     * See the License for the specific language governing permissions and
+     * limitations under the License.
+     */
+
+    /// <summary>
+    /// TaxonomyWriterCache is a relatively simple interface for a cache of
+    /// category->ordinal mappings, used in TaxonomyWriter implementations (such as
+    /// <seealso cref="DirectoryTaxonomyWriter"/>).
+    /// <para>
+    /// It basically has put() methods for adding a mapping, and get() for looking a
+    /// mapping up the cache. The cache does <B>not</B> guarantee to hold everything
+    /// that has been put into it, and might in fact selectively delete some of the
+    /// mappings (e.g., the ones least recently used). This means that if get()
+    /// returns a negative response, it does not necessarily mean that the category
+    /// doesn't exist - just that it is not in the cache. The caller can only infer
+    /// that the category doesn't exist if it knows the cache to be complete (because
+    /// all the categories were loaded into the cache, and since then no put()
+    /// returned true).
+    /// </para>
+    /// <para>
+    /// However, if it does so, it should clear out large parts of the cache at once,
+    /// because the user will typically need to work hard to recover from every cache
+    /// cleanup (see <seealso cref="#put(FacetLabel, int)"/>'s return value).
+    /// </para>
+    /// <para>
+    /// <b>NOTE:</b> the cache may be accessed concurrently by multiple threads,
+    /// therefore cache implementations should take this into consideration.
+    /// 
+    /// @lucene.experimental
+    /// </para>
+    /// </summary>
+    public interface TaxonomyWriterCache
+    {
+
+        /// <summary>
+        /// Let go of whatever resources the cache is holding. After a close(),
+        /// this object can no longer be used.
+        /// </summary>
+        void Close();
+
+        /// <summary>
+        /// Lookup a category in the cache, returning its ordinal, or a negative
+        /// number if the category is not in the cache.
+        /// <P>
+        /// It is up to the caller to remember what a negative response means:
+        /// If the caller knows the cache is <I>complete</I> (it was initially
+        /// fed with all the categories, and since then put() never returned true)
+        /// it means the category does not exist. Otherwise, the category might
+        /// still exist, but just be missing from the cache.
+        /// </summary>
+        int Get(FacetLabel categoryPath);
+
+        /// <summary>
+        /// Add a category to the cache, with the given ordinal as the value.
+        /// <P>
+        /// If the implementation keeps only a partial cache (e.g., an LRU cache)
+        /// and finds that its cache is full, it should clear up part of the cache
+        /// and return <code>true</code>. Otherwise, it should return
+        /// <code>false</code>.
+        /// <P>
+        /// The reason why the caller needs to know if part of the cache was
+        /// cleared is that in that case it will have to commit its on-disk index
+        /// (so that all the latest category additions can be searched on disk, if
+        /// we can't rely on the cache to contain them).
+        /// <P>
+        /// Ordinals should be non-negative. Currently there is no defined way to
+        /// specify that a cache should remember a category does NOT exist.
+        /// It doesn't really matter, because normally the next thing we do after
+        /// finding that a category does not exist is to add it.
+        /// </summary>
+        bool Put(FacetLabel categoryPath, int ordinal);
+
+        /// <summary>
+        /// Returns true if the cache is full, such that the next <seealso cref="#put"/> will
+        /// evict entries from it, false otherwise.
+        /// </summary>
+        bool Full { get; }
+
+        /// <summary>
+        /// Clears the content of the cache. Unlike <seealso cref="#close()"/>, the caller can
+        /// assume that the cache is still operable after this method returns.
+        /// </summary>
+        void Clear();
+
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/982eaf60/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
----------------------------------------------------------------------
diff --git a/Lucene.Net.Facet/TopOrdAndFloatQueue.cs b/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
new file mode 100644
index 0000000..6430624
--- /dev/null
+++ b/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
@@ -0,0 +1,73 @@
+namespace Lucene.Net.Facet
+{
+
+	/*
+	 * Licensed to the Apache Software Foundation (ASF) under one or more
+	 * contributor license agreements.  See the NOTICE file distributed with
+	 * this work for additional information regarding copyright ownership.
+	 * The ASF licenses this file to You under the Apache License, Version 2.0
+	 * (the "License"); you may not use this file except in compliance with
+	 * the License.  You may obtain a copy of the License at
+	 *
+	 *     http://www.apache.org/licenses/LICENSE-2.0
+	 *
+	 * Unless required by applicable law or agreed to in writing, software
+	 * distributed under the License is distributed on an "AS IS" BASIS,
+	 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+	 * See the License for the specific language governing permissions and
+	 * limitations under the License.
+	 */
+
+    using Lucene.Net.Util;
+
+	/// <summary>
+	/// Keeps highest results, first by largest float value,
+	///  then tie break by smallest ord. 
+	/// </summary>
+	public class TopOrdAndFloatQueue : PriorityQueue<TopOrdAndFloatQueue.OrdAndValue>
+	{
+
+	  /// <summary>
+	  /// Holds a single entry. </summary>
+	  public sealed class OrdAndValue
+	  {
+
+		/// <summary>
+		/// Ordinal of the entry. </summary>
+		public int ord;
+
+		/// <summary>
+		/// Value associated with the ordinal. </summary>
+		public float value;
+
+		/// <summary>
+		/// Default constructor. </summary>
+		public OrdAndValue()
+		{
+		}
+	  }
+
+	  /// <summary>
+	  /// Sole constructor. </summary>
+	  public TopOrdAndFloatQueue(int topN) : base(topN, false)
+	  {
+	  }
+
+	  public override bool LessThan(OrdAndValue a, OrdAndValue b)
+	  {
+		if (a.value < b.value)
+		{
+		  return true;
+		}
+		else if (a.value > b.value)
+		{
+		  return false;
+		}
+		else
+		{
+		  return a.ord > b.ord;
+		}
+	  }
+	}
+
+}
\ No newline at end of file


Mime
View raw message