GUI: trie utility operations, and test code.
Change-Id: I7f41d84b880a8e2075cf1c983be9a4a2def01856
diff --git a/web/gui/src/main/webapp/_sdh/trie-test.html b/web/gui/src/main/webapp/_sdh/trie-test.html
new file mode 100644
index 0000000..2d6517a
--- /dev/null
+++ b/web/gui/src/main/webapp/_sdh/trie-test.html
@@ -0,0 +1,64 @@
+<!DOCTYPE html>
+<!--
+ ~ Copyright 2016 Open Networking Laboratory
+ ~
+ ~ Licensed 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.
+ -->
+
+<!--
+ ONOS -- Sample use of trie functions in fn.js
+ -->
+
+<html>
+<head lang="en">
+ <meta charset="UTF-8">
+ <title>Test Trie Functions</title>
+
+ <script type="text/javascript" src="../tp/angular.js"></script>
+ <script type="text/javascript" src="../tp/angular-route.js"></script>
+
+ <script type="text/javascript" src="../tp/d3.js"></script>
+
+ <script type="text/javascript" src="../app/fw/util/util.js"></script>
+ <script type="text/javascript" src="../app/fw/util/fn.js"></script>
+
+ <script type="text/javascript" src="trie-test.js"></script>
+
+ <link rel="stylesheet" href="../app/common.css">
+
+ <style>
+ html,
+ body {
+ background-color: #ddf;
+ font-family: Arial, Helvetica, sans-serif;
+ font-size: 9pt;
+ }
+
+ h2 {
+ color: darkred;
+ }
+
+ #output div {
+ font-family: monospace;
+ white-space: pre;
+ }
+ </style>
+
+</head>
+
+<!-- outline for using a controller in Angular -->
+<body class="light" ng-app="trie" ng-controller="OvTrieTest as ctrl">
+ <h2>Testing the Trie Functions</h2>
+ <div id="output"></div>
+</body>
+</html>
\ No newline at end of file
diff --git a/web/gui/src/main/webapp/_sdh/trie-test.js b/web/gui/src/main/webapp/_sdh/trie-test.js
new file mode 100644
index 0000000..2c8716c
--- /dev/null
+++ b/web/gui/src/main/webapp/_sdh/trie-test.js
@@ -0,0 +1,116 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed 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.
+ */
+
+/*
+ ONOS GUI -- Test code illustrating use of trie functions
+ */
+
+(function () {
+ 'use strict';
+
+ // injected refs
+ var $log, fs;
+
+ // internal state
+ var out,
+ trie = {},
+ counter = 5000;
+
+ function write(string) {
+ out.append('div').text(string);
+ }
+
+ function lookup(word) {
+ var result = fs.trieLookup(trie, word),
+ f = fs.isF(result),
+ show = f ? '{function}' : result;
+
+
+ write('------> ' + word + ' ==> ' + show);
+
+ f && f();
+ }
+
+ function add(word, data) {
+ var result = fs.addToTrie(trie, word, data);
+ write(' ADD> ' + word + ' [' + data + '] ==> ' + result);
+ }
+
+ function remove(word) {
+ var result = fs.removeFromTrie(trie, word);
+ write('REMOVE> ' + word + ' ==> ' + result);
+ }
+
+ function func1() {
+ counter++;
+ write('** function call ** ' + counter);
+ }
+
+ function func2() {
+ counter += 11;
+ write('** alternate call ** ' + counter);
+ }
+
+ function runTests() {
+ lookup('cat');
+
+ add('cat', 101);
+
+ lookup('ca');
+ lookup('cat');
+ lookup('cats');
+
+ add('cab', 103);
+ add('cog', 105);
+
+ lookup('cut');
+ lookup('cab');
+
+ remove('cab');
+
+ lookup('cab');
+ lookup('cat');
+
+ add('fun', func1);
+
+ lookup('fun');
+ lookup('fun');
+ lookup('fun');
+ lookup('cat');
+ lookup('fun');
+
+ add('fun', func2);
+
+ lookup('fun');
+ lookup('fun');
+ lookup('fun');
+
+ remove('fun');
+
+ lookup('fun');
+ }
+
+ angular.module('trie', ['onosUtil'])
+ .controller('OvTrieTest', ['$log', 'FnService',
+
+ function (_$log_, _fs_) {
+ $log = _$log_;
+ fs = _fs_;
+ out = d3.select('#output');
+
+ runTests();
+ }]);
+}());
diff --git a/web/gui/src/main/webapp/app/fw/util/fn.js b/web/gui/src/main/webapp/app/fw/util/fn.js
index d60ed2e..b0506fa 100644
--- a/web/gui/src/main/webapp/app/fw/util/fn.js
+++ b/web/gui/src/main/webapp/app/fw/util/fn.js
@@ -287,11 +287,16 @@
}
}
- // generate a trie structure from the given array of strings
- // if ignoreCase is true, all words are converted to uppercase first
- // note: each letter in each string must be valid as an object property key
- function createTrie(words, ignoreCase) {
- var trie = {};
+ // trie operation
+ function _trieOp(op, trie, word, data) {
+ var p = trie,
+ w = word.toUpperCase(),
+ s = w.split(''),
+ c = { p: p, s: s },
+ t = [],
+ x = 0,
+ f1 = op === '+' ? add : probe,
+ f2 = op === '+' ? insert : remove;
function add(c) {
var q = c.s.shift(),
@@ -300,31 +305,87 @@
if (!np) {
c.p[q] = {};
np = c.p[q];
+ x = 1;
}
-
- return {
- p: np,
- s: c.s
- }
+ return { p: np, s: c.s }
}
- words.forEach(function (word) {
- var p = trie,
- w = ignoreCase ? word.toUpperCase() : word,
- s = w.split(''),
- c = {
- p: p,
- s: s
- };
+ function probe(c) {
+ var q = c.s.shift(),
+ k = Object.keys(c.p).length,
+ np = c.p[q];
- while (c.s.length) {
- c = add(c);
+ t.push({ q:q, k:k, p:c.p });
+ if (!np) {
+ t = [];
+ return { s: [] };
}
- });
+ return { p: np, s: c.s }
+ }
- return trie;
+ function insert() {
+ c.p._data = data;
+ return x ? 'added' : 'updated';
+ }
+
+ function remove() {
+ if (t.length) {
+ t = t.reverse();
+ while (t.length) {
+ c = t.shift();
+ delete c.p[c.q];
+ if (c.k > 1) {
+ t = [];
+ }
+ }
+ return 'removed';
+ }
+ return 'absent';
+ }
+
+ while (c.s.length) {
+ c = f1(c);
+ }
+ return f2();
}
+ // add word to trie (word will be converted to uppercase)
+ // data associated with the word
+ // returns 'added' or 'updated'
+ function addToTrie(trie, word, data) {
+ return _trieOp('+', trie, word, data);
+ }
+
+ // remove word from trie (word will be converted to uppercase)
+ // returns 'removed' or 'absent'
+ function removeFromTrie(trie, word) {
+ return _trieOp('-', trie, word);
+ }
+
+ // lookup word (converted to uppercase) in trie
+ // returns:
+ // undefined if the word is not in the trie
+ // -1 for a partial match (word is a prefix to an existing word)
+ // data for the word for an exact match
+ function trieLookup(trie, word) {
+ var s = word.toUpperCase().split(''),
+ p = trie,
+ n;
+
+ while (s.length) {
+ n = s.shift();
+ p = p[n];
+ if (!p) {
+ return undefined;
+ }
+ }
+ if (p._data) {
+ return p._data;
+ }
+ return -1;
+ }
+
+
angular.module('onosUtil')
.factory('FnService',
['$window', '$location', '$log', function (_$window_, $loc, _$log_) {
@@ -360,7 +421,9 @@
noPxStyle: noPxStyle,
endsWith: endsWith,
parseBitRate: parseBitRate,
- createTrie: createTrie
+ addToTrie: addToTrie,
+ removeFromTrie: removeFromTrie,
+ trieLookup: trieLookup
};
}]);