Portable C++98 thread class akin to std::thread I want a homegrown version of C++11's std::thread. My motivation is to avoid manual memory management of the arguments passed to the thread function. I'm restricted to C++98. I want better type safety than what's available in the POSIX and Win32 thread APIs.

Two notes:

I can't think of a way to avoid a heap allocation for the thunk argument. The thread instance could be deleted before the thunk has a chance to construct its arguments. I suppose I could wait on an event in the constructor signaled by thunk() once the thread is in a 'ready' state, but that seems horrible.
I'm not too concerned about exception safety as exceptions are disabled for most of this C++ codebase.

/* There is a portable thread implementation in C available already */
int portable_thread_create(portable_thread_t *)
{
    pthread_create() **OR**
    _beginthreadex()
}

#define PORTABLE_THREAD_FUNC_DECL void *
#define PORTABLE_THREAD_FUNC_DECL unsigned int __cdecl **OR**

void portable_thread_join(portable_thread_t)
{
    pthread_join() **OR**
    WaitForSingleObject()
}

template < typename TArg0 >
class thread
{
public:
    typedef void (*function_t)(TArg0);
    thread(function_t func, TArg0 arg0)
        : m_func(func)
    {
        m_arg0 = new TThunkArg(this, arg0);
        if (0 != portable_thread_create(&m_thread, thunk, m_arg0))
        {
            delete m_arg0;
            throw new std::runtime_error("Could not create a thread");
        }
    }

    void join()
    {
        portable_thread_join(m_thread);
    }

private:
    struct TThunkArg
    {
        thread<TArg0> *Self;
        TArg0 Arg0;
        TThunkArg(thread<TArg0> *self, TArg0 arg0)
            : Self(self)
            , Arg0(arg0)
        {}
    };
    static PORTABLE_THREAD_FUNC_DECL thunk(void *unsafe_args)
    {
        TThunkArg *args = reinterpret_cast<TThunkArg*>(unsafe_args);
        try
        {
            args->Self->m_func(args->Arg0);
        }
        catch(...)
        {
            delete args;
            throw;
        }

        delete args;
        return 0;
    }
    portable_thread_t m_thread;
    function_t m_func;
    TThunkArg *m_arg0;
};

You can put the unsafe_args in a auto_ptr so RAII can delete them safely. This is safe because you will not be copying it around.

static PORTABLE_THREAD_FUNC_DECL thunk(void *unsafe_args)
{
    std::auto_ptr<TThunkArg> args(reinterpret_cast<TThunkArg*>(unsafe_args));
    args->Self->m_func(args->Arg0);

    return 0;
}

Also don't worry about having to new the args; you are creating a new thread, this is much more expensive than a quick malloc call.


Morse code translator I have a Morse Code translator, which can translate text to Morse code and vice-versa. Note that for the two files that the first three lines are generated by the Code::Blocks IDE.

translator.h

#ifndef SPLIT_H_INCLUDED
#define SPLIT_H_INCLUDED
#endif // SPLIT_H_INCLUDED

#include <iostream>
#include <map>
#include <string>
#include "split.h"

std::string SPACE (" ");
std::map<char, std::string> charMap;
std::map<std::string, char> morseMap;
bool hasInit = false;

void init()
{
    charMap['a'] = ".-";
    charMap['b'] = "-...";
    charMap['c'] = "-.-.";
    charMap['d'] = "-..";
    charMap['e'] = ".";
    charMap['f'] = "..-.";
    charMap['g'] = "--.";
    charMap['h'] = "....";
    charMap['i'] = "..";
    charMap['j'] = ".---";
    charMap['k'] = "-.-";
    charMap['l'] = ".-..";
    charMap['m'] = "--";
    charMap['n'] = "-.";
    charMap['o'] = "---";
    charMap['p'] = ".--.";
    charMap['q'] = "--.-";
    charMap['r'] = ".-.";
    charMap['s'] = "...";
    charMap['t'] = "-";
    charMap['u'] = "..-";
    charMap['v'] = "...-";
    charMap['w'] = ".--";
    charMap['x'] = "-..-";
    charMap['y'] = "-.--";
    charMap['z'] = "--..";
    charMap['0'] = "-----";
    charMap['1'] = ".----";
    charMap['2'] = "..---";
    charMap['3'] = "...--";
    charMap['4'] = "....-";
    charMap['5'] = ".....";
    charMap['6'] = "-....";
    charMap['7'] = "--...";
    charMap['8'] = "---..";
    charMap['9'] = "----.";
    charMap['.'] = ".-.-.-";
    charMap[','] = "--..--";
    charMap['?'] = "..--..";
    charMap[' '] = "/";
    for (std::map<char, std::string>::iterator i = charMap.begin(); i != charMap.end(); i++) {
        morseMap[i -> second] = i -> first;
    }
}

std::string translateToMorse(std::string plainText)
{
    if (!hasInit) {
        init();
    }
    std::string result;
    for (int i = 0; plainText[i]; i++) {
        result.append(charMap[plainText[i]]);
        result.append(SPACE);
    }
    return result;
}

std::string translateFromMorse(std::string morseText)
{
    if (!hasInit) {
        init();
    }
    std::string result;
    std::vector<std::string> morse = split(morseText, SPACE[0]);
    for (std::vector<std::string>::iterator i = morse.begin(); i != morse.end(); i++) {
        result.push_back(morseMap[*i]);
    }
    return result;
}

split.h

#ifndef SPLIT_H_INCLUDED
#define SPLIT_H_INCLUDED
#endif // SPLIT_H_INCLUDED

#include <string>
#include <sstream>
#include <vector>

std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems) {
    std::stringstream ss(s);
    std::string item;
    while (std::getline(ss, item, delim)) {
        elems.push_back(item);
    }
    return elems;
}

std::vector<std::string> split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    split(s, delim, elems);
    return elems;
}

Concerns:

Are the three generated lines necessary and are they used correctly?
Is there a way to simplify the code?

I see a number of things that may help you improve your code.

Headers should not contain code

Header files in C++ should generally only contain other headers, definitions and structure and class definitions.  They should not contain code implementations, so neither of these .h files should really be .h files.  Instead they should both be .cpp files because they contain code implementations or they should be split into separate declaration/implementation (.h/.cpp) pieces.

Use objects

The init() function seems to me that it would be better implemented as an object constructor and then the individual functions could be static member functions.  Here's another way to do Morse conversion.

Eliminate global variables

There is really no reason here to have global variables.  Instead, these should be wrapped into an object, or at least a namespace.

Use const where practical

The SPACE variable should be const as should be the arguments to the functions.

Pass complex objects by reference

The std::string arguments to either of the functions should be a reference to avoid an unnecessary copy.  That is the function could instead be:

std::string translateToMorse(const std::string &plainText)

Consider the user

If someone very reasonably tries to translate a callsign such as W1AW they'll get back the string ".----" which is only the Morse code for '1'.  The problem is that the code only accepts lowercase characters and neither throws an error nor gives any indication that the uppercase characters were simply ignored.  That's not very helpful to the user.  Consider instead throwing an exception.  Simply ignoring characters is unlikely to be a desirable behavior in any case.

Eliminate split

The one place that split is used is in the translateFromMorse routine, but it's really not needed there.  Instead you could introduce new functions that would translate a word at a time and use std::stringstream to extract a word at a time for translation.


Single Page App - Browser Storage API Design I'm working on building a Browser storage handler for my single page application.  The idea is that you make an API call and the API calls the storage handler which either returns the local/session storage or if it doesn't exist it calls the actual web service.  The StorageHandler uses a Proxy to first check if the browser has local and session storage enabled.  The "callback" is really just an Axios instance with a base url and some headers attached.  TBH I'm not sure this is even remotely a good idea or if it should just be handled in the actual API since I've read wrapping a Promise with another Promise is a bad idea and I don't have much experience with proxies.

const StorageHandler = {
    TestedStorage: false,
    StorageEnabled: false,
    TestStorage() {
        this.TestedStorage = true;
        this.StorageEnabled = this.TestLocal();
        return this.StorageEnabled;
    },
    TestLocal() {
        if (typeof window.localStorage !== 'undefined') {
            try {
                const test = 'TEST';
                window.localStorage.setItem(test, test);
                window.localStorage.removeItem(test);
                return true;
            } catch (e) {
                return false;
            }
        }
        return false;
    },
    ClearLocal() {
        window.localStorage.clear();
    },
    UpdateLocalWithObj(url, obj) {
        window.localStorage.setItem(url, JSON.stringify(obj));
    },
    // Gets from local storage or calls api, burst refers to cache bursting
    GetOrSetLocal(url, callback, burst = false) {
        return new Promise((resolve, reject) => {
            let result;
            if (this.StorageEnabled && burst === false) {
                result = window.localStorage.getItem(url);

                if (result !== null && result !== 'null') {
                    resolve(JSON.parse(result));
                }
            }

            callback.get(url)
            .then((response) => {
                result = response.data;
                if (this.StorageEnabled) {
                    window.localStorage.setItem(url, JSON.stringify(result));
                }
                resolve(result);
            })
            .catch((error) => { reject(error); });
        });
    },
    ....
};

const ProxyHandler = {
    get(target, key) {
        if (target.TestedStorage === false) {
            target.TestStorage();
        }
        return target[key];
    },
};

const proxy = new Proxy(StorageHandler, ProxyHandler);

export default proxy;

You are correct that there is no need to wrap this with a promise. As it is, there are a few problems with the GetOrSetLocal function.

The function will always try to fetch the values from the server, even if it is cached locally.
The function's name is misleading, when first reading the code I assumed the function could be used to set a value in storage - not just retrieve values. I'm not really sure what to suggest for a name...
I would recommend using something other than callback for the Axios instance as it is decidedly not a callback. It might be best to just call it axios.
burst would be better named ignoreCache to more clearly indicate it's purpose.

If I was unable to use async/await, here is how I would write this function:

const StorageHandler = {
    ...,
    GetFromCache(url) {
        if (!this.StorageEnabled) return null
        return JSON.parse(localStorage.getItem(url))
    },
    GetOrSetLocal(url, axios, ignoreCache = false) {
        if (!ignoreCache) {
            return new Promise(resolve => {
                const cached = this.GetFromCache(url)
                resolve(cached === null ? this.GetOrSetLocal(url, axios, true) : cached)
            })
        }

        return axios.get(url)
            .then(response => {
                if (this.StorageEnabled) {
                    localStorage.setItem(url, JSON.stringify(response.data))
                }
                return response.data
            })
    },
}

Alternatively, if you are able to use async/await, I would prefer this version.

const StorageHandler = {
    ...,
    async GetOrSetLocal2(url, axios, ignoreCache = false) {
        if (!ignoreCache) {
            const cached = this.GetFromCache(url)
            return cached === null ? this.GetOrSetLocal2(url, axios, true) : cached
        }

        const { data } = await axios.get(url)

        if (this.StorageEnabled) {
            window.localStorage.setItem(url, JSON.stringify(data))
        }

        return data
    },
}

Another comment: I tend to avoid using proxies as I find they quickly multiply and end up making debugging a royal pain. It might be better to define StorageEnabled as a getter.

const StorageHandler = {
    TestedStorage: false,
    _StorageEnabled: false,
    get StorageEnabled() {
        if (!this.TestedStorage) {
            this.TestStorage()
        }
        return this._StorageEnabled
    }
}

And one more thing:
It is probably better to implement caching with response headers instead of saving responses in localStorage. Since this is a get api, you can use headers to tell user's browsers to cache the responses for the appropriate amount of time and you get faster responses automatically, without introducing more JS. (Unless the response is out of your control of course - in which case this is probably a good idea.)


Finding common Integers between two lists Write a method numInCommon that takes two Lists of integers as
  parameters and returns the number of unique integers that occur in
  both lists. Use one or more Sets as storage to help you solve this
  problem.

  For example, if one list contains the values [3, 7, 3, -1, 2, 3, 7, 2,
  15, 15] and the other list contains the values [-5, 15, 2, -1, 7, 15,
  36], your method should return 4 (because the elements -1, 2, 7, and
  15 occur in both lists).

I'd like feedback on how to make this code better. Are there better ways to do it? If I wasn't following the prompt (e.g. no set required), how could I find the common elements in the laziest, most efficient, best optimized, etc. way? Last but not least, does my code have any major bugs?

public static int numInCommon(List<Integer> list1, List<Integer> list2) {
        if (list1.isEmpty() || list2.isEmpty()) {
            return 0;
        } else {
            Set<Integer> setCommon = new HashSet<Integer>();
            for (Integer val : list1) {
                // add the values of list1 to the set
                setCommon.add(val);
            }
            int common = 0;
            for (Integer val : list2) {
                if (setCommon.contains(val)) {
                    // if a value in list2 exists in the set, increase common
                    common++;
                    setCommon.remove(val);
                }
            }
            return common;
        }
    }

I personally would shorten this greatly:

public static int numInCommon(List<Integer> list1, List<Integer> list2){
    if(list1.isEmpty() || list2.isEmpty()){
        return 0;
    }

    Set<Integer> setCommon = new HashSet<>(list1);
    setCommon.retainAll(list2);
    return setCommon.size();
}

Returning 0 at the start is good, but no need for the else block on the If code.
Next task is to calculate the common elements - putting list1 into the set removes duplicates and then retainAll removes anything that isn't in list2. This leaves everythin in list1 and list2 without duplicates. Returning the size() counts the elements.

For performance - I'm taking the major assumption that HashSet is one of the quickest ways to check if an item exists and handle removal.


Sierpinski turtle triangle I am working through Programming Fundamentals with Python on Udacity. The assignment was to create a recursive triangle. I am happy with the output, but I am hoping for feedback on the actual construction of the program. Could I have done this in a more simple and concise way?

import turtle

def draw_polygon(a_turtle, length, sides):
    counter = 0
    while (counter < sides):
        a_turtle.forward(length)
        a_turtle.right(360 / sides)
        counter = counter + 1

def draw_triangle(a_turtle, length):
    draw_polygon(a_turtle, length, 3)

def draw_fractal_triangle(a_turtle, length, depth):
    if (depth == 1):
        draw_triangle(a_turtle, length)
    else:
        for i in range(1,4):
            draw_fractal_triangle(a_turtle, length/2, depth-1)
            a_turtle.forward(length)
            a_turtle.right(120)

def draw():
    window = turtle.Screen()
    window.bgcolor("black")

    brent = turtle.Turtle()
    brent.shape("turtle")
    brent.color("yellow")

    length = 200
    brent.backward(length/2)
    draw_fractal_triangle(brent, length, 5)
    window.exitonclick()

draw()

```

Nice.  I only have three comments.

In draw_polygon() use a for loop rather than an explicit counter:

def draw_polygon(a_turtle, length, sides):
    for counter in range(sides):
        a_turtle.forward(length)
        a_turtle.right(360 / sides)

Add comments and/or docstrings.  These will help you when you look at the code in the future.

For these kinds of tasks I usually add a top level docstring with a description of the task.  Include a url to the problem if applicable.  For example at the top of the file:

'''Recursive implementation of Sierpinski Triangle

Assignment from Programming Fundamentals with Python on Udacity.
'''

For any function/method etc. that has an algorithm that isn't immediately obvious from the code, add a comment or docstring explaining what/how it's doing it.  For example, I would add a docstring to draw_recursive_triangle() to explain what the function is doing, any assumptions (does it matter which way the turtle is pointing?, are there min or max limits on length? are the triangles always equilateral?, etc.).
The functions might be useful in another program/assignment.  Rather than rewriting them, you could import this file as a library if you use a if __name__ == "__main__": guard like so:

if __name__ == "__main__":
    draw()

That way it runs the program if you execute the file, but not if you import it as a library


100 gunmen in circle kill next person The question is here.

  100 people are standing in a circle with gun in their hands. 1 kills 2, 3 kills 4, 5 kills 6 and so on till we are left with only one person. Who will be the last person alive. Write code to implement this efficiently.

Here is my Java implementation:

public static void main(String[] args) throws Exception {
    int numberOfGuys = 100;
    MyObject[] objetList = new MyObject[numberOfGuys];
    for(int i=1;i<numberOfGuys+1;i++) {
        objetList[i-1] = new MyObject(i);
    }
    boolean oneElementLeft = false;
    while(!oneElementLeft) {

        for(int i=0;i<objetList.length;i++) {
            if(i != objetList.length-1 && (i+1)%2==1) {
                objetList[i+1]=null;
            }
            if(i == objetList.length-1 && objetList[i] != null) {
                objetList[0]=null;
            }
        }
        List<MyObject> newList = new ArrayList<MyObject>();
        for (MyObject myObject:objetList) {
            if(myObject != null) {
                newList.add(myObject);
            }
        }
        objetList = new MyObject[newList.size()];
        for(int i=0;i<newList.size();i++) {
            objetList[i] = newList.get(i);
        }
        if(objetList.length==1) {
            oneElementLeft = true;
        }
    }
    System.out.println(objetList[0].getIndex());
}

I am not a math guy, so I do not really understand the clever solutions with formulas, recursion etc...

Any review or better code with explanations are welcome.

The accepted answer in the linked question uses a cirucular linked list, which is the data structure that most closely represents this situation. That answer shows how to do that implementation, so I'll instead focus on the approach you look to be taking, which can be equally valid if it produces equivalent results.

public static void main(String[] args) throws Exception {

Why does your main method throw Exception? This is useless and potentially confusing. Your code does not encounter any expected exceptions, so why are you telling the reader to expect one? The exception you are telling them to expect is any exception, which is itself completely unhelpful. If your program encounters an uncaught exception, it will die just the same. Drop the throws Exception.

int numberOfGuys = 100;

Here, this is fine, but many people would probably just move it outside the method as static final int NUMBER_OF_GUYS = 100; since it is essentially a constant (unless you are planning to vary it with input in another iteration of the program).

MyObject[] objetList = new MyObject[numberOfGuys];

Two major issues here. First is naming. MyObject is a terrible name that tells the reader nothing of the nature of this class. A better name might be Gunman or Shooter, etc. For the variable name, objetList is also a terrible name. First, it looks very close to objectList, which increases the possibility of misspellings. It also says little to the nature of the variable, and what it does say is wrong. The suffix "List" might be interpreted to mean that this is a List object, but it is not. A better name might be gunmen or shooters (preferably matching off of the class name of the objects it holds).

The second major issue is the data structure chosen. We know that we will be removing elements from this structure, but we also know this is not efficient with a primitive array. Either we delete by using nulls, having to check that condition through the loop, or we delete by making a copy of the array, sans an element, each time we remove an element. A data structure built for this type of scenario is a List. There are several to choose from, each giving a potentially different performance profile, but we can just pick one to start and change that later if performance demands are not met.

for(int i=1;i<numberOfGuys+1;i++) {
    objetList[i-1] = new MyObject(i);
}

First, spacing is important. It is much harder to read code that does not have spacing around operators and such. Second, you perform excess operations that confuse what the loop is doing. Rather than start at one, go to numberOfGuys + 1, and insert at index objetList[i-1], start at 0. It would look more like this:

for(int i = 0; i < numberOfGuys; i++) {
    objetList[i] = new MyObject(i + 1);
}

boolean oneElementLeft = false;
while(!oneElementLeft) {
    ...
    if(objetList.length==1) {
        oneElementLeft = true;
    }
}

(SPOILER: Read all the way through this part before changing the code.)

This code tells a story, but it has a lot of noise in it. We test against a boolean, and exit out of the loop if it changes. We will only change that boolean based on a boolean test (objetList.length == 1) checked at the end of the loop. We already have a loop structure that does this more succinctly: the do-while loop! We could rewrite it so that we just have do { ... } while(objetList.length != 1); So much cleaner! And wrong. The story this code tells is misleading, and is in fact buggy. If objetList.length is already 1, we don't want to do anything! What we want is a simple while loop without the need for the flag:

while(objetList.length > 1) {
    ...
}

for(int i=0;i<objetList.length;i++) {
    if(i != objetList.length-1 && (i+1)%2==1) {
        objetList[i+1]=null;
    }
    if(i == objetList.length-1 && objetList[i] != null) {
        objetList[0]=null;
    }

}

Again, spacing.

These conditionals do not really tell a clear story. First of note, (i+1)%2 == 1 is asking if i plus one is odd. What it is really asking, though, is if i is even, or the same thing more succinctly, i % 2 == 0. (You will also see this written as i & 1 == 0 on occasion). Looking more generally, though, we are nulling the odd elements, and the first element if the list is an odd length. The conditionals don't come out and say this clearly, though. We check if we are at the end of the list every iteration, and do something when we reach the end only under certain special conditions. It is not totally clear that the condition is when the list is an odd length, either. More clearly, we can write:

for(int i = 0; i < objetList.length - 1; i += 2) {
    objetList[i + 1] = null;
}

if(objetList.length % 2 == 1) {
    objetList[0] = null;
}

Also note the vertical spacing used here. We often need space in both directions to make code the most readable.

List<MyObject> newList = new ArrayList<MyObject>();
for (MyObject myObject:objetList) {
    if(myObject != null) {
        newList.add(myObject);
    }
}
objetList = new MyObject[newList.size()];
for(int i=0;i<newList.size();i++) {
    objetList[i] = newList.get(i);
}

Here the code is basically just shuffling array data. This is the biggest indicator that a primitive array is the wrong data structure to be using.

I wrote the following version that accomplishes the same thing in a similar (non-circular) manner. It can probably be improved by using an iterator inside of it, but it suffices on its own.

Main class:

public class Main
{
    public static final int NUMBER_OF_GUNMEN = 100;

    public static void main(String[] args) {
        List<Gunman> gunmen = new ArrayList<>(NUMBER_OF_GUNMEN);
        for(int i = 1; i <= NUMBER_OF_GUNMEN; i++) {
            gunmen.add(new Gunman(i));
        }

        while(gunmen.size() > 1) {
            for(int i = 0; i < gunmen.size(); i++) {
                Gunman killer = gunmen.get(i);
                Gunman killed = gunmen.remove((i + 1) % gunmen.size());
                System.out.println(killer.getNumber() + " kills " + killed.getNumber());
            }
        }

        System.out.println("\n" + gunmen.get(0).getNumber() + " lives another day...");
    }
}

Gunman class:

public class Gunman
{
    private int number;

    public Gunman(int number) {
        this.number = number;
    }

    public int getNumber() {
        return number;
    }
}


Print out numbers of increasing distance from center value in Python I am trying to print out numbers by increasing positive and negative values around a center number, and I don't think I've found the best way. For example, say I want to find what number in a list my center value is closest to. I do that by adding one, see if it matches, then subtracting one from the original number and see if that matches, then add two from the original number and so on. I know there are other ways of finding the closest match but I'm not looking for that - I'm looking for the best way to print out numbers steadily getting farther from a center value. Here's my code:

def inc_val(center, i, neg_toggle):
    mult = 1
    if neg_toggle:
        neg_toggle = False
        mult = -1
    else:
        neg_toggle = True
        mult = 1
        i += 1
    val = center + (i * mult)
    return val, i, neg_toggle

i = 0
center = 24
val = center
neg_toggle = False
my_set = {30, 50, 90}
while val not in my_set:
    print(val)
    val, i, neg_toggle = inc_val(center, i, neg_toggle)

This prints out the following list, as desired:

24
25
23
26
22
27
21
28
20
29
19

To be clear, I'm interested in the incrementing numbers. The while not in my_set part is just to illustrate. I am not intentionally trying to re-invent anything, so if there's a built-in or simpler way to do this, please let me know.

Rather than maintaining the state of the iteration using three variables val, i, and neg_toggle, it would be more elegant to write a generator.  Then, the state of the iteration would be maintained by the flow of the execution of the generator itself.

def zoom_out(center):
    decr = center
    incr = center + 1
    while True:
        yield decr
        decr -= 1
        yield incr
        incr += 1

for n in zoom_out(24):
    if n in (30, 50, 90):
        break
    print(n)

Furthermore, fancy iteration can often be expressed more elegantly using itertools.  Here, I'd take advantage of itertools.count() to implement the generator, and itertools.takewhile() to detect when to stop executing the infinite generator.

from itertools import count, takewhile

def zoom_out(center):
    decr = count(center, -1)
    incr = count(center + 1)
    while True:
        yield next(decr)
        yield next(incr)

for n in takewhile(lambda n: n not in (30, 50, 90), zoom_out(24)):
    print(n)


Bit Array in Ruby using integer as a storage Ruby's Fixnum and Bignum can hold very large integers and automatically handle overflow. I decided to implement BitArray using an integer as storage. Please let me know what you think about code and functionality of a BitArray.

class BitArray
  include Enumerable

  def initialize size
    @size = size
    @field = 2**size
  end

  def set positions
    bits = positions.kind_of?(Integer) ? [positions] : positions
    bits.each {  |position| @field |= 1 << (@size - position) }
    self
  end

  def clear positions
    bits = positions.kind_of?(Integer) ? [positions] : positions
    bits.each {  |position| @field ^= 1 << (@size - position) }
    self
  end

  def get position
    (@field >> (@size - position) ).to_s(2)[-1].to_i
  end

  def each(&block)
    @field.to_s(2)[1..-1].split("").each { |bit_string| yield(bit_string.to_i) }
  end

  def to_s
    @field.to_s(2)[1..-1]
  end

  def count
    @field.to_s(2)[1..-1].split("").inject(0) {|sum,bit| sum + bit.to_i}
  end

end

And the Test

require 'minitest/autorun'
require_relative 'bit_array'

class BitArrayTest < MiniTest::Unit::TestCase

  def test_equal
    assert_equal "00000", BitArray.new(5).to_s
  end

  def test_set
    assert_equal "00100", BitArray.new(5).set(3).to_s
    assert_equal "00010", BitArray.new(5).set(4).to_s
    assert_equal "11100", BitArray.new(5).set([1,2,3]).to_s
    assert_equal "100000000101", BitArray.new(12).set([1,10,12]).to_s
  end

  def test_clear
    assert_equal "01000", BitArray.new(5).set([1,2]).clear(1).to_s
  end

  def test_get
    assert_equal 0, BitArray.new(5).set([1,2]).get(3)
    assert_equal 0, BitArray.new(12).set([12]).get(11)
    assert_equal 0, BitArray.new(12).set([12]).get(1)
  end

  def test_count
    assert_equal 2, BitArray.new(5).set([1,2]).count
  end

  def test_iterate
    assert_equal ["0", "0", "0", "0", "0"],  BitArray.new(5).each {|n| puts n }
  end

end

My 2nd question on this site concerned bitmasks, actually. As @tokland correctly pointed out back then, bitmasks are really a pretty low-level technique that doesn't quite belong in a high-level language. Yes, it has its uses, but a hash or an array of symbols would solve the same kinds of problems in a more high-level, more expressive, and more readable manner.

In fact, trying to do this in a high-level language like Ruby presents some oddities, since you're using strings and integers to work with bits. And strings and integers are objects in Ruby, so you've got all these really high-level concepts and constructs involved in trying to do something with the lowest-level aspect of computing. It works, but it's like packing something tiny in a giant padded box.

Still, code's code, so:

Your #test_iterate doesn't quite test what you think. You're just printing to stdout. What the assertion is actually testing is the value of @field.to_s(2)[1..-1].split("") - it doesn't really test that anything is being iterated. This implementation would also pass your test, even though it never iterates anything:

def each(&block)
  # block argument ignored, no iteration; passes tests anyway
  @field.to_s(2)[1..-1].split("")
end

With your current code, I'd write the test like:

expected = [1, 1, 0]
BitArray.new(3).set([1,2]).each do |bit|
  assert_equal expected.shift, bit
end
assert expected.empty? # check that we looped the expected number of times

You test for #get is also kinda strange. In all cases you check for 0 - how about a test where you expect to get 1 back? There really are only two possible return values, so you should probably check both.
Why on Earth is your class using a 1-based indexing scheme? It's an array of a sort, so why not use a zero-based index like, well, like an array would do? I know this confused me greatly.
Your #get method could perhaps just return a boolean. That's the closest you'll get to returning a raw bit.

Update: I wasn't aware of this, but Fixnum actually has subscripting access to bits already. So #get can be written as simply:

def get position
  @field[position]
end

Your #set and #clear methods should probably just use splats - it'd let you skip the array-boxing if just a single integer's passed in:

def set *positions # use a splat
  positions.each { |position| @field |= 1 << (@size - position) }
  self
end

unset might be a better name than clear - I'd expect clear to reset the entire array.
You're going out of your way to always calculating @size - (some position) to make sure that you fill your array "from the left". I.e. position 1 is the left-most bit, rather than the (more natural) right-most bit. However, there's really no need. Inside your class, you can do whatever you want. Your current tests mostly check the string representation, so you can just flip that, rather than flip everything else.
Filling from the right would also let you skip the size argument entirely; as you say, Ruby will catch overflows anyway, but you never actually check (or test) trying to get or set a bit outside the size.
It's also just simpler to find and flip bits if you go from the right, and use a zero-based index, since any bit is given as simply 2**position. For instance:

def set *positions
  positions.each { |position| @field |= 2**position }
  self
end

You're including Enumerable, so use it. Your #count method could be written as just

def count
  inject(0, :+)
end

since it'll use each, and each will yield either 1 or 0.

Again, this is all academic, as you're no doubt better off just using regular arrays or hashes. Still, here's a refactored version, because why not? Slightly different output for #to_s since I'm not using a size argument. And I'm using 0-based indices. But otherwise it's the same.

class BitArray
  include Enumerable

  def initialize
    @bits = 0
  end

  def set *positions
    positions.each { |position| @bits |= 2**position }
    self
  end

  def unset *positions
    positions.each { |position| @bits ^= 2**position }
    self
  end

  def get position
    @bits[position]
  end

  def each(&block)
    bits = @bits
    until bits == 0
      yield bits & 1
      bits = bits >> 1
    end
  end

  def to_s
    @bits.to_s(2).reverse
  end

  def count
    inject(0, :+)
  end
end

require 'minitest/autorun'

class BitArrayTest < MiniTest::Test
  def test_equal
    assert_equal "0", BitArray.new.to_s
  end

  def test_set
    assert_equal "0001", BitArray.new.set(3).to_s
    assert_equal "1011", BitArray.new.set(0, 2, 3).to_s
    assert_equal "0100000000101", BitArray.new.set(1, 10, 12).to_s
  end

  def test_unset
    assert_equal "101", BitArray.new.set(0, 1, 2).unset(1).to_s
  end

  def test_get
    assert_equal 1, BitArray.new.set(1, 2).get(2)
    assert_equal 0, BitArray.new.set(12).get(11)
    assert_equal 1, BitArray.new.set(12).get(12)
  end

  def test_count
    assert_equal 3, BitArray.new.set(1, 2, 5).count
  end

  def test_iterate
    expected = [1, 1, 0, 1]
    BitArray.new.set(0, 1, 3).each do |bit|
      assert_equal expected.shift, bit
    end
    assert expected.empty?
  end
end

Note that this version and its tests still don't deal with the issue of passing, say, negative indices or non-numeric indices.


Representing and Parsing an Open or Closed Range I would like to represent a numeric range in C#. Either open-ended, such as "up to 35" or "100 on up" or closed-ended, such as "34 to 65". I'd like to represent the open end with NULL. Further, I'd like to parse strings into the range. Strings will look like "-35", "100+", "34-65" or even "-10.5--0.5". I hate that the dash means negative and the range separator, but it is what I'm given. That all being said, I've tested my cases against this code and they work. My questions are: is this the best way to accomplish this? Is it okay to let certain exceptions be thrown for invalid data or should I do more checking on it beforehand? Should this even be called Range? Is Interval better?

public struct Range<T> where T : struct, IComparable<T>
{
    private static readonly Regex _RemoveSpaces = new Regex(@"\s+", RegexOptions.Compiled);

    private static readonly char[] _SplitOnDash = { '-' };

    private static readonly TypeConverter _Converter = TypeDescriptor.GetConverter(typeof(T));

    private readonly T? _Minimum;

    private readonly T? _Maximum;

    public Range(T? minimum = null, T? maximum = null)
    {
        if ((minimum != null) && (maximum != null) && Comparer<T?>.Default.Compare(minimum, maximum) > 0)
        {
            throw new ArgumentException("minimum is greater than maximum.");
        }

        this._Minimum = minimum;
        this._Maximum = maximum;
    }

    public T? Minimum
    {
        get
        {
            return this._Minimum;
        }
    }

    public T? Maximum
    {
        get
        {
            return this._Maximum;
        }
    }

    public static Range<T> Parse(string range)
    {
        range = _RemoveSpaces.Replace(range, string.Empty);

        // No maximum.
        if (range.EndsWith("+"))
        {
            return new Range<T>(_Converter.ConvertFromString(range.Substring(0, range.Length - 1)) as T?);
        }

        // No minimum.
        if (range.StartsWith("-") && !range.Substring(2).Contains("-"))
        {
            return new Range<T>(null, _Converter.ConvertFromString(range.Substring(1)) as T?);
        }

        var rangeParts = range.Split(_SplitOnDash);

        // Two positive numbers.
        if (rangeParts.Length == 2)
        {
            return new Range<T>(
                _Converter.ConvertFromString(rangeParts[0]) as T?,
                _Converter.ConvertFromString(rangeParts[1]) as T?);
        }

        // One negative, one positive number.
        if (rangeParts.Length == 3)
        {
            return new Range<T>(
                _Converter.ConvertFromString("-" + rangeParts[1]) as T?,
                _Converter.ConvertFromString(rangeParts[2]) as T?);
        }

        // Two negative numbers.
        if (rangeParts.Length == 4)
        {
            return new Range<T>(
                _Converter.ConvertFromString("-" + rangeParts[1]) as T?,
                _Converter.ConvertFromString("-" + rangeParts[3]) as T?);
        }

        // No idea what we were given, give a completely open range.
        return new Range<T>(null, null);
    }

    public override string ToString()
    {
        return (this._Minimum == null) && (this._Maximum == null)
            ? string.Empty
            : (this._Minimum == null
                ? string.Format("-{0}", this._Maximum)
                : (this._Maximum == null
                    ? string.Format("{0}+", this._Minimum)
                    : string.Format("{0} - {1}", this._Minimum, this._Maximum)));
    }
}

I would check the result of range

range = _RemoveSpaces.Replace(range, string.Empty);

against string.Empty because that is one of the cases where the code reaches this.

// No idea what we were given, give a completely open range.
return new Range<T>(null, null);

Returning early will get you some performance here. Doing a null check on range before that call isn't necessary because Regex.Replace() throws a ArgumentNullException for the case that range == null.

Speaking about Regex.Replace I would prefer string.Replace() over Regex.Replace because it seems faster. See: comparing regex replace string replace and stringbuilder replace which has better performance

One should not always do what can be done.

public override string ToString()
{
    return (this._Minimum == null) && (this._Maximum == null)
        ? string.Empty
        : (this._Minimum == null
            ? string.Format("-{0}", this._Maximum)
            : (this._Maximum == null
                ? string.Format("{0}+", this._Minimum)
                : string.Format("{0} - {1}", this._Minimum, this._Maximum)));
}

IMO this isn't readable at first glance so maybe some good old if..else would be better. Having underscore prefixed membervariables and using this is too much.

public override string ToString()
{
    if ((_Minimum == null) && (_Maximum == null)) { return string.Empty; }

    if (_Minimum == null) { return string.Format("-{0}", _Maximum); }

    if (_Maximum == null) { return string.Format("{0}+", _Minimum); }

    return string.Format("{0} - {1}", _Minimum, _Maximum)));
}

If you are using C# 6 you could use the string-interpolation operator $ instead of string.Format().

About Interval vs Range I would prefer Range because Interval IMO suits only with dates and times but e.g don't suits with int.

__

Inside the Parse() method I would check the found minimum and maximum before calling the constructor. IMO throwing an exception in a constructor should be avoided if possible.

In general you code looks tidy and clean.

You are using good variables- and methodnames.
You are using braces although they are optional.
Your code is easy to read.


Parsing hex and decimal numbers in C++11 The function arg_to_uint64 takes a 0-terminated string and returns an unsigned int. The unsigned int is the integer presentation of arg in decimal or in hex (if prefixed with 0x) as defined in the C language standard.

constexpr char hexprefix[]="0x";

inline std::uint64_t
arg_to_uint64(const char* arg)
{
   constexpr std::size_t hexprefix_len=sizeof(hexprefix)-1;
   bool is_hex=std::strncmp(arg,hexprefix,hexprefix_len)==0;
   int base;

   if(is_hex)
   {
      arg+=hexprefix_len;
      base=16;
   }
   else
      base=10;

   std::size_t idx;
   std::uint64_t r=std::stoull(arg,&idx,base);

   if(idx!=std::strlen(arg))
      throw std::runtime_error("garbage at the end of input");
   return r;
}

Is there a better/shorter way to do this? My platform is Linux.

This is my improved code as described in the answer from William Morris:

inline std::uint64_t
arg_to_uint64(const char* arg)
{
   std::size_t idx;
   std::uint64_t r=std::stoull(arg,&idx,0);

   if(arg[idx]!='\x0')
      throw std::runtime_error("garbage at the end of input");
   return r;
}


Identifying first negative number in array of doubles I was asked to create a function that checks if an array of doubles has all negative numbers or none. If these 2 (all negative, all positive) are false, check the first negative number,  using recursion and only using built-in C++ features.

int first_negative(const double val [] , unsigned array, unsigned short instance_ = 0) //Dont change instance!
{
    //None negative?
    bool none_negative;
    for(int i = 0; i < array; i++)
    {
        if(val[i] > 0) none_negative = true;
        else
        {
            none_negative = false;
            break;
        }
    }
    if(none_negative) return 0;

    //All negative?
    bool negative_instance;
    for(int i = 0; i < array; i++)
    {
        if(val[i] < 0) negative_instance = true;
        else
        {
            negative_instance = false;
            break;
        }
    }

    //Never change instance!
    static short instance = instance_;
    if(array < 1) return 0;
    if(val[instance] < 0) return instance;
    instance++;
    return first_negative(val, array, instance);
}

Can I make it better? Can I remove the instance parameter?

I believe the parameter names val and array are switched around.  An array shouldn't be a single variable, and a value shouldn't be an array.  Otherwise, the names themselves are okay.
It's preferred to index through a C-style array with an std::size_t, especially if the array size is larger than an int.  This could be helpful if you'll be working with very large numbers, although the recursion aspect here may render that unlikely.  Even if you're not, it's best to develop that habit.
This looks a bit misleading:

if(val[instance] < 0) return instance;
instance++;

At first, I thought the instance++ was missing indentation and belonged to the if statement.  To make this clearer, you could separate the two lines or, even better, have curly braces for the if statement.  The latter also helps with better maintainability.

if (val[instance] < 0)
{
    return instance;
}

instance++;

Again, some of the naming is misleading:

if(array < 1) return 0;

From a glance, that just looks incorrect as you cannot check an array like that.  Proper naming is very important, even for a small program like this.


Implementing Gaussian integers in Haskell Currently my code (at GitHub) is this:

module Gaussian where

import qualified Data.Complex as Complex
  -- Enables toComplex.
  -- Qualified to avoid clashing.

data Gaussian = (:+)
  {
    real :: Integer,
    imaginary :: Integer
  } deriving
    (Show, Read, Eq)
  -- The gaussian integer type.
  -- A gaussian integer is a complex number of the form a + bi where a and b are integers.

instance Num Gaussian
  where
    (a1 :+ b1) + (a2 :+ b2) = (a1 + a2) :+ (b1 + b2)
    (a1 :+ b1) - (a2 :+ b2) = (a1 - a2) :+ (b1 - b2)
    (a1 :+ b1) * (a2 :+ b2) = (a1 * a2 - b1 * b2) :+ (a1 * b2 + a2 * b1)
    abs (a :+ b) = ((a ^ two) + (b ^ two)) :+ 0
      where
        two = 2 :: Integer
          -- This prevents compiler warnings about defaulting types.
    signum = id
    negate (a :+ b) = negate a :+ negate b
    fromInteger x = x :+ 0
  -- The Num instance for Gaussian.
  -- We use the euclidean norm as abs. norm(a + bi) = a^2 + b^2

i :: Gaussian
i = 0 :+ 1
  -- The imaginary unit, equal to sqrt(-1).

magnitude :: Floating c => Gaussian -> c
magnitude (a :+ b) = sqrt $ (fromInteger a ^ two) + (fromInteger b ^ two)
  where
    two = 2 :: Integer
      -- This prevents compiler warnings about defaulting types.

norm :: Gaussian -> Integer
norm (a :+ b) = (a ^ two) + (b ^ two)
  where
    two = 2 :: Integer
      -- This prevents compiler warnings about defaulting types.

conjugate :: Gaussian -> Gaussian
conjugate (a :+ b) = (a :+ negate b)
  -- The complex conjugate.
  -- Effectively flips about the real axis.

rotate_cw :: Gaussian -> Gaussian
rotate_cw (a :+ b) = (b :+ negate a)
  -- Rotate a gaussian integer clockwise.
  -- Equivalent to multiplying by i.

rotate_ccw :: Gaussian -> Gaussian
rotate_ccw (a :+ b) = (negate b :+ a)
  -- Rotate a gaussian integer counterclockwise.
  -- Equivalent to multiplying by -i.

flip_x :: Gaussian -> Gaussian
flip_x (a :+ b) = (negate a :+ b)
  -- Flips on imaginary axis.
  -- Analogous to conjugate.

flip_y :: Gaussian -> Gaussian
flip_y = conjugate
  -- Alias for conjugate.
  -- See conjugate.

swap_x_y :: Gaussian -> Gaussian
swap_x_y (a :+ b) = (b :+ a)
  -- Utility function, swaps real and imaginary axes.

toComplex :: Num p => Gaussian -> Complex.Complex p
toComplex (a :+ b) = (fromInteger a Complex.:+ fromInteger b)
  -- Converts a Gaussian to any complex number (Num p => Complex p)
  -- Fully qualified operators to avoid clashing.

As far as I know, my brace/indentation style isn't used anywhere else, so I'm a bit worried about that.

This looks good. All necessary type signatures are there, no type is too strict nor too generic. The indentation style is familiar, and the braces on data Gaussian are easy to read, so no worries about that.

However, there are a few oddities. Let's face them.

Num's signum

There aren't any laws for Num in the Haskell report, however there are some expectations. The operations on (+) and (*) should implement a ring and that's certainly true here. However, Num's documentation indicates that the following should hold:

abs x * signum x = x -- (1)

Unfortunately, we cannot take the easy way and just use

signum x = x / abs x

since the result is unlikely to be in Gaussian's domain. As we cannot hold (1), we're free to do whatever we want, but it should be reasonable. How does it become reasonable? By documenting your decision:

signum = id -- < your documentation here >

Prefix vs. postfix documentation

That took me by surprise. Most of Haskell's documentation is placed before the documented item, not after. The same holds for most other documentation in other languages, where the documentation is placed before or in the function itself:

/** @brief Calculates the absolute value of a Gaussian integer.
 *  @param x is a Gaussian integer
 *  @returns x's absolute value
*/
int g_abs(gint x) {
    return x.r * x.r + x.i * x.i;
}

def g_abs(x):
    """Returns the absolute value of x"""
    return x.r * x.r + x.i * x.i

The usual Haddock documentation also placed the documentation before the item, although it's possible to use postfix.

You're welcome to stay in the postfix style, but you should indicate that your documentation refers to the preceding item, for example with Haddock's ^:

i :: Gaussian
i = 0 :+ 1
--^ The imaginary unit, equal to sqrt(-1).

That removes possible ambiguity.

two = 2 :: Integer and x ^ two

The line two = 2 :: Integer violates the DRY principle, thus any optimization or bugfix on x ^ two needs to get repeated throughout the program, which is error prone.

However, there is a greater issue. GHC rewrites x ^ 2 to x * x (see Note [Inlining (^) in base's documention). An explicit variable might hinder that process.

Instead, you should provide a square function or just immediately multiply a value with itself. Both variants will get rid of the warnings and additional bindings, for example:

--| The Num instance for Gaussian.
--  We use the euclidean norm as abs. norm(a + bi) = a^2 + b^2
instance Num Gaussian
  where
    ...
    abs (a :+ b) = (a * a + b * b) :+ 0
    signum = id -- chosen at random
    ...

By the way: if you chose square x = x ^ (2 :: Int) you won't need to repeat your documentation.

Precision

You always want to stay as precise as possible, unless you are aiming for speed. Therefore, you should try to stay in exact types till the very last moment in magnitude.

Instead of

magnitude :: Floating c => Gaussian -> c
magnitude (a :+ b) = sqrt $ (square $ fromInteger a) + (square $ fromInteger b)

use

magnitude :: Floating c => Gaussian -> c
magnitude (a :+ b) = sqrt $ fromInteger (square a + square b)

You could also reuse abs if you split it into two functions:

instance Num Gaussian where
    ...
    abs x = (absIntegral x :+ 0)
    ...

absIntegral :: Gausian -> Integer
absIntegral (a :+ b) = square a + square b

magnitude :: Floating c => Gaussian -> c
magnitude = sqrt . fromInteger . absIntegral


Mergesort linked list in C++ My teacher gave us an exercise. We have to sort as quickly as possible. The fastest one gets a reward. On my own system, I am sorting 125000 words within 1.2 seconds. On my teacher's system that is 0.6s.

In my main.cpp I wrote the following code:

#include "FileStructure.h"
#include "Value.h"

template<typename T>
T* Merge(T* firstNode, T* secondNode)
{
  if (!firstNode) return secondNode;
  else if (!secondNode) return firstNode;

  else if (firstNode->getText() >= secondNode->getText())
  {
    firstNode->setPrev(Merge(firstNode->getPrev(), secondNode));
    return firstNode;
  }
  else
  {
    secondNode->setPrev(Merge(firstNode, secondNode->getPrev()));
    return secondNode;
  }
}

template<typename T>
T* Split(T* my_node)
{
  if (!my_node || !my_node->getPrev()) return NULL;
  T* secondNode = my_node->getPrev();
  my_node->setPrev(secondNode->getPrev());
  secondNode->setPrev(Split(secondNode->getPrev()));
  return secondNode;
}

template<typename T>
T* MergeSort(T* my_node)
{
  if (!my_node) return NULL;
  else if (!my_node->getPrev()) return my_node;
  return Merge(MergeSort(my_node), MergeSort(Split(my_node)));
}

int main(void)
{
  FileStructure f;
  Key* head = new Key();
  f.loadFile("data/gibberish.bin", *head);

  head = MergeSort(head);
  Key* tempHead = head; //values

  while (tempHead)
  {
    tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
    tempHead = tempHead->getPrev();
  }
  // save sorted data into a new file called sorted.bin
  f.saveFile(*head, "sorted.bin");

  delete head;
  //newHead = NULL;

  return 0;
}

The key.h and value.h only have getters and setters. Key also has another method called AddValue().

This one is:

void Key::addValue(std::string word)
{
    if (key == word.substr(0, 2))
    {
        Value *temp = valueTail;
        valueTail = new Value(word);
        valueTail->setPrev(temp);
        return;
    }
    else if (prevKey)
    {
        prevKey->addValue(word);
        return;
    }
    prevKey = new Key();
    prevKey->setText(word.substr(0, 2));
    prevKey->valueTail = new Value(word);
}

All the other functions are inline functions.
As you can see it's dirty code. I removed as much as possible variables. I think it can be faster, but I don't know how.

I ran Gprof on my code:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 72.73      0.24     0.24                             Key::addValue(std::string)
 12.12      0.28     0.04   151883     0.26     0.26  Value* Split<Value>(Value*)
  9.09      0.31     0.03   151883     0.20     0.20  Value* Merge<Value>(Value*, Value*)
  6.06      0.33     0.02      522    38.31    38.31  Value::~Value()
  0.00      0.33     0.00      522     0.00     0.00  Key* Merge<Key>(Key*, Key*)
  0.00      0.33     0.00      522     0.00     0.00  Key* Split<Key>(Key*)

Help me out please!
Btw: I have no memory leaks, thanks to valgrind.

I had a similar contest in high school.  I decided to win in every category :)

In modern architectures, linked lists are slow.  See https://www.youtube.com/watch?v=YQs6IC-vgmo for example.  Does it need to be a linked list?  Does it need to be a merge sort in particular?  I can advice more specifically if you update your post to add that info.

Even though it would not be a legal entry, you might try using a std::vector<std::string> and just calling std::sort and using that speed as a baseline!

  Btw: I have no memory leaks, thanks to valgrind.

That is a heroic effort to achieve something that should normally be the case in C++.  Use unique_ptr and general RAII techniques, and memory leaking in a single-threaded program is simply not an issue to worry about!  That is, you are making it too hard.

Read through and bookmark the C++ Standard Guidelines.  Numbers I note later are citations from this.

Use the proper #include files.  You have a couple project-specific includes, but no standard library stuff; maybe you are not using anything from the library, not even language-support features?  But that will change if you improve the code.

template<typename T>
T* Merge(T* firstNode, T* secondNode)
{
  if (!firstNode) return secondNode;
  else if (!secondNode) return firstNode;

  else if (firstNode->getText() >= secondNode->getText())
  {
    firstNode->setPrev(Merge(firstNode->getPrev(), secondNode));
    return firstNode;
  }
  else
  {
    secondNode->setPrev(Merge(firstNode, secondNode->getPrev()));
    return secondNode;
  }
}

So let’s see… you are taking a couple node pointers, not any kind of abstraction as the linked list as a collection?  I understand if this is the kind of stuff you are learning, but it is hard to follow as it is not “normal” programming.

So far, I see some good habits.  C++ (not C) style placement of the *, use of contextual conversion to bool as a truth test of the pointer, putting quick-return tests at the very top, in a compact manner … all very mature style!

The logic looks like straight functional programming style.  Good for Haskell, not good for C++.  I don’t think the compiler can do tail recursion elimination here.  You will run out of stack space if your list is long!

Writing this as a loop rather than recursively will make it faster and avoid the size limit.

template<typename T>
T* Split(T* my_node)
{
  if (!my_node || !my_node->getPrev()) return NULL;
  T* secondNode = my_node->getPrev();
  my_node->setPrev(secondNode->getPrev());
  secondNode->setPrev(Split(secondNode->getPrev()));
  return secondNode;
}

Forget that the NULL macro ever existed!  Banish it from your memory.  C++ has the special nullptr value.

Again, I see a good habit:  declared secondNode when you were ready to initialize it.

template<typename T>
T* MergeSort(T* my_node)
{
  if (!my_node) return NULL;
  else if (!my_node->getPrev()) return my_node;
  return Merge(MergeSort(my_node), MergeSort(Split(my_node)));
}

As before, nullptr, not NULL.

It looks like you are peeling off one node at a time, not cutting the list in half.  If I follow this right, you have implemented an insertion sort where you need a linear search over the list to find the insertion position, not a proper merge sort.  Each item will have to compare (on average) with half of the items processed already.  This is O(n²).  A proper merge will compare once for each item in the shorter list, recursively sorting the half-lists first.  That is O(n log n).

Now I’m sure you know that the “big O” will trump the linear speedup of any of the steps!

int main(void)
{
  FileStructure f;
  Key* head = new Key();
  f.loadFile("data/gibberish.bin", *head);

  head = MergeSort(head);
  Key* tempHead = head; //values

  while (tempHead)
  {
    tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
    tempHead = tempHead->getPrev();
  }
  // save sorted data into a new file called sorted.bin
  f.saveFile(*head, "sorted.bin");

  delete head;
  //newHead = NULL;

  return 0;
}

Don’t write (void) for an empty parameter list!  Stroustrup calls that “an abomination”.  It is supported so that it can read C header files; but you should not write that in C++, ever.

  Key* head = new Key();

⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.

  while (tempHead)
  {
    tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
    tempHead = tempHead->getPrev();
  }

I don’t understand that part.  You sorted with the call to MergeSort, right?  Why do you have to back up a node and sort it again?  This might be a work-around for a problem with the sorting or the data structure.

Then you treat the original node,  head, as the sorted list’s head?  So what was the deal with tempHead?

void Key::addValue(std::string word)
{
    if (key == word.substr(0, 2))
    {
        Value *temp = valueTail;
        valueTail = new Value(word);
        valueTail->setPrev(temp);
        return;
    }
    else if (prevKey)
    {
        prevKey->addValue(word);
        return;
    }
    prevKey = new Key();
    prevKey->setText(word.substr(0, 2));
    prevKey->valueTail = new Value(word);
}

You are taking the string word by value, copying it into the function.  You don’t modify word, right?

I don’t know what Value is, or why you don’t just store the std::string in your nodes.

substr is not a normal or good way to manipulate strings in the standard library.  If I knew what you were trying to do, I could advise how it should naturally be done.

Good luck to you!  Keep at it.


Merging two sorted linked lists C++ Routine to merge two linked lists together and return a new merged list. One optimization I can think of is passing by reference instead of value. Any other suggestions ? Is there a shorthand to make lines 4 and 5 single/shorter?

template<class t>
Linkedlist<t> merge(Linkedlist<t> firstList, Linkedlist<t> secondList) {

/*4*/   Node<int> * current = ( firstList.head->data < secondList.head->data ) ? firstList.head : secondList.head;
/*5*/   Node<int> * other = ( firstList.head->data > secondList.head->data ) ? firstList.head : secondList.head;

    Node<int> * oldOther = nullptr;
    Node<int> * oldNext = nullptr;

    while ( current && other ) {
        if ( current->next == nullptr || current->next->data > other->data ) {
            oldOther = other;
            oldNext = current->next;
            current->next = other;
            other = oldNext;
            current = oldOther;
        } else {
            current = current->next;
        }
    }

    return ( firstList.head->data < secondList.head->data ) ? firstList : secondList;
}

Your code has three issues I can see.....

the stated goal is to return a new list, but your code returns one of the input lists that have been modified to have the merged results. This is buggy.
If the first two elements in each list are equals, your initialization process will fail, one of the comparisons, either the first, or the second has to have an = component, either <= or >=. As it stands, both the current and the other will point to the secondList if the first values are equals.
What's Node<int>? Why is it not Node<t>? Why use templates at all if you have only one template type that works?


Greatest common divisor I wrote a program to find the greatest common divisor between two numbers. How do I improve this program?

#include<iostream>
using namespace std;

int main() {

int first_number;
cout<<"Enter First Number : ";
cin>>first_number;

if(first_number < 0)
cout << "Please enter a positive number" << endl;
cin >> first_number;

int  second_number;
cout<<"Enter Second Number: ";
cin>>second_number;

if(second_number < 0)
cout << "Please enter a positive number" << endl;
cin >> second_number;

int  gcd;
for(int i=1;i<=first_number&&i<=second_number;i++){

if(first_number%i==0 && second_number%i == 0 ){

gcd=i;

   }

}

cout<<"Greatest Common Divison (GCD):"<<gcd<<endl;
return 0;
}

A more elegant implementation of the gcd function:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

To ensure that the arguments are positive, it's easiest to use the abs(...) function.

Please also indent your code nicely to make it more readable.

And put spaces around operators. For example, instead of this:

for(int i=1;i<=first_number&&i<=second_number;i++){

Write like this:

for (int i = 1; i <= first_number &&i <= second_number; i++) {

Putting it together, the implementation of the entire program can become short and sweet:

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int num1, num2;

    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;

    cout << "Greatest Common Divisor: " << gcd(abs(num1), abs(num2)) << endl;
}

You can play with this on ideone.


Find Shortest Word Edit Path in python I was given this problem in an interview.

  Given two words source and target, and a list of words words, find the
  length of the shortest series of edits that transforms source to
  target. Each edit must change exactly one letter at a time, and each
  intermediate word (and the final target word) must exist in words.

  If the task is impossible, return -1.

  Examples:

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

  Output: 5

  Explanation: bit -> but -> put -> pot -> pog -> dog has 5
  transitions.

source = "no"
target = "go"
words = ["to"]

  Output: -1

def one_letter_difference(current_word, next_word):
      count = 0
      for i in range(len(current_word) -1):

        if current_word[i] != next_word[i]:
          count += 1;
      if count == 1:
        return True
      else:
        return False

    def shortestWordEditPath(source, target, words):
      """
        @param source: str
        @param target: str
        @param words: str[]
        @return: int

      Input: source = "bit", target = "dog"
      words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

      Output: 5
      explanation:
                 1  ->  1   ->   1  ->    1  ->     1
      (source) bit -> but -> put -> pot -> pog -> dog (target)
      has minimum of 5 transitions
        """
      graph = {}

      for i in range(-1, len(words)):
        if i == -1:
          current_word = source
        else:
          current_word = words[i]
        graph[current_word] = []
        for word in range(len(words)):
          next_word = words[word]
          if one_letter_difference(current_word, next_word):
            graph[current_word].append(next_word)

      #perform BFS
      queue = collections.deque()
      seen = set() # visited words
      queue.append([source, 1])
      seen.add(source)

      while len(queue) > 0:
        current, distance = queue.popleft()
        if current == target: return distance
        for neighbor in graph[current]:
          if neighbor not in seen:
            queue.append([neighbor, distance +1])
            seen.add(neighbor)
      return -1

    source = "bit"
    target = "dog"
    words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
    test = shortestWordEditPath(source, target,words)
    print(test)

Let's start with the good:

You documented your public API!
You used decently descriptive variable names
You somewhat have a test case
Your use of a dictionary is resourceful here. No need for some fancy Node class.
You separated out some of the functionality to make the algorithm easier to reason about (checking if words are 1 edit distance apart)

Here are some things I noticed that perhaps the interviewer did as well:

Your formatting is inconsistent. PEP8 your code (4 space indents, space around operators).
You mix snake_case and camelCase. Python typically prefers snake_case.
You didn't document your internal function (not the end of the world, but it is a nice touch)
You didn't indicate that your internal function was private by prefixing it with a _ (my policy is always if it doesn't have a leading _ it must be documented)
if count == 1: return True else: return False would concern me as an interviewer as it demonstrates that you may not understand boolean expressions. return count == 1 would work. But this additionally would pose another concern for me. Namely, one_letter_difference could be a short circuited function, but you did not implement it this way. I also would name it differently, one_letter_difference doesn't say what it does. Also, this function does not care about current or next words, so don't call them that. We also typically try to avoid indexing in Python. You should use zip here. And not to pile on, but this function is also probably not correct. You should have test cases for it. I believe that dog to doge should be an edit distance of 1 as well. With that in mind:

def _is_one_edit_apart(word_a, word_b):
    if abs(len(word_a) - len(word_b)) > 1:
        # It is impossible for words differing by 2 or more letters in length to
        # be just one edit apart
        return False

    if len(word_a) != len(word_b):
        shorter_word, longer_word = \
            (word_a, word_b) if len(word_a) < len(word_b) else (word_b, word_a)

        if longer_word.startswith(shorter_word) or longer_word.endswith(shorter_word):
            # The shorter word is a prefix or a suffix of the longer and
            # they differ by 1 character in length, so they are 1 edit apart
            return True

    num_edits = 0

    # We know that word_a and word_b are the same length, so zip won't truncate
    for a, b in zip(word_a, word_b):
        if a != b:
            num_edits += 1
            if num_edits > 1:
                return False

    return num_edits == 1

Note that you could also get clever here and make the edits a bit more succinct: num_edits = sum(1 for a, b in zip(word_a, word_b) if a != b). This is up to you. This certainly reads better. The approach above likely performs better because it short circuits (stops when it finds more than 1 edit).

Your graph construction is weird. range(-1, len(words)) seems like it could lead to trouble if you aren't careful. Generally, prefer for word in words. It seems like you add the edges to your graph for the current_word twice as a result of this.
Prefer for word in words to for word in range(len(words)). This may indicate to an interviewer that you don't understand Python iterators or common patterns. This could also be a comprehension (and probably should be a tuple since edges can't change): graph[word] = tuple(other_word for other_word in words if _is_one_edit_apart(word, other_word))
You should probably pull your BFS out into a helper function. It is used in your algorithm. It is not part of your algorithm. This way you can test it separately.
BFS is also probably not the best approach here. Dijkstra's is more suitable because it can find the shortest path between two nodes (we can just assume the edges indicate edit distance and are all cost 1).
queue.append([neighbor, distance +1]) should be a tuple not a list. You aren't going to mutate it. This would likely concern an interviewer.
This is part of the question, but I don't like returning -1 for error. If you forget to handle this, this could lead to a problem (say you try to do math on the distance and assume it's always positive). You should be raising some sort of error. If I was asked to do something this silly, I would probably write my own function that raises and then provide an alternate API for this use case which wraps this function and converts the exception to a -1 out of principle.
unittest your code. Don't just throw a print statement and manually verify! And test all the pieces! This is why you separate out the one edit distance check and the BFS (well, Dijkstra's)

There's another larger problem in my mind, which isn't specified by the question, but it's the kind of question that I'd expect an engineer who encountered this problem to explore: what is the use case? Is this is one off (eg. are we using different word lists with every query)? If the word list is reused, this algorithm is inefficient, because it constructs a graph for each query. If the word list remains the same, then you should build the graph up once and then only do Dijkstra's for each query. I would implement this with a class the encapsulates the built graph and provide external API to query for edit distances. Then you could provide a function that uses this class for a one off query (where the words list is unique--never to be used again) to satisfy this interview question.

There is also an optimization you can make in constructing the graph. It is apparent from my revised _is_one_edit_apart. Namely, words can only be one edit apart if they are the same length or differ in length by only 1 character. So, when building the graph you can take this into account. Take all of the words group them by length. Then to build the part of the graph for length 1 words, you only have to consider length 1 or length 2 words. For length 2 words you have to consider length 1, 2, and 3 words. Etc. You original approach is always O(n^2). This is still worst case O(n^2) but will average much better than this given a decent distribution of word lengths.


JavaScript binding loss with setTimeout My current task is to extend some JavaScript of a framework we are using. A pop-up should slide in, instead of just appear in the middle of the window.
So I have overridden one of the framework's methods, and do at the end this:

AdfDhtmlPage.prototype.showMessages = function (componentId) {

// Some code here

function slideIn() {
  var maxTop = windowHeight - (thisHeight + 18);
  var tempTop = parseInt(popupElement._rootElement.style.top);

  if (maxTop >= tempTop) {
    setTimeout(function () {
      AdfPage.PAGE.clearMessages(componentId);
    },5000);
    return;
  }

  popupElement._rootElement.style.top = tempTop - 1 + 'px';
  setTimeout(slideIn, 20);
}
slideIn();
}

Everything worked just fine, but then I thought that the slideIn method should somehow be a behavior of the popupElement.
During refactoring I encountered a behavior that was new to me and which is here called binding loss.
So what I came up with is this:

AdfDhtmlPage.prototype.showMessages = function (componentId) {
    // Some code here
    popupElement._slideIn(popupElement, componentId);
}

AdfDhtmlSimpleFloat.prototype._slideIn = function(element, componentId) {
    var maxTop = AdfAgent.AGENT.getWindowHeight() - (element.getHeight() + 18);
    var thisTop = parseInt(element._rootElement.style.top);

    if (maxTop >= thisTop) {
        setTimeout(function () {
            AdfPage.PAGE.clearMessages(componentId);
        },5000);
        return;
    }

    element._rootElement.style.top = thisTop - 1 + 'px';
    setTimeout(function() {
        element._slideIn(element, componentId);
    }, 20);
}

So when calling the _slideIn method of popupElement I need to pass popupElement as argument. So I can access the objects properties, after the method has been called via setTimeout (When the binding loss happens).

However, this seems odd to me. So I would like to ask you to review my design. Maybe someone comes up with a better solution?

that was, what I wanted to do:

AdfDhtmlPage.prototype.showMessages = function (componentId) {
    // Some code here
    popupElement._slideIn(componentId);
}

AdfDhtmlSimpleFloat.prototype._slideIn = function(componentId) {
    var maxTop = AdfAgent.AGENT.getWindowHeight() - (this.getHeight() + 18);
    var thisTop = parseInt(this._rootElement.style.top);

    if (maxTop >= thisTop) {
        setTimeout(function () {
            AdfPage.PAGE.clearMessages(componentId);
        },5000);
        return;
    }

    this._rootElement.style.top = thisTop - 1 + 'px';
    setTimeout(this._slideIn, 20);
}

The problem is that this._slideIn refers to a function, not a method invocation.  In your third code sample, changing your last line to

var self = this;
setTimeout(function() { self._slideIn(componentId) }, 20);

should be sufficient.  You have to capture this in the closure that you pass to setTimeout(), because when the code runs later, this will refer to something else in that execution context.


Implementation of unix utility tail in C I've written a simple implementation of tail as part of reading The C Programming Language by Kernighan & Ritchie.

The question states to write tail, which prints the last n lines of its input. By default, n is 10 but should be able to be specified by writing:
tail -n to print the last n lines. I don't think the program has to open and read files, as that hasn't been covered in the book as of yet.

I chose to take input as tail -n <number> and wrote the code for parsing the arguments in (hopefully) that would allow for addition of more arguments at a later date easier using the switch statement. However right now, if there were more arguments (say x and z) one could write tail -xzn 10 which would be valid, printing the last 10 lines of input - which maybe could be viewed as a problem.

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

#define MAXLEN 1000

int tail(char *buffer[], int n);
int read_line(char *line, int max);
void print_lines(char* buffer[], int n);

static int lines_read = 0;

int main(int argc, char* argv[]) {
  int number_of_lines = 10;
  char c;

  while(--argc > 0 && (*++argv)[0] == '-') {
    while((c = *++argv[0])) {
      switch(c) {
        case 'n':
          if(argc-1 > 0)
            number_of_lines = atoi(*(argv+1));
          break;
      }
    }
  }

  char *line_buffer[number_of_lines];

  if(tail(line_buffer, number_of_lines) < 0) {
    printf("ERROR: failed to allocate memory for a line.\n");
    return -1;
  }

  printf("Output:\n");
  print_lines(line_buffer, number_of_lines);

  return 0;
}

int tail(char *buffer[], int n) {
  int characters_read = 0;
  char *p, line[MAXLEN];

  while((characters_read = read_line(line, MAXLEN)) > 0) {
    if((p = malloc(sizeof(char)*characters_read)) == NULL) {
      return -1;
    }
    strcpy(p, line);
    buffer[lines_read++ % n] = p;
  }

  return 0;
}

int read_line(char *line, int max) {
  int c, chars_read = 0;

  while((c = getchar()) != EOF && c != '\n' &&  ++chars_read < max-1)
    *line++ = c;

  *line = '\0';

  return chars_read;
}

void print_lines(char *buffer[], int n) {
  for(int i=0; i < (lines_read > n ? n : lines_read); i++)
    printf("%s\n", buffer[lines_read > n ? lines_read++ % n : i]);
}

Avoid globals. lines_read is naturally suited to return lines_read.
tail leaks memory. You shall free the line pointed by buffer[....] before reassigning it.
sizeof(char) is guaranteed to be 1.

I don't remember at which point K&R offer this exercise. In any case,

The line-reading loop is better expressed as fgets.
malloc/strcpy combination is a long way to say strdup.


Wait for a "3rd party" element to be appended to the DOM Let's say we're writing a user script which interacts with a 3rd party site we don't control. We want to open a menu, so we trigger a click on the button and then wait 10ms before accessing the menu (which is appended to the document after the click), like this:

$button = $('#button');
$button.trigger('click');
setTimeout(function() {
    //access the menu
}, 10);

This works, because it takes less than 10ms for the 3rd party site's handler to appended the menu to the DOM once the button is clicked. But it feels like bad code. Is there a better way to write this?

That's a perfect job for MutationObserver.

new MutationObserver(function(mutations) {
    this.disconnect();
    // access the menu
    ........
}).observe($('.immediate-parent-of-the-menu')[0], {childList: true});

$button = $('#button');
$button.trigger('click');

The simplest case above works as-is if the menu is added in one mutation, otherwise you'd have to check each of the mutations array elements for addedNodes.


Regex for a string with at least a letter and no repeating dash I had a problem a few days back and had to find a regex that matches a string that:

Contains only letters in the alphabet [a-z0-9-] so lowercase latin letters, numbers 0 to 9, and the dash character
Must contains at least a letter [a-z]
Must not contains repeating dashes. abc-def-gh is ok but not abc--def
The size of the string must be between 1 and 10 characters

I came up with:

^(?=[a-z0-9-]*[a-z][a-z0-9-]*)(?:[a-z0-9]|[-](?![-])){1,10}$

A little explanation:

(?=[a-z0-9-]*[a-z][a-z0-9-]*) lookahead to find if the string contains at least a letter
(?:[a-z0-9]|[-](?![-])){1,10} A non capturing group (not really important to capture or not I believe) with two parts, that must be between 1 and 10 chars

[a-z0-9] any letter in the alphabet I want
[-](?![-] a dash then a negative lookahead to see if there is no dash following

Here is a list of strings that should not match:

#should not match
-
1
1-
-1
aaaaaaaaaaaaaaaaa
11111
2a2--af
a2a--22

And a list of string that should match:

#should match
a
a-
-a
a-2
a2a
2a2-
a2a-2a2
a-b-c-d
a123213232
123213213a
a12321322a

HERE you can find an online regex tester to play with it.

All improvements, remarks, feedbacks is welcome. My guts is telling me the lookahead can be improved but I did not find how. Also, I'm not even sure the lookahead is needed at all. I'm eager to improve my regex skill so if you have any alternative method also I'd be really glad to know.

The lookahead (?=[a-z0-9-]*[a-z][a-z0-9-]*) can be reduce to:

(?=.*[a-z])

because the allowed characters are defined after in the non capturing group.

The dash [-] doesn't need to be inside a character class, - is enough

Then, the whole regex becomes:

^(?=.*[a-z])(?:[a-z0-9]|-(?!-)){1,10}$


Rubberduck VBA Parser, Episode V: The ANTLR Strikes Back I changed my mind. I don't want to implement 200-some Node classes. Instead, I'll be working directly with the ANTLR generated classes, to implement the Rubberduck code inspections, unit test method discovery, the "Code Explorer" tree view, and everything else Rubberduck might need a parse tree for.

The Node derived classes already implemented aren't wasted though: I'll eventually use them to expose a high-level view of the VBA code, to VBA itself (through COM interop) - that will enable very cool stuff, like VBA code that can enumerate its modules' members.

I changed the VBParser - I renamed ParseInternal to Parse (it becomes an overload of the public Parse method), and made it public as well:

public class VBParser : IRubberduckParser
{
    public INode Parse(string projectName, string componentName, string code)
    {
        var result = Parse(code);
        var walker = new ParseTreeWalker();

        var listener = new VBTreeListener(projectName, componentName);
        walker.Walk(listener, result);

        return listener.Root;
    }

    public IParseTree Parse(string code)
    {
        var input = new AntlrInputStream(code);
        var lexer = new VisualBasic6Lexer(input);
        var tokens = new CommonTokenStream(lexer);
        var parser = new VisualBasic6Parser(tokens);

        return parser.startRule();
    }
}

Now I can have an ANTLR IParseTree wherever I need it. One place I'm going to need it, is to discover test methods in the active VBA project. Rubberduck test methods are always public, parameterless methods, so I wrote this extension method/class:

public static class ParseTreeExtensions
{
    /// <summary>
    /// Finds all public procedures in specified parse tree.
    /// </summary>
    public static IEnumerable<VisualBasic6Parser.SubStmtContext> GetPublicProcedures(this IParseTree parseTree)
    {
        var walker = new ParseTreeWalker();

        var listener = new PublicSubListener();
        walker.Walk(listener, parseTree);

        return listener.Members;
    }

    private class PublicSubListener : VisualBasic6BaseListener
    {
        private readonly IList<VisualBasic6Parser.SubStmtContext> _members = new List<VisualBasic6Parser.SubStmtContext>();
        public IEnumerable<VisualBasic6Parser.SubStmtContext> Members { get { return _members; } }

        public override void EnterSubStmt(VisualBasic6Parser.SubStmtContext context)
        {
            var visibility = context.visibility();
            if (visibility == null || visibility.PUBLIC() != null)
            {
                _members.Add(context);
            }
        }
    }
}

Here's a unit test for it:

    [TestMethod]
    public void GetPublicProceduresReturnsPublicSubs()
    {
        IRubberduckParser parser = new VBParser();
        var code = "Sub Foo()\nEnd Sub\n\nPrivate Sub FooBar()\nEnd Sub\n\nPublic Sub Bar()\nEnd Sub\n\nPublic Sub BarFoo(ByVal fb As Long)\nEnd Sub\n\nFunction GetFoo() As Bar\nEnd Function";

        var module = parser.Parse(code);
        var procedures = module.GetPublicProcedures().ToList();
        var parameterless = procedures.Where(p => p.argList().arg().Count == 0).ToList();

        Assert.AreEqual(3, procedures.Count);
        Assert.AreEqual(2, parameterless.Count);
    }

This works, so I'm going to run with it. I don't want to expose the ANTLR generated classes to COM, so I'm moving it all into its own assembly, which Rubberduck will reference.

It looks to me like VBParser is somewhat mixing abstraction levels... but is that much of an issue? Is it a good idea to "walk" the tree like this? I'm not re-parsing the code, but I'll probably end up walking it multiple times when I run code inspections, and I'll have to implement several [simple] tree listeners, to retrieve the "interesting" nodes. Is this how I'm supposed to be doing this?

Anything else strikes you as weird with this approach?

One would expect that a method of a parser which returns an IParseTree would be named Parse() instead of startRule() which is in addition violating the naming guidelines.

You should declare variables as near as possible to their usage. You could also omit the assignment of the call to Parse()

public INode Parse(string projectName, string componentName, string code)
{
    var walker = new ParseTreeWalker();
    var listener = new VBTreeListener(projectName, componentName);

    walker.Walk(listener, Parse(code));

    return listener.Root;
}

The VisualBasic6Parser.SubStmtContext.visibility() method is also not going conform with the naming guidelines.

  Is it a good idea to "walk" the tree like this?

It is hard to say something about something one can't see.

  It looks to me like VBParser is somewhat mixing abstraction levels... but is that much of an issue?

It is a little bit distracting to see inside a Parse() method of a VBParser class which implements an IRubberduckParser interface that a VisualBasic6Parser class is used. But I have no idea how to solve this and if this has to be solved.


Simplify ASP.Net StreamWriter for appendtext to file Is there anyway to simplify this code so there aren't so many redundant w = File.AppendText(filePath) and w.flush() and w.close() in each if statement?

Anything else I have tried ends up locking the file, and crashing the site because to text file is in use by another process.

Public filePath As String = "c:\inetpub\logs\login.txt"
Public w As StreamWriter

Protected Sub LoginUser_LoginError(ByVal sender As Object, ByVal e As System.EventArgs) Handles LoginUser.LoginError

    Dim UserName As TextBox = DirectCast(LoginUser.FindControl("UserName"), TextBox)

    Dim CurrentUser As MembershipUser = Membership.GetUser(LoginUser.UserName)

    Dim logLoginError As New Thread(
        Sub()
            If (CurrentUser IsNot Nothing) Then

                If (CurrentUser.IsLockedOut = True) Then
                    w = File.AppendText(filePath)
                    w.WriteLine(CurrentUser.ToString & "'s (" & IPAddress & ") account is locked out - " & DateAndTime.Now)
                    w.Flush()
                    w.Close()
                ElseIf (CurrentUser.IsApproved = False) Then
                    w = File.AppendText(filePath)
                    w.WriteLine(CurrentUser.ToString & " (" & IPAddress & ") is attempting to login, but the account is disabled - " & DateAndTime.Now)
                    w.Flush()
                    w.Close()
                Else
                    w = File.AppendText(filePath)
                    w.WriteLine(CurrentUser.ToString & "'s (" & IPAddress & ") login credentials failed - " & DateAndTime.Now)
                    w.Flush()
                    w.Close()
                End If

            Else
                w = File.AppendText(filePath)
                w.WriteLine("Unknown user " & UserName.Text & " (" & IPAddress & ") attempting to login - " & DateAndTime.Now)
                w.Flush()
                w.Close()
            End If
        End Sub
    )
    logLoginError.Start()

End Sub

Careful with naming.

UserName is an identifier for a TextBox, but it's named like a String (which contains a user's name).

I'd declare and assign UserName like this:

Dim UserName As String = DirectCast(LoginUser.FindControl("UserName"), TextBox).Text

And now the rest of the code can refer to a string that represents a user's name without any further conversions.

logLoginError is an identifier for a Thread, but it's named like a Task (which runs on a thread).

loggerThread would be a more accurate name for it.

This code:

w.WriteLine(CurrentUser.ToString & "'s (" & IPAddress & ") account is locked out - " & DateAndTime.Now)

Is using way more String instances than you'd think:

CurrentUser.ToString()
"'s ("
IPAddress
") account is locked out - "
DateAndTime.Now[.ToString]

And also:

The string resulting from CurrentUser.ToString() & "'s ("
The string resulting from CurrentUser.ToString() & "'s (" & IPAdress
The string resulting from CurrentUser.ToString() & "'s (" & IPAdress & ") account is locked out - "
The string resulting from CurrentUser.ToString() & "'s (" & IPAdress & ") account is locked out - " & DateAndTime.Now

Are you sure DateAndTime isn't supposed to be DateTime? Also there's a typo in IPAdress, should be IPAddress.

To fix the number of String objects being created, you can use String.Format instead of inline concatenations - remember that String is an immutable class, "appending to it" doesn't really append anything, it just creates a new instance.

This would be cleaner and more efficient (multiline to avoid horizontal scrolling):

w.WriteLine(String.Format("{0}'s ({1}) account is locked out - {2}",
                          CurrentUser.ToString, IPAddress, DateAndTime.Now))


Getting a user's property Can this extension method be improved?

    public static string GetAvatar(this System.Security.Principal.IIdentity user)
    {
        var service = SmObjectFactory.Container.GetInstance<IApplicationUserManager>();
        return service.FindByIdAsync(int.Parse(user.GetUserId())).Result.Avatar;
    }

Now in my view I use the extension method this way:

User.Identity.GetAvatar()

But every time the page refreshes, it hits database for getting user's avatar.
I'd like to know this can be improved by caching that or something like that.

public static string GetAvatar(this System.Security.Principal.IIdentity user)
{
    var service = SmObjectFactory.Container.GetInstance<IApplicationUserManager>();
    return service.FindByIdAsync(int.Parse(user.GetUserId())).Result.Avatar;
}

Do you know that you can access this static method not only as a extension method ? Assume the containing class is called UserExtensions one could execute this method using UserExtensions.GetAvatar(null) and if the creation of the service would take some time to be created it would nevertheless throw an ArgumentNullException. So adding a guard condition to the method like

if (user == null) { throw new ArgumentNullException("user"); }

would be a good idea.

Otherwise the method is looking good.

By using a private static ConcurrentDictionary<string, string> you could add caching to this like so

private static ConcurrentDictionary<string, string> avatarDictionary = new ConcurrentDictionary<string, string>();
public static string GetAvatar(this System.Security.Principal.IIdentity user)
{

    if (user == null) { throw new ArgumentNullException("user"); }

    string userId = user.GetUserId();
    string avatar;
    if (avatarDictionary.TryGetValue(userId, out avatar))
    {
        return avatar;
    }

    var service = SmObjectFactory.Container.GetInstance<IApplicationUserManager>();
    avatar = service.FindByIdAsync(int.Parse(user.GetUserId())).Result.Avatar;

    avatarDictionary.AddOrUpdate(userId, avatar, (key, oldValue) => avatar);

    return avatar;
}

Based on @mjolka's comment

  Using a ConcurrentDictionary as a cache in this manner could be problematic, depending on the number of users and the size of the avatars. As they say, "A cache without an expiration policy is another name for a memory leak."

you should add some mechanism to let the entries of the dictionary expire.

Like @DavidArno has correctly stated in his comment

  And now you have a global method with static state, which is not a good place to be.

this isn't the best way to do this. By having a static dictionary this just can't be tested correctly, because the dictionary keeps its content between tests which is a no go.

A better way would be to create an interface having the GetAvatar() method which is implemented by a simple class. The interface should then be constructor injected and stored in a private field.

public interface IAvatarService
{
    string GetAvatar(System.Security.Principal.IIdentity user);
}

public class AvatarService : IAvatarService
{
    private ConcurrentDictionary<string, string> avatarDictionary = new ConcurrentDictionary<string, string>();
    public string GetAvatar(System.Security.Principal.IIdentity user)
    {

        if (user == null) { throw new ArgumentNullException("user"); }

        string userId = user.GetUserId();
        string avatar;
        if (avatarDictionary.TryGetValue(userId, out avatar))
        {
            return avatar;
        }

        avatar = user.GetAvatar() // call of the extension method

        avatarDictionary.AddOrUpdate(userId, avatar, (key, oldValue) => avatar);

        return avatar;
    }
}

having a expire mechanism would still be needed and should be implemented.