--- /dev/null
+definition module BinSearchTree\r
+\r
+import StdClass\r
+import BinTree\r
+\r
+is_geordend :: (BTree a) -> Bool | Ord a // meest algemene type\r
+is_gebalanceerd :: (BTree a) -> Bool | Ord a // meest algemene type\r
+insertTree :: a (BTree a) -> BTree a | Ord a
\ No newline at end of file
--- /dev/null
+// Mart Lubbers, s4109503
+// Camil Staps, s4498062
+
+implementation module BinSearchTree
+
+import StdEnv
+import BinTree
+
+insertTree :: a (BTree a) -> BTree a | Ord a
+insertTree e BLeaf = BNode e BLeaf BLeaf
+insertTree e (BNode x le ri)
+| e <= x = BNode x (insertTree e le) ri
+| e > x = BNode x le (insertTree e ri)
+
+deleteTree :: a (BTree a) -> (BTree a) | Eq, Ord a
+deleteTree e BLeaf = BLeaf
+deleteTree e (BNode x le ri)
+| e < x = BNode x (deleteTree e le) ri
+| e == x = join le ri
+| e > x = BNode x le (deleteTree e ri)
+where
+ join :: (BTree a) (BTree a) -> (BTree a)
+ join BLeaf b2 = b2
+ join b1 b2 = BNode x b1` b2
+ where
+ (x,b1`) = largest b1
+
+ largest :: (BTree a) -> (a,(BTree a))
+ largest (BNode x b1 BLeaf) = (x,b1)
+ largest (BNode x b1 b2) = (y,BNode x b1 b2`)
+ where
+ (y,b2`) = largest b2
+
+
+is_geordend :: (BTree a) -> Bool | Ord a // meest algemene type
+is_geordend BLeaf = True
+is_geordend (BNode x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
+where
+ members :: (BTree a) -> [a]
+ members BLeaf = []
+ members (BNode x le ri) = [x:(members le) ++ (members ri)]
+
+is_gebalanceerd :: (BTree a) -> Bool | Ord a // meest algemene type
+is_gebalanceerd BLeaf = True
+is_gebalanceerd (BNode x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
+where
+ depth :: (BTree a) -> Int
+ depth BLeaf = 0
+ depth (BNode x le ri) = max (depth le) (depth ri) + 1
\ No newline at end of file
--- /dev/null
+module BinSearchTreeImage\r
+\r
+/* Instructions:\r
+\r
+(1) copy BinTree.(i/d)cl and BinSearchTree.(i/d)cl from Practicum to\r
+ {iTasks-SDK}\Experiments\SVG_tests\\r
+ \r
+(2) in these modules change the type\r
+\r
+ :: Tree a = Node a (Tree a) (Tree a) | Leaf\r
+ \r
+ to\r
+ \r
+ :: BTree a = BLeaf | BNode a (BTree a) (BTree a) // ORDER OF DATACONSTRUCTORS IS ESSENTIAL!!\r
+ \r
+ and adapt the corresponding function definitions.\r
+ \r
+(3) this main file (BinSearchTreeImage.icl) must be in the same folder:\r
+ {iTasks-SDK}\Experiments\SVG_tests\\r
+ \r
+(4) create a new project and set de environment to 'iTasks'\r
+\r
+(5) Bring-Up-To-Date and start generated application\r
+\r
+(6) Open a browser and navigate to localhost.\r
+ The application creates two tasks:\r
+ (a) The task on the left allows you to enter subsequent elements that are inserted in the tree, one after another.\r
+ (b) The task on the right must be finished by you by writing the function treeImage. This function must render the tree structure in such a way\r
+ that Nodes of the same depth have the same y-coordinate, and the root having the smallest y-coordinate.\r
+*/\r
+\r
+import iTasks // de algemene iTask API\r
+import iTasks.API.Extensions.SVG.SVGlet // specialiseer task editors\r
+from StdFunc import flip\r
+\r
+import BinSearchTree // type definition of Tree and sample trees z0 .. z8\r
+derive class iTask BTree\r
+\r
+Start :: *World -> *World\r
+Start world = startEngine [publish "/" (WebApp []) (\_ -> task)] world\r
+\r
+task :: Task [Int]\r
+task = withShared [] (\sharedList ->\r
+ ( (updateSharedInformation (Title "Edit list") [] sharedList <<@ ArrangeHorizontal)\r
+ -||-\r
+ (viewSharedInformation (Title "Tree view") [imageView treeImage` (\_ _ -> Nothing)] sharedList <<@ ArrangeHorizontal)\r
+ ) <<@ ArrangeHorizontal\r
+ ) <<@ FullScreen\r
+\r
+font = normalFontDef "Courier New" fonthoogte\r
+fonthoogte = 14.0\r
+\r
+treeImage` :: [Int] *TagSource -> Image m\r
+treeImage` nrs tags = fst(treeImage (foldl (flip insertTree) BLeaf nrs) tags)\r
+\r
+TMargin = 10.0\r
+\r
+treeImage :: (BTree Int) *TagSource -> (Image m, *TagSource)\r
+treeImage BLeaf ts = (margin (px TMargin) (circle (px fonthoogte)), ts)\r
+treeImage (BNode x t1 t2) [(tg1, utg1),(tg2, utg2):ts]\r
+= (above (repeat AtMiddleX) [] [textbox, lines, subtrees] Nothing, ts2)\r
+ where\r
+ (i1, ts1) = treeImage t1 ts\r
+ (i2, ts2) = treeImage t2 ts1\r
+ subtrees = beside (repeat AtTop) [] [tag utg1 i1, tag utg2 i2] Nothing\r
+ box = rect (textxspan font (toString x)) (px fonthoogte) <@< {fill=toSVGColor "none"}\r
+ textbox = overlay (repeat (AtMiddleX, AtMiddleY)) [] [box, text font (toString x)] Nothing\r
+ lines = beside (repeat AtBottom) [] [\r
+ line Nothing Slash ((imagexspan tg1) /. 2) (px TMargin),\r
+ line Nothing Backslash ((imagexspan tg2) /. 2) (px TMargin)] Nothing\r
+\r
--- /dev/null
+definition module BinTree\r
+\r
+:: BTree a = BNode a (BTree a) (BTree a) | BLeaf\r
+\r
+t0 :: BTree Int\r
+t1 :: BTree Int\r
+t2 :: BTree Int\r
+t3 :: BTree Int\r
+t4 :: BTree Int\r
+t5 :: BTree Int\r
+t6 :: BTree Int\r
+t7 :: BTree Int\r
+\r
+//nodes :: // meest algemene type\r
+//leaves :: // meest algemene type\r
+//diepte :: // meest algemene type\r
--- /dev/null
+implementation module BinTree\r
+\r
+import StdEnv\r
+\r
+:: BTree a = BNode a (BTree a) (BTree a) | BLeaf\r
+\r
+t0 :: BTree Int\r
+t0 = BLeaf\r
+t1 :: BTree Int\r
+t1 = BNode 4 t0 t0\r
+t2 :: BTree Int\r
+t2 = BNode 2 t0 t1\r
+t3 :: BTree Int\r
+t3 = BNode 5 t2 t0\r
+t4 :: BTree Int\r
+t4 = BNode 5 t2 t2\r
+t5 :: BTree Int\r
+t5 = BNode 1 BLeaf (BNode 2 BLeaf (BNode 3 BLeaf (BNode 4 BLeaf BLeaf)))\r
+t6 :: BTree Int\r
+t6 = BNode 1 (BNode 2 (BNode 3 (BNode 4 BLeaf BLeaf) BLeaf) BLeaf) BLeaf\r
+t7 :: BTree Int\r
+t7 = BNode 4 (BNode 1 BLeaf BLeaf) (BNode 5 (BNode 2 BLeaf BLeaf) BLeaf)\r
+\r
+// 2.\r
+//nodes :: // meest algemene type\r
+//nodes ...\r
+\r
+//Start = map nodes [t0,t1,t2,t3,t4,t5,t6,t7]\r
+\r
+//leaves :: // meest algemene type\r
+//leaves ...\r
+\r
+//Start = map leaves [t0,t1,t2,t3,t4,t5,t6,t7]\r
+\r
+//diepte :: // meest algemene type\r
+//diepte ...\r
+\r
+//Start = map diepte [t0,t1,t2,t3,t4,t5,t6,t7]\r
repositories / fp1415.git / commitdiff