Jess Information

Jess Home
Jess 7 Features
Download Now!
Online Demo

Documentation
FAQ
Manual
Mailing List
Jess Wiki

More information Related Web Sites
User Contributions
JSR94 Info
Developer's Log
About This Site

JESS ®, the Rule Engine for the JavaTM Platform

Jess Wiki: Ivy On Trees

Author

Wolfgang Laun
Wolfgang Laun a-t thalesgroup com

Name: Ivy On Trees

Intent: Processing facts on a binary tree

Motivation:

This is, perhaps, more of a mental exercise than a design pattern. The essential prerequisite for this pattern to work is that you have facts arranged in a binary sorted tree. Then it's possible to create some "ivy" that clings to the root and sends up sprouts to the tree leaves, doing whatever needs to be done.

Applicability:

As it is presented her, it is restricted to the processing of binary trees. But similar approaches may be considered for more general graphs.

Participants:

Basic ingredients are facts and lambda expressions. The "inline" definition of actions as lambda expressions requires a Jess command extension for calling a lambda expression. See AddingCommandsToJess.

Sample code:

Notice that this presents two kinds of processings: tree traversal and node insertion. They are essentially different, because a tree traversal ends only after visiting all nodes whereas node insertion ends when the right place has been found.

(clear)

(load-function at.laune.jess.CallLambda)

;; a tree node
(deftemplate Node
    (slot value (type INTEGER))
    (slot left  (type INTEGER) (default nil))
    (slot right (type INTEGER) (default nil))
)

;; a sprout of Ivy
(deftemplate Ivy
    (slot current (type INTEGER) (default nil))  ; a node value
    (slot state   (type SYMBOL)  (default sBeg)) ; sBeg sLeft sMid sRight sEnd
    (slot parent  (type ANY)     (default nil))  ; the parent crawler
    (slot act     (type ANY)     (default nil))  ; processing argument
    (slot process (type ANY))                    ; processing function
)

;; The rule for detecting that a sprout of ivy is on a node and
;; ready to do something.
;;
(defrule atBeg
    ?n <- (Node (value ?value)(left ?left)(right ?right))
    ?c <- (Ivy (current ?value)
               (state ?state & sBeg | sMid | sEnd)
               (process ?process)
               (parent ?parent))
    =>
    (lcall ?process ?n ?value ?left ?right ?c ?state ?parent)
)

(reset)

;; Creates a sprout of Ivy on a child node.
;;
(deffunction spawn (?c ?curr)
    (bind ?res (neq ?curr nil))
    (if (eq ?res TRUE) then
        (assert (Ivy (current ?curr)
                     (parent  ?c)
                     (act     (fact-slot-value ?c act))
                     (process (fact-slot-value ?c process)))))
    (return ?res))

;; The processing function for traversing a tree.
;; The distinction between pre-, post- and endorder is set by act
;; (but could be coded into the function).
;;
(bind ?pfTraverse
  (lambda (?n ?value ?left ?right ?c ?state ?parent)
    (if (eq ?state sBeg) then
      (modify ?c (state (if (spawn ?c ?left) then sLeft else sMid)))
    )
    (if (eq ?state sMid) then
      (modify ?c (state (if (spawn ?c ?right) then sRight else sEnd)))
    )
    (if (eq ?state sEnd) then
      (if (neq ?parent nil) then
        (modify ?parent
        (state (if (eq (fact-slot-value ?parent state) sLeft) then sMid else sEnd)))
      )
      (retract ?c)
    )
    ;; The action.
    (if (eq ?state (fact-slot-value ?c act)) then
      (printout t "value=" ?value crlf)
    )
  )
)

;; The processing function for inserting a tree node.
;; The value to be inserted is set by act.
;;
(bind ?pfInsert
  (lambda (?n ?value ?left ?right ?c ?state ?parent)
    (bind ?newval (fact-slot-value ?c act))
    (if (< ?newval ?value) then
      (if (not (spawn ?c ?left)) then
        (modify ?n (left ?newval))
        (assert (Node (value ?newval)))
      )
    )      
    (if (> ?newval ?value) then
      (if (not (spawn ?c ?right)) then
        (modify ?n (right ?newval))
        (assert (Node (value ?newval)))
      )
    )
    (retract ?c)
  )
)

;; The sorted binary tree:
;;                       5
;;                  1         7
;;                     3           10
;;                               9     12

(defglobal ?*root* = 5)

(assert (Node (value  1)(right 3)))
(assert (Node (value  3)))
(assert (Node (value  7)(right 10)))
(assert (Node (value  5)(left 1)(right 7)))  ; root
(assert (Node (value 10)(left 9)(right 12)))
(assert (Node (value  9)))
(assert (Node (value 12)))

;; Display the tree
;; (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sBeg)))
   (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sMid)))
;; (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sEnd)))
   (run)

;; Insert some new nodes
   (assert (Ivy (process ?pfInsert)(current ?*root*)(act 13)))
   (run)
   (assert (Ivy (process ?pfInsert)(current ?*root*)(act 4)))
   (run)

;; Display the tree
   (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sMid)))
   (run)


Front Page | Sandbox | Recent Changes | Powered by Friki | Last Edited: 27 June 2007