ConcurrentInvertedRadixTree

ConcurrentInvertedRadixTree is a radix tree, in addition to functionalities supported by Radix tree; you can also search for all the keys in given string.

Applications

1.   You can find a word in proportional time to the size of the word.

2.   Used for prefix matching: If you want to find all the words where prefix is “st”, you can get {stock, stop…} etc.

3.   You can find keywords in external documents.

import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;

public class ConcurrentInvertedRadixTreeEx {

    public static void main(String args[]) {
        InvertedRadixTree<Integer> tree = new ConcurrentInvertedRadixTree<Integer>(new DefaultCharArrayNodeFactory());

        tree.put("stock", new Integer(1));
        tree.put("bear", new Integer(2));
        tree.put("bid", new Integer(3));
        tree.put("bell", new Integer(4));
        tree.put("buy", new Integer(5));
        tree.put("bull", new Integer(6));
        tree.put("sell", new Integer(7));
        tree.put("stop", new Integer(8));
        tree.put("beap", new Integer(9));

        System.out.println("Tree structure:");
        PrettyPrinter.prettyPrint((PrettyPrintable) tree, System.out);

        System.out.println();
        System.out.println("Value for 'bid' (exact match): " + tree.getValueForExactKey("bid"));
        System.out.println("Value for 'sell' (exact match): " + tree.getValueForExactKey("sell"));
        System.out.println();
        System.out.println("Keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getKeysContainedIn("i am going to buy and sell stocks today")));
        System.out.println("Keys contained in 'buyers and sellers are outside': " + Iterables.toString(tree.getKeysContainedIn("buyers and sellers are outside")));
        System.out.println("Values for keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getValuesForKeysContainedIn("i am going to buy and sell stocks today")));
        System.out.println("Key-value pairs for keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getKeyValuePairsForKeysContainedIn("i am going to buy and sell stocks today")));

    }
}

Output

Tree structure:
○
├── ○ b
│   ├── ○ e
│   │   ├── ○ a
│   │   │   ├── ○ p (9)
│   │   │   └── ○ r (2)
│   │   └── ○ ll (4)
│   ├── ○ id (3)
│   └── ○ u
│       ├── ○ ll (6)
│       └── ○ y (5)
└── ○ s
    ├── ○ ell (7)
    └── ○ to
        ├── ○ ck (1)
        └── ○ p (8)

Value for 'bid' (exact match): 3
Value for 'sell' (exact match): 7

Keys contained in 'i am going to buy and sell stocks today': [buy, sell, stock]
Keys contained in 'buyers and sellers are outside': [buy, sell]
Values for keys contained in 'i am going to buy and sell stocks today': [5, 7, 1]
Key-value pairs for keys contained in 'i am going to buy and sell stocks today': [(buy, 5), (sell, 7), (stock, 1)]

If you want to add keys without any value, you can use “VoidValue.SINGLETON”.

import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.concrete.voidvalue.VoidValue;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;

public class ConcurrentInvertedRadixTreeEx {

    public static void main(String args[]) {
        InvertedRadixTree<VoidValue> tree = new ConcurrentInvertedRadixTree<VoidValue>(new DefaultCharArrayNodeFactory());

        tree.put("stock", VoidValue.SINGLETON);
        tree.put("bear", VoidValue.SINGLETON);
        tree.put("bid", VoidValue.SINGLETON);
        tree.put("bell", VoidValue.SINGLETON);
        tree.put("buy", VoidValue.SINGLETON);
        tree.put("bull", VoidValue.SINGLETON);
        tree.put("sell", VoidValue.SINGLETON);
        tree.put("stop", VoidValue.SINGLETON);
        tree.put("beap", VoidValue.SINGLETON);

        System.out.println("Tree structure:");
        PrettyPrinter.prettyPrint((PrettyPrintable) tree, System.out);

        System.out.println();
        System.out.println("Value for 'bid' (exact match): " + tree.getValueForExactKey("bid"));
        System.out.println("Value for 'sell' (exact match): " + tree.getValueForExactKey("sell"));
        System.out.println();
        System.out.println("Keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getKeysContainedIn("i am going to buy and sell stocks today")));
        System.out.println("Keys contained in 'buyers and sellers are outside': " + Iterables.toString(tree.getKeysContainedIn("buyers and sellers are outside")));
        System.out.println("Values for keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getValuesForKeysContainedIn("i am going to buy and sell stocks today")));
        System.out.println("Key-value pairs for keys contained in 'i am going to buy and sell stocks today': " + Iterables.toString(tree.getKeyValuePairsForKeysContainedIn("i am going to buy and sell stocks today")));

    }
}

Output

Tree structure:
○
├── ○ b
│   ├── ○ e
│   │   ├── ○ a
│   │   │   ├── ○ p (-)
│   │   │   └── ○ r (-)
│   │   └── ○ ll (-)
│   ├── ○ id (-)
│   └── ○ u
│       ├── ○ ll (-)
│       └── ○ y (-)
└── ○ s
    ├── ○ ell (-)
    └── ○ to
        ├── ○ ck (-)
        └── ○ p (-)

Value for 'bid' (exact match): -
Value for 'sell' (exact match): -

Keys contained in 'i am going to buy and sell stocks today': [buy, sell, stock]
Keys contained in 'buyers and sellers are outside': [buy, sell]
Values for keys contained in 'i am going to buy and sell stocks today': [-, -, -]
Key-value pairs for keys contained in 'i am going to buy and sell stocks today': [(buy, -), (sell, -), (stock, -)]

Prevoius                                                 Next                                                 Home