adt.trie.TriePath

   1 /* Osm4j is a library that provides utilities to handle Openstreetmap data in java.
   2  *
   3  * Copyright (C) 2011  Sebastian Kuerten
   4  * 
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 3 of the License, or (at your option) any later version.
   9  * 
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  * 
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  */
  19 
  20 package adt.trie;
  21 
  22 import java.util.ArrayList;
  23 import java.util.List;
  24 
  25 class TriePath<T> {
  26 
  27     List<PathNode<T>> path;
  28 
  29     public TriePath(Node<T> root) {
  30         path = new ArrayList<PathNode<T>>();
  31         path.add(new PathNode<T>(root));
  32 
  33         while (!path.get(path.size() - 1).node.hasData) {
  34             PathNode<T> pathNode = path.get(path.size() - 1);
  35             pathNode.position = 0;
  36             if (pathNode.node.nodes.size() == 0)
  37                 break;
  38             Node<T> node = pathNode.node.nodes.get(0);
  39             path.add(new PathNode<T>(node));
  40             // System.out.println("ADD: " + node.word);
  41         }
  42     }
  43 
  44     public boolean hasNext() {
  45         while (true) {
  46             if (path.size() == 0)
  47                 return false;
  48             PathNode<T> pathNode = path.get(path.size() - 1);
  49             if (!pathNode.hasMore()) {
  50                 // System.out.println("REM: " + path.get(path.size() - 1).node.word);
  51                 path.remove(path.size() - 1);
  52             } else {
  53                 return true;
  54             }
  55         }
  56     }
  57 
  58     public TrieIterEntry<T> next() {
  59         if (!hasNext())
  60             return null;
  61         PathNode<T> pathNode = path.get(path.size() - 1);
  62         if (!pathNode.selfDone) {
  63             pathNode.selfDone = true;
  64             // System.out.println("RET0");
  65             // return new TrieIterEntry<T>(pathNode.node.word, null);
  66             return new TrieIterEntry<T>(buildPath(), null);
  67         }
  68         pathNode.position += 1;
  69         Node<T> nextNode = pathNode.node.nodes.get(pathNode.position);
  70         path.add(new PathNode<T>(nextNode));
  71         // System.out.println("ADD1: " + nextNode.word);
  72         pathNode = path.get(path.size() - 1);
  73 
  74         while (!path.get(path.size() - 1).node.hasData) {
  75             pathNode.position = 0;
  76             Node<T> node = pathNode.node.nodes.get(0);
  77             path.add(new PathNode<T>(node));
  78             // System.out.println("ADD2: " + node.word);
  79             pathNode = path.get(path.size() - 1);
  80         }
  81         // System.out.println("RET1");
  82         if (!pathNode.selfDone)
  83             pathNode.selfDone = true;
  84         // return new TrieIterEntry<T>(pathNode.node.word, null);
  85         return new TrieIterEntry<T>(buildPath(), null);
  86     }
  87 
  88     private String buildPath() {
  89         StringBuilder strb = new StringBuilder();
  90         for (int i = 0; i < path.size(); i++) {
  91             strb.append(path.get(i).node.word);
  92         }
  93         return strb.toString();
  94     }
  95 }