Changeset 25759 in project

Timestamp:

01/05/12 04:48:59 (9 years ago)

Author:

Ivan Raikov

Message:

renamed trie to suffix-tree

Location:

release/4/suffix-tree

Files:

• . (moved) (moved from release/4/trie)
• trunk/suffix-tree.meta (copied) (copied from release/4/trie/trunk/trie.meta)
• trunk/suffix-tree.scm (copied) (copied from release/4/trie/trunk/trie.scm) (10 diffs)
• trunk/suffix-tree.setup (copied) (copied from release/4/trie/trunk/trie.setup)
• trunk/tests/run.scm (modified) (2 diffs)
• trunk/trie.meta (deleted)
• trunk/trie.scm (deleted)
• trunk/trie.setup (deleted)

release/4/suffix-tree/trunk/suffix-tree.scm

@@ -1 +1 @@
 ;;
 ;;
-;; An implementation of tries, a data type for representing sets of
-;; lists efficiently, provided there is an ordering relation on the
-;; elements of lists. 
+;; An implementation of suffix tree, a data structure for representing
+;; sets of lists efficiently, provided there is an ordering relation
+;; on the elements of lists.
 ;;
 ;; Copyright 2011 Ivan Raikov and the Okinawa Institute of Science and
@@ -9 +9 @@
 ;;
 ;;
-;; A trie is a tree with arcs labeled by elements from the element
-;; type of the lists and with branches ordered on the basis of their
-;; arc labels; moreover, only one branch per distinct label value is
-;; allowed per node.  Ends of lists are designated by an "EOL" marker;
-;; a value may be associated with the EOL symbol.
-;;
-;;
-
-(module trie
+;; A suffix tree is a tree with arcs labeled by elements from the
+;; element type of the lists and with branches ordered on the basis of
+;; their arc labels; moreover, only one branch per distinct label
+;; value is allowed per node.  Ends of lists are designated by an
+;; "EOL" marker; a value may be associated with the EOL symbol.
+;;
+;;
+
+(module suffix-tree
         
-        ( make-trie trie-equal? )
+        ( make-suffix-tree suffix-tree-equal? )
 
         (import scheme chicken)
@@ -35 +35 @@
        (branches (list-of branch?))))
 
-(define trie?  (list-of branch?))
-
-
-(define (trie-equal? t1 t2)
+(define suffix-tree?  (list-of branch?))
+
+
+(define (suffix-tree-equal? t1 t2)
   (let ((t1 (t1 'repr)) (t2 (t2 'repr)))
     (let ((aeq (car t1)) (tr1 (caddr t1))
@@ -54 +54 @@
 
 
-(define (make-trie leq key->list . rest)
+(define (make-suffix-tree leq key->list . rest)
   
   (let-optionals rest ((tr '()))
 
-  (assert (trie? tr))
+  (assert (suffix-tree? tr))
 
   (define empty '())
@@ -120 +120 @@
        ))
 
-  ;; Removes lst from tr.  Any branches having a null subtrie
+  ;; Removes lst from tr.  Any branches having a null subsuffix-tree
   ;; associated with them are deleted.
 
@@ -143 +143 @@
 
   ;; Merges tr1 and tr2.  If there is a list that appears in both
-  ;; tries, an exception is raised.
+  ;; suffix-trees, an exception is raised.
 
   (define (merge tr1 tr2)
@@ -152 +152 @@
 
            (((($ branch 'EOL b1) . _) (($ branch 'EOL _) . _))
-            (error "already in trie" tr1 tr2))
+            (error "already in suffix-tree" tr1 tr2))
 
            (((($ branch 'EOL b1) . tr11) tr2)
@@ -170 +170 @@
 
 
-  ;; Splits tr into three tries on the basis of a.  The first trie
+  ;; Splits tr into three suffix-trees on the basis of a.  The first suffix-tree
   ;; consists of branches headed by actions less than a (plus any EOL
   ;; symbol), the second contains the branch (if any) associated with a,
@@ -199 +199 @@
           
       ((insert) 
-       (lambda (k bval) (make-trie leq key->list (insert (key->list k) bval tr))))
+       (lambda (k bval) (make-suffix-tree leq key->list (insert (key->list k) bval tr))))
 
       ((lookup) 
@@ -207 +207 @@
        (lambda (k)
          (let ((v (lookup (key->list k) tr identity)))
-           (if (trie? v) 
-               (make-trie leq key->list v)
+           (if (suffix-tree? v) 
+               (make-suffix-tree leq key->list v)
                v))))
 
       ((remove) 
-       (lambda (k) (make-trie leq key->list (remove (key->list k) tr))))
+       (lambda (k) (make-suffix-tree leq key->list (remove (key->list k) tr))))
 
       ((merge)  
-       (lambda (x) (make-trie leq key->list (merge tr x))))
+       (lambda (x) (make-suffix-tree leq key->list (merge tr x))))
 
       ((partition) 

release/4/suffix-tree/trunk/tests/run.scm

@@ -1 @@
-(use trie)
+(use suffix-tree)
 
-(define t (make-trie char=? string->list ))
+(define t (make-suffix-tree char=? string->list ))
 
 (define t1 ((t 'insert) "key1" 'test1))
@@ -13 +13 @@
 (assert (equal? 'test1 ((t3 'lookup)  "1")))
 (assert (equal? 'test2 ((t3 'lookup)  "2")))
-
-
-