foray-commit Mailing List for FOray (Page 71)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Revision: 12127
          http://sourceforge.net/p/foray/code/12127
Author:   victormote
Date:     2021-11-24 14:01:19 +0000 (Wed, 24 Nov 2021)
Log Message:
-----------
Allow TernaryTree and related classes to specify an initial capacity so that the correct data structure for the nodes can be selected the first time.

Modified Paths:
--------------
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
    trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java
    trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java
    trunk/foray/foray-fotree/src/main/java/org/foray/fotree/PropertyType.java
    trunk/foray/foray-orthography/src/main/java/org/foray/orthography/SegmentDictionary.java
    trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParser.java
    trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParserText.java
    trunk/foray/foray-orthography/src/test/java/org/foray/orthography/SegmentDictionaryTests.java

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java
===================================================================

--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryNodesChar.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -41,6 +41,9 @@
  */
 public class TernaryNodesChar extends TernaryNodes {
 
+    /** The maximum number of nodes that can be stored. */
+    public static final int MAX_NODES = 65_536;
+
     /** Constant needed for serialization. */
     private static final long serialVersionUID = 6351290262839607022L;
 

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTree.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -120,13 +120,27 @@
 
     /**
      * Constructor.
+     * @param initialCapacity The number of nodes expected to be used by this tree.
+     * Note that the number of nodes is not the same as (is usually greater than) the number of key-value pairs.
      */
-    public TernaryTree() {
-        this.nodes = new TernaryNodesChar();
+    public TernaryTree(final int initialCapacity) {
+        if (initialCapacity > TernaryNodesChar.MAX_NODES) {
+            this.nodes = new TernaryNodesInt();
+        } else {
+            this.nodes = new TernaryNodesChar();
+        }
         init();
     }
 
     /**
+     * Constructor which assumes that the number of nodes will not exceed {@link TernaryNodesChar#MAX_NODES}.
+     * @see TernaryTree#TernaryTree(int)
+     */
+    public TernaryTree() {
+        this(-1);
+    }
+
+    /**
      * Private constructor used during cloning.
      * @param nodes The data structure containing the branch indexes.
      */

Modified: trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java
===================================================================
--- trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-common/src/main/java/org/foray/common/data/TernaryTreeMap.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -53,10 +53,16 @@
     /** The values stored in this map. */
     private List<V> values;
 
+    /** The number of nodes expected to be added to this map. */
+    private int initialCapacity;
+
     /**
      * Constructor.
+     * @param initialCapacity The number of nodes expected to be added to this map.
      */
-    public TernaryTreeMap() {
+    public TernaryTreeMap(final int initialCapacity) {
+        /* Cache this in case we need to access it for clear(). */
+        this.initialCapacity = initialCapacity;
         init();
     }
 
@@ -64,7 +70,11 @@
      * Initialize or clear the map data.
      */
     private void init() {
-        this.keys = new TernaryTree();
+        /* There is no good way to estimate the number of nodes in the ternary tree that will be needed to store a
+         * certain number of key-value pairs. If we estimate too high, we may waste some memory. If we estimate too
+         * low, we may waste some time as the tree resizes itself. */
+        final int estimatedQtyTernaryNodes = this.initialCapacity * 3;
+        this.keys = new TernaryTree(estimatedQtyTernaryNodes);
         this.values = new ArrayList<V>();
     }
 

Modified: trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java
===================================================================
--- trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-common/src/test/java/org/foray/common/data/TernaryTreeMapTests.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -49,7 +49,7 @@
      */
     @Before
     public void setUp() {
-        this.out = new TernaryTreeMap<String>();
+        this.out = new TernaryTreeMap<String>(1000);
         Assert.assertTrue(this.out.isEmpty());
         this.out.put("Key 1", "Value 1");
         this.out.put("Key 2", "Value 2");

Modified: trunk/foray/foray-fotree/src/main/java/org/foray/fotree/PropertyType.java
===================================================================
--- trunk/foray/foray-fotree/src/main/java/org/foray/fotree/PropertyType.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-fotree/src/main/java/org/foray/fotree/PropertyType.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -30,6 +30,7 @@
 
 /**
  * Common interface for all enumerated property classes.
+ * Use of this interface allows the enumerated property types from different namespaces to have a common parent.
  */
 public interface PropertyType {
 

Modified: trunk/foray/foray-orthography/src/main/java/org/foray/orthography/SegmentDictionary.java
===================================================================
--- trunk/foray/foray-orthography/src/main/java/org/foray/orthography/SegmentDictionary.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-orthography/src/main/java/org/foray/orthography/SegmentDictionary.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -49,11 +49,8 @@
     /** Constant needed for serialization. */
     private static final long serialVersionUID = -8752423281137349847L;
 
-    /** The data structure containing the dictionary words.
-     * TODO: More work needs to be done to determine which Map implementation should be used here.
-     * The TernaryTreeMap currently uses approximately 50% more memory, but has not been optimized for memory use.
-     * The other tradeoff axis is speed, and we are not sure which implementation is faster. */
-    private Map<CharSequence, SegmentDictionaryWord> wordMap = new TernaryTreeMap<SegmentDictionaryWord>();
+    /** The data structure containing the dictionary words. */
+    private Map<CharSequence, SegmentDictionaryWord> wordMap;
 
     /** Map of the ambiguous words. These are expected to be few, so we worry less about memory and performance. */
     private Map<CharSequence, AmbiguousWord<SegmentDictionaryWord>> ambiguousWordMap =
@@ -65,8 +62,10 @@
     /**
      * Constructor.
      * @param uniqueWordSegments The array of word segments that can be used by words in this dictionary.
+     * @param initialCapacity The number of words that are expected to be added to this dictionary.
+     * This will give the dictionary a clue about how best to balance memory and performance issues.
      */
-    public SegmentDictionary(final StringWordSegment[] uniqueWordSegments) {
+    public SegmentDictionary(final StringWordSegment[] uniqueWordSegments, final int initialCapacity) {
         if (uniqueWordSegments.length > Character.MAX_VALUE + 1) {
             throw new IllegalArgumentException("Size of segments: " + uniqueWordSegments.length +
                     " exceeds capacity: " + (Character.MAX_VALUE + 1));
@@ -73,6 +72,11 @@
         }
         Arrays.sort(uniqueWordSegments);
         this.wordSegments = uniqueWordSegments;
+
+        /* TODO: More work needs to be done to determine which Map implementation should be used here.
+         * The TernaryTreeMap currently uses approximately 50% more memory, but has not been optimized for memory use.
+         * The other tradeoff axis is speed, and we are not sure which implementation is faster.*/
+        this.wordMap = new TernaryTreeMap<SegmentDictionaryWord>(initialCapacity);
     }
 
     /**
@@ -132,7 +136,7 @@
         }
         final StringWordSegmentUtf16[] segmentArray = new StringWordSegmentUtf16[segments.size()];
         segments.toArray(segmentArray);
-        final SegmentDictionary dictionary = new SegmentDictionary(segmentArray);
+        final SegmentDictionary dictionary = new SegmentDictionary(segmentArray, stringWords.size());
 
         for (int index = 0; index < stringWords.size(); index ++) {
             final StringWord stringWord = stringWords.get(index);

Modified: trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParser.java
===================================================================
--- trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParser.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParser.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -150,7 +150,7 @@
         final StringWordSegment[] uniqueWordSegments = new StringWordSegment[segmentSet.size()];
         segmentSet.toArray(uniqueWordSegments);
         Arrays.sort(uniqueWordSegments);
-        final SegmentDictionary dictionary = new SegmentDictionary(uniqueWordSegments);
+        final SegmentDictionary dictionary = new SegmentDictionary(uniqueWordSegments, this.wordMap.size());
 
         for (Map.Entry<String, StringWord> entry : this.wordMap.entrySet()) {
             dictionary.addWord(entry.getKey(), entry.getValue());

Modified: trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParserText.java
===================================================================
--- trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParserText.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-orthography/src/main/java/org/foray/orthography/util/DictionaryParserText.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -158,7 +158,7 @@
         final StringWordSegment[] uniqueWordSegments = new StringWordSegment[segmentSet.size()];
         segmentSet.toArray(uniqueWordSegments);
         Arrays.sort(uniqueWordSegments);
-        final SegmentDictionary dictionary = new SegmentDictionary(uniqueWordSegments);
+        final SegmentDictionary dictionary = new SegmentDictionary(uniqueWordSegments, wordMap.size());
         for (Map.Entry<String, StringWord> entry : wordMap.entrySet()) {
             dictionary.addWord(entry.getKey(), entry.getValue());
         }

Modified: trunk/foray/foray-orthography/src/test/java/org/foray/orthography/SegmentDictionaryTests.java
===================================================================
--- trunk/foray/foray-orthography/src/test/java/org/foray/orthography/SegmentDictionaryTests.java	2021-11-24 12:32:34 UTC (rev 12126)
+++ trunk/foray/foray-orthography/src/test/java/org/foray/orthography/SegmentDictionaryTests.java	2021-11-24 14:01:19 UTC (rev 12127)
@@ -92,7 +92,7 @@
          * */
         Assert.assertEquals(8, segmentsArray.length);
 
-        out = new SegmentDictionary(segmentsArray);
+        out = new SegmentDictionary(segmentsArray, 1000);
         out.addWord(WORD_ATTENTION.getActualContent().toString(), WORD_ATTENTION);
         out.addWord(WORD_INTENTION.getActualContent().toString(), WORD_INTENTION);
         out.addWord(WORD_AMBITION.getActualContent().toString(), WORD_AMBITION);

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.





2006	Jan	Feb	Mar (139)	Apr (98)	May (250)	Jun (394)	Jul (84)	Aug (13)	Sep (420)	Oct (186)	Nov (1)	Dec (3)
2007	Jan (108)	Feb (202)	Mar (291)	Apr (247)	May (374)	Jun (227)	Jul (231)	Aug (60)	Sep (31)	Oct (45)	Nov (18)	Dec
2008	Jan (38)	Feb (71)	Mar (142)	Apr	May (59)	Jun (6)	Jul (10)	Aug	Sep	Oct	Nov	Dec
2009	Jan (12)	Feb (4)	Mar (88)	Apr (121)	May (17)	Jun (30)	Jul	Aug (5)	Sep	Oct (1)	Nov	Dec
2010	Jan (11)	Feb (76)	Mar (11)	Apr	May (11)	Jun	Jul	Aug (44)	Sep (14)	Oct (7)	Nov	Dec
2011	Jan	Feb	Mar	Apr	May (9)	Jun	Jul	Aug	Sep	Oct (10)	Nov	Dec
2012	Jan	Feb	Mar	Apr	May	Jun (3)	Jul (4)	Aug	Sep	Oct	Nov	Dec
2016	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec (168)
2017	Jan (77)	Feb (11)	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2018	Jan	Feb	Mar (1)	Apr (6)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2019	Jan	Feb (88)	Mar (118)	Apr (1)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2020	Jan	Feb	Mar	Apr	May (6)	Jun	Jul	Aug	Sep	Oct	Nov	Dec (141)
2021	Jan (170)	Feb (20)	Mar	Apr	May	Jun	Jul (1)	Aug	Sep	Oct (62)	Nov (189)	Dec (162)
2022	Jan (201)	Feb (118)	Mar (8)	Apr	May (2)	Jun (47)	Jul (19)	Aug (14)	Sep (3)	Oct	Nov (28)	Dec (235)
2023	Jan (112)	Feb (23)	Mar (2)	Apr (2)	May	Jun (1)	Jul	Aug (70)	Sep (92)	Oct (20)	Nov (1)	Dec (1)
2024	Jan	Feb	Mar (1)	Apr (1)	May (14)	Jun (11)	Jul (1)	Aug	Sep	Oct	Nov	Dec
2025	Jan (10)	Feb (29)	Mar	Apr (162)	May (245)	Jun (83)	Jul	Aug (1)	Sep	Oct	Nov (4)	Dec

foray-commit Mailing List for FOray (Page 71)

Modular XSL-FO Implementation for Java.

foray-commit — FOray repository commit log messages