StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'd like to thank all of you for the effort you put in answering my question, they all were very useful and taking the best from each of them made me come up to the solution I actually implemented in my project.</p> <hr> <p>What I beleive to be best answers to my single questions are:</p> <p>2) There is not an Iterator defined on TreeMaps as @Isoliveira sais:</p> <pre><code>There's no such implementation in the JDK itself. Although TreeMap iterates in natural key ordering, its internal data structures are all based on trees and not arrays (remember that Maps do not order keys, by definition, in spite of that the very common use case). </code></pre> <p>and as I found in this SO answer <a href="https://stackoverflow.com/questions/1318980/how-to-iterate-over-a-treemap">How to iterate over a TreeMap?</a>, the only way to iterate on elements in a <code>Map</code> is to use <code>map.entrySet()</code> and use Iterators defined on <code>Set</code> (or some other class with Iterators).</p> <hr> <p>3) It's possible to use a <code>TreeMap</code> to implement Dictionary, but this will garantuee a complexity of O(logN) in finding index of a contained word (cost of a lookup in a Tree Data Structure). </p> <p>Using a <code>HashMap</code> with same procedure will instead have complexity O(1).</p> <hr> <p>1) There exists no such method. Only solution is to implement it entirely.</p> <p>As @Paul stated </p> <pre><code>Assumes that once getPosition() has been called, the dictionary is not changed. </code></pre> <p>assumption of solution is that once that Dictionary is created it will not be changed afterwards: in this way position of a word will always be the same.</p> <p>Giving this assumption I found a solution that allows to build Dictionary with complexity O(N) and after garantuees the possibility to get index of a word contained with constat time O(1) in lookup.</p> <p>I defined Dictionary as a <code>HashMap</code> like this:</p> <pre><code>public HashMap<String, WordStruct> dictionary = new HashMap<String, WordStruct>(); </code></pre> <ul> <li>key --> the <code>String</code> representing the word contained in Dictionary</li> <li>value --> an <code>Object</code> of a created class <code>WordStruct</code></li> </ul> <p>where <code>WordStruct</code> class is defined like this:</p> <pre><code>public class WordStruct { private int DictionaryPosition; // defines the position of word in dictionary once it is alphabetically ordered public WordStruct(){ } public SetWordPosition(int pos){ this.DictionaryPosition = pos; } } </code></pre> <p>and allows me to keep memory of any kind of attribute I like to couple with the word entry of the Dictionary.</p> <p>Now I fill dictionary iterating over all words contained in all files of my collection:</p> <pre><code>THE FOLLOWING IS PSEUDOCODE for(int i = 0; i < number_of_files ; i++){ get_file(i); while (file_contais_words){ dictionary.put( word(j) , new LemmaStruct()); } } </code></pre> <p>Once HashMap is filled in whatever order I use procedure indicated by @dasblinkenlight to order it once and for all with complexity O(N)</p> <pre><code> Object[] dictionaryArray = dictionary.keySet().toArray(); Arrays.sort(dictionaryArray); for(int i = 0; i < dictionaryArray.length; i++){ String word = (String) dictionaryArray[i]; dictionary.get(word).SetWordPosition(i); } </code></pre> <p>And from now on to have index position in alphatebetic order of word in dictionary only thing needed is to acces it's variable <code>DictionaryPosition</code>:</p> <p>since word is know you just need to access it and this has constant cost in a <code>HashMap</code>.</p> <hr> <p>Thanks again and Iwish you all a Merry Christmas!!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload