LeftLane

leftlane

Creating Scrollable Lists using Protocol-Oriented Programming and UICollectionViewFlowLayout

We figured out how the search and insert operation works in the red-black tree in the . In this part, we figure out how the delete operation works. The delete operation is more complicated than the insert operation. first part The Delete Operation The delete operation as well as the insert operation ensures O(log(n)) time complexity. First, we must implement an auxiliary transplant method that transplants y’s node to x’s node place. func (tree *Tree[K, V]) transplant(x *TreeNode[K, V], y *TreeNode[K, V]) {
	if x.parent == tree.leaf {
		tree.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}

	y.parent = x.parent
} The delete operation is similar to the delete operation in the binary search tree but has several differences. We have to keep the original color of the deleted node. If the deleted node is red, we don’t violate any properties of the red-black tree, but if the deleted node is black, we can violate the red-black properties. We might violate the first property: the root is black, if a transplanted node is red, and the deleted node is black. We might violate the third property: there cannot be two neighboring red nodes if the parent of the deleted node is red and the transplanted node is red. We will violate the fifth property: having the same number of black nodes from the root to each leaf. We must run the auxiliary method to restore the red-black properties. The algorithm for deleting a node in a red-black tree is as follows. 1. We need to declare a variable that will store the color of the node to be deleted. 2. If the node has no children or only one child, we can transplant this node or leaf in case the node has no children to the node to be deleted. If the color of the node to be deleted is black, we need to run the deleteFixup helper method. 3. If the node to be deleted has two children, it is necessary to find a successor of this node. The successor of the node is the leftmost node of its right child. It is essential to save the color of the descendant to a variable, as there may be violations there after the transplantation. If the successor is not the right child of the node being deleted, we need to transplant the right subtree of the successor to the successor. Then we must transplant the successor into the node to be deleted and set the color of the node to be deleted. Then we must run the method deleteFixup if it is required. func (tree *Tree[K, V]) Delete(key K) {
	x := tree.lookup(key)

	if x == tree.leaf {
		return
	}

	var y *TreeNode[K, V]
	originalColor := x.color

    
	if x.left == tree.leaf { 
		y = x.right
		tree.transplant(x, x.right)
	} else if x.right == tree.leaf {
		y = x.left
		tree.transplant(x, x.left)
	} else {
		successor := tree.leftmost(x.right)
		originalColor = successor.color
    
		y = successor.right

		if successor != x.right {
			tree.transplant(successor, successor.right)
			successor.right = x.right
			successor.right.parent = successor
		} else {
			y.parent = successor
		}

		tree.transplant(x, successor)
		successor.left = x.left
		successor.left.parent = successor
		successor.color = x.color
	}

	tree.len--

	if originalColor == black {
		tree.deleteFixup(y)
	}
} 4 cases are used to rebalance the red-black tree after deleting the node. Case one occurs when the sibling of the node is red. We must exchange the color of the current node’s parent and the current node’s sibling and rotate the node’s parent to the left if the node belongs to a left subtree, or rotate to the right if the node belongs to the right subtree and then updating the sibling. Case two occurs when both sibling’s children have the black color. The sibling is also black. We must change the color of the sibling to red and leave the current node. If the node’s parent is red, the cycle terminates. Case 3 occurs when both the sibling and its right child have the black color, and the left child has the red color. Need to exchange colors of the sibling’s left child and sibling and rotate the sibling to the right if the node belongs to the left subtree, and rotate to the left if the node belongs to the right subtree and update the sibling. Then we go to the fourth case. 4. Case 4 occurs when the right child of the sibling is red and the sibling has a black color. We must change the color of the sibling’s right child to black, and change the current node’s parent to black. Then we must rotate the node’s parent to the left if the node belongs to the left subtree, or rotate to the right if the node belongs to the right subtree. Then we set the current node as the root tree. func (tree *Tree[K, V]) deleteFixup(x *TreeNode[K, V]) {
	for x != tree.root && x.color == black {
		if x == x.parent.left {
			y := x.parent.right

			if y.color == red {
				y.color = black
				x.parent.color = red
				tree.leftRotate(x.parent)
				y = x.parent.right
			}

			if y.left.color == black && y.right.color == black {
				y.color = red
				x = x.parent
			} else {

				if y.right.color == black {
					y.left.color = black
					y.color = red
					tree.rightRotate(y)
					y = x.parent.right
				}

				y.color = x.parent.color
				x.parent.color = black
				y.right.color = black
				tree.leftRotate(x.parent)
				x = tree.root
			}
		} else {
			y := x.parent.left

			if y.color == red {
				y.color = black
				x.parent.color = red
				tree.rightRotate(x.parent)
				y = x.parent.left
			}

			if y.left.color == black && y.right.color == black {
				y.color = red
				x = x.parent
			} else {

				if y.left.color == black {
					y.right.color = black
					y.color = red
					tree.leftRotate(y)
					y = x.parent.left
				}

				y.color = x.parent.color
				x.parent.color = black
				x.left.color = black
				tree.rightRotate(x.parent)
				x = tree.root
			}
		}
	}
	tree.root.color = black
} I hope it is now more clear how node deleting works in the red-black tree.

Implementing Red-Black Tree in Go — Part 2: The Delete Operation

The binary search tree has one serious problem. They can transform into a linked list. The red-black tree solves this problem and ensures O(log(n)) time complexity for get, insert, and delete operations. To avoid this problem we can use self-balancing trees. The red-black tree is one of safe-balanced tree. It ensures that the depth between the right and left subtree does not differ by more than 1. In addition to binary search properties, the red-black tree introduces additional properties: The root of the red-black tree is black The leaf is always black The black node can have either a black or red node. If the node is red, both children are black. A simple path from a node to its descendant leaves always has the same number of black nodes. We will also keep a separate instance per tree leaf. We could create an instance for each leaf, but that would be more memory-intensive. Also, we will create a comparator that will compare keys. package util

import (
	"cmp"
)

type Comparator[T any] interface {
	Compare(a T, b T) int
}

type OrderedComparator[T cmp.Ordered] struct {
}

func (o OrderedComparator[T]) Compare(a T, b T) int {
	return cmp.Compare(a, b)
} package redblacktree

import (
	"github.com/dmitriiantonov/go-ds/tree"
	"github.com/dmitriiantonov/go-ds/util"
)

type color int

const (
	black color = iota
	red
)

type TreeNode[K any, V any] struct {
	key    K
	value  V
	color  color
	parent *TreeNode[K, V]
	left   *TreeNode[K, V]
	right  *TreeNode[K, V]
}

func (node *TreeNode[K, V]) Key() K {
	return node.key
}

func (node *TreeNode[K, V]) Value() V {
	return node.value
}

type Tree[K any, V any] struct {
	leaf       *TreeNode[K, V]
	root       *TreeNode[K, V]
	comparator util.Comparator[K]
	len        int
}

func NewTree[K any, V any](comparator util.Comparator[K]) *Tree[K, V] {
	instance := new(Tree[K, V])
	instance.leaf = &TreeNode[K, V]{color: black}
	instance.root = instance.leaf
	instance.comparator = comparator
	return instance
}

func (tree *Tree[K, V]) Len() int {
	return tree.len
} The difference from a binary search tree is that we end the search if the current node is leaf, rather than nill. The more interesting differences begin when inserting the node in our tree. We mark the new node as red and we can violate property 1 if the tree is empty, and property 4 because we can’t have two red nodes in the path. And, we must rebalance our tree. First, we need to introduce the two operations used to balance the tree. These are rotating the tree to the left and to the right. func (tree *Tree[K, V]) leftRotate(x *TreeNode[K, V]) {
	right := x.right
	x.right = right.left
	if right.left != tree.leaf {
		right.left.parent = x
	}
	right.parent = x.parent
	if x.parent == tree.leaf {
		tree.root = right
	} else if x == x.parent.left {
		x.parent.left = right
	} else {
		x.parent.right = right
	}
	right.left = x
	x.parent = right
}

func (tree *Tree[K, V]) rightRotate(x *TreeNode[K, V]) {
	left := x.left
	x.left = left.right
	if left.right != tree.leaf {
		left.right.parent = x
	}
	left.parent = x.parent
	if x.parent == tree.leaf {
		tree.root = left
	} else if x == x.parent.left {
		x.parent.left = left
	} else {
		x.parent.right = left
	}
	left.right = x
	x.parent = left
} We have three cases in which we must fix violations in our tree. Also, we need to denote an uncle node, that is a sibling node’s parent. If the uncle is a red node and the node’s parent is red we must make them black. Also, we must make their parent red and set it as the current node. If its parent is red, then we must fix the following violation. If the node belongs to the left subtree and the node’s right child is red or if the node belongs to the right subtree and the node’s left child is red we must make the node’s parent current node and do the left rotation in the 1 case, or the right rotation in the second case. And then we come to case 3. In the third case, we must make the current node’s parent black and its parent red, and then we must do a right rotation if the node’s parent is a left subtree, or a left rotation if the node’s parent is a right subtree. I illustrated cases for the left subtree. For the right subtree, you must change the right rotation to the left rotation, and the left rotation to the right rotation. func (tree *Tree[K, V]) Insert(key K, value V) {
    x := tree.lookup(key) // try to find a node by key

    if x != tree.leaf { // if we found it, update value and exit
       x.value = value
       return
    }
    // find the parent
    parent := tree.leaf
    current := tree.root

    for current != tree.leaf {
       parent = current

       switch tree.comparator.Compare(key, current.key) {
       case -1:
          current = current.left
       case 1:
          current = current.right
       }
    }
    // create a new node
    x = &TreeNode[K, V]{
       key:    key,
       value:  value,
       color:  red,
       parent: parent,
       left:   tree.leaf,
       right:  tree.leaf,
    }

    // send the node as child
    if parent == tree.leaf {
       tree.root = parent
    } else if tree.comparator.Compare(key, parent.key) < 0 {
       parent.left = x
    } else {
       parent.right = x
    }
    // do the rebalance
    tree.insertFixup(x)
}

func (tree *Tree[K, V]) insertFixup(x *TreeNode[K, V]) {
    for x.parent.color == red { // we must iterate only if the node's parent is red
       if x.parent == x.parent.parent.left { // if the node belongs to left subtree
          y := x.parent.parent.right // set uncle
          if y.color == red { // case 1
             x.parent.color = black
             y.color = black
             x.parent.parent.color = red // set 
             x = x.parent.parent
          } else {
             if x == x.parent.right { // case 2
                x = x.parent
                tree.leftRotate(x)
             }
             x.parent.color = black // case 3
             x.parent.parent.color = red
             tree.rightRotate(x.parent.parent)
          }
       } else { // if the node belongs to the right subtree
          y := x.parent.parent.left 
          if y.color == red { // case 1
             x.parent.color = black
             y.color = black
             x.parent.parent.color = red
             x = x.parent.parent
          } else {
             if x == x.parent.left { // case 2
                x = x.parent
                tree.rightRotate(x)
             }
             x.parent.color = black // case 3
             x.parent.parent.color = red
             tree.leftRotate(x.parent.parent)
          }
       }
    }
    tree.root.color = black // change the root color to black
} In the second part of this article, we will consider the delete operation.

Implementing Red-Black Tree in Go — Part 1, The Search and Insert Operation

Alice in Wonderland by Lewis Carroll, is part of the HackerNoon Books Series. You can jump to any chapter in this book . Pig and Pepper here CHAPTER VI. Pig and Pepper For a minute or two she stood looking at the house, and wondering what to do next, when suddenly a footman in livery came running out of the wood—(she considered him to be a footman because he was in livery: otherwise, judging by his face only, she would have called him a fish)—and rapped loudly at the door with his knuckles. It was opened by another footman in livery, with a round face, and large eyes like a frog; and both footmen, Alice noticed, had powdered hair that curled all over their heads. She felt very curious to know what it was all about, and crept a little way out of the wood to listen. The Fish-Footman began by producing from under his arm a great letter, nearly as large as himself, and this he handed over to the other, saying, in a solemn tone, “For the Duchess. An invitation from the Queen to play croquet.” The Frog-Footman repeated, in the same solemn tone, only changing the order of the words a little, “From the Queen. An invitation for the Duchess to play croquet.” Then they both bowed low, and their curls got entangled together. Alice laughed so much at this, that she had to run back into the wood for fear of their hearing her; and when she next peeped out the Fish-Footman was gone, and the other was sitting on the ground near the door, staring stupidly up into the sky. Alice went timidly up to the door, and knocked. “There’s no sort of use in knocking,” said the Footman, “and that for two reasons. First, because I’m on the same side of the door as you are; secondly, because they’re making such a noise inside, no one could possibly hear you.” And certainly there a most extraordinary noise going on within—a constant howling and sneezing, and every now and then a great crash, as if a dish or kettle had been broken to pieces. was “Please, then,” said Alice, “how am I to get in?” “There might be some sense in your knocking,” the Footman went on without attending to her, “if we had the door between us. For instance, if you were , you might knock, and I could let you out, you know.” He was looking up into the sky all the time he was speaking, and this Alice thought decidedly uncivil. “But perhaps he can’t help it,” she said to herself; “his eyes are so nearly at the top of his head. But at any rate he might answer questions.—How am I to get in?” she repeated, aloud. inside very “I shall sit here,” the Footman remarked, “till tomorrow—” At this moment the door of the house opened, and a large plate came skimming out, straight at the Footman’s head: it just grazed his nose, and broke to pieces against one of the trees behind him. “—or next day, maybe,” the Footman continued in the same tone, exactly as if nothing had happened. “How am I to get in?” asked Alice again, in a louder tone. “ you to get in at all?” said the Footman. “That’s the first question, you know.” Are It was, no doubt: only Alice did not like to be told so. “It’s really dreadful,” she muttered to herself, “the way all the creatures argue. It’s enough to drive one crazy!” The Footman seemed to think this a good opportunity for repeating his remark, with variations. “I shall sit here,” he said, “on and off, for days and days.” “But what am to do?” said Alice. I “Anything you like,” said the Footman, and began whistling. “Oh, there’s no use in talking to him,” said Alice desperately: “he’s perfectly idiotic!” And she opened the door and went in. The door led right into a large kitchen, which was full of smoke from one end to the other: the Duchess was sitting on a three-legged stool in the middle, nursing a baby; the cook was leaning over the fire, stirring a large cauldron which seemed to be full of soup. “There’s certainly too much pepper in that soup!” Alice said to herself, as well as she could for sneezing. There was certainly too much of it in the air. Even the Duchess sneezed occasionally; and as for the baby, it was sneezing and howling alternately without a moment’s pause. The only things in the kitchen that did not sneeze, were the cook, and a large cat which was sitting on the hearth and grinning from ear to ear. “Please would you tell me,” said Alice, a little timidly, for she was not quite sure whether it was good manners for her to speak first, “why your cat grins like that?” “It’s a Cheshire cat,” said the Duchess, “and that’s why. Pig!” She said the last word with such sudden violence that Alice quite jumped; but she saw in another moment that it was addressed to the baby, and not to her, so she took courage, and went on again:— “I didn’t know that Cheshire cats always grinned; in fact, I didn’t know that cats grin.” could “They all can,” said the Duchess; “and most of ’em do.” “I don’t know of any that do,” Alice said very politely, feeling quite pleased to have got into a conversation. “You don’t know much,” said the Duchess; “and that’s a fact.” Alice did not at all like the tone of this remark, and thought it would be as well to introduce some other subject of conversation. While she was trying to fix on one, the cook took the cauldron of soup off the fire, and at once set to work throwing everything within her reach at the Duchess and the baby—the fire-irons came first; then followed a shower of saucepans, plates, and dishes. The Duchess took no notice of them even when they hit her; and the baby was howling so much already, that it was quite impossible to say whether the blows hurt it or not. “Oh, mind what you’re doing!” cried Alice, jumping up and down in an agony of terror. “Oh, there goes his nose!” as an unusually large saucepan flew close by it, and very nearly carried it off. please precious “If everybody minded their own business,” the Duchess said in a hoarse growl, “the world would go round a deal faster than it does.” “Which would be an advantage,” said Alice, who felt very glad to get an opportunity of showing off a little of her knowledge. “Just think of what work it would make with the day and night! You see the earth takes twenty-four hours to turn round on its axis—” not “Talking of axes,” said the Duchess, “chop off her head!” Alice glanced rather anxiously at the cook, to see if she meant to take the hint; but the cook was busily stirring the soup, and seemed not to be listening, so she went on again: “Twenty-four hours, I ; or is it twelve? I—” think “Oh, don’t bother ,” said the Duchess; “I never could abide figures!” And with that she began nursing her child again, singing a sort of lullaby to it as she did so, and giving it a violent shake at the end of every line: me “Speak roughly to your little boy, And beat him when he sneezes: He only does it to annoy, Because he knows it teases.” CHORUS. (In which the cook and the baby joined): “Wow! wow! wow!” While the Duchess sang the second verse of the song, she kept tossing the baby violently up and down, and the poor little thing howled so, that Alice could hardly hear the words:— “I speak severely to my boy, I beat him when he sneezes; For he can thoroughly enjoy The pepper when he pleases!” CHORUS. “Wow! wow! wow!” “Here! you may nurse it a bit, if you like!” the Duchess said to Alice, flinging the baby at her as she spoke. “I must go and get ready to play croquet with the Queen,” and she hurried out of the room. The cook threw a frying-pan after her as she went out, but it just missed her. Alice caught the baby with some difficulty, as it was a queer-shaped little creature, and held out its arms and legs in all directions, “just like a star-fish,” thought Alice. The poor little thing was snorting like a steam-engine when she caught it, and kept doubling itself up and straightening itself out again, so that altogether, for the first minute or two, it was as much as she could do to hold it. As soon as she had made out the proper way of nursing it, (which was to twist it up into a sort of knot, and then keep tight hold of its right ear and left foot, so as to prevent its undoing itself,) she carried it out into the open air. “If I don’t take this child away with me,” thought Alice, “they’re sure to kill it in a day or two: wouldn’t it be murder to leave it behind?” She said the last words out loud, and the little thing grunted in reply (it had left off sneezing by this time). “Don’t grunt,” said Alice; “that’s not at all a proper way of expressing yourself.” The baby grunted again, and Alice looked very anxiously into its face to see what was the matter with it. There could be no doubt that it had a turn-up nose, much more like a snout than a real nose; also its eyes were getting extremely small for a baby: altogether Alice did not like the look of the thing at all. “But perhaps it was only sobbing,” she thought, and looked into its eyes again, to see if there were any tears. very No, there were no tears. “If you’re going to turn into a pig, my dear,” said Alice, seriously, “I’ll have nothing more to do with you. Mind now!” The poor little thing sobbed again (or grunted, it was impossible to say which), and they went on for some while in silence. Alice was just beginning to think to herself, “Now, what am I to do with this creature when I get it home?” when it grunted again, so violently, that she looked down into its face in some alarm. This time there could be mistake about it: it was neither more nor less than a pig, and she felt that it would be quite absurd for her to carry it further. no So she set the little creature down, and felt quite relieved to see it trot away quietly into the wood. “If it had grown up,” she said to herself, “it would have made a dreadfully ugly child: but it makes rather a handsome pig, I think.” And she began thinking over other children she knew, who might do very well as pigs, and was just saying to herself, “if one only knew the right way to change them—” when she was a little startled by seeing the Cheshire Cat sitting on a bough of a tree a few yards off. The Cat only grinned when it saw Alice. It looked good-natured, she thought: still it had long claws and a great many teeth, so she felt that it ought to be treated with respect. very “Cheshire Puss,” she began, rather timidly, as she did not at all know whether it would like the name: however, it only grinned a little wider. “Come, it’s pleased so far,” thought Alice, and she went on. “Would you tell me, please, which way I ought to go from here?” “That depends a good deal on where you want to get to,” said the Cat. “I don’t much care where—” said Alice. “Then it doesn’t matter which way you go,” said the Cat. “—so long as I get ,” Alice added as an explanation. somewhere “Oh, you’re sure to do that,” said the Cat, “if you only walk long enough.” Alice felt that this could not be denied, so she tried another question. “What sort of people live about here?” “In direction,” the Cat said, waving its right paw round, “lives a Hatter: and in direction,” waving the other paw, “lives a March Hare. Visit either you like: they’re both mad.” that that “But I don’t want to go among mad people,” Alice remarked. “Oh, you can’t help that,” said the Cat: “we’re all mad here. I’m mad. You’re mad.” “How do you know I’m mad?” said Alice. “You must be,” said the Cat, “or you wouldn’t have come here.” Alice didn’t think that proved it at all; however, she went on “And how do you know that you’re mad?” “To begin with,” said the Cat, “a dog’s not mad. You grant that?” “I suppose so,” said Alice. “Well, then,” the Cat went on, “you see, a dog growls when it’s angry, and wags its tail when it’s pleased. Now growl when I’m pleased, and wag my tail when I’m angry. Therefore I’m mad.” I “ call it purring, not growling,” said Alice. I “Call it what you like,” said the Cat. “Do you play croquet with the Queen to-day?” “I should like it very much,” said Alice, “but I haven’t been invited yet.” “You’ll see me there,” said the Cat, and vanished. Alice was not much surprised at this, she was getting so used to queer things happening. While she was looking at the place where it had been, it suddenly appeared again. “By-the-bye, what became of the baby?” said the Cat. “I’d nearly forgotten to ask.” “It turned into a pig,” Alice quietly said, just as if it had come back in a natural way. “I thought it would,” said the Cat, and vanished again. Alice waited a little, half expecting to see it again, but it did not appear, and after a minute or two she walked on in the direction in which the March Hare was said to live. “I’ve seen hatters before,” she said to herself; “the March Hare will be much the most interesting, and perhaps as this is May it won’t be raving mad—at least not so mad as it was in March.” As she said this, she looked up, and there was the Cat again, sitting on a branch of a tree. “Did you say pig, or fig?” said the Cat. “I said pig,” replied Alice; “and I wish you wouldn’t keep appearing and vanishing so suddenly: you make one quite giddy.” “All right,” said the Cat; and this time it vanished quite slowly, beginning with the end of the tail, and ending with the grin, which remained some time after the rest of it had gone. “Well! I’ve often seen a cat without a grin,” thought Alice; “but a grin without a cat! It’s the most curious thing I ever saw in my life!” She had not gone much farther before she came in sight of the house of the March Hare: she thought it must be the right house, because the chimneys were shaped like ears and the roof was thatched with fur. It was so large a house, that she did not like to go nearer till she had nibbled some more of the lefthand bit of mushroom, and raised herself to about two feet high: even then she walked up towards it rather timidly, saying to herself “Suppose it should be raving mad after all! I almost wish I’d gone to see the Hatter instead!” About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Lewis Carroll (2008). Alice in Wonderland. Urbana, Illinois: Project Gutenberg. Retrieved https://www.gutenberg.org/cache/epub/11/pg11-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at , located at www.gutenberg.org https://www.gutenberg.org/policy/license.html.

Pig and Pepper

Alice in Wonderland by Lewis Carroll, is part of the HackerNoon Books Series. You can jump to any chapter in this book . Advice from a Caterpillar here CHAPTER V. Advice from a Caterpillar The Caterpillar and Alice looked at each other for some time in silence: at last the Caterpillar took the hookah out of its mouth, and addressed her in a languid, sleepy voice. “Who are ” said the Caterpillar. you? This was not an encouraging opening for a conversation. Alice replied, rather shyly, “I—I hardly know, sir, just at present—at least I know who I when I got up this morning, but I think I must have been changed several times since then.” was “What do you mean by that?” said the Caterpillar sternly. “Explain yourself!” “I can’t explain , I’m afraid, sir,” said Alice, “because I’m not myself, you see.” myself “I don’t see,” said the Caterpillar. “I’m afraid I can’t put it more clearly,” Alice replied very politely, “for I can’t understand it myself to begin with; and being so many different sizes in a day is very confusing.” “It isn’t,” said the Caterpillar. “Well, perhaps you haven’t found it so yet,” said Alice; “but when you have to turn into a chrysalis—you will some day, you know—and then after that into a butterfly, I should think you’ll feel it a little queer, won’t you?” “Not a bit,” said the Caterpillar. “Well, perhaps your feelings may be different,” said Alice; “all I know is, it would feel very queer to .” me “You!” said the Caterpillar contemptuously. “Who are ” you? Which brought them back again to the beginning of the conversation. Alice felt a little irritated at the Caterpillar’s making such short remarks, and she drew herself up and said, very gravely, “I think, you ought to tell me who are, first.” very you “Why?” said the Caterpillar. Here was another puzzling question; and as Alice could not think of any good reason, and as the Caterpillar seemed to be in a unpleasant state of mind, she turned away. very “Come back!” the Caterpillar called after her. “I’ve something important to say!” This sounded promising, certainly: Alice turned and came back again. “Keep your temper,” said the Caterpillar. “Is that all?” said Alice, swallowing down her anger as well as she could. “No,” said the Caterpillar. Alice thought she might as well wait, as she had nothing else to do, and perhaps after all it might tell her something worth hearing. For some minutes it puffed away without speaking, but at last it unfolded its arms, took the hookah out of its mouth again, and said, “So you think you’re changed, do you?” “I’m afraid I am, sir,” said Alice; “I can’t remember things as I used—and I don’t keep the same size for ten minutes together!” “Can’t remember things?” said the Caterpillar. what “Well, I’ve tried to say “How doth the little busy bee,” but it all came different!” Alice replied in a very melancholy voice. “Repeat, “ ,’” said the Caterpillar. You are old, Father William Alice folded her hands, and began:— “You are old, Father William,” the young man said, “And your hair has become very white; And yet you incessantly stand on your head— Do you think, at your age, it is right?” “In my youth,” Father William replied to his son, “I feared it might injure the brain; But, now that I’m perfectly sure I have none, Why, I do it again and again.” “You are old,” said the youth, “as I mentioned before, And have grown most uncommonly fat; Yet you turned a back-somersault in at the door— Pray, what is the reason of that?” “In my youth,” said the sage, as he shook his grey locks, “I kept all my limbs very supple By the use of this ointment—one shilling the box— Allow me to sell you a couple?” “You are old,” said the youth, “and your jaws are too weak For anything tougher than suet; Yet you finished the goose, with the bones and the beak— Pray, how did you manage to do it?” “In my youth,” said his father, “I took to the law, And argued each case with my wife; And the muscular strength, which it gave to my jaw, Has lasted the rest of my life.” “You are old,” said the youth, “one would hardly suppose That your eye was as steady as ever; Yet you balanced an eel on the end of your nose— What made you so awfully clever?” “I have answered three questions, and that is enough,” Said his father; “don’t give yourself airs! Do you think I can listen all day to such stuff? Be off, or I’ll kick you down stairs!” “That is not said right,” said the Caterpillar. “Not right, I’m afraid,” said Alice, timidly; “some of the words have got altered.” quite “It is wrong from beginning to end,” said the Caterpillar decidedly, and there was silence for some minutes. The Caterpillar was the first to speak. “What size do you want to be?” it asked. “Oh, I’m not particular as to size,” Alice hastily replied; “only one doesn’t like changing so often, you know.” “I know,” said the Caterpillar. don’t Alice said nothing: she had never been so much contradicted in her life before, and she felt that she was losing her temper. “Are you content now?” said the Caterpillar. “Well, I should like to be a larger, sir, if you wouldn’t mind,” said Alice: “three inches is such a wretched height to be.” little “It is a very good height indeed!” said the Caterpillar angrily, rearing itself upright as it spoke (it was exactly three inches high). “But I’m not used to it!” pleaded poor Alice in a piteous tone. And she thought of herself, “I wish the creatures wouldn’t be so easily offended!” “You’ll get used to it in time,” said the Caterpillar; and it put the hookah into its mouth and began smoking again. This time Alice waited patiently until it chose to speak again. In a minute or two the Caterpillar took the hookah out of its mouth and yawned once or twice, and shook itself. Then it got down off the mushroom, and crawled away in the grass, merely remarking as it went, “One side will make you grow taller, and the other side will make you grow shorter.” “One side of The other side of ” thought Alice to herself. what? what? “Of the mushroom,” said the Caterpillar, just as if she had asked it aloud; and in another moment it was out of sight. Alice remained looking thoughtfully at the mushroom for a minute, trying to make out which were the two sides of it; and as it was perfectly round, she found this a very difficult question. However, at last she stretched her arms round it as far as they would go, and broke off a bit of the edge with each hand. “And now which is which?” she said to herself, and nibbled a little of the right-hand bit to try the effect: the next moment she felt a violent blow underneath her chin: it had struck her foot! She was a good deal frightened by this very sudden change, but she felt that there was no time to be lost, as she was shrinking rapidly; so she set to work at once to eat some of the other bit. Her chin was pressed so closely against her foot, that there was hardly room to open her mouth; but she did it at last, and managed to swallow a morsel of the lefthand bit. *      *      *      *      *      *      * *      *      *      *      *      * *      *      *      *      *      *      * “Come, my head’s free at last!” said Alice in a tone of delight, which changed into alarm in another moment, when she found that her shoulders were nowhere to be found: all she could see, when she looked down, was an immense length of neck, which seemed to rise like a stalk out of a sea of green leaves that lay far below her. “What all that green stuff be?” said Alice. “And where my shoulders got to? And oh, my poor hands, how is it I can’t see you?” She was moving them about as she spoke, but no result seemed to follow, except a little shaking among the distant green leaves. can have As there seemed to be no chance of getting her hands up to her head, she tried to get her head down to them, and was delighted to find that her neck would bend about easily in any direction, like a serpent. She had just succeeded in curving it down into a graceful zigzag, and was going to dive in among the leaves, which she found to be nothing but the tops of the trees under which she had been wandering, when a sharp hiss made her draw back in a hurry: a large pigeon had flown into her face, and was beating her violently with its wings. “Serpent!” screamed the Pigeon. “I’m a serpent!” said Alice indignantly. “Let me alone!” not “Serpent, I say again!” repeated the Pigeon, but in a more subdued tone, and added with a kind of sob, “I’ve tried every way, and nothing seems to suit them!” “I haven’t the least idea what you’re talking about,” said Alice. “I’ve tried the roots of trees, and I’ve tried banks, and I’ve tried hedges,” the Pigeon went on, without attending to her; “but those serpents! There’s no pleasing them!” Alice was more and more puzzled, but she thought there was no use in saying anything more till the Pigeon had finished. “As if it wasn’t trouble enough hatching the eggs,” said the Pigeon; “but I must be on the look-out for serpents night and day! Why, I haven’t had a wink of sleep these three weeks!” “I’m very sorry you’ve been annoyed,” said Alice, who was beginning to see its meaning. “And just as I’d taken the highest tree in the wood,” continued the Pigeon, raising its voice to a shriek, “and just as I was thinking I should be free of them at last, they must needs come wriggling down from the sky! Ugh, Serpent!” “But I’m a serpent, I tell you!” said Alice. “I’m a—I’m a—” not “Well! are you?” said the Pigeon. “I can see you’re trying to invent something!” What “I—I’m a little girl,” said Alice, rather doubtfully, as she remembered the number of changes she had gone through that day. “A likely story indeed!” said the Pigeon in a tone of the deepest contempt. “I’ve seen a good many little girls in my time, but never with such a neck as that! No, no! You’re a serpent; and there’s no use denying it. I suppose you’ll be telling me next that you never tasted an egg!” one “I tasted eggs, certainly,” said Alice, who was a very truthful child; “but little girls eat eggs quite as much as serpents do, you know.” have “I don’t believe it,” said the Pigeon; “but if they do, why then they’re a kind of serpent, that’s all I can say.” This was such a new idea to Alice, that she was quite silent for a minute or two, which gave the Pigeon the opportunity of adding, “You’re looking for eggs, I know well enough; and what does it matter to me whether you’re a little girl or a serpent?” that “It matters a good deal to ,” said Alice hastily; “but I’m not looking for eggs, as it happens; and if I was, I shouldn’t want : I don’t like them raw.” me yours “Well, be off, then!” said the Pigeon in a sulky tone, as it settled down again into its nest. Alice crouched down among the trees as well as she could, for her neck kept getting entangled among the branches, and every now and then she had to stop and untwist it. After a while she remembered that she still held the pieces of mushroom in her hands, and she set to work very carefully, nibbling first at one and then at the other, and growing sometimes taller and sometimes shorter, until she had succeeded in bringing herself down to her usual height. It was so long since she had been anything near the right size, that it felt quite strange at first; but she got used to it in a few minutes, and began talking to herself, as usual. “Come, there’s half my plan done now! How puzzling all these changes are! I’m never sure what I’m going to be, from one minute to another! However, I’ve got back to my right size: the next thing is, to get into that beautiful garden—how that to be done, I wonder?” As she said this, she came suddenly upon an open place, with a little house in it about four feet high. “Whoever lives there,” thought Alice, “it’ll never do to come upon them size: why, I should frighten them out of their wits!” So she began nibbling at the righthand bit again, and did not venture to go near the house till she had brought herself down to nine inches high. is this About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Lewis Carroll (2008). Alice in Wonderland. Urbana, Illinois: Project Gutenberg. Retrieved https://www.gutenberg.org/cache/epub/11/pg11-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at , located at www.gutenberg.org https://www.gutenberg.org/policy/license.html.

Advice from a Caterpillar

A Comprehensive Guide for Building Efficient Data Structures in Dart

As app developers, we're not just coders – we're creators, builders, and sometimes, illusionists. The art of app development goes beyond just code and design. Sometimes, it's about crafting an element of surprise and illusion that captures users' attention and creates an immersive experience. This time around, we're stepping out of our comfort zone of the 2D world, and taking a bold leap into the captivating world of . 3D UIKit is more than a set of tools for building user interfaces. It's a powerful toolkit that, when used right, can create amazing visual effects. In this article, we'll dig deep into UIKit and showcase a technique to create a mirror-like reflection. This effect can give your app a visually impressive and engaging look that typically seems achievable only with complex graphical tools, yet it's crafted with nothing but code. The end result Check out this beautiful, shiny cube. It will never rust, as it doesn't use any Metal. Now, let's learn how to create it using code. Some basics first For our purposes, UIKit serves as a slim layer atop Quartz Core, providing us with free access to its 3D capabilities. A holds a reference to a object, which is the actual component the OS uses for on-screen rendering. There are three properties of that influence its on-screen presentation: position, bounds, and transform. The first two are fairly self-explanatory, while can be initialized with any arbitrary 4x4 matrix. When multiple 3D layers need to be presented simultaneously, we must employ a specialized CATransformLayer, which uniquely preserves the 3D space of its child layers instead of flattening them onto a 2D plane. UIView CALayer CALayer transform A cube Let's begin by drawing a simple cube. First, we'll create a helper function to adjust the position of each side: func setupFace(
    layer: CALayer,
    size: CGFloat,
    baseTransform: CATransform3D,
    translation: (x: CGFloat, y: CGFloat, z: CGFloat),
    rotation: (angle: CGFloat, x: CGFloat, y: CGFloat, z: CGFloat)
) {
    layer.bounds = CGRect(origin: CGPoint(), size: CGSize(width: size, height: size))
    
    var transform = baseTransform
    transform = CATransform3DTranslate(transform, translation.x, translation.y, translation.z)
    transform = CATransform3DRotate(transform, rotation.angle, rotation.x, rotation.y, rotation.z)
    layer.transform = transform
} Next, in the body of our ViewController's function, we will assemble all six sides of the cube: viewDidLoad let cubeLayer = CATransformLayer()
cubeLayer.position = CGPoint(x: view.bounds.midX, y: view.bounds.midY)
view.layer.addSublayer(cubeLayer)

let cubeSize: CGFloat = 200.0

var baseTransform = CATransform3DIdentity
baseTransform = CATransform3DRotate(baseTransform, 0.5, 0.0, 1.0, 0.0)
baseTransform = CATransform3DRotate(baseTransform, -0.5, 1.0, 0.0, 0.0)

let frontFace = CALayer()
frontFace.isDoubleSided = false
frontFace.backgroundColor = UIColor.blue.cgColor
setupFace(layer: frontFace, size: cubeSize, baseTransform: baseTransform, translation: (0.0, 0.0, cubeSize * 0.5), rotation: (0.0, 0.0, 1.0, 0.0))
cubeLayer.addSublayer(frontFace)

let backFace = CALayer()
backFace.isDoubleSided = false
backFace.backgroundColor = UIColor.red.cgColor
setupFace(layer: backFace, size: cubeSize, baseTransform: baseTransform, translation: (0.0, 0.0, -cubeSize * 0.5), rotation: (-.pi, 0.0, 1.0, 0.0))
cubeLayer.addSublayer(backFace)

let leftFace = CALayer()
leftFace.isDoubleSided = false
leftFace.backgroundColor = UIColor.green.cgColor
setupFace(layer: leftFace, size: cubeSize, baseTransform: baseTransform, translation: (-cubeSize * 0.5, 0.0, 0.0), rotation: (-.pi * 0.5, 0.0, 1.0, 0.0))
cubeLayer.addSublayer(leftFace)

let rightFace = CALayer()
rightFace.isDoubleSided = false
rightFace.backgroundColor = UIColor.yellow.cgColor
setupFace(layer: rightFace, size: cubeSize, baseTransform: baseTransform, translation: (cubeSize * 0.5, 0.0, 0.0), rotation: (.pi * 0.5, 0.0, 1.0, 0.0))
cubeLayer.addSublayer(rightFace)

let topFace = CALayer()
topFace.isDoubleSided = false
topFace.backgroundColor = UIColor.cyan.cgColor
setupFace(layer: topFace, size: cubeSize, baseTransform: baseTransform, translation: (0.0, -cubeSize * 0.5, 0.0), rotation: (.pi * 0.5, 1.0, 0.0, 0.0))
cubeLayer.addSublayer(topFace)

let bottomFace = CALayer()
bottomFace.isDoubleSided = false
bottomFace.backgroundColor = UIColor.gray.cgColor
setupFace(layer: bottomFace, size: cubeSize, baseTransform: baseTransform, translation: (0.0, cubeSize * 0.5, 0.0), rotation: (-.pi * 0.5, 1.0, 0.0, 0.0))
cubeLayer.addSublayer(bottomFace) Here's what this code looks like in action: It's undeniably 3D, but something feels off, doesn't it? The concept of 3D perspective in art was first mastered by Italian Renaissance painters in the 15th century. Fortunately, we can achieve a similar effect by just using a perspective projection matrix: var baseTransform = CATransform3DIdentity
baseTransform.m34 = -1.0 / 400.0
baseTransform = CATransform3DRotate(baseTransform, 0.5, 0.0, 1.0, 0.0)
baseTransform = CATransform3DRotate(baseTransform, -0.5, 1.0, 0.0, 0.0) Now let’s look at the result: Better, isn’t it? The term at m34 is what creates the perspective effect. For the actual math, see -1.0 / 400.0 https://www.scratchapixel.com/lessons/3d-basic-rendering/perspective-and-orthographic-projection-matrix/building-basic-perspective-projection-matrix.html Mapping the environment Our goal is to demonstrate a mirror effect, so we'll need something to reflect. In 3D graphics, cube maps are commonly used to simulate reflective surfaces. In our example, we can create one using the actual cube we made earlier. First, we assign images to the corresponding faces: frontFace.contents = UIImage(named: "front")?.cgImage
backFace.contents = UIImage(named: "back")?.cgImage
leftFace.contents = UIImage(named: "left")?.cgImage
rightFace.contents = UIImage(named: "right")?.cgImage
topFace.contents = UIImage(named: "up")?.cgImage
bottomFace.contents = UIImage(named: "down")?.cgImage Next, for every face, we set and increase the size of the cube to . This essentially places the "camera" inside the cube: isDoubleSided = true cubeSize: CGFloat = 2000.0 Next, since we're going to create several cubes at once, let's simplify the setup functions: enum CubeFace: CaseIterable {
    case front
    case back
    case left
    case right
    case top
    case bottom

    func translationAndRotation(size: CGFloat) -> (translation: (x: CGFloat, y: CGFloat, z: CGFloat), rotation: (angle: CGFloat, x: CGFloat, y: CGFloat, z: CGFloat)) {
        switch self {
        case .front:
            return ((0.0, 0.0, size * 0.5), (0.0, 0.0, 1.0, 0.0))
        case .back:
            return ((0.0, 0.0, -size * 0.5), (-.pi, 0.0, 1.0, 0.0))
        case .left:
            return ((-size * 0.5, 0.0, 0.0), (-.pi * 0.5, 0.0, 1.0, 0.0))
        case .right:
            return ((size * 0.5, 0.0, 0.0), (.pi * 0.5, 0.0, 1.0, 0.0))
        case .top:
            return ((0.0, -size * 0.5, 0.0), (.pi * 0.5, 1.0, 0.0, 0.0))
        case .bottom:
            return ((0.0, size * 0.5, 0.0), (-.pi * 0.5, 1.0, 0.0, 0.0))
        }
    }
    
    func texture() -> UIImage? {
        ...
    }
    
    func color() -> UIColor {
        ...
    }
}

func setupFace(
    layer: CALayer,
    size: CGFloat,
    baseTransform: CATransform3D,
    face: CubeFace,
    textured: Bool
) {
    layer.bounds = CGRect(origin: CGPoint(), size: CGSize(width: size, height: size))
    layer.isDoubleSided = textured
    
    let (translation, rotation) = face.translationAndRotation(size: size)
    var transform = baseTransform
    transform = CATransform3DTranslate(transform, translation.x, translation.y, translation.z)
    transform = CATransform3DRotate(transform, rotation.angle, rotation.x, rotation.y, rotation.z)
    layer.transform = transform
    
    if textured {
        layer.contents = face.texture()?.cgImage
    } else {
        layer.backgroundColor = face.color().cgColor
    }
}

func setupCube(
    view: UIView,
    size: CGFloat,
    textured: Bool,
    baseTransform: CATransform3D,
    faces: [CubeFace]
) -> CATransformLayer {
    let cubeLayer = CATransformLayer()
    cubeLayer.position = CGPoint(x: view.bounds.midX, y: view.bounds.midY)
    
    for face in faces {
        let faceLayer = CALayer()
        setupFace(layer: faceLayer, size: size, baseTransform: baseTransform, face: face, textured: textured)
        cubeLayer.addSublayer(faceLayer)
    }
    
    return cubeLayer
} Now, let's render both the cube map and a small cube simultaneously: var baseTransform = CATransform3DIdentity
baseTransform.m34 = -1.0 / 400.0
baseTransform = CATransform3DRotate(baseTransform, 0.5, 0.0, 1.0, 0.0)

view.layer.addSublayer(setupCube(view: view, size: 2000.0, textured: true, baseTransform: baseTransform))
view.layer.addSublayer(setupCube(view: view, size: 100.0, textured: false, baseTransform: baseTransform)) Reflections UIKit is a robust framework, yet it lacks built-in features for complex visual effects. However, it does offer the ability to apply arbitrary masks to objects, and that's precisely what we're going to exploit to create the mirror effect. Essentially, we will render the environment six times, each masked by the corresponding cube face. The tricky aspect is that we can't directly mask a . However, we can circumvent this limitation by nesting it inside a container: CATransformLayer CALayer func setupReflectiveFace(
    view: UIView,
    size: CGFloat,
    baseTransform: CATransform3D,
    face: CubeFace
) -> CALayer {
    let maskLayer = CALayer()
    maskLayer.frame = view.bounds
    maskLayer.addSublayer(setupCube(view: view, size: size, textured: false, baseTransform: baseTransform, faces: [face]))
    
    let colorLayer = CALayer()
    colorLayer.frame = view.bounds
    colorLayer.mask = maskLayer
    colorLayer.addSublayer(setupCube(view: view, size: 2000.0, textured: true, baseTransform: baseTransform, faces: [.front, .back, .left, .right, .top, .bottom]))
    
    return colorLayer
} And now, our viewDidLoad should look like this: var baseTransform = CATransform3DIdentity
baseTransform.m34 = -1.0 / 400.0
baseTransform = CATransform3DRotate(baseTransform, 0.5, 0.0, 1.0, 0.0)

for face in CubeFace.allCases {
    view.layer.addSublayer(setupReflectiveFace(view: view, size: 100.0, baseTransform: baseTransform, face: face))
} This image already closely resembles what we intended to achieve, but at this point, the cube is merely a 3D-esque mask over the cube map. So, how do we transform it into an actual mirror? The Mirror Dimension It turns out there's a straightforward method to mirror the world relative to an arbitrary plane in 3D space. Without delving into complex , this is the matrix we're seeking: mathematics func mirrorMatrix(planePoint: Vector4D, planeTransform: CATransform3D, planeNormal: Vector4D) -> CATransform3D {
    let pt = applyTransform(transform: planeTransform, point: planePoint)
    
    let normalTransform = CATransform3DInvert(planeTransform).transposed
    let normal = applyTransform(transform: normalTransform, point: planeNormal).normalized()
    
    let a = normal.x
    let b = normal.y
    let c = normal.z
    let d = -(a * pt.x + b * pt.y + c * pt.z)
    
    return CATransform3D([
        1 - 2 * a * a, -2 * a * b, -2 * a * c, -2 * a * d,
        -2 * a * b, 1 - 2 * b * b, -2 * b * c, -2 * b * d,
        -2 * a * c, -2 * b * c, 1 - 2 * c * c, -2 * c * d,
        0.0, 0.0, 0.0, 1.0
    ]).transposed
} Next, we incorporate the following code into the cube setup function: func setupCube(
    view: UIView,
    size: CGFloat,
    textured: Bool,
    baseTransform: CATransform3D,
    faces: [CubeFace],
    mirrorFace: CubeFace? = nil
) -> CATransformLayer {
    ...
    if let mirrorFace {
        let mirrorPlane = mirrorFace.transform(size: size, baseTransform: baseTransform)
        let mirror = mirrorMatrix(planePoint: Vector4D(x: 0.0, y: 0.0, z: 0.0, w: 1.0), planeTransform: mirrorPlane, planeNormal: Vector4D(x: 0.0, y: 0.0, z: 1.0, w: 1.0))
        cubeLayer.sublayerTransform = mirror
    }
} And finally, we can behold the shiny cube we've been striving for: Why UIKit? Sure, achieving the same effect might seem easier with Metal or a Metal-based framework like SceneKit. But those come with their own set of limits. The big one? You can't bring live UIKit views into the 3D content drawn by Metal. The method we've looked at in this article lets us display all sorts of content in a 3D setting. This includes maps, videos, and interactive views. Plus, it can smoothly blend with any UIKit animations you might want to use. The source code for this article, along with some helper functions, can be found at https://github.com/petertechstories/uikit-mirrors Happy coding!

Smoke and Mirrors in Pure UIKit

বিশুদ্ধ UIKit-এ ধোঁয়া ও আয়না

Rauch und Spiegel in Pure UIKit

Humo y espejos en UIKit puro

Fumée et miroirs dans Pure UIKit

शुद्ध UIKit में धुआँ और दर्पण

Pure UIKit の煙とミラー

Pure UIKit의 연기와 거울

Fumaça e espelhos em Pure UIKit

Pure UIKit'te Duman ve Aynalar

Khói và Gương trong Pure UIKit

纯 UIKit 中的烟雾和镜子

At the Earth's Core by Edgar Rice Burroughs, is part of the HackerNoon Books Series. You can jump to any chapter in this book here . THE SLY ONE THE SLY ONE THE SAGOTHS WERE GAINING ON US RAPIDLY, FOR once they had sighted us they had greatly increased their speed. On and on we stumbled up the narrow canyon that Ghak had chosen to approach the heights of Sari. On either side rose precipitous cliffs of gorgeous, parti-colored rock, while beneath our feet a thick mountain grass formed a soft and noiseless carpet. Since we had entered the canyon we had had no glimpse of our pursuers, and I was commencing to hope that they had lost our trail and that we would reach the now rapidly nearing cliffs in time to scale them before we should be overtaken. Ahead we neither saw nor heard any sign which might betoken the success of Hooja's mission. By now he should have reached the outposts of the Sarians, and we should at least hear the savage cries of the tribesmen as they swarmed to arms in answer to their king's appeal for succor. In another moment the frowning cliffs ahead should be black with primeval warriors. But nothing of the kind happened—as a matter of fact the Sly One had betrayed us. At the moment that we expected to see Sarian spearmen charging to our relief at Hooja's back, the craven traitor was sneaking around the outskirts of the nearest Sarian village, that he might come up from the other side when it was too late to save us, claiming that he had become lost among the mountains. Hooja still harbored ill will against me because of the blow I had struck in Dian's protection, and his malevolent spirit was equal to sacrificing us all that he might be revenged upon me. As we drew nearer the barrier cliffs and no sign of rescuing Sarians appeared Ghak became both angry and alarmed, and presently as the sound of rapidly approaching pursuit fell upon our ears, he called to me over his shoulder that we were lost. A backward glance gave me a glimpse of the first of the Sagoths at the far end of a considerable stretch of canyon through which we had just passed, and then a sudden turning shut the ugly creature from my view; but the loud howl of triumphant rage which rose behind us was evidence that the gorilla-man had sighted us. Again the canyon veered sharply to the left, but to the right another branch ran on at a lesser deviation from the general direction, so that appeared more like the main canyon than the lefthand branch. The Sagoths were now not over two hundred and fifty yards behind us, and I saw that it was hopeless for us to expect to escape other than by a ruse. There was a bare chance of saving Ghak and Perry, and as I reached the branching of the canyon I took the chance. Pausing there I waited until the foremost Sagoth hove into sight. Ghak and Perry had disappeared around a bend in the left-hand canyon, and as the Sagoth's savage yell announced that he had seen me I turned and fled up the right-hand branch. My ruse was successful, and the entire party of man-hunters raced headlong after me up one canyon while Ghak bore Perry to safety up the other. Running has never been my particular athletic forte, and now when my very life depended upon fleetness of foot I cannot say that I ran any better than on the occasions when my pitiful base running had called down upon my head the rooter's raucous and reproachful cries of "Ice Wagon," and "Call a cab." The Sagoths were gaining on me rapidly. There was one in particular, fleeter than his fellows, who was perilously close. The canyon had become a rocky slit, rising roughly at a steep angle toward what seemed a pass between two abutting peaks. What lay beyond I could not even guess—possibly a sheer drop of hundreds of feet into the corresponding valley upon the other side. Could it be that I had plunged into a cul-de-sac? Realizing that I could not hope to outdistance the Sagoths to the top of the canyon I had determined to risk all in an attempt to check them temporarily, and to this end had unslung my rudely made bow and plucked an arrow from the skin quiver which hung behind my shoulder. As I fitted the shaft with my right hand I stopped and wheeled toward the gorilla-man. In the world of my birth I never had drawn a shaft, but since our escape from Phutra I had kept the party supplied with small game by means of my arrows, and so, through necessity, had developed a fair degree of accuracy. During our flight from Phutra I had restrung my bow with a piece of heavy gut taken from a huge tiger which Ghak and I had worried and finally dispatched with arrows, spear, and sword. The hard wood of the bow was extremely tough and this, with the strength and elasticity of my new string, gave me unwonted confidence in my weapon. Never had I greater need of steady nerves than then—never were my nerves and muscles under better control. I sighted as carefully and deliberately as though at a straw target. The Sagoth had never before seen a bow and arrow, but of a sudden it must have swept over his dull intellect that the thing I held toward him was some sort of engine of destruction, for he too came to a halt, simultaneously swinging his hatchet for a throw. It is one of the many methods in which they employ this weapon, and the accuracy of aim which they achieve, even under the most unfavorable circumstances, is little short of miraculous. My shaft was drawn back its full length—my eye had centered its sharp point upon the left breast of my adversary; and then he launched his hatchet and I released my arrow. At the instant that our missiles flew I leaped to one side, but the Sagoth sprang forward to follow up his attack with a spear thrust. I felt the swish of the hatchet as it grazed my head, and at the same instant my shaft pierced the Sagoth's savage heart, and with a single groan he lunged almost at my feet—stone dead. Close behind him were two more—fifty yards perhaps—but the distance gave me time to snatch up the dead guardsman's shield, for the close call his hatchet had just given me had borne in upon me the urgent need I had for one. Those which I had purloined at Phutra we had not been able to bring along because their size precluded our concealing them within the skins of the Mahars which had brought us safely from the city. With the shield slipped well up on my left arm I let fly with another arrow, which brought down a second Sagoth, and then as his fellow's hatchet sped toward me I caught it upon the shield, and fitted another shaft for him; but he did not wait to receive it. Instead, he turned and retreated toward the main body of gorilla-men. Evidently he had seen enough of me for the moment. Once more I took up my flight, nor were the Sagoths apparently overanxious to press their pursuit so closely as before. Unmolested I reached the top of the canyon where I found a sheer drop of two or three hundred feet to the bottom of a rocky chasm; but on the left a narrow ledge rounded the shoulder of the overhanging cliff. Along this I advanced, and at a sudden turning, a few yards beyond the canyon's end, the path widened, and at my left I saw the opening to a large cave. Before, the ledge continued until it passed from sight about another projecting buttress of the mountain. Here, I felt, I could defy an army, for but a single foeman could advance upon me at a time, nor could he know that I was awaiting him until he came full upon me around the corner of the turn. About me lay scattered stones crumbled from the cliff above. They were of various sizes and shapes, but enough were of handy dimensions for use as ammunition in lieu of my precious arrows. Gathering a number of stones into a little pile beside the mouth of the cave I waited the advance of the Sagoths. As I stood there, tense and silent, listening for the first faint sound that should announce the approach of my enemies, a slight noise from within the cave's black depths attracted my attention. It might have been produced by the moving of the great body of some huge beast rising from the rock floor of its lair. At almost the same instant I thought that I caught the scraping of hide sandals upon the ledge beyond the turn. For the next few seconds my attention was considerably divided. And then from the inky blackness at my right I saw two flaming eyes glaring into mine. They were on a level that was over two feet above my head. It is true that the beast who owned them might be standing upon a ledge within the cave, or that it might be rearing up upon its hind legs; but I had seen enough of the monsters of Pellucidar to know that I might be facing some new and frightful Titan whose dimensions and ferocity eclipsed those of any I had seen before. Whatever it was, it was coming slowly toward the entrance of the cave, and now, deep and forbidding, it uttered a low and ominous growl. I waited no longer to dispute possession of the ledge with the thing which owned that voice. The noise had not been loud—I doubt if the Sagoths heard it at all—but the suggestion of latent possibilities behind it was such that I knew it would only emanate from a gigantic and ferocious beast. As I backed along the ledge I soon was past the mouth of the cave, where I no longer could see those fearful flaming eyes, but an instant later I caught sight of the fiendish face of a Sagoth as it warily advanced beyond the cliff's turn on the far side of the cave's mouth. As the fellow saw me he leaped along the ledge in pursuit, and after him came as many of his companions as could crowd upon each other's heels. At the same time the beast emerged from the cave, so that he and the Sagoths came face to face upon that narrow ledge. The thing was an enormous cave bear, rearing its colossal bulk fully eight feet at the shoulder, while from the tip of its nose to the end of its stubby tail it was fully twelve feet in length. As it sighted the Sagoths it emitted a most frightful roar, and with open mouth charged full upon them. With a cry of terror the foremost gorilla-man turned to escape, but behind him he ran full upon his on-rushing companions. The horror of the following seconds is indescribable. The Sagoth nearest the cave bear, finding his escape blocked, turned and leaped deliberately to an awful death upon the jagged rocks three hundred feet below. Then those giant jaws reached out and gathered in the next—there was a sickening sound of crushing bones, and the mangled corpse was dropped over the cliff's edge. Nor did the mighty beast even pause in his steady advance along the ledge. Shrieking Sagoths were now leaping madly over the precipice to escape him, and the last I saw he rounded the turn still pursuing the demoralized remnant of the man hunters. For a long time I could hear the horrid roaring of the brute intermingled with the screams and shrieks of his victims, until finally the awful sounds dwindled and disappeared in the distance. Later I learned from Ghak, who had finally come to his tribesmen and returned with a party to rescue me, that the ryth, as it is called, pursued the Sagoths until it had exterminated the entire band. Ghak was, of course, positive that I had fallen prey to the terrible creature, which, within Pellucidar, is truly the king of beasts. Not caring to venture back into the canyon, where I might fall prey either to the cave bear or the Sagoths I continued on along the ledge, believing that by following around the mountain I could reach the land of Sari from another direction. But I evidently became confused by the twisting and turning of the canyons and gullies, for I did not come to the land of Sari then, nor for a long time thereafter. About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Edgar Rice Burroughs (1994). At the Earth's Core. Urbana, Illinois: Project Gutenberg. Retrieved October 2022 https://www.gutenberg.org/cache/epub/123/pg123-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at www.gutenberg.org , located at https://www.gutenberg.org/policy/license.html.

THE SLY ONE

In this part of creating your own programming language, we’ll continue improving our language by implementing nested classes and slightly upgrading the classes introduced in the previous part. Please check out the previous parts: Building Your Own Programming Language From Scratch Building Your Own Programming Language From Scratch: Part II - Dijkstra's Two-Stack Algorithm Build Your Own Programming Language Part III: Improving Lexical Analysis with Regex Lookaheads Building Your Own Programming Language From Scratch Part IV: Implementing Functions Building Your Own Programming Language From Scratch: Part V - Arrays Building Your Own Programming Language From Scratch: Part VI - Loops Building Your Own Programming Language From Scratch: Part VII - Classes The full source code is available . over on GitHub 1 Lexical Analysis In the first section, we will cover lexical analysis. In short, it’s a process to divide the source code into language lexemes, such as keyword, variable, operator, etc. You may remember from the previous parts that I was using the regex expressions listed in the enum to define all the lexeme types: TokenType package org.example.toylanguage.token;

public enum TokenType {
    Comment("\\#.*"),
    LineBreak("[\\n\\r]"),
    Whitespace("[\\s\\t]"),
    Keyword("(if|elif|else|end|print|input|class|fun|return|loop|in|by|break|next)(?=\\s|$)"),
    GroupDivider("(\\[|\\]|\\,|\\{|}|[.]{2})"),
    Logical("(true|false)(?=\\s|$)"),
    Numeric("([-]?(?=[.]?[0-9])[0-9]*(?![.]{2})[.]?[0-9]*)"),
    Null("(null)(?=,|\\s|$)"),
    This("(this)(?=,|\\s|$)"),
    Text("\"([^\"]*)\""),
    Operator("(\\+|-|\\*|/{1,2}|%|>=|>|<=|<{1,2}|={1,2}|!=|!|:{2}|\$|\$|(new|and|or)(?=\\s|$))"),
    Variable("[a-zA-Z_]+[a-zA-Z0-9_]*");

    private final String regex;
} Let’s look into this nested classes prototype, and add the missing regex expressions into our lexemes: TokenType When we create an instance of a nested class, we use the following construction with two expressions and one operator between them: The left expression is an instance of the class we are referring to get a nested class from. The right expression is a nested class with the properties to create an instance. class_instance NestedClass [args] Lastly, as an operator to create a nested class, I’ll be using the following expression: , meaning that we refer to the class instance property with the two colon operator, and then we create an instance with the operator. :: new :: new With the current set of lexemes, we only need to add a regular expression for the operator. This operator can be validated by the following regex expression: :: new :{2}\\s+new Let’s add this expression in the lexeme as OR expression before the part standing for accessing class property: Operator :{2} public enum TokenType {
    ...
    Operator("(\\+|-|\\*|/{1,2}|%|>=|>|<=|<{1,2}|={1,2}|!=|!|:{2}\\s+new|:{2}|\$|\$|(new|and|or)(?=\\s|$))"),
    ...
} 2 Syntax Analysis In the second section, we will convert lexemes received from the lexical analyzer into the final statements following our language rules. 2.1 OperatorExpression To evaluate math expressions, we’re using . Each operation in this algorithm can be presented by a unary operator with one operand or by a binary operator with respectively two operands: Dijkstra's Two-Stack algorithm Nested class’s instantiation is a binary operation where the left operand is a class instance we use to refer to the class where the nested class is defined, and the second operand is a nested class we create an instance of: Let’s create the implementation by extending NestedClassInstanceOperator : BinaryOperatorExpression package org.example.toylanguage.expression.operator;

public class NestedClassInstanceOperator extends BinaryOperatorExpression {
    public NestedClassInstanceOperator(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    public Value<?> evaluate() {
        ...
    }
} Next, we should complete the method that will perform nested class instantiation: evaluate() First, we evaluate the left operand’s expression into the expression: Value @Override
public Value<?> evaluate() {
    // ClassExpression -> ClassValue
    Value<?> left = getLeft().evaluate();
} Next, we need to the right operand. In this case, we can't directly invoke because the nested classes' definitions are declared in the parent class's DefinitionScope (in the left operand). evaluate() Expression#evaluate() To access the definitions of nested classes, we should create an auxiliary method that will take the left operand and use its DefinitionScope to access the nested class definition and create an instance of: ClassExpression#evaluate(ClassValue) @Override
public Value<?> evaluate() {
    Value<?> left = getLeft().evaluate();

    if (left instanceof ClassValue && getRight() instanceof ClassExpression) {
        // instantiate nested class
        // new Class [] :: new NestedClass []
        return ((ClassExpression) getRight()).evaluate((ClassValue) left);
    } else {
        throw new ExecutionException(String.format("Unable to access class's nested class `%s``", getRight()));
    }
} Lastly, let’s implement the missing method. ClassExpression#evaluate(ClassValue) This implementation will be similar to the method with the only difference being that we should set the in order to retrieve nested class definitions: ClassExpression#evaluate() ClassDefinition#getDefinitionScope() package org.example.toylanguage.expression;

…
public class ClassExpression implements Expression {
    private final String name;
    private final List<Expression> argumentExpressions;

    @Override
    public Value<?> evaluate() {
        //initialize class arguments
        List<Value<?>> values = argumentExpressions.stream().map(Expression::evaluate).collect(Collectors.toList());
        return evaluate(values);
    }

    /**
     * Evaluate nested class
     *
     * @param classValue instance of the parent class
     */
    public Value<?> evaluate(ClassValue classValue) {
        //initialize class arguments
        List<Value<?>> values = argumentExpressions.stream().map(Expression::evaluate).collect(Collectors.toList());

        //set parent class's definition
        ClassDefinition classDefinition = classValue.getValue();
        DefinitionContext.pushScope(classDefinition.getDefinitionScope());

        try {
            return evaluate(values);
        } finally {
            DefinitionContext.endScope();
        }
    }

    private Value<?> evaluate(List<Value<?>> values) {
        //get class's definition and statement
        ClassDefinition definition = DefinitionContext.getScope().getClass(name);
        ClassStatement classStatement = definition.getStatement();

        //set separate scope
        MemoryScope classScope = new MemoryScope(null);
        MemoryContext.pushScope(classScope);

        try {
            //initialize constructor arguments
            ClassValue classValue = new ClassValue(definition, classScope);
            ClassInstanceContext.pushValue(classValue);
            IntStream.range(0, definition.getArguments().size()).boxed()
                    .forEach(i -> MemoryContext.getScope()
                            .setLocal(definition.getArguments().get(i), values.size() > i ? values.get(i) : NullValue.NULL_INSTANCE));

            //execute function body
            DefinitionContext.pushScope(definition.getDefinitionScope());
            try {
                classStatement.execute();
            } finally {
                DefinitionContext.endScope();
            }

            return classValue;
        } finally {
            MemoryContext.endScope();
            ClassInstanceContext.popValue();
        }
    }
} 2.2 Operator All the operators we’re using to evaluate math expressions are stored in the enum with the corresponding precedence, character, and type that we refer to calculate the result of each operation: Operator OperatorExpression ...
public enum Operator {
    Not("!", NotOperator.class, 7),
    ClassInstance("new", ClassInstanceOperator.class, 7),
    ...

    private final String character;
    private final Class<? extends OperatorExpression> type;
    private final Integer precedence;

    Operator(String character, Class<? extends OperatorExpression> type, Integer precedence) {
        this.character = character;
        this.type = type;
        this.precedence = precedence;
    }

    public static Operator getType(String character) {
        return Arrays.stream(values())
                .filter(t -> Objects.equals(t.getCharacter(), character))
                .findAny().orElse(null);
    }
    ...
} We already have the value for a regular class’s initialization. Let’s add a new value to manage nested class instances. ClassInstance The new value will have the same character expression as we defined in the earlier and the same precedence as the regular class's instance. NestedClassInstance TokenType For the OperatorExpression type, we will use the previously defined : NestedClassInstanceOperator ...
public enum Operator {
    Not("!", NotOperator.class, 7),
    ClassInstance("new", ClassInstanceOperator.class, 7),
    NestedClassInstance(":{2}\\s+new", NestedClassInstanceOperator.class, 7),
    ...
} You may notice that we don’t have regex expressions in the character property except for this new operator. To read the operator using a regex expression, we should update the method to match an operator with a regular expression: NestedClassInstance Operator#getType() public enum Operator {
    ...
    public static Operator getType(String character) {
        return Arrays.stream(values())
                .filter(t -> character.matches(t.getCharacter()))
                .findAny().orElse(null);
    }
    ...
} Lastly, we should add two backslashes before a character for operations containing the following symbols: to make sure these characters are not treated as regex search symbols: \\ +, *, (, ) Multiplication("\\*", MultiplicationOperator.class, 6),
Addition("\\+", AdditionOperator.class, 5),
LeftParen("\$", 3),
RightParen("\$", 3), After we introduced the operator, we should inject it into the class that actually parses math expressions into operands and operators. We just need to find the line where we read the class instance: NestedClassInstance ExpressionReader if (!operators.isEmpty() && operators.peek() == Operator.ClassInstance) {
    operand = readClassInstance(token);
} To support reading the operator, we add the corresponding condition for the current operator in the operator’s stack: NestedClassInstance if (!operators.isEmpty() && (operators.peek() == Operator.ClassInstance || operators.peek() == Operator.NestedClassInstance)) {
    operand = readClassInstance(token);
} The method will read a nested class's declaration with properties the same way it reads a regular class declaration. This method returns instance as a whole operand expression. readClassInstance() ClassExpression 3. Wrap Up Everything is ready now. In this part, we implemented nested classes as one more step toward making a complete programming language.

Building Your Own Programming Language From Scratch: Part VIII - Nested Classes

Construyendo su propio lenguaje de programación desde cero: Parte VIII - Clases anidadas

Construire votre propre langage de programmation à partir de zéro : Partie VIII - Classes imbriquées

स्क्रैच से अपनी खुद की प्रोग्रामिंग लैंग्वेज बनाना: भाग VIII - नेस्टेड क्लासेस

ゼロから独自のプログラミング言語を構築する: パート VIII - ネストされたクラス

Construindo sua própria linguagem de programação do zero: Parte VIII - Classes aninhadas

Xây dựng ngôn ngữ lập trình của riêng bạn từ đầu: Phần VIII - Các lớp lồng nhau

从头开始构建您自己的编程语言：第八部分 - 嵌套类

Stolen Brains

cerebros robados

Cerveaux volés

चोरी दिमाग

盗まれた頭脳

cérebros roubados

bộ não bị đánh cắp

偷来的大脑

Big O Notation, collectively called Bachmann-Landau notation or asymptotic notation, is a way to describe the performance of an algorithm. It is used to describe the worst-case scenario of an algorithm. It is used to compare the performance of different algorithms. It describes the implementation of an algorithm in terms of the input size. Big O notation characterizes functions according to their growth rates: tasks with the same growth rate are considered to be of the same order. It is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify algorithms according to how their run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also called its order. Iteration For loop for (let i = 0; i < n; i++) {
  console.log(i)
} The above code will run n times. The time complexity of this code is O(n). While loop let i = 0
while (i < n) {
  console.log(i)
  i++
} The above code will run n times. The time complexity of this code is O(n). Do while loop let i = 0
do {
  console.log(i)
  i++
} while (i < n) The above code will run n times. The time complexity of this code is O(n). Recursion Factorial function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
} The above code will run n times. The time complexity of this code is O(n). Fibonacci function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
} The above code will run n times. The time complexity of this code is O(n). Searching Linear search function linearSearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return i
    }
  }
  return -1
} The above code will run n times. The time complexity of this code is O(n). Binary search function binarySearch(arr, value) {
  let start = 0
  let end = arr.length - 1
  let middle = Math.floor((start + end) / 2)
  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1
    } else {
      start = middle + 1
    }
    middle = Math.floor((start + end) / 2)
  }
  if (arr[middle] === value) {
    return middle
  }
  return -1
} The above code will run log(n) times. The time complexity of this code is O(log(n)). Sorting Bubble sort function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Selection sort function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      let temp = arr[i]
      arr[i] = arr[lowest]
      arr[lowest] = temp
    }
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Insertion sort function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
  }
  return arr
} The above code will run n^2 times. The time complexity of this code is O(n^2). Merge sort function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  let results = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      results.push(left[i])
      i++
    } else {
      results.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    results.push(left[i])
    i++
  }
  while (j < right.length) {
    results.push(right[j])
    j++
  }
  return results
} The above code will run n log(n) times. The time complexity of this code is O(n log(n)). Quick sort function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start]
  let swapIdx = start
  function swap(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
  }
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++
      swap(arr, swapIdx, i)
    }
  }
  swap(arr, start, swapIdx)
  return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
} The above code will run n log(n) times. The time complexity of this code is O(n log(n)). Tips for Big O Arithmetic operations are constant Variable assignment is constant Accessing elements in an array (by index) or object (by key) is constant In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop Resources Big O Cheat Sheet Big O Notation Big O Notation Originally published . here

The Big O Notation in JavaScript

Description of the Situation: We have an arbitrary binary tree, a node of that tree, and also an integer: 'K.' We need to print all such nodes which have a distance K from the given node and return the list of these nodes. You can check out this problem here as well: . Print Nodes at Distance k from Node The distance between the two nodes in a binary tree is defined as the number of connections/edges in the path between the two nodes. Let’s see an example: Let's examine the tree shown in the diagram: = pointer to node with data 8. Inputs: target = pointer to node with data 20. root k = 2. 10 14 22 Output : If the target is 14 and k is 3, then the output  should be “4 20.” In this type of node, two types of nodes are to be considered: 1. The target node is rooted in the subtree. If the value of k is 2 and the target node is 8, for example, such nodes are 10 and 14. 2. Other nodes could be a target's ancestor or a node in a different subtree. This category includes node 22 for target node 8 when k is 2. Finding the first type of node is straightforward. In a recursive call, simply visit subtrees rooted with the target node and decrement k. As soon as k becomes 0, print the node that is currently being traversed. So, we will call a new function printkdistance(). And we must go through all ancestors for the output nodes that are not in the subtree that has the target node as the root. We calculate the distance between each ancestor and the target node, d. We then travel to the ancestor's other subtree (if the target was discovered in the left subtree, we go to the right subtree, and vice versa) and find all nodes at k-d distance from the ancestor. Let’s see how can we implement this approach: int data;
	Node left, right; {
		data = item; }
} Node root; { } {
			System.out.print(node.data); } } { } {
			printkdistance(node, k); } int dl = printkdistanceNode(node.left, target, k); { {
				System.out.print(node.data); } } int dr = printkdistanceNode(node.right, target, k); { {
				System.out.print(node.data); } } } Node target = tree.root.left.right; }
} // This is a java program //to print nodes at a distance k from the given node // A Node of a Binary Tree class Node { Node ( int item ) left = right = null ; class BinaryTree { // Recursive function that will help to print all the nodes at distance k in // tree (or subtree) rooted with a given root. void printkdistance ( Node node, int k ) // Base Case will be, if (node == null || k < 0 ) { return ; // If we find a k distant node, we'll print it if (k == 0 ) System.out.println( "" ); return ; // Recursion for left and right subtrees printkdistance(node.left, k- 1 ); printkdistance(node.right, k- 1 ); // Prints nodes at a distance k from a given target node. // The nodes that are at k distance may be in an up or down direction. // This function will return the distance of the root node from the target node. // And, it will return -1 if the target node is not present in a tree rooted with the root // node. int printkdistanceNode ( Node node, Node target, int k ) // The First Base Case: If the tree is empty, then return (-1). if (node == null ) { return - 1 ; // If the target is the same as the root node. We will use the downward // function that will print all nodes at distance k in the subtree rooted with // target or root if (node == target) return 0 ; // Recursion for left subtree. // Check if the target node was in the left subtree. if (dl != - 1 ) // If the root is at k distance from the target, then print the root node. // Note that the distance of root's left child from the target is dl. if (dl + 1 == k) System.out.println( "" ); // Else go into the right subtree and print all the nodes that are at distance of k-dl-2. // Note that the right child is only 2 edges away from the left child. else printkdistance(node.right, k - dl - 2 ); // Now, add 1 to the distance and return the value for parent calls. return 1 + dl; // Now, we will MIRROR THE ABOVE CODE FOR THE RIGHT SUBTREE as well. // Note that we will reach here only when node was not found in left // subtree if (dr != - 1 ) if (dr + 1 == k) System.out.println( "" ); else printkdistance(node.left, k - dr - 2 ); return 1 + dr; // If target is neither in the left nor in the right subtree return - 1 ; // To test the above functions, a Driver Program public static void main ( String args[] ) { BinaryTree tree = new BinaryTree(); /* Let us make the tree as shown in above diagram */ tree.root = new Node( 20 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 22 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 12 ); tree.root.left.right.left = new Node( 10 ); tree.root.left.right.right = new Node( 14 ); tree.printkdistanceNode(tree.root, target, 2 ); Output: 4 20 In this approach, no node is being traversed more than twice. So, the time complexity is O(n). Time Complexity: Another Approach: First, get the Path from the Root Node and add it to a list. For every 'i' th element from Path, just iterate and print nodes that are at '(K-i)'th distance. public int val;
	public TreeNode left;
	public TreeNode right; } { discoverPath(root, target); findKDistance(
				path.get(i), K - j, answer, } } { } answer.add(node.val);
		} } { path.add(node); } } { TreeNode target = root.left.right; }
} import java.io.*; import java.util.*; class TreeNode { public TreeNode ( ) {} public TreeNode ( int val ) { this .val = val; } class CodingNinjas { List<TreeNode> path = null ; //Finding the nodes that are at a distance of K from the target node. public List<Integer> distanceK ( TreeNode root, TreeNode target, int K ) path = new ArrayList<>(); List<Integer> answer = new ArrayList<>(); for (int j= 0 ; j<path.size(); j++) { j == 0 ? null : path.get(j - 1 )); //Now return the list of all nodes at a distance K. return answer; // Blocker is used for nodes that are ancestors; if the target is at left, then we will // have to go right, or if the target is at right, then we will have to go left. public void findKDistance ( TreeNode node, int dist, List<Integer> answer, TreeNode blocker ) if (dist < 0 || node == null || (blocker != null && node == blocker)) { return ; if (dist == 0 ) { findKDistance(node.left, dist - 1 , answer, blocker); findKDistance(node.right, dist - 1 , answer, blocker); //To find the path of the target node from the root node. public boolean discoverPath ( TreeNode node, TreeNode target ) if (node == null ) return false ; if (node==target || discoverPath(node.left, target) || discoverPath(node.right, target))   { return true ; return false ; public static void main ( String [] args ) CodingNinjas codingninjas = new CodingNinjas(); /* Let us make the tree shown in above diagram */ TreeNode root = new TreeNode( 20 ); root.left = new TreeNode( 8 ); root.right = new TreeNode( 22 ); root.left.left = new TreeNode( 4 ); root.left.right = new TreeNode( 12 ); root.left.right.left = new TreeNode( 10 ); root.left.right.right = new TreeNode( 14 ); System.out.println(codingninjas.distanceK(root, target, 2 )); Output: [4, 20] Conclusion In this article, we have studied how to print Nodes at Distance k from Node. We hope that this article has provided you with the help to enhance your knowledge regarding Binary Tree.

Learning to Code: Print Nodes at Distance K From Node

1 Introduction In this article we will improve mathematical expressions evaluation for our programming language (please see ) using Dijkstra's Two-Stack algorithm. The essence of this algorithm is that any complex expression ultimately comes down to the simple expression. In the end, It will be a unary or binary operation on one/two operands. Part I How  Dijkstra's Two-Stack algorithm works: We iterate tokens expression If our token is an operand (e.g. number), we push it into the operands stack If we find an operator, we push into the operators stack We pop operators with the higher priority than the current one and apply it on the top operand(s) If an opening parenthesis is found, we push it into the operands stack. If a closing parenthesis is found, pop all operators and apply it on the top operand(s) until the opening parenthesis will be reached, and finally pop the opening parenthesis. Example Let’s suppose we have the following expression: . When we calculate this expression first we summarize and in the parentheses. After that, we multiply the result by . And in the end we subtract from the result. Down below is the expression evaluation using Dijkstra's Two-Stack algorithm: 2 * (3 + 4) - 5 3 4 2 5 Push to the operands stack: 2 Push to operators: * Push to operands: ( Push to operands: 3 Push to operators: + Push to operands: 4 Push to operators. Closing parenthesis pops an operation until a nearest opening parenthesis . Therefore, we pop operator and apply it on the operands: ) ( top two top Push to operators.  The operators stack's top element has greater precedence than the current operator . Therefore, first we apply operator on operands: - * - top two top Push to operands: 5 Pop left operator: - 2 Operators Let’s dive into the code. First, we will update our enum including operators precedence and introduce a few new operators: Operator @RequiredArgsConstructor
@Getter
public enum Operator {
    Not("!", NotOperator.class, 5),
    StructureValue("::", StructureValueOperator.class, 5),

    Addition("+", AdditionOperator.class, 3),
    Subtraction("-", SubtractionOperator.class, 3),

    LessThan("<", LessThanOperator.class, 2),
    GreaterThan(">", GreaterThanOperator.class, 2);

    private final String character;
    private final Class<? extends OperatorExpression> type;
    private final Integer precedence;

    Operator(String character, Integer precedence) {
        this(character, null, precedence);
    }

    public static Operator getType(String character) {
        return Arrays.stream(values())
                .filter(t -> Objects.equals(t.getCharacter(), character))
                .findAny().orElse(null);
    }

    public boolean greaterThan(Operator o) {
        return getPrecedence().compareTo(o.getPrecedence()) > 0;
    }
} public class StatementParser {
    ...
    private Expression readExpression() {
        ...
        while (peek(TokenType.Operator)) {
            Token operation = next(TokenType.Operator);
            Operator operator = Operator.getType(operation.getValue());
            Class<? extends OperatorExpression> operatorType = operator.getType();
            ...
        }

        ...
    }
    ...
} 2.1 StructureInstance We will no longer mark as the keyword lexeme, it will be the operator which will help us to instantiate a structure object inside a more complex expression: new public enum TokenType {
	...
	Keyword("(if|then|end|print|input|struct|arg)"),
	Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new)");
    ...
} We set it the highest priority: public enum Operator {
	...
    StructureInstance("new", StructureInstanceOperator.class, 5),
	...
} public class StructureInstanceOperator extends UnaryOperatorExpression {
    public StructureInstanceOperator(Expression value) {
        super(value);
    }

    @Override
    public Value<?> calc(Value<?> value) {
        return value; //will return toString() value
    }
} 2.2 Multiplication & Division We will also include two more operators with higher priority than addition and subtraction. Don’t forget to add regex expression for each operator to be counted when we’re doing lexical analysis: public enum TokenType {
	...
	Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new|\\*|\\/)");
    ...
} public enum Operator {
    ...
    Multiplication("*", MultiplicationOperator.class, 4),
    Division("/", DivisionOperator.class, 4),
    ...
} 2.3 LeftParen & RightParen These operators will be used to change operator’s precedence by surrounding expression in the parentheses. We will not create implementations as we make an expression calculation using parentheses: OperatorExpression public enum TokenType {
	...
	Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new|\\*|\\/|\$|\$)");
    ...
} public enum Operator {
    ...
    LeftParen("(", 1),
    RightParen(")", 1),
    ...
} 2.4 Assignment We also need to introduce a new assignment operator with a single equal sign. The variable value will be assigned to the variable only when we complete evaluation of the right expression. Therefore, this operator should have the lowest priority: = public enum Operator {
	...
    Assignment("=", AssignmentOperator.class, 6),
	...
} public class AssignOperator extends BinaryOperatorExpression {
    public AssignOperator(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    public Value<?> calc(Value<?> left, Value<?> right) {
        if (getLeft() instanceof VariableExpression) {
            ((VariableExpression) getLeft()).setValue(right);
        }
        return left;
    }
} During the execution we expect to retrieve the left expression as a - the variable we’re assigning value to. Thus, we introduce a new method in our to set the variable value. As you may remember our variables Map is being stored in the . To set access it and set a new value we introduce a instance, passing variable name as a key and variable value as a new value: VariableExpression VariableExpression StatementParser BiConsumer public class VariableExpression implements Expression {
    ...
    private final BiConsumer<String, Value<?>> setter;
    ...

    public void setValue(Value<?> value) {
        setter.accept(name, value);
    }
} public class StatementParser {
	...
    private Expression nextExpression() {
        ...
        return new VariableExpression(value, variables::get, variables::put);
    }
	...
} 2.5 Expression dividers 2.5.1 End of the row Previously, to build a mathematical expression we expected to obtain an operator after each operand: Expression left = nextExpression();

//recursively read an expression
while (peek(TokenType.Operator)) {
    Token operation = next(TokenType.Operator);
    Operator operator = Operator.getType(operation.getValue());
    Class<? extends OperatorExpression> operatorType = operator.getType();
    if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) {
        Expression right = nextExpression();
        left = operatorType
                .getConstructor(Expression.class, Expression.class)
                .newInstance(left, right);
    } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) {
        left = operatorType
                .getConstructor(Expression.class)
                .newInstance(left);
    }
} With the current behavior we can expect two subsequent operators in the row, e.g. addition of structure instantiation as an right operand or two following opening parentheses: value + new Car [“E30” “325i”] :: model

or

( ( 1 + 2) * 3) - 4 To read an entire expression with any sequence of operands and operators we will introduce the lexeme which will help us to catch all expression tokens until we reach end of the row: LineBreak public class StatementParser {
    LineBreak("[\\n\\r]"),
    Whitespace("[\\s\\t]"),
    ...
} 2.5.2 Structure arguments The second divider we need to count is when we instantiate a structure object: new Car [ “E30” “325i” new Engine [“M20B25”] :: model ] This structure instantiation is quite complex for the to divide each passing argument into separate expression. To deal with it we can introduce new comma : StatementParser GroupDivider public enum TokenType {
	...
   	GroupDivider("(\\[|\\]|\\,)"),
	...
} new Car [ “E30”, “325i”, new Engine [“M20B25”] :: model ] 3 Expression evaluation Now we can start refactoring our expression evaluation in the using Dijkstra’s Two-Stack algorithm. StatementParser 3.1 Next token Firstly, we will introduce method, that will increment  tokens position while we reach token: skipLineBreaks() LineBreak private void skipLineBreaks() {
    while (tokens.get(position).getType() == TokenType.LineBreak 
            && ++position != tokens.size()) ;
} It will be used on the top of each and methods to escape catching token: next() peek() LineBreak private Token next(TokenType type, TokenType... types) {
    skipLineBreaks();
    ...
}

private Token next(TokenType type, String value) {
    skipLineBreaks();
    ...
}

private boolean peek(TokenType type, String content) {
    skipLineBreaks();
    ...
}

private boolean peek(TokenType type) {
    skipLineBreaks();
    ...
} We will also override the method without any arguments just returning the next token: next() private Token next() {
    skipLineBreaks();
    return tokens.get(position++);
} 3.2 ExpressionReader To read and calculate an entire expression using Dijkstra's Two-Stack algorithm we will need two stacks, the operators stack, and the operands stack. The first stack of operators will contain the enum types. The second stack of operands will have type, it will help us to store every type of expression including values, variables and composite operators. It will be clearer if we perform expression reading in a separate inner class : Operator Expression ExpressionReader private class ExpressionReader {
    private final Stack<Expression> operands;
    private final Stack<Operator> operators;

    private ExpressionReader() {
        this.operands = new Stack<>();
        this.operators = new Stack<>();
    }
} Then we create a method with a while loop to read an entire expression. Our mathematical expression can begin with , , , or token types. In this case we can’t exclude the token during token retrieval because this token means the end of the expression. Therefore, we introduce an additional method inside our inner class that will read an expression until we reach the end of the row: readExpression() Operator Variable Numeric Logical Text LineBreak peek() private class ExpressionReader {
    ...
    private Expression readExpression() {
		while (peek(TokenType.Operator, TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text)) {
 	        Token token = next();
            switch (token.getType()) {
               case Operator:
			       ...
			    default:
			        ...
            }
        }
        ...
    }

    private boolean peek(TokenType type, TokenType... types) {
        TokenType[] tokenTypes = ArrayUtils.add(types, type);
        if (position < tokens.size()) {
            Token token = tokens.get(position);
            return Stream.of(tokenTypes).anyMatch(t -> t == token.getType());
        }
        return false;
    }
} 3.2.1 Operator The first lexeme type we will process is . We retrieve the enum by token’s value and use it in the switch block. There are 3 cases we will deal with: Operator Operator - just put an operator into the operators stack LeftParen - calculate previously pushed expressions until we reach the left parenthesis . RightParen LeftParen Before inserting other operators we need to be sure that the current operator has greater precedence than the top operator, in the negative case we pop the top operator and apply it on the top operand(s). In the end we push the less prioritized operator into the operators stack. ...
case Operator:
    Operator operator = Operator.getType(token.getValue());
    switch (operator) {
        case LeftParen:
            operators.push(operator);
            break;
        case RightParen:
            //until left parenthesis is not reached
            while (!operators.empty() && operators.peek() != Operator.LeftParen)
                applyTopOperator();
            operators.pop(); //pop left parenthesis
            break;
        default:
            //until top operator has greater precedence
            while (!operators.isEmpty() && operators.peek().greaterThan(operator))
                applyTopOperator();
            operators.push(operator); // finally, add less prioritized operator
    }
    break;
... To apply the top operator on the top operand(s) we create an additional method. First we pop an operator and the first operand. Then if our operator is binary we pop the second operand.  To create an object we retrieve a suitable constructor for unary or binary operator implementation and make an instance with earlier popped operands. In the end we push the instance to the operands stack. Thus, this pushed operand can be used later by other operators inside a more composite expression: applyTopOperator() OperatorExpression OperatorExpression Expression @SneakyThrows
private void applyTopOperator() {
    // e.g. a + b
    Operator operator = operators.pop();
    Class<? extends OperatorExpression> operatorType = operator.getType();
    Expression left = operands.pop();
    if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) {
        Expression right = operands.pop();
        operands.push(operatorType
                .getConstructor(Expression.class, Expression.class)
                .newInstance(right, left));
    } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) {
        // e.g. new Instance []
        operands.push(operatorType
                .getConstructor(Expression.class)
                .newInstance(left));
    } else {
        throw new SyntaxException(String.format("Operator `%s` is not supported", operatorType));
    }
} 3.2.2 Value & VariableExpression If our token is a variable or a literal, we transform it to the appropriate object inside the following switch block and then push the result to the operands stack: Expression ...
default:
    String value = token.getValue();
    Expression operand;
    switch (token.getType()) {
        case Numeric:
            operand = new NumericValue(Integer.parseInt(value));
            break;
        case Logical:
            operand = new LogicalValue(Boolean.valueOf(value));
            break;
        case Text:
            operand = new TextValue(value);
            break;
        case Variable:
        default:
            if (!operators.isEmpty() && operators.peek() == Operator.StructureInstance) {
                operand = readInstance(token);
            } else {
                operand = new VariableExpression(value, variables::get, variables::put);
            }
    }
    operands.push(operand);
... A variable token can also indicate the start of the structure instantiation. In this case  we read an entire structure expression with arguments inside square brackets and only then assign it to the value. We will move existent method from class into the inner class with following changes: StructureExpression readInstance() StatementParser ExpressionReader ...
private Expression readInstance(Token token) {
    StructureDefinition definition = structures.get(token.getValue());

    List<Expression> arguments = new ArrayList<>();
    if (StatementParser.this.peek(TokenType.GroupDivider, "[")) {

        next(TokenType.GroupDivider, "["); //skip open square bracket

        while (!StatementParser.this.peek(TokenType.GroupDivider, "]")) {
            Expression value = new ExpressionReader().readExpression();
            arguments.add(value);

            if (StatementParser.this.peek(TokenType.GroupDivider, ","))
                next();
        }

        next(TokenType.GroupDivider, "]"); //skip close square bracket
    }

    if (definition == null) {
        throw new SyntaxException(String.format("Structure is not defined: %s", token.getValue()));
    }
    return new StructureExpression(definition, arguments, variables::get);
}
... 3.2.3 Evaluation After we finished processing expression tokens and reached the end of the expression we will need an extra while loop to pop remaining operators and apply it on the top operand(s). In the end we should have the only one resulting composite operand in the operands stack, we return it as a final expression result: private Expression readExpression() {
    ...

    while (!operators.isEmpty()) {
        applyTopOperator();
    }

    return operands.pop();
} 3.3 AssignStatement Now we can now build in the method. The can start with a Variable or an Operator token type (in case we have a operator for the structure instantiation). When we read an expression we expect to read an entire expression accumulating left value as a variable name and right expression as a variable value. Therefore, we go to one tokens position back and start reading the expression using starting from variable’s name declaration: AssignmentStatement parseExpression() AssignStatement new Assignment ExpressionReader private Statement parseExpression() {
    Token token = next(TokenType.Keyword, TokenType.Variable, TokenType.Operator);
    switch (token.getType()) {
        case Variable:
        case Operator:
            position--;
            Expression value = new ExpressionReader().readExpression();
		    ...
        case Keyword:
        default:
            ...
    }
} In the end we expect to obtain the complete and we can create an instance: AssignmentOperator AssignmentStatement ...
case Variable:
case Operator:
    position--;
    Expression value = new ExpressionReader().readExpression();

    if (value instanceof AssignmentOperator) {
        VariableExpression variable = (VariableExpression) ((AssignmentOperator) value).getLeft();
        return new AssignmentStatement(variable.getName(), ((AssignmentOperator) value).getRight(), variables::put);
    } else {
        throw new SyntaxException(String.format("Unsupported statement: `%s`", value));
    }
... The last thing we need to do is to update expressions reading for the and statements using our new inner class. It will allow us to read complex expression inside and statements: input if ExpressionReader print if ...
case Keyword:
default:
    switch (token.getValue()) {
        case "print":
            Expression expression = new ExpressionReader().readExpression();
            ...
        case "if":
            Expression condition = new ExpressionReader().readExpression();
		    ...
    }
... 4 Wrapping up In this article, we improved our own programming language with mathematical expressions evaluation using Dijkstra's Two-Stack algorithm. We injected operators priority with an ability to change it using parentheses, including complex structure instantiations. The full source code is available . over on GitHub

Building Your Own Programming Language From Scratch: Part II - Dijkstra's Two-Stack Algorithm

Whenever you start wondering how to create your syntax or rules on expression, it’s probably time to check out this powerful tool you may be interested in. The allows you to build your own grammar rules, validate, and parse the result at the end. Chevrotain What does this library structurally consist of? of all, it’s . Lexer is the class that basically goes through input text and match token to each symbol or sequence of symbols (words), it found. To create an instance of the Lexer class, I need to define all tokens that I want to use. The token should have a unique name, the pattern - means regex. First Lexer For example token will match the exact word in the text. ‘hackernoon‘ const hackernoon = createToken({
  name: 'hackernoon',
  pattern: /hackernoon/
}) Also, there is a possibility to tokens. For this purpose, I need to define one more token with a reserved pattern value . In this case, Lexer will not use it to match some characters. And in other tokens that I want to categorize, I add my new token to a property ‘categories’. Like in the example below, I introduce and add this token to and . categorize Lexer.NA MathOperator MathPlus MathMinus export const MathOperator = createToken({
    name: Token.MathOperator,
    pattern: Lexer.NA,
});

export const MathPlus = createToken({
    name: Token.MathPlus,
    pattern: /\+/,
    categories: MathOperator,
});

export const MathMinus = createToken({
    name: Token.MathMinus,
    pattern: /-/,
    categories: MathOperator,
});

export const Number = createToken({ 
    name: Token.Number, 
    pattern: /[+-]?\d*\.?\d+(?:[Ee][+-]?\d+)?/
});

export const Whitespace = createToken({
    name: Token.WhiteSpace,
    pattern: /\s+/,
    group: Lexer.SKIPPED,
}); When all tokens are defined, I need to create a new instance of the Lexer class and put there an array of these tokens. const allTokens = [
  WhiteSpace,
  Number,
  MathPlus,
  MathMinus
]

const mathLexer = new Lexer(allTokens) And from this moment the Lexer is ready to tokenize input strings. I need to invoke the function ‘tokenize’ of the Lexer, and as a result, I will receive an object with tokens. With them, I can go to the next step. const lexingResult = mathLexer.tokenize(text); is having next interface . Where errors array can be very helpful to understand for the user what is wrong in the expression because it contains coordinates to the problem: line and column. lexingResult ILexingResult export interface ILexingResult {
  tokens: IToken[]
  groups: {
    [groupName: string]: IToken[]
  }
  errors: ILexingError[]
} The important thing is . It is a tool to describe the rules of your expression. For example, in math expression, you are expecting that the first variable will be a the second should be some operator and the third must be a as well. So rule will describe such behavior. First things first I create my own class the inherited from . That will accept tokens list in the constructor, and the constructor will contain all required rules and after them the to check all written rules. second Parser Number +/- Number MathParser CstParser this.performSelfAnalysis() class MathParser extends CstParser {
    public mathCond: RuleFn;
    private valueOrParen: RuleFn;
    private parentheses: RuleFn;
    private value: RuleFn;
    private mathOp: RuleFn;

    constructor(tokens: TokenType[]) {
      super(tokens);
      const $ = this;

      // Rules here
      
      this.performSelfAnalysis(); // Must be after all rules
    }
} The rule is the main entrance rule that will be invoked to perform the parsing. Basically, in my example, I assume that expression should be starting from some number or from parentheses. You are wondering how to read this rule? It actually tells if at least one number or parentheses with a number or parentheses with some operation (the operation described in keyword), then the expression is valid. mathCond 123 (123) (123 + 456) MANY Of course, as you can see there could be more  parentheses and math operations inside one parentheses, in these terms - recursion. And says that expression can repeat zero or more times. As like the example with - it repeats one time if it will be like then 2 repeats. this can be read: 1 repeat in parentheses and one after them. MANY (123 + 456) (123 + 456 - 789) (123 + 456) - 789 mathCond this.mathCond = $.RULE('mathCond', () => {
    $.SUBRULE($.valueOrParen, { LABEL: 'lhs' });
    $.MANY(() => {
        $.SUBRULE1($.mathOp)
        $.SUBRULE2($.valueOrParen, { LABEL: 'rhs' });
    });
}); The rule is expecting some Number or other parentheses with math expression. valueOrParen this.valueOrParen = $.RULE('valueOrParen', () => {
    $.OR([
        { ALT: () => $.SUBRULE($.value) },
        { ALT: () => $.SUBRULE($.parentheses) },
    ]);
}); In the next rule parentheses, I want to cover the case with braces and inside braces, recursion happens. and are two more tokens. is the main rule function. () LeftParen RightParen mathCond this.parentheses = $.RULE('parentheses', () => {
    $.CONSUME(LeftParen);
    $.SUBRULE($.mathCond);
    $.CONSUME(RightParen);
}); is the rule which looks for OR . mathOp + - this.mathOp = $.RULE('mathOp', () => {
    $.OR([
        { ALT: () => $.CONSUME(MathPlus) },
        { ALT: () => $.CONSUME(MathMinus) },
    ]);
}); The rule is created just to show that it can be extended with other specific types. value this.value = $.RULE('value', () => {
    $.OR([
        { ALT: () => $.CONSUME(Number) }
    ]);
}); Once the parser is ready, create it and call the main function. const mathParser = new MathParser(allTokens);
mathParser.mathCond(); As for Lexer, there are errors that help users, here as well, after calling the main function parser may contain errors with Token where the error happened. mathParser.errors So this library helps you to verify the string that the user typed and actually evaluate the expression. And even more, you can try a custom to create your own expression tree. Visitor

Creating Your Own Grammar Rules

How to do faster preparation for coding interviews? Coding interviews are getting harder every day. A few years back, brushing up on key data structures and going through 50–75 practice questions was more than enough prep for an interview. Today, everyone has access to massive sets of coding problems, and they’ve gotten more difficult as well. The overall interview process has gotten more competitive. In this post, I like to share a strategy that I’ve been following to prepare for coding interviews. My software engineering career spans around 15 years, in which I have switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I’ve some experience sitting on the other side of the table too. I’ve taken 200+ coding interviews and 100+ system design interviews. I consider myself a reasonably smart engineer, but I have had my challenges solving coding problems on a whiteboard, especially in an interview setting where someone is evaluating me. To tackle this problem, I had been spending a reasonable time for preparation and practice. One thing I didn’t realize was that while doing my preparation, I was following a systematic approach. I was able to go through 12–15 questions practicing two hours every day. This meant that I was able to solve 350+ questions within one month. Using this routine, I was able to crack my interviews for FAANGs (Facebook, Apple, Amazon, Netflix, Google). How was I able to practice 12+ coding questions every day with a full-time job? Well, I was not solving coding problems but practicing to ‘map’ problems to already known problems that I’ve solved before. . I used to read a problem, spend a few minutes mapping it to a similar problem that I have seen before. If I can map it, I focus only on the different constraints this problem has compared to the parent problem If it is a new problem, then I try to solve it and also read around to find smart ways other people have used to device its algorithm. Over time, I developed a set of problem-patterns, that helped me quickly ‘map’ a problem to an already known pattern. Here are some examples of these patterns: If the given input is sorted (array, list, or matrix), then we will be using a variation of or a strategy. Binary Search Two Pointers If we are dealing with top/maximum/minimum/closest ‘k’ elements among ’n’ elements, we will be using a . Heap If we need to try all combinations (or permutations) of the input, we can either use recursive or iterative . Backtracking Breadth-First Search Following this pattern-based approach helped me save a lot of preparation time. As once you’re familiar with a pattern, you will be able to solve dozens of problems with it. In addition to that, this strategy made me confident to tackle unknown problems, as I’ve been practicing to map unknown problems to known problems. In the remaining post, I will share all the patterns that I’ve collected over time and present sample problems for a few. For a detailed discussion of these patterns and their related problems with solutions take a look at Grokking the Coding Interview . Sample problem for Binary Search: Bitonic Array Maximum Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array . Problem statement: arr[i] != arr[i+1] : [1, 3, 8, 12, 4, 2], : 12 Example : Input Output A bitonic array is a sorted array; the only difference is that its first part is sorted in ascending order and the second part is sorted in descending order. We can use a variation of to solve this problem. Remember that in we have , , and indices and in each step we reduce our search space by moving or . Since no two consecutive numbers are same (as the array is monotonically increasing or decreasing), whenever we calculate the index for , we can compare the numbers pointed out by the index and to find if we are in the ascending or the descending part. So: Solution: Binary Search Binary Search start end middle start end middle Binary Search middle middle+1 If , we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by or will be before . This means we will be doing: end = middle. arr[middle] > arr[middle + 1] middle middle If , we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after . This means we will be doing: . arr[middle] <= arr[middle + 1] middle start = middle + 1 We can break when . Due to the two points mentioned above, both and will be pointing at the maximum number of the Bitonic array. start == end start end Here is the Java code to solve this problem: Code: { { start = , end = arr.length - ; (start < end) { mid = start + (end - start) / ; (arr[mid] > arr[mid + ]) {
        end = mid;
      } {
        start = mid + ;
      }
    } arr[start];
  } {
    System.out.println(MaxInBitonicArray.findMax( [] { , , , , , }));
    System.out.println(MaxInBitonicArray.findMax( [] { , , , }));
    System.out.println(MaxInBitonicArray.findMax( [] { , , , }));
    System.out.println(MaxInBitonicArray.findMax( [] { , , }));
  }
} class MaxInBitonicArray public static int findMax ( [] arr) int int 0 1 while int 2 if 1 else 1 // at the end of the while loop, 'start == end' return public static void main (String[] args) new int 1 3 8 12 4 2 new int 3 8 3 1 new int 1 3 8 12 new int 10 9 8 Sample Problem for Two Pointers: Pair with Target Sum Given an array of sorted numbers and a target sum, find a . Problem statement: pair in the array whose sum is equal to the given target Write a function to return the indices of the two numbers (i.e., the pair) such that they add up to the given target. : [1, 2, 3, 4, 6], =6, : [1, 3] (The numbers at index 1 and 3 add up to 6: 2+4=6) Example: Input target Output Since the given array is sorted, a brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through . The time complexity of this algorithm will be O(N*logN). Can we do better than this? Solution: Binary Search We can follow the approach. We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair. Otherwise, we will do one of two things: Two Pointers If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer. If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer. Here is the visual representation of this algorithm for the example mentioned above: Here is what our algorithm will look like: Code: { [] search( [] arr, targetSum) { left = , right = arr.length - ; (left < right) { targetDiff = targetSum - arr[left]; (targetDiff == arr[right]) [] { left, right }; (targetDiff > arr[right])
        left++; right--; } [] { - , - };
  } { [] result = PairWithTargetSum.search( [] { , , , , }, );
    System.out.println( + result[ ] + + result[ ] + );
    result = PairWithTargetSum.search( [] { , , , }, );
    System.out.println( + result[ ] + + result[ ] + );
  }
} class PairWithTargetSum public static int int int int 0 1 while // comparing the sum of two numbers to the 'targetSum' can cause integer overflow // so, we will try to find a target difference instead int if return new int // found the pair if // we need a pair with a bigger sum else // we need a pair with a smaller sum return new int 1 1 public static void main (String[] args) int new int 1 2 3 4 6 6 "Pair with target sum: [" 0 ", " 1 "]" new int 2 5 9 11 11 "Pair with target sum: [" 0 ", " 1 "]" Sample problem: ‘K’ Closest Points to the Origin Given an array of points in a 2D plane, find ‘K’ closest points to the origin. Problem statement: : points = [[1,2],[1,3]], K = 1, : [[1,2]] Example: Input Output The of a point from the origin can be calculated through the following formula: Solution: Euclidean distance P(x,y) We can use a to find ‘K’ points closest to the origin. We can start with pushing first ‘K’ points in the heap. While iterating through the remaining points, if a point (say ‘P’) is closer to the origin than the top point of the max-heap, we will remove that top point from the heap and add ‘P’ to always keep the closest points in the heap. Max Heap Here is what our algorithm will look like: Code: java.util.*; { x; y; { .x = x; .y = y;
  } { (x * x) + (y * y);
  }
} { {
    PriorityQueue<Point> maxHeap = PriorityQueue<>(
              (p1, p2) -> p2.distFromOrigin() - p1.distFromOrigin()); ( i = ; i < k; i++)
      maxHeap.add(points[i]); ( i = k; i < points.length; i++) { (points[i].distFromOrigin() < maxHeap.peek().distFromOrigin()) {
        maxHeap.poll();
        maxHeap.add(points[i]);
      }
    } ArrayList<>(maxHeap);
  } {
    Point[] points = Point[] { Point( , ), Point( , ), Point( , - ) };
    List<Point> result = KClosestPointsToOrigin.findClosestPoints(points, );
    System.out.print( ); (Point p : result)
      System.out.print( + p.x + + p.y + );
  }
} import class Point int int public Point ( x, y) int int this this public int distFromOrigin () // ignoring sqrt return class KClosestPointsToOrigin List<Point> public static findClosestPoints (Point[] points, k) int new // put first 'k' points in the max heap for int 0 // go through the remaining points of the input array, if a point is closer to // the origin than the top point of the max-heap, remove the top point from // heap and add the point from the input array for int if // the heap has 'k' points closest to the origin, return them in a list return new public static void main (String[] args) new new 1 3 new 3 4 new 2 1 2 "Here are the k points closest the origin: " for "[" " , " "] " Sample Problem: Subsets : Given a set with distinct elements, find all of its distinct subsets. Problem Statement : [1, 5, 3], : [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3] Example: Input Output To generate all subsets of the given set, we can use the approach. We can start with an empty set, iterate through all numbers one-by-one, and add them to existing sets to create new subsets. Solution: Breadth-First Search (BFS) Let’s take the above-mentioned example to go through each step of our algorithm: Given set: [1, 5, 3] Start with an empty set: [[]] Add the first number (1) to all the existing subsets to create new subsets: [[], ; [1]] Add the second number (5) to all the existing subsets: [[], [1], ]; [5], [1,5] Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], ]. [3], [1,3], [5,3], [1,5,3] Here is the visual representation of the above steps: Here is what our algorithm will look like: Code: java.util.*; { List<List<Integer>> findSubsets( [] nums) {
    List<List<Integer>> subsets = ArrayList<>(); subsets.add( ArrayList<>()); ( currentNumber : nums) { n = subsets.size(); ( i = ; i < n; i++) { List<Integer> set = ArrayList<>(subsets.get(i));
        set.add(currentNumber);
        subsets.add(set);
      }
    } subsets;
  } {
    List<List<Integer>> result = Subsets.findSubsets( [] { , });
    System.out.println( + result);

    result = Subsets.findSubsets( [] { , , });
    System.out.println( + result);
  }
} import class Subsets public static int new // start by adding the empty subset new for int // we will take all existing subsets and insert the current number in them to // create new subsets int for int 0 // create a new subset from the existing subset and // insert the current element to it new return public static void main (String[] args) new int 1 3 "Here is the list of subsets: " new int 1 5 3 "Here is the list of subsets: " Sample Problem: Binary Tree Path Sum : Given a binary tree and a number ‘S,’ find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals ‘S.’ Problem Statement As we are trying to search for a root-to-leaf path, we can use the technique to solve this problem. Solution: Depth First Search (DFS) To recursively traverse a binary tree in a DFS fashion, we can start from the root and at every step, make two recursive calls one for the left and one for the right child. Here are the steps for our Binary Tree Path Sum problem: Start DFS with the root of the tree. If the current node is not a leaf node, do two things: a) Subtract the value of the current node from the given number to get a new sum => , b) Make two recursive calls for both the children of the current node with the new number calculated in the previous step. S = S - node.value At every step, see if the current node being visited is a leaf node and if its value is equal to the given number ‘S.’ If both these conditions are true, we have found the required root-to-leaf path, therefore return . true If the current node is a leaf, but its value is not equal to the given number ‘S,’ return false. Here is what our algorithm will look like: Code: { val;
  TreeNode left;
  TreeNode right;

  TreeNode( x) {
    val = x;
  }
}; { { (root == ) ; (root.val == sum && root.left == && root.right == ) ; hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
  } {
    TreeNode root = TreeNode( );
    root.left = TreeNode( );
    root.right = TreeNode( );
    root.left.left = TreeNode( );
    root.right.left = TreeNode( );
    root.right.right = TreeNode( );
    System.out.println( + TreePathSum.hasPath(root, ));
    System.out.println( + TreePathSum.hasPath(root, ));
  }
} class TreeNode int int class TreePathSum public static boolean hasPath (TreeNode root, sum) int if null return false // if current node is a leaf and its value is equal to the sum, we've found a path if null null return true // recursively call to traverse the left and right sub-tree // return true if any of the two recursive call return true return public static void main (String[] args) new 12 new 7 new 1 new 9 new 10 new 5 "Tree has path: " 23 "Tree has path: " 16 Following these patterns helped me tremendously to save time for my coding interview prep. Take a look at and to find more of such patterns and their sample problems. Grokking the Coding Interview Grokking Dynamic Programming Patterns for Coding Interviews This post was originally published on Medium: The Ultimate Strategy to Preparing for the Coding Interview

The Ultimate Strategy to Preparing for the Coding Interview

In this article, I will show you how to use the , which hasn’t received significant dissemination among Java developers. ForkJoinPool is one of the ’s implementations. It is used in and Stream API. It was designed to simplify parallelism for recursive tasks by breaking the single task into independent ones until they are small enough to be executed asynchronously. With this class, you can perform a significantly large amount of tasks in a small number of threads. ForkJoinPool ExecutorService CompletableFuture Java has a common implementation that can be created through the static method: ForkJoinPool commonPool() ForkJoinPool forkJoinPool = ForkJoinPool.commonPool(); ForkJoinTask has its own and implementations. These implementations are called and respectively. Each of them has an abstract method, which must be implemented during implementation. returns generic <T> value, returns void. Both of these implementations are inherited from the abstract class. ForkJoinTask Runnable Callable RecursiveAction RecursiveTask compute() RecursiveTask<T>#compute() RecursiveAction#compute() ForkJoinTask To start a task in , use the method : ForkJoinPool T invoke(ForkJoinTask<T> task) ForkJoinTask forkJoinTask = new ForkJoinTaskImpl(...);
forkJoinPool.invoke(forkJoinTask); In addition to the method, has the following methods: and . In terms of usage, the is similar to the . But in the case of a fork-join, the thread may not actually fall asleep, it will rather switch to another task. This strategy is called “work stealing”, it allows more efficient use of a limited number of threads. compute() ForkJoinTask fork() join() ForkJoinTask#join() Thread#join() Fibonacci example Let's look at the simple example of the implementation for calculating the Fibonacci numbers: ForkJoinTask public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    public FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    public Integer compute() {
        if (n < 2) return n;
        FibonacciTask f1 = new FibonacciTask(n - 1);
        FibonacciTask f2 = new FibonacciTask(n - 2);
        f1.fork();
        return f2.compute() + f1.join();
    }
} In this example, implements the method, which creates additional instances and forks them. The method asks the current thread to wait until results are returned by the forked methods. FibonacciTask compute() FibonacciTask join() Merge Sort Let's take a look at the more complex example of - the Merge Sort. It is based on the "Divide and Conquer" principle, old as the world. We need to divide source problems into subtasks, solve them recursively and combine the results: ForkJoinTask For this task we will use as the implementation, since we don't need a return value. We will add as a parameter to the constructor and instantiate the class's field: RecursiveAction ForkJoinTask int[] arr public class MergeSortAction extends RecursiveAction {

    private final int[] arr;

    public MergeSortAction(int[] arr) {
        this.arr = arr;
    }

    @Override
    public void compute() {
        ...
    }

    private void merge(int[] left, int[] right) {
        ...
    }

} Next, we implement the method. It will accept 2 arrays - and parts. We need to merge these unsorted arrays by comparing elements and assigning the smallest element to the appropriate arr index. When one of the arrays will be empty, the loop will break, but the data from another non-empty array part still needs to be merged. To do this we have two additional while loops to get all the data from both arrays: merge() left right while private void merge(int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
} Next, we will write the method to recursively divide the original array and pass the results to the method. To do this we need to calculate the middle index of the array. Then we divide the original array into two parts: and . To fill them we copy original data by calling : compute() merge() left right System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) @Override
public void compute() {
    if (arr.length < 2) return;
    int mid = arr.length / 2;

    int[] left = new int[mid];
    System.arraycopy(arr, 0, left, 0, mid);

    int[] right = new int[arr.length - mid];
    System.arraycopy(arr, mid, right, 0, arr.length - mid);

    ...
} Now, we have two separate arrays. Let’s divide them recursively by creating new tasks and run them asynchronously by passing them into method. To sort and combine two arrays we use method: MergeSortAction invokeAll() merge() @Override
public void compute() {
    if (arr.length < 2) return;
    int mid = arr.length / 2;

    int[] left = new int[mid];
    System.arraycopy(arr, 0, left, 0, mid);

    int[] right = new int[arr.length - mid];
    System.arraycopy(arr, mid, right, 0, arr.length - mid);

    invokeAll(new MergeSortAction(left), new MergeSortAction(right));
    merge(left, right);
} Speed testing We’ve finished our parallel Merge Sort. Let’s test it and compare performance with the non-parallel version. I used to generate random numbers and to calculate the execution time: ThreadLocalRandom ZonedDateTime class MergeSortTest {

    private final List<MergeSort> mergeSortImpls = 
            Arrays.asList(new MergeSortImpl(), new ParallelMergeSortImpl());

    @Test
    void sort() {
        for (MergeSort mergeSort : mergeSortImpls) {
            int[] arr = IntStream
                    .range(0, 100_000_000)
                    .map(i -> ThreadLocalRandom.current().nextInt())
                    .toArray();
            ZonedDateTime now = ZonedDateTime.now();
            mergeSort.sort(arr);
            System.out.printf("%s exec time: %dms\n",
                    mergeSort.getClass().getSimpleName(),
                    ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
            assertTrue(isSorted(arr));
        }
    }

    private boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

} There are the execution results for 100 million of numbers on 8-core CPU: Conclusion In this article, I showed you an example of how to use Fork/Join Framework. I hope you now have a basic idea of how to speed up your applications. The source code is available . over on GitHub

Parallel Merge Sort with Fork/Join Framework

Almost every web application needs the functionality to send transactional emails in response to various triggers. Events like account registration, password resets, purchase receipts, and user verification are among the many tasks today’s applications need to accomplish via email. These emails are crucial for notifying users of important updates and enabling key user workflows in your application. This post explores three different options for sending emails from within a Node.js app. I’ll share each method’s pros and cons, so you can select the best method for your needs. 3 options for sending an email with Node.js As a server-side tool, Node.js allows you to send emails using a few different options. I’ll provide an overview of the three main options — SMTP, email API, and multi-channel notification service — before diving into a technical tutorial for each of them. 1. Using SMTP Simple Mail Transfer Protocol (SMTP) is a technology for sending outgoing emails across networks and is the most common transport method. It serves as a relay service to send emails from one server to another. When you send an email to a friend using an email client like Gmail, an outgoing (SMTP) server picks it up and connects with your friend’s receiving server. The two servers communicate using guidelines defined by the SMTP protocol, determining who the recipient is and how they can receive the incoming mail. Email clients usually have an SMTP server associated with them to aid in email delivery. Advantages of using SMTP The major advantage of SMTP is that it’s widely adopted and easy to set up and integrate in a web application. Email service providers, which I cover below, might have more features, but using them also means relying on a third-party intermediary to deliver your emails. With SMTP, you get fine-grained control over every aspect of your email sending. Drawbacks of using SMTP The major drawback of SMTP is . The standard SMTP protocol is susceptible to DDoS attacks, phishing, and data breaches. If you decide to use your own email SMTP server, you will be responsible for long-term server maintenance, which requires a lot of ongoing effort to maintain security. it can be insecure and easily hacked Sending emails with SMTP is also much slower than using an API service. SMTP requires extensive back-and-forth between mail SMTP servers to deliver a message. Even then the email may fail to deliver without feedback if the server’s IP address is blacklisted or a firewall has blocked a port. This back-and-forth also means multiple points of failure. 2. Using a transactional email API allow you to send emails from your app using a hosted API. Instead of managing email servers and their requirements yourself, you can use an email API to handle message assembly, sending, and deliverability. Transactional email APIs come in handy when you need a reliable service that can be integrated quickly, can support high-volume sending and offers rich functionality. Transactional email services There are many transactional email services on the market. The most popular ones include , , , , , and (formerly Mandrill). All of them are paid services, though most offer free or low-cost introductory plans. Amazon SES Postmark SparkPost SendGrid Mailgun Mailchimp Transactional Advantages of using a transactional email API The main advantage of using a transactional email service is they’re very easy to set up and easy to use, especially since most services come with comprehensive documentation. They provide monitoring, such as whether emails are delivering, as well as web analytics and reporting, including bounce rate, open, click, and unsubscribe tracking. Other key advantages of using an email API are that they’re highly scalable, they add an extra layer of security by utilizing API keys as opposed to the SMTP method, and they can save you significant engineering time and costs when it comes to ongoing maintenance. Drawbacks of using a transactional email API The major drawback of using a hosted email service, instead of SMTP, is you’re relying on a third party to handle your emails. Before picking a provider, spend some time their features, guaranteed uptime, email deliverability rates, and API documentation. researching The other drawback of using a hosted email service, instead of a (which I cover below), is if your application needed to notify users on other channels, you’d have to integrate each new channel separately. For example, you’d have to separately integrate mobile and web push, SMS, and chat apps like Slack and WhatsApp. Whether all the extra code and effort is worth it is up to you. multi-channel notifications service 3. Using multi-channel notification services Multichannel notification services, such as , allow you to reach users across a number of different channels using one uniform API. They usually allow you to bring your own provider for each channel; in the case of email, that could be your own SMTP server or a hosted transactional email API. Courier With a multichannel notification service, you can easily add more channels or even switch your email service provider without having to touch your code. If you wanted to notify users across email, SMS, push, or chat apps like Slack and WhatsApp, you could do that in one fell swoop. , in particular, gives you additional functionality — on top of what you’d get with a transactional email service. You can design your emails in a flexible visual and code editor, set delivery rules and create simple workflows, and monitor delivery status in real-time. Courier Advantages of using a multichannel notification service The major advantage of using a multichannel notification service is you can easily start sending notifications from other channels, such as SMS, push, and chat apps, using the same API. This means there’s less code to maintain when integrating multiple services and no additional work required to add a new channel or switch providers. Another advantage of using a service like is it allows non-technical users to edit the content, styling, and even branding of outgoing emails without involving developers or deploying code. You can easily preview your emails in Courier using dummy data and safely troubleshoot notifications in a separate test environment before pushing to production. Courier Drawbacks of using a multichannel notification service The drawbacks of using a multichannel notification service are similar to directly integrating with a transactional email API. You are relying on a third party to manage your message assembly, sending, and delivery. Plan to spend time researching your options and exploring the product before making a decision. Courier has a , which includes 10,000 notifications per month. generous free plan Tutorial: How to send emails with Nodemailer and SMTP is a Node.js module used for sending emails and is the most popular Node.js email package. You can use Nodemailer to create HTML or plain-text emails, add attachments, and send your emails through different transport methods, including built-in SMTP support. It requires Node.js 6.0 or newer. Nodemailer Let’s walk through how to send email using Nodemailer. The first step is to create a Node.js application: mkdir email-nodeapp && cd email-nodeapp 
    npm init -y Here you’ve created a folder and initialized a file using the command. The flag is there to skip the interactive back-and-forth questions by npm. package.json npm init -y Next, install the Nodemailer module: npm install nodemailer Nodemailer’s function specifies which method you want to use for sending an email. It takes the connection data and credentials as an argument. In this case, since SMTP is the preferred transport, you will need to define an SMTP host, port, and credential password for accessing a host SMTP server. createTransport To get a host URL, you need an SMTP server. For development purposes, you can use , or a similar service, to serve as a fake SMTP server. A fake SMTP server lets you avoid cluttering your real account with multiple tests while still seeing how your test emails behave — do all the buttons work the way they’re supposed to, is the formatting still correct after sending, and so on. Mailtrap Create a Mailtrap account if you don’t already have one. In the Integrations dropdown on the dashboard, select and copy the credentials displayed. Nodemailer Create an file and add the following: email.js const nodemailer = require('nodemailer');
      let transporter = nodemailer.createTransport({
             host: 'smtp.mailtrap.io',
             port: 2525,
             auth: {
                 user: "<user>",
                 pass: "<pass>"
             }
     }) Substitute the host, user, and password with the Mailtrap credentials you copied from the dashboard above. Now you can send an email using the method of Nodemailer’s function. sendMail createTransport Append the following to the : email.js message = {
         from: "from-example@email.com",
         to: "to-example@email.com",
         subject: "Subject",
         text: "Hello SMTP Email"
    }
    transporter.sendMail(message, **function**(err, info) {
         if (err) {
           console.log(err)
         } else {
           console.log(info);
         } Nodemailer also supports sending emails using HTML. All you need to do is add the attribute to your message object like so: html message = {
         from: "from@email.com",
         to: "to@email.com",
         subject: "Subject",
         html: "<h1>Hello SMTP Email</h1>"
     } To test that it works, go to your terminal and run: node email.js Go to your Mailtrap dashboard to see your email was received. Tutorial: How to send emails using a transactional email API There are a variety of email-as-a-service platforms and APIs, such as and , among others. For this article, I’ll demonstrate sending emails from within a Node application using SendGrid, which allows you to send up to 100 emails per month for free. SendGrid Mailgun To start sending emails with SendGrid, the first step is to for the service. Then you’ll need to create a SendGrid API key for sending emails. sign up To create an API key, go to Settings > API Keys on SendGrid’s dashboard, then click “Create API Key.” Give the key a name, select “Full Access,” then click “Create & View.” Copy your API key and keep it safe for later use. Next, install the SendGrid JavaScript client with npm: npm install --save @sendgrid/mail Create a file in your project directory named : sendgrid.js touch sendgrid.js In the file, add the following lines of code: sendgrid.js const sendgrid = require('@sendgrid/mail');

    const SENDGRID_API_KEY = "<SENDGRID_API_KEY>"

    sendgrid.setApiKey(SENDGRID_API_KEY)

    const msg = {
       to: 'test@example.com',
     // Change to your recipient
       from: 'test@example.com',
     // Change to your verified sender
       subject: 'Sending with SendGrid Is Fun',
       text: 'and easy to do anywhere, even with Node.js',
       html: '<strong>and easy to do anywhere, even with Node.js</strong>',
    }
    sendgrid
       .send(msg)
       .then((resp) => {
         console.log('Email sent\n', resp)
       })
       .catch((error) => {
         console.error(error)
     }) Replace the variable with the SendGrid API key, you created previously and make sure the email address in the From field has been verified by SendGrid. You can do this by creating a . This verifies that the email address actually belongs to you. Also, replace the email address in the To field from to your test recipient. SENDGRID_API_KEY sender identity test@example.com To test that it works, run: node sendgrid.js To see if your email was delivered, check the SendGrid dashboard, and on the sidebar, select “Activity.” There, you should see the email you just sent. SendGrid will show you whether it was delivered or not and whether it has been opened. Tutorial: How to send emails using a multichannel notification service is a multichannel notifications platform that enables you to reach your users on any channel using one uniform API. With Courier, you can bring , including or any of the popular email APIs like , , and . Courier your own email service provider SMTP SendGrid Amazon SES Postmark To start using Courier, . You can send up to 10,000 notifications per month for free. create an account To use Courier to send transactional emails, head to the Courier dashboard and select on the lefthand menu. Then, click the “Create Notification” button. Designer Next, you’ll need to add at least one channel. There are different channel options such as email, push, SMS, and direct message. For this tutorial, select “Email” and add your third-party integration provider, such as SendGrid from the previous tutorial. Click on the plug icon in the sidebar on the left and select SendGrid or any other provider you would prefer, from the available list. To integrate SendGrid, just add your API key and a verified SendGrid “From address.” From there, you’ll want to add the content for your email notification. You can use the toolbar to drag and drop blocks for text, images, buttons, and more. You can even add Markdown or add code blocks to further customize your email. Next, send the email notification from within Node.js using the Courier npm package . To install it, run: @trycourier/courier npm install @trycourier/courier Create a file in your app directory named : courier.js touch courier.js Courier will automatically generate a code snippet for your notification, which you can copy-paste from the Send tab. Add the following lines of code to the file: const { CourierClient } = require("@trycourier/courier");

    const courier = CourierClient({ authorizationToken: "<AUTH_TOKEN>" });
      courier.send({
       eventId: "<EVENT ID>", *// your Notification ID
       recipientId: "<RECIPIENT_ID", *// usually your system's User ID
       profile: {
         email: "<EMAIL_ADDRESS>"
       },
       data: {} *// optional variables for merging into templates }).then((resp) => {
         console.log('Email sent', resp)
       })
       .catch((error) => {
         console.error(error)
       }); The Courier package is imported into the file, and the Courier client is instantiated. The client takes an authentication token, which you can get from the Courier notification settings created earlier. Click the gear icon from within your notification and copy the masked auth token. The Courier client has a send method that takes an event ID, which is either the or . The recipient Id should be a unique string you can use to identify the recipient and look them up in data logs. Note that refers to the email address of the recipient. notification ID custom event that you’ve mapped to your notification email To check the status of your email, head to the in your Courier dashboard. Courier will tell you if your email has been delivered, opened, and/or clicked. Courier will also tell you if there are any errors and when in the delivery pipeline they occurred. Data tab Conclusion In this guide, we’ve explored methods for sending email in a Node.js web application. You’ve learned how to use SMTP and Nodemailer, a transactional email service (in this case, SendGrid), and a multichannel notifications service (in this case, ). Hopefully, reviewing these pros and cons will help you pick the best option for efficiently and securely sending emails in your web application. Courier

Send Emails with Node.js: A How-To Guide

Hello world! In preparation of a talk for an in Hamburg I struggled and stumbled upon some documentations and tutorials for using Bitbucket and Heroku together. So I’ve decided to write my own first developer article about Atlassian Community Event Building a basic CI/CD pipeline for deploying a to using React App Heroku Bitbucket Getting Started Step 1 — Create React app In this tutorial we will focus on deploying a React app to Heroku, so we will just use the React starter app. To run the App in Heroku we’ll add a basic express server setup later on. Prerequisite for creating and running a React app make sure you have: 1. and installed Node.js npm 2. installed (optional) Visual Studio Code Now with that basic setup we are ready to create our React app: npx create-react-app name- -your-app of Depending on your development environment grap yourself a coffee, the next 2–5 minutes are not that interessting, except you like watching how all the project dependencies are downloaded and bundled together. After you are back, type the following lines into your terminal to start the app cd name- -your-app
npm start of You can now view the app in a browser by open the URL http://localhost:3000 Step 2 — Create Bitbucket Repository Now that we have our app up and running on our local machine we should create our git repository. Therefore we head over to . If you don’t have an account yet, get one its for free (important nowadays)! https://bitbucket.org When creating a new repository you need to at least give it a name and you want to set the access level to private. Most of the settings here can be changed afterwards. Well done! You’ve created your — maybe first — git repository. Time to explore the menu which you’ll now see on the lefthand side. If you want to know more about Bitbucket head over to the . official documentation Step 3 — Create Heroku App We are pretty close to deploying our app now. Head over to - again create an account if you don’t have one (IT’S FREE!). https://heroku.com On your dashboard click and choose . In the dialog: New Create new app 1. Set a - this one is unique world-wide, so it might happen that some else already picked or - be creative! App Name test123 demoapp 2. Choose the where your app should run Region Your app is now created, but before you head back to your code and git repository we need to tell our app which we’d like to use. Buildpack Go to in your AppUnder click and choose Settings Buildpacks Add buildback heroku/nodejs For deploying the app later on we also need an API Key. 1. In your Profile go to Account Settings 2. In the Section click API Key Reveal 3. Safe the key for later configuration Deploy with Bitbucket pipelines Now comes the fun part… for you actually, I learned the hard way so you don’t have to. Step 1 — Setup an express Server Go to Visual Studio Code and add a new folder called to the root of the repository. Within that folder create a file called and install express by running this command in your terminal: server server.js npm install express --save Within the file copy & paste these lines of code: server.js path = ( ); express = ( ); app = express(); publicPath = path.join(__dirname, , ); port = process.env.PORT || ;app.use(express.static(publicPath));app.get( , (req, res) => {
    res.sendFile(path.join(publicPath, ));
});app.listen(port, () => { .log( + port);
}); const require 'path' const require 'express' const const '..' 'build' const 3000 '*' 'index.html' console 'Hello World I run on PORT ' In your file change the script line for start your app to: package.json : , "start" "node server/server.js" Step 2 — Upload everything to your git repository Open a terminal windows make sure you are in the root directory of your React app and type the following lines: git init
git add .
git commit -m git remote add origin https: git push -u origin master "initial commit" //username@bitbucket.org/username/name-of-your-repository.git When you refresh the browser page you should see all the files and folders of your app we’ve just commited the the git repository. Step 3 — Setup and configure Bitbucket pipelines Now that our code is in our repository we need to enable Pipelines for our repository. Go to Repository SettingsUnder the Section click Right above Settings, go to Add a variable with name HEROKU_API_KEY and your key from aboveAdd a variable with name HEROKU_APP_NAME and the app name as value Pipelines SettingsEnable Pipelines Repository variables Now we can finally create our Pipeline configuration. In our case we want (not true, the author wants it!) to build a pipeline with following rules and steps: 1. We don’t have branches yet, so everytime someone commits something to the master branch we want to run our pipeline 2. We want to test our app first 3. We need to create a Zip file for the heroku pipline add-on 4. We want to finally push our repository to Heroku Author’s note: YES, I could push the repository to Heroku using git, but NO that was not my intention for writing this article! The file holds all the build configurations for your repository. There is really a lot you can do with this file, so if you want to dig deeper take a look at the . Here the basics of the file: bitbucket-pipelines.yml official documentation YAML : contains all your pipeline definitions. pipelines : contains the steps that run on every push if one of the following criteria is not met. default : each step starts a new Docker container with a clone of your repository, then runs the contents of your section. step script : a list of commands that are executed in sequence. script :  a pipe is more like an add-on or function, it takes some input and does stuff for you — like uploading your repository to Heroku pipe Our final file looks like this: bitbucket-pipelines.yml image: node: pipelines:
  branches:
    master:
      - step:
          name: Test App
          caches:
            - node
          script:
            - rm -rf package-lock.json
            - rm -rf node_modules
            - npm install
            - npm run test
       - step:
           name: Create artifact
           script: 
             - git archive --format=tar.gz master -o                   application.tar.gz 
         artifacts: 
           - application.tar.gz
       - step:
           name: Deploy to heroku
           deployment: production
           caches:
             - node
           script:
             - pipe: atlassian/heroku-deploy: variables:
                 HEROKU_API_KEY: $HEROKU_API_KEY
                 HEROKU_APP_NAME: $HEROKU_APP_NAME
                 ZIP_FILE: WAIT: 10.15 .3 1.1 .4 "application.tar.gz" 'true' The END Hope you liked it, even more I hope it helps you! Please let me know via comment or clap :) About Jodocus is a full-service provider for Atlassian Systems based in Hamburg, Düsseldorf and Cologne Germany. Our team combines more than 25 years of experience in building and running the solution you need. We are Atlassian experts and know how to analyze and understand your problems. Innovative and future-proof solutions are our passion and we always meet our customers at eye-level. Jodocus About the Author Jan Szczepanski specializes in project and process management and has been an Atlassian specialist since the beginning of his professional career. He was in charge of technical as well as non-technical teams in different companies and was responsible for the optimization of business processes. Today he uses his specialist knowledge, which he has acquired over many years, in to improve communication and collaboration structures.

Stories, News & Mentions about LEFTLANE

Leftlane’s Stories on HackerNoon