Converting array of bytes to the hex string representation Is it possible to make the hexStr function faster?

#include <sstream>
#include <iomanip>
#include <stdio.h>

std::string hexStr(unsigned char* data, int len)
{
    std::stringstream ss;
    ss << std::hex;
    for(int i=0;i<len;++i)
        ss << std::setw(2) << std::setfill('0') << (int)data[i];
    return ss.str();
}

int main()
{
   std::string packet = "";
   packet += 0x6b;
   packet += 0x0f;
   std::string hex = hexStr((unsigned char*)packet.c_str(), packet.length());
   printf("%s\n", hex.c_str()); // 6b0f
   return 0;
}

Yes, but I doubt you'll see any practical difference with such short input.

Two ideas: reduce the number of possible dynamic allocations, and do the conversion yourself with a small lookup table.

You can do both of these by pre-allocating the string container (you know the target size already), then doing the hex conversion manually. Something like this:

constexpr char hexmap[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                           '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};

std::string hexStr(unsigned char *data, int len)
{
  std::string s(len * 2, ' ');
  for (int i = 0; i < len; ++i) {
    s[2 * i]     = hexmap[(data[i] & 0xF0) >> 4];
    s[2 * i + 1] = hexmap[data[i] & 0x0F];
  }
  return s;
}

Running this on my machine, with a test string that is 128k times 256 chars (from 0 to 255) gives me about 1.1s for your code, and about 0.18s for mine (redirecting to /dev/null to avoid I/O issues).

This should be at least not-worse than your version for small strings - there's no opportunity for the compiler to make a sub-optimal inlining decision on the string stream operators in particular, and (named) RVO will take care of eliding the copy from the return value to the caller's std::string hex.

Small benchmark to test this on (bad quality) pseudo-random 300 char long strings:

#include <sstream>
#include <iomanip>
#include <stdio.h>
#include <ctime>
#include <vector>

std::string hexStr(unsigned char *data, int len)
{
  std::stringstream ss;
  ss << std::hex;
  for (int i = 0; i < len; ++i)
    ss << std::setw(2) << std::setfill('0') << (int)data[i];
  return ss.str();
}

constexpr char hexmap[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                           '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};

std::string hexStr2(unsigned char *data, int len)
{
  std::string s(len * 2, ' ');
  for (int i = 0; i < len; ++i) {
    s[2 * i]     = hexmap[(data[i] & 0xF0) >> 4];
    s[2 * i + 1] = hexmap[data[i] & 0x0F];
  }
  return s;
}

int main()
{
  srand(time(NULL));
  std::vector<std::string> data;

  for (int i = 0; i < 1000; i++) {
    std::string packet;
    for (int i = 0; i < 300; i++)
      packet += static_cast<char>(rand() % 256);
    data.push_back(packet);
  }
  for (int i = 0; i < 10; i++) {
    clock_t beg = clock();
    for (auto const &s : data) {
      std::string hex = hexStr((unsigned char *)s.c_str(), s.length());
      printf("%s\n", hex.c_str());
    }
    fprintf(stderr, "Elapsed 1: %f\n",
            (clock() - beg) / (1.0 * CLOCKS_PER_SEC));
    beg = clock();
    for (auto const &s : data) {
      std::string hex2 = hexStr2((unsigned char *)s.c_str(), s.length());
      printf("%s\n", hex2.c_str());
    }
    fprintf(stderr, "Elapsed 2: %f\n",
            (clock() - beg) / (1.0 * CLOCKS_PER_SEC));
  }
}

Sample output compiled with clang++ (3.5) -std=c++11 -O3 (doesn't vary too much), stdout redirected to /dev/null:

Elapsed 1: 0.018132
Elapsed 2: 0.001365
Elapsed 1: 0.017858
Elapsed 2: 0.001373
Elapsed 1: 0.018429
Elapsed 2: 0.001313
Elapsed 1: 0.018918
Elapsed 2: 0.001229
Elapsed 1: 0.019134
Elapsed 2: 0.001244
Elapsed 1: 0.018915
Elapsed 2: 0.001239
Elapsed 1: 0.018031
Elapsed 2: 0.001266
Elapsed 1: 0.018051
Elapsed 2: 0.001239
Elapsed 1: 0.017071
Elapsed 2: 0.001315
Elapsed 1: 0.017841
Elapsed 2: 0.001239


Binary Search Tree delete function I have implemented this delete function for BST. Tt takes care of all the three cases, deleting node with 0, 1, or 2 children.

I have added comments throughout to explain my decisions. Is it sloppy or acceptable? Will I get full marks if this was a question in an exam to implement the delete function of a BST?

//I am having the node start parameter, so I can specify from where the
//deletion starts. So I can use it for recursion for the third case,
//where the node to be deleted has 2 children.
public void delete(Node start, int data) {
    if(root == null) return;

    /*If I want to call this method from any other class, I will pass in
    null as the start node, since I don't have reference to the root in
    that class.
    I have this start parameter because in the case of a node having 2
    children, I am calling this method recursivly to delete, but I don't
    want to start from the root in that case. See below, last else */
    Node parent = start == null ? root : start;
    Node current = parent;
    boolean isLeftNode = false;

    while(data != current.getData() && current != null) {
        parent = current;

        if(data < current.getData()) {
            current = current.getLeftNode();
            isLeftNode = true;
        }
        else {
            current = current.getRightNode();
            isLeftNode = false;
        }
    }

    //If not found.
    if(current == null) return;

    if(current == root) {
        root = null;
        return;
    }
    //Case 1: If node to be removed is a leaf, no children.
    if(current.getLeftNode() == null && current.getRightNode() == null) {
        if(isLeftNode)
            parent.setLeftNode(null);
        else
            parent.setRightNode(null);
    }
    //Case 2: If node to be removed has only 1 child.
    else if(current.getLeftNode() != null && current.getRightNode() == null) {
        if(isLeftNode)
            parent.setLeftNode(current.getLeftNode());
        else
            parent.setRightNode(current.getLeftNode());
    }
    else if(current.getLeftNode() == null && current.getRightNode() != null) {
        if(isLeftNode)
            parent.setLeftNode(current.getRightNode());
        else
            parent.setRightNode(current.getRightNode());
    }
    //Case 3: If node to be deleted has 2 children.
    else {
        Node smallest = findSmallest(current.getRightNode());
        current.setData(smallest.getData());
        //Calling recursion to delete the smallest. Because the smallest
        //might have a right subtree. Explanation above relates to this.
        delete(current.getRightNode(), smallest.getData());
        //Calling the delete method to start deleting from the right sub
        //tree since at this point there is a duplicate value, I can't
        //start from the root.
    }
}

public Node findSmallest(Node start) {
    //This is so in the main method, I can call findSmallest and pass in
    //null to search the whole tree. Because in main, I won't have reference
    //to the root. I have the start parameter so I can specifiy where to
    //start the search, because of the way I am dealing with deleting
    //a node with 2 children. See above.
    Node smallest = start == null ? root : start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}

public Node findSmallest(Node start) {
    //This is so in the main method, I can call findSmallest and pass in
    //null to search the whole tree. Because in main, I won't have reference
    //to the root. I have the start parameter so I can specifiy where to
    //start the search, because of the way I am dealing with deleting
    //a node with 2 children. See above.
    Node smallest = start == null ? root : start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}

I would break this into two methods:

public Node findSmallest() {
    return findSmallest(root);
}

private Node findSmallest(Node candidate) {
    // I have the start parameter so I can specify where to
    // start the search, because of the way I am dealing with deleting
    // a node with 2 children. See above.
    while (candidate.getLeftNode != null) {
        candidate = candidate.getLeftNode();
    }

    return candidate;
}

Now your external caller isn't asked to pass information that it doesn't have.  And you don't have to check whether the method is being called internally or externally on every call.

I prefer the name candidate to smallest for accuracy's sake.  Until the last iteration, it's not the smallest.  It's a candidate to be the smallest on every iteration.

    }
    //Case 3: If node to be deleted has 2 children.
    else {

I'm not a fan of the half-cuddled else in the first place, but if you have to use it, please use it without separation.  It's bad enough that C-style languages (e.g. Java) do not explicitly end their if/then blocks.  Adding arbitrary content between the then block and the else just makes this worse.

    }
    else {
        // Case 3: If node to be deleted has 2 children.

Now I can easily see that there is an else.  I don't have to scroll down to the next statement to see if it might be an else.

Also, there are four cases, not three.  Your case 2 is two cases:  a null left child or a null right.

    while(data != current.getData() && current != null) {

This is a bug.  Create a test case where the data is not found and you'll see.


Performance of a method to mask all but one rectangular element on the page The point of this code is to mask a page where the user is editing the page's 'body' content. This is in a CMS. The rest of the page is the website template (i.e. header, index bar etc...). I've covered resizing the window, and the DIV itself growing larger.

I'd love to know if there is a more efficient way to do this. I've used a DIV position: fixed as a mask under the editable DIV but some of our templates have irregular background colours (or images) and I really want to have a transparent editing area so that the experience is as close as possible to the end result.

If it's not apparent, this code creates a DIV whose borders cover the space that the editable DIV does not take up on the document. As the page resizes or the editable DIV changes size, these borders need to change size.

NOTE: The outer container may have overflow: hidden applied (thus the need to append the mask to the body element). The intention of the mask is to prevent clicking on any other area of the page other than the area that is being edited.

var content_builder_element = $("#content_builder");

var mask = $('

');

buildMask(content_builder_element, mask, false);

$('body').append(mask);

$(window).resize(function() {
    buildMask(content_builder_element, mask, true);
});

window.setInterval(function() {
    buildMask(content_builder_element, mask, true);
}, 100);

function buildMask(reference, mask, resize) {
    var offset = reference.offset();
    var height = reference.outerHeight(true);
    var width = reference.outerWidth(true);

    // We don't want the width of the masks to mess with the document width
    if (resize) {
        mask.css('borderRightWidth', 0);
        mask.css('borderBottomWidth', 0);
    }

    var document_width = $(document).width();
    var document_height = $(document).height();

    mask.width(width);
    mask.height(height);

    mask.css('borderTopWidth', offset.top);
    mask.css('borderRightWidth', document_width - offset.left - width);
    mask.css('borderBottomWidth', document_height - offset.top - height);
    mask.css('borderLeftWidth', offset.left);
};
body {
  background-color: orange;
}

.content_builder_mask {
  border: 0px solid rgba(0, 0, 0, 0.6);
  position: absolute;
  top: 0;
  left: 0;
}

#somecontainer {
  margin: 50px;
  overflow: hidden;
  }

#content_builder {
  min-height: 200px;
  position: relative;
  z-index: 500;
}
<!DOCTYPE html>

It is not entirely clear to me what the goal of that mask exactly is, but I guess you want to bring focus to your content div while editing it (correct me if I'm wrong, perhaps a simple demo would be nice to see what you want to achieve exactly)

If my assumption is correct, I would keep thing a lot simpler, and let css take care of things. This is by far the most performant solution I believe, since browser are obviously quite well optimized for applying css.

You could just apply a ridiculously large box shadow to your focus div, which will obscure the rest of the content, while keeping it's background in tact. No need to alter your DOM and check for resizes or anything. The css would look something like this:

div[contenteditable] {
  box-shadow: 0 0 0 9999px rgba(0,0,0,.8);
}

I've set up a very simple demo to demonstrate (hit the edit button to see the effect, and edit the content to see how it reacts on resize)

$('button').click(function() {
 $('div').first().attr('contenteditable', true);
});
body {
  background: red;
}

div[contenteditable] {
  box-shadow: 0 0 0 9999px rgba(0,0,0,.8);
}

Test CMS

  Lorem ipsum

  Lorem ipsum

<button>edit</button>


if-elseif chain. Is there a better pattern? I'm working on a TCP Server using .NET and the following code is my first attempt to process the received data (from the socket) to create a packet to deliver. Basically, the packet has a header (7 bytes) where the first 3 bytes are always 0x12 0x34 0x89 and the next 7 bytes are the message length. For example:

0x12 0x34 0x89 0x00 0x00 0x00 0x02 0x20 0x20

The packet then is a 2 length packet and the sent data is 0x20 0x20.

To process this I am using an if-elseif chain, which I don't like. Is there a better pattern to take away that if-elseif chain?

    public void ProcessIncomingData(byte[] buffer, int length)
    {
        for (int i = 0; i < length; i++)
        {
            ProcessByte(buffer[i]);
        }
    }

    private void ProcessByte(byte b)
    {
        if (_status == PacketStatus.Empty && b == FirstHeaderByte)
        {
            _status = PacketStatus.FirstHeaderReceived;
        }
        else if (_status == PacketStatus.FirstHeaderReceived && b == SecondHeaderByte)
        {
            _status = PacketStatus.SecondHeaderReceived;
        }
        else if (_status == PacketStatus.SecondHeaderReceived && b == ThridHeaderByte)
        {
            _status = PacketStatus.ThirdHeaderReceived;
        }
        else if (_status == PacketStatus.ThirdHeaderReceived || _status == PacketStatus.ReceivingPacketLenght)
        {
            const int sizeOfInt32 = sizeof (int);
            const int sizeOfByte = sizeof (byte);

            _packetLength |= b << (sizeOfInt32 - ++_packetLenghtOffset) * sizeOfByte;
            _status = _packetLenghtOffset < 4 ? PacketStatus.ReceivingPacketLenght : PacketStatus.ReceivingData;
        }
        else if (_status == PacketStatus.ReceivingData)
        {
            _packet.Add(b);
            var receivedByteCount = _packet.Count;
            if (receivedByteCount == _packetLength)
            {
                var packetData = new byte[_packet.Count];
                _packet.CopyTo(packetData);

                var receivedPacketHandler = PacketReceived;
                if(receivedPacketHandler != null)
                {
                    receivedPacketHandler(this, new PacketReceivedEventArgs{ Packet = packetData });
                }
                ResetControlVariables();
            }
        }
    }

Simple pattern: Set up a hash table or map that maps the incoming byte to a function that returns the correct response.

(C++ pseudocode - can be done in C# as well - don't have time now for all the implementation details:)

__statusType responseFunc(_statusType,byte);

map<byte,responseFunc> responseMap;

private void ProcessByte(byte b)

{
  _status= responseMap[_status](_status,b);
}

Although you have some nested conditions, etc, your handler functions can deal with those conditions - but you may have to rethink your design and set up some classes that properly represent and understand your conditions. A long switch case or 'if else if' is invariably the result of poor design. You need to think carefully about your architecture.

Another thing to consider is abstracting your conditions a bit and setting up an enumeration or class hierarchy to represent them. They can then be used as the key for your map or a parameter to your handler functions.

Yes - this is work - but clean design does require some effort. If you don't like long conditional statements (and you shouldn't) put in the effort to clean them up.

You should think along those lines - maps, dictionaries, enumerations, class hierarchies, factories, etc - whenever you run into a situation that seems to require an extended 'if else if..' or 'switch case';


From a set of words, output all words that fit a string of random letters (like Scrabble) I am in my first year of programming with Python 3 and am wondering if anyone had a better way to program this problem. When the user provides up to 7 random letters as a single string, the program should read the ‘wordlist.txt’ file, list the words from that file that can be constructed using some or all of those letters.

For example, if the user provides three letters, ‘AER’ as a string, the program will suggest the following words from the given file:
'AE', 'AR', 'ARE', 'EA', 'EAR', 'ER', 'ERA', 'RE'

This is what I have for now:

wordlist=list(line.strip('\n') for line in open('wordlist.txt','r'))

def wordFinder():
    words=[]
    letters=str.upper(input('enter up to 7 letters:'))
    for word in wordlist:
        candidate=True
        letterlist=list(letters)
        for letter in word:
            if letter not in letterlist:
                candidate=False
                break
            else:
                letterlist.remove(letter)
        if candidate==True:
            words.append(word)
    return words

>>>options()

enter up to 7 letters:aer
>>>['AE', 'AR', 'ARE', 'EA', 'EAR', 'ER', 'ERA', 'RE']

Even though it works I am looking to see if there is an easier/more efficient way for doing it. I came close with list comprehension, but I couldn't figure out how to avoid input letters matching more than once with the potential words.

def options2():
    words=[]
    letters=set(str.upper(input('Enter up to 7 letters:')))
    words=[w for w in wordlist
        if set(w).issubset(letters)
        and len(w)<=len(letters)]
    return words

>>>options2()

enter up to 7 letters:aer
>>>['AA','AE','AR','ARE','EA','EAR','EE','ER','ERA','ERE','ERR','RE','REE']

If any changes could be made for the second function to work that would be awesome.

The way you handle the file is not ideal. It's not apparent in such a small program, but you are not .close()-ing the file after opening it. Of course, Python will close the file once the program is done running, but in a bigger application, using your method would get clunky since you would have to remember to call .close() each time you open a file. Python's with keyword can take care of that for you, though.

with open('wordlist.txt','r') as file:
    wordlist=list(line.strip('\n') for line in file
    # more file handling code...

# file will be automagically closed after `with` block exits

I think your wordFinder function does too much (also per PEP8 convention it should be named word_finder). I would expect a function named like that to just find and return words, but it also handles user input, which I think should be a separate function.

Speaking of handling input, your program does not seem to handle non-letter characters at all. What happens when a user enters abc_123 as input? I'm guessing it will just use ABC_123 to look in your file, and return results for ABC after it finds nothing for _123. My suggestion would be to get input in a while loop, and exit the loop only after validating it:

input_is_only_letters = False
while not input_is_only_letters:
    letters = str.upper(input('enter up to 7 letters:'))
    if letters.isalpha():
        input_is_only_letters = True
    else:
        print('Please enter only letters A-Z (not case sensitive)')

I would also wrap this logic into its own function that returns the input.

A few small things:

Since you are using Python 3, you can (and IMO should) use type hints, which I did in the below code.
Get in the habit of making a separate function for each "action" or separate type of thing. This makes debugging and testing code much easier.
When you assign values, use a space on each side of the equal sign, e.g., my_value = 42.
Use snake_case naming for functions, variables, etc.
You don't need to check for if my_var == True: or if my_var == False:, you can simply write if my_var: and if not my_var:
Try to get in the habit of writing docstring for your functions, you will thank yourself later when you or others have to revisit your code.
Get in the habit of executing your self-contained calls in if __name__ == '__main__', so that if you were to import this into another module it wouldn't execute the file itself when it's loaded. See this article on thepythonguru.com for more information.
I haven't looked at your list comprehension code, maybe someone else will think of a way to do it that way.

My refactored code.

Note that I don't have a way to test it, to the best of my knowledge it should work fine but please let me know if I made an error.

from typing import List

def get_7_letters_input() -> str:
    """Captures up to 7 letters from stdin"""
    input_is_only_letters = False
    while not input_is_only_letters:
        letters = str.upper(input('enter up to 7 letters:'))
        if letters.isalpha():
            if len(letters) <= 7:
                input_is_only_letters = True
            else:
                print('Please enter no more than 7 letters')
        else:
            print('Please enter only letters A-Z (not case sensitive)')
    return letters

def get_words_from_file(filename: str) -> List:
    """Opens a file and splits it into a list for each new line"""
    with open(filename, 'r') as file:
        return list(line.strip('\n') for line in file

def find_words_matching_letters(letters: str) -> List:
    """Find words that match the letters provided"""
    words = []
    word_list = get_words_from_file('wordlist.txt')

    for word in word_list:
        candidate = True
        letterlist = list(letters)
        for letter in word:
            if letter not in letterlist:
                candidate = False
                break
            else:
                letterlist.remove(letter)
        if candidate:
            words.append(word)
    return words

if __name__ == '__main__':
    find_words_matching_letters(get_7_letters_input())


Hash Table insertion linear probinig My code is working fine Could you please review how I can make it more accurate and efficient?

import java.util.Scanner;

public class LinearProbing {

    public static void hash(String store[],int index,int num){
        if (store[index].equals(" ")) {
            store[index] = String.valueOf(num);
        } else {
            index++;
            if(index==10){
                index=0;
            }
            hash(store,index,num);
        }

    }

    public static void main(String args[]) {
        String store[] = new String[10];
        for (int a = 0; a < store.length; a++) {
            store[a] = " ";
        }

        Scanner input = new Scanner(System.in);

        int num;
        int index;

        for (int a = 0; a < store.length; a++) {
            System.out.print("Enter Num: ");
            num = input.nextInt();
            index = num % 10;
            hash(store,index,num);
        }

        for (int a = 0; a < store.length; a++) {
            System.out.println("Index: "+a+ "Store: "+store[a]);
        }

    }

}

You do not have to initialize string array with "". By default array values will be initialized with null. So afterwards, you can check if (store[index] == null).
You are already doing '%' operation in for loop, no need to check if(index == 10)
String array is not required at all as mentioned by @kraskevich. But if you do need, make it as a property of class LinearProbbing. So that you do not have to pass it within methods.
No actual implementation of Hash is involved. So better rename methods.


Reducing nested while statements for building a grid? I have the following grid shape:

 __ __ __
|__|__|__|
|__|__|__|

I have the following 3 types of shapes to fill it (they cannot rotate):

 __
|__|    __
|__|   |__|   (6x6 one above, or full size)

I have also 3 "shape lists" that need to fill it in priority, as in:

ShapeList1 = all types
ShapeList2 = all types
ShapeList3 = only single type

The lists are actually stacks, and I cannot have any empty spaces. I also need to pop the the first shape off each stack, if it does not fill it, go to the next type. ShapeList3 will always be able to complete the grid as it only has the 1x1 type. If it gets to the end of ShapeList3 I try the shapes in order again, trying to fill the grid, until the shape is filled.

I have this working but I have a lot of while loops, including a nested loop. This is a code smell and I feel as if I could do this better. Here's my current building code in pseudo-C#:

    var largeContentBlock = new LargeContentBlock();

    while (!largeContentBlock.Complete && aggregatePageFeed.ShapeList3.Any())
    {
    while (aggregatePageFeed.ShapeList1.Any()
                    && largeContentBlock.CanAddBlock(aggregatePageFeed.ShapeList1.Peek().Size)
                    && !largeContentBlock.Complete)
    {
        largeContentBlock.Add(aggregatePageFeed.ShapeList1.Pop());
    }

    while (aggregatePageFeed.ShapeList2.Any()
           && largeContentBlock.CanAddBlock(aggregatePageFeed.ShapeList2.Peek().Size)
           && !largeContentBlock.Complete)
    {
        largeContentBlock.Add(aggregatePageFeed.ShapeList2.Pop());
    }

        if (!largeContentBlock.Complete && largeContentBlock.CanAddBlock(aggregatePageFeed.ShapeList3.Peek().Size))
            largeContentBlock.Add(aggregatePageFeed.ShapeList3.Pop());
    }

    return largeContentBlock;

That's pretty ugly, I have it a little nicer by wrapping the while statements in functions. What pattern can I be using to make this nicer? I feel as if this is a solved problem.

There is a fair amount of common code that can be extracted into a function.

There is a common check in the while clause and the if clause.

boolean CanAdd(LargeContentBlock largeContentBlock, ShapeList shapes)
{
    return largeContentBlock.CanAddBlock(shapes.Peek().Size)
                && !largeContentBlock.Complete;
}

The two inner while loops are doing the same thing, just with two different lists. This is a perfect instance to abstracting the common code into a function.

void AddContent(LargeContentBlock largeContentBlock, ShapeList shapes)
{
    while (shapes.Any() && CanAdd(largeContentBlock, shapes))
    {
        largeContentBlock.Add(shapes.Pop());
    }
}

Now your code looks like:

var largeContentBlock = new LargeContentBlock();

while (!largeContentBlock.Complete && aggregatePageFeed.ShapeList3.Any())
{
    AddContent(largeContentBlock, aggregatePageFeed.ShapeList1);
    AddContent(largeContentBlock, aggregatePageFeed.ShapeList2);

    if (CanAdd(largeContentBlock, aggregatePageFeed.ShapeList3))
        largeContentBlock.Add(aggregatePageFeed.ShapeList3.Pop());
}

return largeContentBlock;


Basic call-and-response Slack bot I'd love thoughts on how to make this more elegant. I'm planning to add some additional functionality, but basically this is just my first pass at creating a pythonic Slack bot from scratch.

You need Slack API token to run it. I am deploying to Heroku, so I have it looking for an environment variable called API_TOKEN which I set (in bash, anyway) export API_TOKEN='abc-1234xyzFakeTokenString'

There are two files, app.py:

from slackclient import SlackClient
import time
import re
import datetime

class Bot(object):

    def __init__(self, token, searches):
        self.searches = searches
        self.client = SlackClient(token)
        self.username = {}
        self.user_id = {}

    def run(self):
        if self.client.rtm_connect():
            try:
                self.user_id = self.client.api_call("auth.test")['user_id']
                self.username = self.client.api_call("auth.test")['user']
                self._log(self.username + ": " + self.user_id)
            except:
                print Exception
            while True:
                self.process_messages(self.client.rtm_read())
                time.sleep(0.25)
        else:
            self._log("Connection failed.")

    def _log(self, message, level=' DEBUG '):
        """
        TODO this should actually put logs somewhere useful;
        """
        print str(datetime.datetime.utcnow()) + level + message

    def filter_speak(self, room, message):
        """
        posts a message to a channel if it matches the call.
        """
        for call in self.searches:
            response = self.searches[call]
            if re.search(call, message):
                self.client.api_call("chat.postMessage", as_user="true",
                                     channel=room, text=response)

    def process_messages(self, messages):
        for msg in messages:
            # We're only interested in entries of type "message"
            if msg['type'] == "message":
                # TODO also check the text of expanded links.
                if 'text' in msg:
                    body = msg['text']
                elif 'subtype' in msg:
                    if msg['subtype'] == "message_changed":
                        body = msg['message']['text']
                else:
                    self._log(msg + " didn't appear to have text or subtype?")

                if 'user' in msg:
                    if msg['user'] != self.user_id:
                        self.filter_speak(message=body, room=msg['channel'])

And then in a separate run.py file I have:

from app import Bot
from os import environ

pairs = {}

pairs["[kK]nock[, -]*[kK]nock"] = "Who's there?"

pope_bot = Bot(environ['API_TOKEN'], pairs)
pope_bot.run()

I'm hoping to add a bit more functionality -- I'd like it to chirp a few more things when prompted by a DM, for instance, but this works so I wanted feedback on how I could streamline it or what you might have done differently.

It is almost never a good idea to catch all exceptions in one block.  If you are using a try block, there are probably certain types of exceptions that you are expecting.  If some exception shows up that you aren't expecting, you want to know about it.  It should be thrown -- stop the program -- let's deal with this.  Make a list of the exceptions that you want to catch.  Add them to your except line with parentheses around them and commas between them.  If you want to print the exception, add as e: to the end and put print e inside the block.  Doing print Exception means this is your output:

<type 'exceptions.Exception'>

I don't think that is what you want.

Getting key-value pairs in a dictionary is so common that Python made it easy.  You can use something like for call, response in self.searches.items(): in filter_speak().  Since you are using Python 2, it would be more memory-efficient to use .iteritems() (In Python 3, .iteritems() was removed and .items() changed to take its place.)

You seem to have a bug.  What if msg does not have the text key, does have the subtype key, but msg['subtype'] does not equal message_changed?  What if msg also has the user key and msg['user'] does not equal self.user_id?  Wheew, that takes a lot.  If all of that happens, your program will have a NameError because you never define body in that first sentence, but it is required in the second.  You need to combine the elif and the if inside it:

if msg['type'] == "message":
    if 'text' in msg:
        body = msg['text']
    elif msg.get('subtype') == "message_changed":
        body = msg['message']['text']
    else:
        ...

Your later if statements can be combined:

if msg.get('user') != self.user_id:
    ...

Ah, the wonderful advantage of dict.get().


Get all the PDF files from FTP server in different folders Well, quite a biggie with all the foreach's. It works, it gets me 981 results, but there must be a way to shorten this code. Right?

<?php

$class = new FTPcleanup();
echo $class->index();

class FTPcleanup {

    private $server = "1.1.1.1";
    private $user   = "ftpuser";
    private $passwd = "ftppassword";
    private $path   = "/Folder/Productthingfolderthing/";

    private function connect_ftp() {
        $connection = ftp_connect($this->server);

        ftp_login($connection, $this->user, $this->passwd);
        ftp_chdir($connection, $this->path);

        return $connection;
    }

    private function connect_sql() {

    }

    private function get_files_from_ftp() {
        $FinalObjectList = array();

        $connection = $this->connect_ftp();

        $folders = ftp_nlist($connection, ".");

        foreach($folders as $folder) {
            ftp_chdir($connection, $this->path.$folder);

            $subfolders = ftp_nlist($connection, ".");
            if (count($subfolders !== 0)) {
                foreach ($subfolders as $subfolder) {

                    if (ftp_size($connection, $subfolder) == "-1") {
                        //Folder, open and go on to child folders
                        if(ftp_chdir($connection, $this->path.$folder."/".$subfolder)){
                            $childfolders = ftp_nlist($connection, ".");

                            if (count($childfolders !== 0)) {
                                foreach ($childfolders as $childfolder) {
                                    if (ftp_size($connection, $childfolder) == "-1") {
                                        //Folder, open and then add files to array.
                                        if(ftp_chdir($connection, $this->path.$folder."/".$subfolder."/".$childfolder)) {
                                            $folderobjects = ftp_nlist($connection, ".");

                                            foreach ($folderobjects as $folderobject) {
                                                $FinalObjectList[] = $this->path.$folder."/".$subfolder."/".$childfolder."/".$folderobject;
                                            }
                                        }

                                        else {
                                            print_r($this->path.$folder."/".$subfolder."/".$childfolder);
                                            echo "
";
                                        }

                                    }
                                    else {
                                        $FinalObjectList[] = $FinalObjectList[] = $this->path.$folder."/".$subfolder."/".$childfolder;
                                    }
                                }
                            }
                        }
                        else{
                            print_r($this->path.$folder."/".$subfolder);
                            echo "
";
                        }
                    }
                    else {
                        $FinalObjectList[] = $FinalObjectList[] = $this->path.$folder."/".$subfolder;
                    }
                }
            }
        }
        return $FinalObjectList;
    }

    public function index () {
        $SortedObjectList = array();

        $objectlist = $this->get_files_from_ftp();
        foreach($objectlist as $object) {
            $chunks = explode("_", $object);
            $strippath = explode("/", $chunks[0]);

            $SortedObjectList[end($strippath)] = $object;

            unset($chunks);
            unset($strippath);
        }

        var_dump(count($SortedObjectList));

    }
}

Verify the return values of all the ftp_chdir() calls. Otherwise, you might be way off, fetching the wrong stuff.

Excessive nesting is a problem. As in most programming tasks, here you have one goal, and many things that can go wrong along the way. You want to return early if an error occurs. A general pattern to follow is:

if (OK1 != ($result1 = operation1(…))) {
    return null; # or however you want to indicate failure
}
if (empty($result2 = operation2(…))) {
    return $result2; # nothing more to do
}
$retval = array('something involving' => $result2);
return $retval;

Note that all calls to functions that can fail occur within a if condition. The handler for the exceptional case follows immediately, and usually involves bailing out. Then the success codepath is linear and doesn't need to be nested.


Macro for counting number of elements in an array We all know the classic version of counting the number of elements in a C array: sizeof(a)/sizeof(*a)

But this is dangerous, because if used on a pointer it will return garbage values.

So I made this macro, utilizing gcc extensions. As far as I can tell, it works the way it is supposed to, which is causing compiler error when used on a pointer instead of array.

#define COUNT(a) (__builtin_choose_expr( \
                  __builtin_types_compatible_p(typeof(a), typeof(&a[0])), \
                  (void)0, \
                  (sizeof(a)/sizeof(a[0]))))

/* Only to demonstrate how to use the macro. It's not part of the code
   I want reviewed. */
int main(void)
{
    int arr[5];
    int *p;
    int x = COUNT(arr);

    // This line will yield the compiler error:
    //     error: void value not ignored as it ought to be
    int y = COUNT(p);
}

Any suggestions? Have I missed anything crucial?

We need to protect a when it's an expression - we've put parens around a[0] where we should have put them around a:

(sizeof(a)/sizeof(a)[0])

For the same reason, I think that the second typeof should be

typeof(&(a)[0])

I have to admit that I can't easily contrive an expression of array type where the parens make a difference, but better safe than sorry...


Project Euler: primes in Python This is a Python module I have just finished writing which I plan to use at Project Euler.  Please let me know how I have done and what I could do to improve it.

# This constant is more or less an overestimate for the range in which
# n primes exist.  Generally 100 primes exist well within 100 * CONST numbers.
CONST = 20

def primeEval(limit):
    ''' This function yields primes using the
    Sieve of Eratosthenes.

    '''
    if limit:
        opRange = [True] * limit
        opRange[0] = opRange[1] = False

        for (ind, primeCheck) in enumerate(opRange):
            if primeCheck:
                yield ind
                for i in range(ind*ind, limit, ind):
                    opRange[i] = False

def listToNthPrime(termin):
    ''' Returns a list of primes up to the nth
    prime.
    '''
    primeList = []
    for i in primeEval(termin * CONST):
        primeList.append(i)
        if len(primeList) >= termin:
            break
    return primeList

def nthPrime(termin):
    ''' Returns the value of the nth prime.

    '''
    primeList = []
    for i in primeEval(termin * CONST):
        primeList.append(i)
        if len(primeList) >= termin:
            break
    return primeList[-1]

def listToN(termin):
    ''' Returns a list of primes up to the
    number termin.
    '''
    return list(primeEval(termin))

def lastToN(termin):
    ''' Returns the prime which is both less than n
    and nearest to n.

    '''
    return list(primeEval(termin))[-1]

# This constant is more or less an overestimate for the range in which
# n primes exist.  Generally 100 primes exist well within 100 * CONST numbers.
CONST = 20

def primeEval(limit):

Python convention says that functions should named lowercase_with_underscores

    ''' This function yields primes using the
    Sieve of Eratosthenes.

    '''
    if limit:

What is this for? You could be trying to avoid erroring out when limit=0, but it seems to me that you still error at for limit=1.

        opRange = [True] * limit

As with functions, lowercase_with_underscore

        opRange[0] = opRange[1] = False

        for (ind, primeCheck) in enumerate(opRange):

You don't need the parens around ind, primeCheck

            if primeCheck:
                yield ind
                for i in range(ind*ind, limit, ind):
                    opRange[i] = False

def listToNthPrime(termin):
    ''' Returns a list of primes up to the nth
    prime.
    '''
    primeList = []
    for i in primeEval(termin * CONST):
        primeList.append(i)
        if len(primeList) >= termin:
            break
    return primeList

You are actually probably losing out by attempting to stop the generator once you pass the number you wanted. You could write this as:

 return list(primeEval(termin * CONST))[:termin]

Chances are that you gain more by having the loop be in the loop function than you gain by stopping early.

def nthPrime(termin):
    ''' Returns the value of the nth prime.

    '''
    primeList = []
    for i in primeEval(termin * CONST):
        primeList.append(i)
        if len(primeList) >= termin:
            break
    return primeList[-1]

def listToN(termin):
    ''' Returns a list of primes up to the
    number termin.
    '''
    return list(primeEval(termin))

def lastToN(termin):
    ''' Returns the prime which is both less than n
    and nearest to n.

    '''
    return list(primeEval(termin))[-1]

All of your functions will recalculate all the primes. For any sort of practical use you'll want to avoid that and keep the primes you've calculated.


Generating stock prices using geometric brownian motion I am writing a c++ class of "A simple least squares approach" by Longstaff and Schwartz. I have only finished writing a function for creating the stock price paths using geometric brownian motion. I am still a bit of a novice when it comes to writing classes in c++ and I just want to see if there is anything I can improve on with what I have written so far.

That being said, should I include pointers or any other type of data structure to make the code better?

Here is my main.cpp:

#include <iostream>
#include <vector>
#include <random>
#include <time.h>
#include <math.h>
#include "LSM.h"

using namespace std;

int main(){
    const double r = 0.04;          // Riskless interest rate
    const double q = 0.0;           // Divident yield
    const double sigma = 0.20;      // Volatility of stock
    const double T = 1;             // Time (expiry)
    const int N = 2;                // Number of time steps
    const double K = 100.0;         // Strike price
    const double S0 = 102.0;        // Initial stock price
    const int M = 4;                // Number of paths
    const int R = 2;                // Choice of basis for Laguerre polynomial

    LSM Option_value(r,q,sigma,T,N,K,S0,M,R);

    return 0;
}

Here is the header file:

#include <iostream>
#include <vector>
#include <random>
#include <time.h>
#include <math.h>

using namespace std;

#ifndef LSM_H
#define LSM_H

class LSM {
public:
    // Overload Constructor
    LSM(const double, const double, const double, const int, const int, const double, const double, const int, const int);

    // Destructor
    ~LSM();

    // Generate M paths of stock prices (Geometric Brownian Motion)
    vector<double> GBM(const int, const int, const double, const double, const double, const double, const double);

private:
    // Member variables
    double new_r;
    double new_q;
    double new_sigma;
    int new_T;
    int new_N;
    double new_K;
    double new_S0;
    int new_M;
    int new_R;

};

#endif

and here is the .cpp file correlated to the header file above:

#include "LSM.h"

LSM::LSM( const double r, const double q, const double sigma, const int T, const int N, const double K, const double S0, const int M, const int R){
    new_r = r;
    new_q = q;
    new_sigma = sigma;
    new_T = T;
    new_N = N;
    new_K = K;
    new_S0 = S0;
    new_M = M;
    new_R = R;

    vector<double> v;
    v = GBM(new_M, new_N, new_T, new_r, new_q, new_sigma, new_S0);
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << endl;
    }

}

LSM::~LSM(){

}

vector<double> LSM::GBM(const int M, const int N, const double T, const double r, const double q, const double sigma, const double S0){
    double dt =  T/N;
    vector<double> Z;
    vector<double> S;
    S.push_back(S0);
    mt19937 e2(time(0));
    normal_distribution<double> dist(0.0, 1.0);
    for(int i = 0; i < M; i++){
        Z.push_back(dist(e2));
    }
    double drift  = exp(dt*(r-0.5*sigma*sigma));
    double vol = sqrt(sigma*sigma*dt);
    for(int i = 1; i < M; i++){
        S.push_back(S[i-1] * drift * exp(vol*Z[i]));
    }
    return S;
}

This looks like a really interesting use of Brownian motion! Neat idea! Here are some suggestions for improving the code:
Avoid using namespace std
In general, using using namespace std is a bad idea. In a header, it's a very bad idea. Here's one description of why.
Naming
You should name your function arguments in the header so a user of your code knows what they represent. For example, in the future, you might compile this into a library to include in other programs, and ship just the header and the compiled library. If you do that, a user of your library will have no idea what the arguments to the LSM constructor are. (And remember that that user may be a future you who doesn't remember all the details of the implementation!)
I'd also recommend that you use better names than 1 letter names that may be meaningless or worse, confusing to readers of your code. You have some great ideas for what the names should be in the comments in main(). Instead of adding comments to explain the names, just name the variables what you wrote in the comments. For example, instead of r, call it risklessInterestRate. Instead of q, call it dividendYield. Yes, it takes a little bit longer to type, but those few extra seconds of typing will end up saving minutes or hours of frustration if you get 2 of the variables with similar names confused (like M and N).
Headers
Only include what you need. Only include it where you need it. Your main() function doesn't need any header other than LSM.h, so it should be the only thing you include there. LSM.h doesn't need any of the files it has included except for <vector>. LSM.cpp should include those files instead because it does use them. It might not seem like a big deal now, but once your project gets a little bigger, including the wrong files or including files you don't need can really slow down a compile.
Constructors
In C++, the constructor should never call a virtual method of its own class because it's not yet fully constructed. Luckily your code does not do that. But it does call a non-virtual method. When I see that, it raises a red flag to me, because it's fairly common for a non-virtual method to later become virtual if a subclass needs to override it. For that reason, I tend to avoid calling any (non-static) methods of the same class within a constructor. Furthermore, the LSM::GBM function doesn't use any member variables or change any state in the object or call any member functions of LSM, so it could be implemented as a free-standing static function inside LSM.cpp. (Unless, of course, you're going to want other code outside the class to call it, in which case it should probably be a static member function of the LSM class.)
const
Nice use of const! So few people use it, so it's really refreshing to see it being used well. Good work!


Program that generates brainfuck code that outputs given text I created program that generates brainfuck code that outputs given text.
Arguments for the program are input file with the text and output file where code will be generated to.
Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALLOCATION_ERROR 1
#define FILE_ERROR 2
#define OTHER_ERROR 3

static inline FILE*
get_file_pointer(const char* filename,const char* mode){
    FILE* file_pointer=fopen(filename,mode);
    if(file_pointer==NULL){
        fprintf(stderr,"Error: failed to open file %s\n",filename);
        exit(FILE_ERROR);
    }
    return file_pointer;
}
static inline char*
int_to_brainfuck(int difference){
    if(difference==0)
        return ".";
    else{
        char character_in_loop=difference>0?'+':'-';
        difference=difference>0?difference:-difference;
        const unsigned int loop_body_length=17;
        const unsigned int number_of_ones=(unsigned int)(difference%10);
        const unsigned int number_of_tens=(unsigned int)(difference/10);
        char* brainfuck_code=calloc(number_of_tens+loop_body_length+number_of_ones+2,sizeof*brainfuck_code);
        if(number_of_tens>0){
            brainfuck_code[strlen(brainfuck_code)]='>';
            memset(brainfuck_code+strlen(brainfuck_code),'+',number_of_tens);
            strcat(brainfuck_code+strlen(brainfuck_code),"[<");
            memset(brainfuck_code+strlen(brainfuck_code),character_in_loop,10);
            strcat(brainfuck_code+strlen(brainfuck_code),">-]<");
        }
        memset(brainfuck_code+strlen(brainfuck_code),character_in_loop,number_of_ones);
        brainfuck_code[strlen(brainfuck_code)]='.';
        return brainfuck_code;
    }
}
static inline void
generate_code(FILE* input_file,FILE* output_file){
    int current_char,last_char=0;
    while((current_char=fgetc(input_file))!=EOF){
        char* brainfuck_code=int_to_brainfuck(current_char-last_char);
        fputs(brainfuck_code,output_file);
        if(brainfuck_code[0]!='.')
            free(brainfuck_code);
        last_char=current_char;
    }
}
static inline void
parse_args(int argc){
    if(argc!=3){
        puts("Usage: bfgen <input> <output>");
        exit(OTHER_ERROR);
    }
}
int
main(int argc,char** argv){
    parse_args(argc);
    FILE* input_file=get_file_pointer(argv[1],"r");
    FILE* output_file=get_file_pointer(argv[2],"wb");
    generate_code(input_file,output_file);
    fclose(input_file);
    fclose(output_file);
    return 0;
}

I opened your code in CLion. The first thing it marked was:

#define ALLOCATION_ERROR 1

It's unused.

Other than that, there were no warnings, which is already quite good.

Next I compiled your code using both GCC and CLang:

$ gcc -Wall -Wextra -Os -c bfgen.c
$ clang -Wall -Weverything -Os -c bfgen.c
bfgen.c:5:9: warning: macro is not used [-Wunused-macros]
#define ALLOCATION_ERROR 1
        ^
1 warning generated.

That's also good. You prepared your code quite well for this code review by fixing the compiler warnings (if there had been any).

Now to the human part of the code review.

I would remove the inline from the function definitions. Trust the compiler to do the right thing here.

The word get in the function name get_file_pointer makes it sound as if this function had no side effects. This assumption is wrong. The function should have a better name. It is typical for these error-checking wrapper functions to be prefixed with x. You will find many implementations of xmalloc, xrealloc, xopen, and so on in other projects.

In the get_file_pointer function, you should include the kind of error in the fprintf output:

fprintf(stderr, "Error: failed to open file '%s': %s\n", filename, strerror(errno));

The function int_to_brainfuck has a bad name. It's clear from the function signature that it takes an int, therefore the function name should rather describe what that int means. It's a difference, but there is no documentation about what differs. After reading the whole code of the function I know that it's the difference between the previous character and the next character. This information should be encoded in the function name.

Calling strlen repeatedly is a waste of time. At each point in the code you know exactly how long the string is, therefore it is more efficient to just store the current end of the brainfuck_code in a pointer and always strcpy to that pointer:

size_t code_len = number_of_tens + loop_body_length + number_of_ones + 2;
char *brainfuck_code = calloc(code_len, sizeof *brainfuck_code);
char *code = brainfuck_code;

if (number_of_tens > 0) {
    *code++ = '>';
    memset(code, '+', number_of_tens);
    code += number_of_tens;
    strcpy(code, "[<");
    code += 3;
    memset(code, character_in_loop, 10);
    code += 10;
    strcpy(code, ">-]<");
    code += 4;
}

memset(code, character_in_loop, number_of_ones);
code += number_of_ones;
*code++ = '.';

assert(brainfuck_code + code_len == code);

return brainfuck_code;

I added the assert at the end because these explicit length calculations can always go wrong. If the compiler is smart enough, it will find out that this assertion always succeeds and may even eliminate it. And in case you forgot a character to change the code later, you will quickly get a crash dump instead of undefined behavior because of a buffer overflow.

I suspected you had already calculated the length wrong because I couldn't find the first character in the formula. Instead, there's a magic number 2 in that formula. You should make the formula correspond to the actual code by writing it like this:

size_t code_len = 1 + number_of_tens + 3 + 10 + 4 number_of_ones + 1;

This allows you to quickly compare it to the code.

Even better would be if you would not need this whole calculation at all. Since you are writing the output to a file anyway, you don't need to allocate the memory yourself. I'm thinking of two functions like these:

typedef struct {
    FILE *out;
} bfgen;

static void bfgen_emit_str(bfgen *gen, const char *code) {
    ...
}

static void bfgen_emit_repeat(bfgen *gen, char code, size_t n) {
    ...
}

Then you can simply write:

static void
bfgen_emit_difference(bfgen *gen, int difference) {
    if (difference == 0) {
        bfgen_emit_str(".");
        return;
    }

    char character_in_loop = difference > 0 ? '+' : '-';
    unsigned int abs_diff = difference > 0 ? difference : -difference;
    unsigned int number_of_tens = abs_diff / 10;

    if (number_of_tens > 0) {
        bfgen_emit_str(gen, ">");
        bfgen_emit_repeat(gen, '+', number_of_tens);
        bfgen_emit_str(gen, "[<");
        bfgen_emit_repeat(gen, character_in_loop, 10);
        bfgen_emit_str(gen, ">-]<");
    }

    bfgen_emit_repeat(gen, character_in_loop, abs_diff % 10);
    bfgen_emit_str(gen, ".");
}

This code looks much clearer. Now that you don't have to think about all this annoying buffer size calculation anymore, it becomes much easier to add new optimizations, such as avoiding the loop when number_of_tens is exactly 1. In the previous version of the code I wouldn't have added this feature out of laziness and fear of breaking things.

Based on this example, you can see that the functions bfgen_emit_str and bfgen_emit_repeat are really useful, and implementing them is easy.

static void bfgen_emit_str(bfgen *gen, const char *code) {
    fputs(code, gen->out);
}

static void bfgen_emit_repeat(bfgen *gen, char code, size_t n) {
    for (size_t i = 0; i < n; i++) {
        fputc(code, gen->out);
    }
}

Looking at bfgen_emit_difference again, that function doesn't do what its name says. It doesn't only emit code to calculate the difference, it also emits code to print the resulting character. It shouldn't do that. The call to bfgen_emit_str(gen, ".") belongs in bfgen_generate_code instead.

It doesn't matter anymore, but your original version of int_to_brainfuck was essentially:

static char *
int_to_brainfuck(...) {
    if (condition) {
        return ".";
    } else {
        return allocated_string;
    }
}

You must never write such a function since the caller cannot know whether they should free the string or not. This leads either to memory leaks or to undefined behavior. You don't want either of these.

In the main function, you should open the input file in binary mode and the output file in text mode. Currently it's the other way round.

The main takeaway from this code review is that it makes sense to define your own data structures and the corresponding functions. Make these functions as easy as possible to use. Free the caller from any unnecessary tasks such as calculating buffer sizes or managing memory, which are really boring and error-prone.

An idea for further work is to make the generated code more efficient by keeping track of the actual memory contents. This can now be easily done in the struct bfgen. Then you can look which memory cell has currently the closest value and use that instead of just using a single memory cell.

The rewritten and restructured code is:

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_ERROR 2
#define OTHER_ERROR 3

static FILE *
xfopen(const char *filename, const char *mode) {
    FILE *file_pointer = fopen(filename, mode);
    if (file_pointer == NULL) {
        fprintf(stderr, "Error: failed to open file '%s': %s\n",
                filename, strerror(errno));
        exit(FILE_ERROR);
    }
    return file_pointer;
}

typedef struct {
    FILE *out;
} bfgen;

static void
bfgen_emit_str(bfgen *gen, const char *code) {
    fputs(code, gen->out);
}

static void
bfgen_emit_repeat(bfgen *gen, char code, size_t n) {
    for (size_t i = 0; i < n; i++) {
        fputc(code, gen->out);
    }
}

static void
bfgen_emit_difference(bfgen *gen, int difference) {
    if (difference == 0) {
        return;
    }

    char character_in_loop = difference > 0 ? '+' : '-';
    unsigned int abs_diff = difference > 0 ? difference : -difference;
    unsigned int number_of_tens = abs_diff / 10;

    if (number_of_tens > 0) {
        bfgen_emit_str(gen, ">");
        bfgen_emit_repeat(gen, '+', number_of_tens);
        bfgen_emit_str(gen, "[<");
        bfgen_emit_repeat(gen, character_in_loop, 10);
        bfgen_emit_str(gen, ">-]<");
    }

    bfgen_emit_repeat(gen, character_in_loop, abs_diff % 10);
}

static void
bfgen_generate_code(bfgen *gen, FILE *input_file) {
    int current_char, last_char = 0;
    while ((current_char = fgetc(input_file)) != EOF) {
        bfgen_emit_difference(gen, current_char - last_char);
        bfgen_emit_str(gen, ".\n");
        last_char = current_char;
    }
}

static void
parse_args(int argc) {
    if (argc != 3) {
        puts("Usage: bfgen <input> <output>");
        exit(OTHER_ERROR);
    }
}

int
main(int argc, char **argv) {
    parse_args(argc);
    FILE *input_file = xfopen(argv[1], "rb");
    FILE *output_file = xfopen(argv[2], "w");
    bfgen gen = {output_file};
    bfgen_generate_code(&gen, input_file);
    fclose(output_file);
    fclose(input_file);
    return 0;
}


Calculate with numbers from different number systems This program calculates with numbers from different number systems and outputs the result in the desired number system.

You call it like that:

java Calculator <operator> <number> <base> <otherNumber> <base> (solutionBase)

Unfortunately it does not work with floating point numbers.

Example:

$java Calculator + 5234 7 FABCD43 16 3
200022201200110011

My gut feeling says me that my code is quite ugly but it doesnt tell me how to improve it. Do you have some hints for me how to make this more beautiful?

public class Calculator {
    public static void main(String[] args) {
        // display usage if user wants so
        if (args[0].contains("help")) {
            displayHelp();
            return;
        }

        // parse arguments
        String operator = args[0];
        String number1 = args[1];
        int baseOfNumber1 = Integer.parseInt(args[2]);
        String number2 = args[3];
        int baseOfNumber2 = Integer.parseInt(args[4]);
        int baseOfSolution = 0;
        if (args.length == 6) {
            baseOfSolution = Integer.parseInt(args[5]);
        }

        int number1Dec = randomBaseToDecimal(number1, baseOfNumber1);
        int number2Dec = randomBaseToDecimal(number2, baseOfNumber2);

        // calculate and print out
        int solutionDec = 0;
        if (operator.equals("+")) {
            solutionDec = number1Dec + number2Dec;
        } else if (operator.equals("-")) {
            solutionDec = number1Dec - number2Dec;
        } else if (operator.equals("x")) {
            solutionDec = number1Dec * number2Dec;
        } else if (operator.equals("/")) {
            solutionDec = number1Dec / number2Dec;
        }

        if (args.length == 6) {
            System.out.println(decimalToRandomBase(solutionDec,
              baseOfSolution));
        } else {
            System.out.println(solutionDec);
        }
    }

    private static int randomBaseToDecimal(String number, int base) {
        int result = 0;
        for (int i = 0; i < number.length(); i++) {
            int digit = Character.getNumericValue(number.charAt(i));
            result = base * result + digit;
        }
        return result;
    }

    // works only till base 16
    private static String decimalToRandomBase(int number, int base) {
        StringBuilder finalNumber = new StringBuilder();
        while (number != 0) {
            if ((number % base) > 9) {
                switch ((number % base)) {
                    case 10: finalNumber.append("A"); break;
                    case 11: finalNumber.append("B"); break;
                    case 12: finalNumber.append("C"); break;
                    case 13: finalNumber.append("D"); break;
                    case 14: finalNumber.append("E"); break;
                    case 15: finalNumber.append("F"); break;
                }
            } else {
                finalNumber.append(number % base);
            }
            number = number / base;
        }
        return new StringBuilder(finalNumber).reverse().toString();
    }

    private static void displayHelp() {
        System.out.println("This program calculates with numbers of different bases");
        System.out.println("Example: ");
        System.out.println("java Calculator + 34 5 554 6");
        System.out.println("You can also specify the base of the output number as the last argument:");
        System.out.println("java Calculator + 34 5 554 6 2");
    }
}

Main feedback has already been given by @AJNeufeld and this post is not about the performance of your program but rather other aspects.

You should try putting a check before you access an index in an array and slightly change your if block from this,

if (args[0].contains("help")) {

to,

if (args.length == 0 || args[0].contains("help") || args.length < 5) {

as the former will run into ArrayIndexOutOfBoundsException if no argument is passed. Also it would be helpful to call the displayHelp() method in case no argument (args.length == 0) was passed so the user knows the usage of program.

Also, for safely accessing array indexes, you should put another OR condition args.length < 5 which will ensure at least five parameters are passed, else again you may run into ArrayIndexOutOfBoundsException.

These checks should make the program a little more safer.


Alternating Characters Online challenge on Hacker Rank.

  Shashank likes strings in which consecutive characters are different.
  For example, he likes ABABA, while he doesn't like ABAA. Given a
  string containing characters A and B only, he wants to change it
  into a string he likes. To do this, he is allowed to delete the
  characters in the string.

  Your task is to find the minimum number of required deletions.

  Input Format

  The first line contains an integer T, i.e. the number of test cases.
  The next T lines contain a string each.

  Output Format

  For each test case, print the minimum number of deletions required.

public class Solution {
    private static int countChanges(String text) {
        char[] chars = new char[text.length()];
        int top = -1;

        int count = 0;
        for (char c : text.toCharArray()) {
            if (top < 0 || c != chars[top]) {
                chars[++top] = c;
            } else {
                // top >= 0 or c == chars[top]
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        for (int i = 0; i < N; i++) {
            System.out.println(countChanges(s.next()));
        }
    }
}

No need for stack

You've complicated things by constructing a stack for no reason.  All you need to remember is the last character.  For example:

private static int countChanges(String text) {
    char prev  = 0;
    int  count = 0;

    for (char c : text.toCharArray()) {
        if (c == prev) {
            count++;
        } else {
            prev = c;
        }
    }
    return count;
}

Misleading comment

This comment:

            // top >= 0 or c == chars[top]

should read:

            // top >= 0 and c == chars[top]


Deleting a node from a binary search tree I have read about it at a few places and tried to write my own version.  I would like to get it reviewed.

class Node {
    private int value;
    private Node left;
    private Node right

    // getters and setters
}

public class DeleteNodeBST {

    Node parent = null;

    boolean deleteNodeBST(Node node, int value) {
        if (node == null) {
            return false;
        }
        if (node.getValue() == value) {

            if ((node.getLeft() == null) && (node.getRight() == null)) {
                // leaf node
                node = null;
                return true;
            }

            if ((node.getLeft() != null) && (node.getRight() != null)) {
                // node with two children
                node.setValue(findMinimumAndReturnWithDelete(node.getRight()));
                return true;
            }

            // either left child or right child
            if (node.getLeft() != null) {
                parent.setLeft(node.getLeft());
                node = null;
                return true;
            }

            if (node.getRight() != null) {
                parent.setRight(node.getRight());
                node = null;
                return true;
            }
        }
        parent = node;
        if (node.getValue() > value) {
            return deleteNodeBST(node.getLeft(), value);
        } else {
            return deleteNodeBST(node.getRight(), value);
        }
    }

    int findMinimumAndReturnWithDelete(Node node) {
        if (node.getLeft() == null) {
            int v = node.getValue();
            node = null;
            return v;
        }
        return findMinimumAndReturnWithDelete(node.getLeft());
    }
}

Here is how I would do this. I've sprinkled comments throughout the code, so hopefully this will be helpful.

//generalize the node to work for types other than just int
public class Node<T extends Comparable<? super T> >
{
    private T value; //get; set;
    private Node<T> left; //get; set;
    private Node<T> right; //get; set;

    /**
     * construct a Node with value
     *
     * @param val value for this node
     */
    public Node(T val)
    {
        value = val;
        left = null;
        right = null;
    }

    /**
     * copy constructor
     *
     * @param n node to copy from
     */
    public Node(Node<T> n)
    {
        value = n.value;
        left = n.left;
        right = n.right;
    }

    /**
     * @return true if this node has no children
     */
    public boolean isLeaf()
    {
        return (left == null && right == null);
    }

    public Node<T> getLeft() { return left; }
    public Node<T> getRight() { return right; }
    public T getValue() { return value; }
    public void setLeft(Node<T> n) { left = n; }
    public void setRight(Node<T> n) { right = n; }
    public void setValue(T v) { value = v; }
}

And the BST. Since it doesn't really make sense to delete without being able to add nodes to the tree first, I've put in adding as well.

public class DeleteNodeBST<T extends Comparable<? super T> >
{
    private Node<T> root = null;
    private int nodes = 0; //get;

    /**
    * add a node to the tree
    *
    * @param n node to add
    * @return true if add is successful
    */
    public boolean add(final Node<T> n)
    {
        //null guard
        if (n == null || n.getValue() == null)
        {
            return false;
        }

        boolean isSuccessful;
        if (root == null)
        {
            root = n;
            ++nodes;
            isSuccessful = true;
        }
        else
        {
            isSuccessful = findHome(root, n);
        }

        return isSuccessful;
    }

    /**
     * create a node containing input value and add it to the tree
     *
     * @param val value for new node
     * @return true if add is successful
     */
    public boolean add(final T val)
    {
        return add( new Node<T>(val) );
    }

    /**
     * attempt to place a node under another
     *
     * @param adoptor node to look under
     * @param adoptee child node looking for a home
     * @return true if child node finds a place, otherwise false
     */
    private boolean findHome(Node<T> adoptor, final Node<T> adoptee)
    {
        int comp = adoptor.getValue().compareTo( adoptee.getValue() );

        if (comp > 0)   //adoptor comps greater than adoptee, so go left
        {
            if (adoptor.getLeft() == null)
            {
                adoptor.setLeft(adoptee);
                ++nodes;
                return true;
            }
            //recurse until we find somewhere to place the adoptee node
            return findHome(adoptor.getLeft(), adoptee);
        }
        else if (comp < 0)  //adoptor comps less than adoptee, so go right
        {
            if (adoptor.getRight() == null)
            {
                adoptor.setRight(adoptee);
                ++nodes;
                return true;
            }
            //recurse until we find somewhere to place the adoptee node
            return findHome(adoptor.getRight(), adoptee);
        }

        return false;
    }

    /**
     * attempts to delete a node from the tree
     *
     * @param n node to delete
     * @return true if node is deleted, otherwise false
     */
    public boolean delete(Node<T> n)
    {
        //null guard
        if (n == null || n.getValue() == null)
        {
            return false;
        }

        return delete( n.getValue() );
    }

    /**
     * attempts to delete a node from the tree containing the value
     *
     * @param val value of node to delete
     * @return true if node is deleted, otherwise false
     */
    public boolean delete(final T val)
    {
        //the node to be deleted
        Node<T> target = null;
        //to keep track of parent node
        Node<T> parent = null;
        //variable node reference
        Node<T> node = root;

        while (node != null)
        {
            if (val.compareTo( node.getValue() ) == 0)  //eureka!
            {
                target = node;
                break;
            }
            else if (val.compareTo( node.getValue() ) > 0)  //target greater, so go right
            {
                parent = node;
                node = node.getRight();
            }
            else    //target less, so go left
            {
                parent = node;
                node = node.getLeft();
            }
        }

        if (target == null)
        {
            //target not found
            return false;
        }

        boolean isLeft = (target == parent.getLeft() );

        if (target == root) //the node that's baleeting is in fact the root node
        {
            //get last house on the left on the right!
            //it becomes the new root
            node = getLastHouseOnTheLeft( parent.getRight() );
            if (node != null)
            {
                node.setLeft( parent.getLeft() );
                node.setRight( parent.getRight() );
                root = node;
            }
        }
        else if ( target.isLeaf() )
        {
            if (isLeft)
            {
                parent.setLeft(null);
            }
            else
            {
                parent.setRight(null);
            }
        }
        else if (target.getLeft() != null && target.getRight() != null) //two children, some shuffling
        {
            if (isLeft)
            {
                parent.setLeft( target.getRight() );
                parent.getLeft().setLeft( target.getLeft() );
            }
            else
            {
                parent.setRight( target.getRight() );
                parent.getRight().setLeft( target.getLeft() );
            }
        }
        else    //one child is simpler
        {
            if (target.getLeft() == null)
            {
                if (isLeft)
                {
                    parent.setLeft( target.getLeft() );
                }
                else
                {
                    parent.setRight( target.getLeft() );
                }
            }
            else
            {
                if (isLeft)
                {
                    parent.setLeft( target.getRight() );
                }
                else
                {
                    parent.setRight( target.getRight() );
                }
            }
        }

        return true;    //baleeted
    }

    /**
     * extract the last house on the left
     *
     * @param start the node to start on
     * @return the last house on the left
     */
    private Node<T> getLastHouseOnTheLeft(final Node<T> start)
    {
        Node<T> candidate = null;
        Node<T> parent = null;
        Node<T> node = start;

        while (node != null)
        {
            if ( node.getLeft() != null )
            {
                parent = node;
                candidate = node.getLeft();
            }

            node = node.getLeft();
        }

        if (parent != null)
        {
            parent.setLeft(null);
        }

        return candidate;
    }

    /**
     * get a node from the value it's associated with
     *
     * @param v value as a key to finding the node containing it
     * @return node associated with the value
     */
    public Node<T> getNode(T v)
    {
        //null guard
        if (v == null)
        {
            return null;
        }

        Node<T> node = root;
        int comp;
        while (root != null)
        {
            comp = node.getValue().compareTo(v);
            if (comp == 0)
            {
                return node;
            }
            if (comp > 0)
            {
                node = node.getLeft();
            }
            else
            {
                node = node.getRight();
            }
        }

        return node;
    }

Finally, some simple test cases, plus an example graph:

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class TestDeleteNodeBST
{
    DeleteNodeBST<Integer> delBst;
    Node<Integer> node;

    @Before
    public void init()
    {
        delBst = new DeleteNodeBST<Integer>();

        assertTrue(delBst.getNumberOfNodes() == 0);
    }

    @Test
    public void testAddNode()
    {
        node = new Node<Integer>(1);
        assertTrue(node.getValue() == 1);
        assertTrue(node.getLeft() == null);
        assertTrue(node.getRight() == null);

        delBst.add(node);
        assertTrue(delBst.getNumberOfNodes() == 1);

        Integer two = 2;
        assertTrue( two > node.getValue() );
        assertTrue( two.compareTo(node.getValue() ) > 0 );

        delBst.add(two);
        assertTrue(delBst.getNumberOfNodes() == 2);
        assertTrue( delBst.getNode(2).getValue().equals(2) );
    }

    @Test
    public void testCorrectness()
    {
        delBst.add(5);
        delBst.add(4);
        delBst.add(3);
        delBst.add(2);
        delBst.add(1);
        delBst.add(0);
        assertTrue(delBst.getNumberOfNodes() == 6);

        node = delBst.getNode(3);
        assertTrue(node.getValue() == 3);
    }

    @Test
    public void testDeleteNode()
    {
        delBst.add(5);
        delBst.add(4);
        delBst.add(6);
        delBst.add(7);
        delBst.add(2);
        delBst.add(3);
        delBst.add(1);
        /*
         * tree should look like this now
         *           5
         *        4     6
         *      2         7
         *     1 3
         */
        assertTrue( delBst.delete(2) ); //3 should take 2's place
        assertFalse( delBst.delete(2) );//nothing to delete now
        node = delBst.getNode(3);
        assertTrue(node.getValue() == 3);
        assertTrue(node.getRight() == null);
        assertTrue(node.getLeft().getValue() == 1);
    }
}


var that = this; Keeping a class in scope of nested functions I've been using this syntax alot recently to keep my class in scope of nested functions. It seems to work well in small to moderately sized class but I'm starting to wonder how efficient it actually is and if there is a better way to handle this. Any suggestions would be really useful.

myClass.prototype.myMethod = function() {
    var that = this; // Without taking the size of the class into consideration
                     // does this create an unecessarily high load?
    function callback_one(data) {
        that.myOtherMethod();
    }

    function callback_two(data) {
        that.myErrorMethod();
    }

    $.post(this.getRequest(), this.getUrl())
        .success(function(data) {
            callback_one(data);
            // Can also use that.anotherMethod() here
        })
        .error(function(data) {
            callback_two(data);
            // Can also use that.anotherMethod() here
        });
}

Your code is fine (assuming your nested functions are merely proxies to the class methods), I would suggest if the only thing you are doing in the anonymous functions is calling the callbacks then you should just pass them in:
$.post(this.getRequest(), this.getUrl()).success(callback_one).error(callback_two);

There is nothing wrong with the use of that in this code.
Edit (after reading Esailija's answer)
You could also do the proxies mentioned in the Esailija's answer inline like so:
myClass.prototype.myMethod = function () {
    $.post(this.getRequest(), this.getUrl())
        .success($.proxy(this.myOtherMethod, this))
        .error($.proxy(this.myErrorMethod, this));
}

Essentially that is what you were doing with the nested functions; this just tightens the code by moving the proxy creation into a utility method.


Employees and Organizational Hierarchy Employee hierarchy in an Organization is classic example of modeling Composite design  pattern. Following are the details that are to be modeled:

There are two type of employees; Manager, and Developer.
A Manager manages a team that can comprise managers, and developer.
A Developer has fixed salary at given point of time and get work from the manager.
The salary of a manager is the sum of salary of all the team members + 10K.
We need to model work distribution, and salary of employees of the organization.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

class Employee {
   private:
      string _name;
   public:
      Employee(string name_) {
         _name = name_;
      }
      string name() {
         return _name;
      }
      void virtual work() = 0;
      float virtual salary() = 0;
};
// Common Interface to interact with Manager, and Developer
class Developer : public Employee {
   private:
      float _salary;
   public:
      Developer(string name_,float salary_) : Employee(name_),_salary(salary_) {}
      void work() {
         cout << "Developer " << name() << " Worked\n";
         // A developer works own.
      }
      float salary() {
         return _salary;
      }
};

class Manager : public Employee {
   private:
      vector<Employee*> _team;
   public:
      Manager(string name_) : Employee(name_) {}
      void add(Employee * emp_) {
          _team.push_back(emp_);
      }
      void work() {
         cout << "Manager " << name() << " Distributed Work\n";
         for(vector<Employee*>::iterator it = _team.begin(); it!=_team.end(); ++it) {
            (*it)->work();
         }
         // A manager distributes work in team members.
      }
      float salary() {
         float salary_ = 0.0;
         for(vector<Employee*>::iterator it = _team.begin(); it!=_team.end(); ++it) {
            salary_ += (*it)->salary()+15000;
         }
         return salary_;
         // Salary of a manager is derived from team members.
      }
};
int main() {
   Developer d1("developer1",10000);
   Developer d2("developer2",15000);
   Manager m1("manager1");
   m1.add(&d1);
   m1.add(&d2);
   Manager m2("manager2");
   m2.add(&m1);
   m2.work();
   return 0;
}

1. Don't use using namespace std

That's generally considered bad practice.

Rather use

using std::cout;
using std::cin;
using std::string;

if you want to avoid typing these out.

2. Use interfaces properly and don't mix them up with abstract class implementations

Instead of simply declaring an abstract class, sort out specific interfaces in 1st place

struct IEmployee {
      virtual const& string name() const = 0; // see 3. regarding const please
      virtual const float& salary() const = 0;
      virtual bool managesOtherEmployees() const = 0; // equivalent to isLeaf() in the
                                                      // common composite pattern
                                                      // examples
      virtual void work() = 0;
};

Add functionality as needed:

struct IManager {
    void add(IEmployee&) = 0;
    void delete(IEmployee&) = 0; // if you have functions to extend the
                                 // composition, you probably want to have
                                 // the reverse operation if reasonable.
                                 // Here it seems to be so, since managers
                                 // sometimes need to fire team members.
};

Provide the abstract class for the common implementation

class Employee : public IEmployee {
private:
    string name_; // Don't use prefix '_' for symbols, these are reserved
                    // for the compiler and standard library implementations (see 4.)
    float salary_;
public:
    Employee(string name, float salary) : name_(name), salary_(salary) {}
    string name() const override {
        return name_;
    }
    float salary() const override {
        return salary_;
    }
    bool managesOtherEmployees() const override { return false; }
};

2. leads to an implementation of Developer and Manager classes as follows:

class Developer : public Employee {
public:
    Developer(string name,float salary) : Employee(name,salary) {}
    void work() {
         cout << "Developer " << name() << " Worked\n";
         // A developer works own.
    }
};

class Manager : public Employee, public IManager {
private:
    vector<std::reference_wrapper<IEmployee>> team_;
public:
    Manager(string name, float salary) : Employee(name,salary) {}
    bool managesOtherEmployees() const override { return true; }
    void add(IEmployee& emp) override {
        team_.push_back(std::reference_wrapper<IEmployee>(emp));
    }
    void delete(IEmployee& emp) override {
        std::remove(team_.begin(),team_.end(),std::reference_wrapper<IEmployee>(emp));
    }
    void work() {
        cout << "Manager " << name() << " Distributed Work\n";
        for(auto& emp : team_) { // Use range based loops and auto whenever possible (see 5.)
            emp.work();
        }
        // A manager distributes work in team members.
     }
     float salary() const override {
        float accumulatedSalary = 0.0;
        for(const auto& emp : team_) { // Note const and reference again
            accumulatedSalary += emp.salary() +15000;
        }
        return accumulatedSalary;
        // Salary of a manager is derived from team members.
     }
};

3. Use const qualifiers as much as possible

If you're declaring a class operation (class member function), decide if this should change the class state in first place.
Append a const qualifier, if you decide it shouldn't.

Same for parameters and return values. Usually you don't have to worry about which method by value or by const reference will be more efficient.
With any sophisticated, modern c++ compiler, you can assume the most efficient emitted assembly code will be chosen.

Passing/returning by value, still might be prone to generate copies if RVO isn't applicable. Thus I simply prefer to be explicit about that.

4. Don't use symbol names prefixed with _

Symbol names prefixed with a single or double underscore (_) are preserved by the c++ standard for compiler internals and standard library implementations.

It's easy to come over that just using underscores as a postfix for symbols as indication of class member variables:

template<typename TValue>
class MyClass {
private:
     TValue myValue_;
public:
     MyClass(const TValue& myValue) : myValue_(myValue) {}
     const TValue& myValue() { return myValue_; } // standard getter signature
     void myValue(const & TValue value) { myValue_ = value; } // standard setter signature
};

The above pattern will serve 98% of cases unambiguously quite well.

5. Use range based loop syntax beyond c++98

Since c++11 standard was established, the language supports range based for() loops of the form

for(<type spec> el : <container_ref>) { /* ... */ }

You should use the auto keyword for <type spec>, it can be garnished with const and & as usual, and automatically evaluates a dereferenced Iterator when enumerating the Containers values.


Recursive sorting algorithm I wrote a recursive sorting algorithm and was wondering what would be the run time complexity of this. The bulk of the work is done in the push_up function, which I think is linear in time. There are a linear amount of recursive calls though. If \$n\$ is the length of the list, would the runtime then be \$O(n^2)\$?

def sort(lst):
    """Recursive sorting algorithm. Sorts the remainder of the list
    and then pushes the first element up to its appropriate position"""

   if lst == []:
       return []
   if len(lst) == 1:
       return [lst[0]]
   elt = lst[0]
   sorted_lst = sort(lst[1:])
   return push_up(elt, sorted_lst)

def insert(val, lst, i):
    """Inserts [val] into [lst] at index [i] """

    return lst[:i] + [val] + lst[i:]

def push_up(val, lst):
    """Pushes [val] up the list until it reaches its sorted position.
    Precondition: lst is sorted"""
    start = 0
    while start < len(lst) and lst[start] < val:
        start += 1

    return insert(val, lst, start)

Yes.

You can see that your sort function operates by recursing directly on itself, using a shorter-by-one version of its list parameter. This is stopped when the list is of length 0 or 1. (That code should be cleaned up.) So your sort recurses n-1 times, given n >= 2.

Each time it recurses, sort calls push_up once. The push_up function linearly scans the list, which is of length 1, then 2, then ... n-1.

So in the worst case (input array is reverse-sorted) you have scans of total length \$ \sum 1 ... (n-1) \$, which makes your code \$ O(n^2) \$.


Loading 'Plugins' in Ruby I have written a plugin loader in Ruby, and I would like to know if it uses the best technique to handle classes, or if anyone has any recommendations on how to improve my code.

I have written a class called PluginManager, and an accompanying module named Plugin. The names of these are self explanatory, one handles the plugins (loading them), and the other is a module to be included by plugin files.

My Plugin module looks like the following, and currently just replaces the puts method, to ensure all output comes through the logger. I had some issues with making the @@logger variable definable, and I have solved it, but I'm not sure if there is a better way to solve it.

module Plugin
    @@logger = nil

    def puts(string)
        if @@logger.nil?
            super(string)
        else
            @@logger.info string
        end
    end

    # I tried the following, but it didn't work (still said "undefined method 'logger='")

    # class << self
    #   attr_accessor :logger
    # end

    def self.logger=(string)
        @@logger = string
    end
end

My PluginManager class is a bit more complex, but not by much. It simply takes an array of file names, performs some checks to ensure everything exists, then loads them into the loaded_plugins array.

class PluginManager

    def initialize(logger=nil)
        set_logger logger
        @loaded_plugins = []
    end

    def set_logger(logger)
        @logger = logger
        Plugin.logger = logger
    end

    def load(plugins, directory="./plugins/")

        # Iterate through plugins
        plugins.each do |plugin|

            # Work out plugin information
            class_name = plugin.split(".").first.downcase.capitalize
            full_path = directory + plugin
            @logger.info "Loading \"#{class_name}\" from \"#{full_path}\""

            # Ensure the plugin file exists
            if File.file? full_path

                # Load the plugin file and ensure the class exists
                require full_path
                unless eval("defined? #{class_name}")
                    @logger.error "Class \"#{class_name}\" not found!"
                    next
                end

                # Get the plugin's class and ensure it includes plugin
                plugin_class = eval class_name
                if plugin_class.ancestors.include? Plugin

                    # Ensure the initialize method takes no arguments
                    if plugin_class.allocate.method(:initialize).arity > 0
                        @logger.error "\"#{class_name}.initialize\" accepts more than 0 arguments"
                        next
                    end

                    # Load the plugin itself by pushing it into the loaded_plugins list
                    @logger.info "Plugin \"#{class_name}\" loaded!"
                    @loaded_plugins.push plugin_class.new
                    @logger.info "Plugin \"#{class_name}\" enabled!"
                else
                    @logger.error "The class \"#{class_name}\" does not include Plugin!"
                    next
                end
            else

                # Check if the file exists, or is a directory
                unless File.exist? full_path
                    @logger.error "Unable to find file \"#{full_path}\""
                else
                    @logger.error "\"#{full_path}\" is a directory!"
                end

                next
            end
        end
    end
end

I am wondering if there are any better ways to perform some of the checks, such as using exec to find if a class exists.

Formatting

Indenting

The standard ruby indent is 2 spaces.  For example:

def puts(string)
  if @@logger.nil?
    super(string)
  else
    @@logger.info string
  end
end

Design

Class Variables

I would not use class variables to set the logging.  As you
discovered, they have surprising
behavior.

Instead, I would just use a class instance variable that belonged
just to the Plugin class and was not automatically shared with its
descendants.

module Plugin
  class << self
    attr_accessor :logger
  end
end

If that's all you do, then the descendants will have to do this to access the logger:

Plugin.logger.info 'Logging some info'

That's awful, so we'll add an instance method that defers to the class method:

module Plugin

  class << self
    attr_accessor :logger
  end

  def logger
    self.class.logger
  end

end

Now instances of Plugin can log easily:

logger.info "Logging some info"

Ruby tricks

Use #inspect to quote strings

Instead of this,

@logger.info "Loading \"#{class_name}\" from \"#{full_path}\""

Use #inspect to do the quoting for you:

@logger.info "Loading #{class_name.inspect} from #{full_path.inspect}"

Remove eval

You don't need eval here:

unless eval("defined? #{class_name}")

instead:

unless defined?(class_name)

ancestors.include?

Instead of this:

if plugin_class.ancestors.include? Plugin

do this:

if plugin_class < Plugin

See this SO answer, and the rdoc for Module#<

instance_method

Instead of this:

if plugin_class.allocate.method(:initialize).arity > 0

this:

if plugin_class.instance_method(:initialize).arity > 0

This avoids the funny business of allocating one.

exceptions

The code wishes, when a plugin cannot be added, to log it and continue
adding more plugins.  That works well, but the way it's done can be
simplified using exceptions.

Instead of this:

plugins.each do |plugin|
  ...
        unless eval("defined? #{class_name}")
            @logger.error "Class \"#{class_name}\" not found!"
            next
        end

  ...
end

consider this:

class PluginError < StandardError ; end

plugins.each do |plugin|
  begin
    ...
    unless eval("defined? #{class_name}")
      raise PluginError, "Class \"#{class_name}\" not found!"
    end
    ...
  rescue PluginError => e
    @logger.error e.to_s
  end
end

This gets rid of all of those "next" calls, simplifying the error handling.


Replace all occurrence of REP [block] with value of the block I have a block with an undefined data and a pair of REP [code]:

arr: [
    REP ["code1"]
    | 'something
     "f"
    | [ f | 3 ]
    REP [40 + 2]
    ]

The pair can be everywhere in the arr.
I replace every occurrence of a pair REP [code] with a value from evaluating the code.

t: true

while [t == true] [
    f: find arr 'REP
    either f [
        t: true
        change/part f do first next f 2
        ][
        t: false
        ]
]

Does this code follow common best practices? Does it have some security issues? Is there any problems with a performance using this code?

Does it have some security issues?

Well, you're doing an evaluation of code.  If that code comes from a foreign source somehow, that could be a problem.  If it's your code, it's no more dangerous than anything else.

But as you wrote it, it does have the property that it can infinite loop within itself.  Because after your substitution you start at the beginning again:

arr: [REP [quote REP]]

That's a stable state, but you could keep growing without bound too.

My answers will assume you didn't want this.

  Does this code follow common best practices?

It's C-like.  Rebol is a great language for writing bad C code.  :-)

Using COMPOSE is the obvious answer here:

>> compose [
    ("code1")
    | 'something
    "f"
    | [ f | 3 ]
    (40 + 2)
]
== ["code1" | 'something "f" | [ f | 3 ] 42]

And if you're worried your content contains parens that you want to leave in place, you can quote them:

>> compose [1 (quote (2 3)) 4]
== [1 (2 3) 4]

But if you want to work with the input as written, there's a lot of approaches.

The most "sensible" way--that the wiki regarding features in R3-Alpha suggests would work (but doesn't seem to)--would be:

>> parse arr [
    any [
        change ['REP blk: block!] (do blk/1)
        |
        skip
    ]
]

Which would more or less capture the essence of the task.  Any number of times, try and match a pattern of REP followed by a BLOCK!, marking the position prior to the block.  Then substitute the execution of do blk/1 for that code".  Otherwise skip and keep looking.

It gets almost there but misses the execution.  So it splices in do blk/1 literally:

== [do blk/1 | 'something "f" | [f | 3] do blk/1]

Try reporting a bug to...whoever works on that.  Or maybe to Red.  :-)

I've seen you mention you don't like UNTIL, so here's a FORALL-based solution...

forall arr [
    if arr/1 = 'REP [
        remove arr
        arr: back change arr do arr/1
    ]
]

(Note: I think forall should be called FOR-NEXT, because all it does is advance the argument until the end via NEXT.  You can modify it during the loop, and then it will run NEXT again.  It will be reset at the end.)

As a talking point on your code: Note that there are two FALSE? values (NONE! and LOGIC! false), and everything else is TRUE? (except unset which is neither).  So it's not that common to work with literal true and false.  NONE is almost always better as a contrast to some value you are interested in.

Just to show what kinds of tricks are available in an "imperative-series-assembly-language" with a WHILE approach: if we are walking along the array replacing, we might use the position back from FIND not being NONE! to cue continuation:

head while [arr: find arr 'REP] [
    arr: change/part arr do arr/2 2
]

It's able to work because change is designed for chaining, so it returns the point after the replacement.  Also because WHILE returns the last evaluation of the body.  So even though the condition wipes out the value of arr when the find comes back with NONE!, it can be recovered because the last time the body evaluated it was the end position of the CHANGE...and you can seek back to the head from that.

So there are a few possibilities.


Has the following query been made in the optimum way? SELECT p.name,m.name
FROM parts p
INNER JOIN Manufacturers m ON p.man_id=m.id
ORDER BY p.name DESC

If not, what should be done for its optimization?

Here is the two tables:

CREATE TABLE `Manufacturers` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `name` varchar(30) NOT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB

CREATE TABLE `parts` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `name` varchar(30) NOT NULL,
    `man_id` int(11) NOT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB

CREATE TABLE Manufacturers ( id int(11) NOT NULL AUTO_INCREMENT,
name varchar(30) NOT NULL, PRIMARY KEY (id) ) ENGINE=InnoDB

CREATE TABLE parts ( id int(11) NOT NULL AUTO_INCREMENT, name varchar(30) NOT NULL,
man_id int(11) NOT NULL, PRIMARY KEY (id) ) ENGINE=InnoDB

your structure looks OK for performance, because you have index the common field where you make the join on.  How ever, shouldn't you use PK and FK instead?.  If you need to know a bigger description use the explain command to be sure that the index are correctly used.