Keeping track of byte count in a binary protocol handler I am putting together a fairly simple server that listens for a connection then creates this thread - textbook Java code - then accepts data on that connection.

I am following a protocol that the manufacturer has laid out for start of message (0xfd)  and EOM (0xfe)  as below. I then simply populate a byte array with using a bytecounter.

I think this is the simplest doing so, and it seems to work fine. Is there any possible problem with taking this approach?  I want to be sure using a bytecounter with an array is acceptable. I can't see anyway that bytecounter could get out of sync or anything like that. I like to keeps things simple. Is there anything wrong with this code with regard to stuffing the inbyte[] array?

public void run() {

try {

    boolean socketalive = true;

    MSG_ID = 0;

    disIn = new DataInputStream( in  );
    disOut = new DataOutputStream ( out );

    String msg = null;

    StringBuilder hexforlog;

    byte[] c ;

    int i = 0;
    int bytecounter = 0;

    byte[] inbyte ;

    while( true ){

        i = 0;
        bytecounter = 0;

        inbyte = new byte[1024];

        byte b ;

        try{

            /* read from network until end of message byte is received */
            while( ( b = disIn.readByte() ) !=  (byte)0xfe ){

                /* checking for start of message */
                if( b == (byte)0xfd  ){

                    inbyte = new byte[1024];
                    inbyte[0] = b;
                    bytecounter = 1;

                }
                else {

                     inbyte[bytecounter] = b;
                     bytecounter++;

                }

            }

        }catch ( java.io.EOFException ioef ){
            System.out.println("EOF recieved bytes"  );
            break;
        }

        /*test for link verification */

        if( bytecounter == 15 ){

             byte SOURCEbyte = inbyte[2];
             byte DESTbyte = inbyte[3];

             /* swap bytes per protocol */
             inbyte[2] = (byte)DESTbyte;
             inbyte[3] = (byte)SOURCEbyte;

            disOut.write( java.util.Arrays.copyOfRange(inbyte,0,16) );
            disOut.flush();

        }

        /* process the data as per manufacturer spec */
        else if( bytecounter> 16  ){

            arrayindex = 12;

            int SOM = inbyte[0];
            int CLASS = inbyte[1];
            int SOURCE = inbyte[2];
            int DEST = inbyte[3];
            int MSG_PRG_NUMBER = inbyte[4];
            int SPARE1 = inbyte[5];
            int SPARE2 = inbyte[6];
            int SPARE3 = inbyte[7];

            LENGTH = twoBytesToInt( new byte[] { inbyte[8], inbyte[9] } );

            NUM_MSG = twoBytesToInt( new byte[] {  inbyte[10], inbyte[11]  } );

           System.out.println("LENGTH: " + LENGTH  + " NUM_MSG: " + NUM_MSG );
           System.out.println("Setting NUM_MSG to 1" );

            NUM_MSG = 1;

            for ( int j=0; j<NUM_MSG; j++  ) {

                MSG_ID = twoBytesToInt( new byte[] { inbyte[arrayindex],
                     inbyte[arrayindex+1] } );

                System.out.println("MSG_ID: " + MSG_ID );

                MSG_LENGTH =twoBytesToInt( new byte[] { inbyte[arrayindex+2],
                    inbyte[arrayindex+3] } );

                System.out.println("MSG_LENGTH: " + MSG_LENGTH  );

                arrayindex = arrayindex+4; //first go around 15

                currentarray = java.util.Arrays.copyOfRange(
                   inbyte, arrayindex, arrayindex+MSG_LENGTH+1);

                arrayindex = arrayindex+MSG_LENGTH ;

                //process messages

                if(MSG_ID == 50){
                    processMessage50( currentarray );
                }
                else if(MSG_ID == 70){
                    processMessage70( currentarray);
                }

            }

        }

    }

    disIn.close();
    disOut.close();

} catch (IOException e) {
    e.printStackTrace();
}

}

Some variables, such as socketAlive and hexforlog, aren't being used.

Another quirk I noticed is that you don't really take advantage of the capabilities of DataInputStream.  If you just want to read a byte at a time, any InputStream can accomplish that.  DataInputStream gives you the ability, for example, to read two bytes and interpret it as an unsigned 16-bit number using .readUnsignedShort().  I'm guessing that that is what your twoBytesToInt() does.  Hopefully, the protocol uses big endian numbers so that you can take advantage of .readUnsignedShort().

Your loop is structured such that any 0xfe byte in the input stream will be treated as the end of a packet.  That means that no 0xfe byte can ever appear in the payload of a message.  Most binary protocols are not designed that way — you should obey the message length fields instead.

Anyway, your code is one long function!  It desperately needs some kind of abstraction.  bytecounter and all of the concerns surrounding it can go away!  The code proposed below compiles, but obviously I can't test it.

Packet.java: This is just a "dumb" struct.

public class Packet {
    public byte som,
                packetClass,    // "class" is a Java keyword
                source,
                dest,
                msgPrgNumber,
                spare1,
                spare2,
                spare3;
    public int  length,         // 2-byte unsigned short
                numMsgs;        // 2-byte unsigned short

    public static class Message {
        public int msgId,
                   length;
        public byte[] payload;
    }
}

PacketInputStream.java: This constructs Packets from the data stream.

import java.io.*;

public class PacketInputStream {

    //////////////////////////////////////////////////////////////////////

    public static class MalformedPacketException extends Exception {
        public MalformedPacketException(String errMsg) {
            super(errMsg);
        }
    }

    //////////////////////////////////////////////////////////////////////

    private DataInputStream in;
    private Packet packet;
    private int messageNumber;

    public PacketInputStream(DataInputStream in) {
        this.in = in;
    }

    /**
     * Reads a 12-byte packet header.
     */
    public Packet readHeader() throws IOException {
        this.packet = new Packet();
        this.messageNumber = 0;
        do {
            this.packet.som       = in.readByte();
        } while (this.packet.som != 0xfd);
        this.packet.packetClass   = in.readByte();
        this.packet.source        = in.readByte();
        this.packet.dest          = in.readByte();
        this.packet.msgPrgNumber  = in.readByte();
        this.packet.spare1        = in.readByte();
        this.packet.spare2        = in.readByte();
        this.packet.spare3        = in.readByte();
        this.packet.length        = in.readUnsignedShort();
        this.packet.numMsgs       = in.readUnsignedShort();
        return this.packet;
    }

    public boolean hasMoreMessages() {
        return this.packet != null && this.messageNumber < this.packet.numMsgs;
    }

    public int getMessageNumber() {
        return this.messageNumber;
    }

    public Packet.Message readMessage() throws IOException {
        Packet.Message msg = new Packet.Message();
        msg.msgId   = in.readUnsignedShort();
        msg.length  = in.readUnsignedShort();
        msg.payload = new byte[msg.length];
        in.read(msg.payload);
        return msg;
    }

    /**
     * Requires the next input byte to be the end-of-packet marker.
     */
    public void readEndOfPacket() throws IOException, MalformedPacketException {
        byte b;
        if ((b = in.readByte()) != 0xfe) {
            throw new MalformedPacketException(String.format("Expected 0xfe, got 0x%02x", b));
        }
    }
}

PacketOutputStream is left as an exercise for the reader.

Consumer:

private void processMessage(Packet.Message msg) {
    switch (msg.msgId) {
      case 50:
        this.processMessage50(msg);
        break;
      case 70:
        this.processMessage70(msg);
        break;
    }
}

public void run() {
    try (DataInputStream  dataIn   = new DataInputStream(in);
         DataOutputStream dataOut  = new DataOutputStream(out)) {
        PacketInputStream  packIn  = new PacketInputStream(dataIn);
        PacketOutputStream packOut = new PacketOutputStream(dataOut);

        while (true) {
            Packet p = packIn.readHeader();

            // Read one message before writing the acknowledgement,
            // because that's what the original code did.  You
            // could simplify this by acknowledging immediately
            // after reading the header instead.
            Packet.Message msg = packIn.readMessage();
            packOut.writeAck(p);
            this.processMessage(msg);

            while (packIn.hasMoreMessages()) {
                this.processMessage(packIn.readMessage());
            }
            packIn.readEndOfPacket();
        }
    } catch (PacketInputStream.MalformedPacketException mpe) {
        mpe.printStackTrace();
    } catch (IOException ioe) {
        ioe.printStackTrace();
    }
}


Objective-C debug macros I'm looking for a review of my macros. I have these in the project pre-compile header. I tent to copy them into all my new projects as well, unless its a very simple project.

#ifdef __APPLE__
    #import <TargetConditionals.h>
#endif

// turn on or off different types of logging. ALog() is always logged.
#define LOG_D       // Turn on standard debug messages  DLog();
#define LOG_N       // Turn on network debug messages   NLog();
#define LOG_DB      // Turn on database debug messages  DBLog();
#undef  LOG_V       // Turn off verose debug messages   VLog();
#undef  LOG_UI      // Turn off popup messages          UILog();

// -- You should not have to mess with anything below this line --

// Be safe, start with all things defined
#define DEBUGLOG(...) do {} while (0)
#define ALERTLOG(...) do {} while (0)
#define ALWAYSLOG(...) do {} while (0)

// Define three basic debug types, DEBUGLOG, ALERTLOG and ALWAYSLOG
// These macros generally should not be called directly
// DEBUGLOG - show a message only when compiled for debugging
// ALERTLOG - show a popup window message only when compile for debugging
// ALWAYSLOG - show a message debugging and release
#ifdef __APPLE__
#ifdef DEBUG
#undef DEBUGLOG
#define DEBUGLOG(type, fmt, ...) NSLog((@"%@: %s [Line %d] " fmt), type, __PRETTY_FUNCTION__, __LINE__, ##__VA_ARGS__)
#undef ALERTLOG
#if TARGET_OS_MAC
#define ALERTLOG(fmt, ...) DEBUGLOG(@"I", fmt, ##__VA_ARGS__)
#else
#define ALERTLOG(fmt, ...)  { UIAlertView *alert = [[UIAlertView alloc] initWithTitle:[NSString stringWithFormat:@"%s\n [Line %d] ", __PRETTY_FUNCTION__, __LINE__] message:[NSString stringWithFormat:fmt, ##__VA_ARGS__]  delegate:nil cancelButtonTitle:@"Ok" otherButtonTitles:nil]; [alert show]; }
#endif
#endif
#undef ALWAYSLOG
#define ALWAYSLOG(type, fmt, ...) NSLog((@"%@: %s [Line %d] " fmt), type, __PRETTY_FUNCTION__, __LINE__, ##__VA_ARGS__)
#endif

// Create some standard logging macros
#ifdef LOG_D
#define DLog(fmt, ...) DEBUGLOG(@"D", fmt, ##__VA_ARGS__)
#else
#define DLog(...) do {} while (0)
#endif
#ifdef LOG_N
#define NLog(fmt, ...) DEBUGLOG(@"Net", fmt, ##__VA_ARGS__)
#else
#define NLog(...) do {} while (0)
#endif
#ifdef LOG_DB
#define DBLog(fmt, ...) DEBUGLOG(@"DB", fmt, ##__VA_ARGS__)
#else
#define DBLog(...) do {} while (0)
#endif
#ifdef LOG_V
#define VLog(fmt, ...) DEBUGLOG(@"V", fmt, ##__VA_ARGS__)
#else
#define VLog(...) do {} while (0)
#endif
#ifdef LOG_UI
#define UILog(fmt, ...) ALERTLOG(fmt, ##__VA_ARGS__)
#else
#define UILog(...) do {} while (0)
#endif
#define ALog(fmt, ...) ALWAYSLOG(@"V", fmt, ##__VA_ARGS__)

At very least, DO NOT copy-paste your macros directly into .pch file

  A PCH file is, by definition, a project specific precompiled header.
  It really shouldn't be used beyond the context of the project and it
  really shouldn't contain anything but #includes/#imports.

As suggested by an Apple engineer, you should make a separate file with your macros e.g. Defines.h, and just put #import Defines.h into .pch file.
I would suggest re-thinking you logging strategy. If it is not absolutely necessary (e.g. you do not have access to production instance of your app), you should log only the critical errors. Abundance of logging code decreases its readability/maintainability and can even CAUSE bugs. I recommend an excellent blog post on this matter from co-founder of Stack Overflow.


Building a 2D Game Engine Using SFML I've always loved making games and using SFML, and up until a few days ago, I've had to re-write code over and over again. So I decided to write a game engine so I can reuse my code.

I've never done something like this before. I've read about it, and I watched a few videos. I'd love if you could look around, give me some ideas. Keep in mind I've only worked on this for less than a week.

GitHub

So far, I've just re-skinned SFML functions and classes using my own classes, but I've changed some functions around and made things a bit simpler.

Is it, for example, any good creating my own Sprite class that is basically a re-skin of the SFML sprite class, with perhaps some added functionality, or should my resource manager just return an SFML sprite, which the user of the engine can just use all the in-built functionality for the sf::Sprite?

Here is a very simple program that creates a sprite and a text and draws them on the screen. And we can use WASD to move the sprite.

#include <Tengine2D\ResourceManager.hpp>
#include <Tengine2D\Window.hpp>
#include <Tengine2D\Keyboard.hpp>
#include <Tengine2D\Clock.hpp>
#include <Tengine2D\Text.hpp>
#include <Tengine2D\Vector2.hpp>
#include <Tengine2D\GameState.hpp>
#include <Tengine2D\Camera.hpp>

#include <iostream>

int screenWidth = 1600;
int screenHeight = 640;

t2d::Clock _clock;
t2d::GameState gameState;

int main()
{

    t2d::Window _window;
    _window.create(screenWidth, screenHeight, "BELLO!");

    gameState = t2d::GameState::PLAY;

    // Text
    t2d::ResourceManager::createText("Text", "Fonts/times.ttf");
    t2d::ResourceManager::getText("Text").setCharacterSize(50);
    t2d::ResourceManager::getText("Text").setStyle(t2d::TextStyle::Bold);
    t2d::ResourceManager::getText("Text").setColor(t2d::Color::Magenta);
    t2d::ResourceManager::getText("Text").setPosition(screenWidth / 4.0f, screenHeight / 2.0f);
    t2d::ResourceManager::getText("Text").setString("Hello World");

    // Sprite
    t2d::ResourceManager::createSprite("RedPlayer", "Sprites/RedPlayer.png");
    t2d::ResourceManager::getSprite("RedPlayer").setPosition(screenWidth / 4.0f, screenHeight / 2.0f);

    while (gameState != t2d::GameState::QUIT)
    {
        float delta = _clock.restart().asSeconds();

        while (_window.pollEvent())
        {
            if(t2d::Keyboard::keyPressed(t2d::Keyboard::Escape))
            {
                gameState = t2d::GameState::QUIT;
            }
        }

        if (t2d::Keyboard::isKeyPressed(t2d::Keyboard::D))
        {
            t2d::ResourceManager::getSprite("RedPlayer").translate(400 * delta, 0.0f);
        }
        if (t2d::Keyboard::isKeyPressed(t2d::Keyboard::A))
        {
            t2d::ResourceManager::getSprite("RedPlayer").translate(-400 * delta, 0.0f);
        }
        if (t2d::Keyboard::isKeyPressed(t2d::Keyboard::S))
        {
            t2d::ResourceManager::getSprite("RedPlayer").translate(0.0f, 400 * delta);
        }
        if (t2d::Keyboard::isKeyPressed(t2d::Keyboard::W))
        {
            t2d::ResourceManager::getSprite("RedPlayer").translate(0.0f, -400 * delta);
        }

        _window.clear(t2d::Color(150, 150, 5, 255));
        _window.draw(t2d::ResourceManager::getSprite("RedPlayer"));
        _window.draw(t2d::ResourceManager::getText("Text"));
        _window.display();
    }

    return 0;
}

Personally, I see no gain in abstracting SFML at this stage. In general I only see two situations where abstracting such a fundamental library really makes sense and that would be for:

If you want to fully test your code. In that case you need to be able to decouple from the "system" and thus from SFML.
If your engine has advanced to a stage where it isn't just a cheap tech demo, but actually something real, used for some real games. Only then does it make sense to think about, whether it would make sense to refactor the code base to potentially allow for different "backends".

Additionally, option 2 is rarely possible to do cleanly, since all the frameworks offer a different set of functionalities and switching between them with a single API on top, doesn't really work and limits the set of features to be used of said library.

As for your code and question, there's a reason why SFML splits font and text, texture and sprites, soundbuffer and sound, etc. The point is that you have a heavy resource (font, texture, soundbuffer) and a light "instance" object (text, sprite, sound). That way you can move, copy, manipulate the light instances all you want and not run into any issues performance wise, while the heavy resources need to be loaded once and then kept alive as long as the light instances are using it.

Your resource manager as such shouldn't hold on to text objects or sprites and instead just handle the heavy resources and ensure that they stay alive as long as they're used. I recommend to take a look at Thor's resource management well and Thor in general as it's a nice addition to SFML.

How you want to store text or sprites is up to you and depends on the kind of game. For most simple games, it's enough to save them directly in a game state class and if you need lots, then just use a std::vector but keep in mind the advantages and limitations of used containers.


Serializing a table for filing I have a table in Lua, which contains two 1-dimensional arrays in which each array contains approximately 800,000 elements. I want to serialize this Lua table to file efficiently. Hence, I planned to use Lua C bindings.

#include "lua.h"
#include "lauxlib.h"
#include <stdio.h>
#include <assert.h>

static int do_it(lua_State *L) {
  assert(L && lua_type(L, -1) == LUA_TTABLE);

  int len, idx;
  void *ptr;
  FILE *f;
  size_t r;

  lua_pushstring(L, "p");
  lua_gettable(L, -2);
  len = lua_objlen(L, -1);
  // instead of using lua_rawlen, i used lua_objlen. see below
  // len = lua_rawlen(L, -1); // it throws the following error
  // lua: error loading module 'savetable' from file './savetable.so':
  //    ./savetable.so: undefined symbol: lua_rawlen
  int p_values[len];
  for (idx = 1; idx <= len; idx++) {
    lua_rawgeti(L, -1, idx);
    p_values[idx - 1] = (int)lua_tonumber(L, -1);
    lua_pop(L, 1);
  }

  f = fopen("p.bin", "wb");
  assert(f);
  r = fwrite(p_values, sizeof(int), len, f);
  printf("[p] wrote %zu elements out of %d requested\n", r, len);
  fclose(f);
  lua_pop(L, 1);

  lua_pushstring(L, "q");
  lua_gettable(L, -2);
  len = lua_objlen(L, -1);
  double q_values[len];
  for (idx = 1; idx <= len; idx++) {
    lua_rawgeti(L, -1, idx);
    q_values[idx - 1] = (double)lua_tonumber(L, -1);
    lua_pop(L, 1);
  }

  f = fopen("q.bin", "wb");
  assert(f);
  r = fwrite(q_values, sizeof(double), len, f);
  printf("[q] wrote %zu elements out of %d requested\n", r, len);
  fclose(f);
  lua_pop(L, 1);

  return 1;
}

int luaopen_savetable(lua_State *L) {
  static const luaL_reg Map[] = {{"do_it", do_it}, {NULL, NULL}};

  luaL_register(L, "mytask", Map);
  return 1;
}

Please note that for debugging purpose, I have defined two very small 1-dimensional arrays:

my_table = {p = {11, 22, 33, 44}, q = {0.12, 0.23, 0.34, 0.45, 0.56}}

require "savetable"
mytask.do_it(my_table)

I used the following commands to compile and run it:

> gcc -I/usr/include/lua5.1 -o savetable.so -shared savetable.c -fPIC
> lua wrapper.lua

The code works, however, I am looking for suggestions to make table serialization to file much faster than current.

Please note that I am using Lua 5.1 on a 64-bit Ubuntu PC.

// undefined symbol: lua_rawlen

This happens because there is no such function in Lua 5.1 C API. As stated by documentation lua_objlen is preffered way to get table length.

FYI lua_rawlen function first appeared in Lua 5.2.

It is very handy to check Lua Reference manual to see availiable C API for particular Lua version.

Serialization with zero latency

Wow, that title stands out. Let me explain what I mean: serialization with zero latency means there is no serialization at all.

Watch out: it heavely depends on the origin of your table.

The caveats:

you must control the table creation
only inserts, no removes

If this is the case, follow on:

As you stated your table is actually an array of Lua numbers. In C Lua number is lua_Number which is probably a double value.

We can create a custom table implementation to only store Lua numbers in it.
The table will be continuos memory with lua_Number members in it.

typedef struct {
    lua_Number *items;
    size_t len; // number of entries in items
    size_t cap; // maximum `len` value before we will `realloc(items)`
} fasterarray;

To provide fasterarray we'll use lua_newuserdata. It will allocate memory that will be watched by Lua garbage collector. In particular when there is no more references the allocated userdata will be collected.

static int new(lua_State *L) {
    fasterarray *fa = lua_newuserdata(L, sizeof(fasterarray));
    luaL_getmetatable(L, NAME); // <-- setting metatable, see below
    lua_setmetatable(L, -2);    // <--
    fa->len = 0;
    fa->cap = 8;
    fa->items = calloc(fa->cap * sizeof(lua_Number), 1);
    return 1;
}

Insert function will realloc items when more space is needed.

static int insert(lua_State *L) {
    fasterarray *fa = lua_touserdata(L, 1);
    lua_Number num = lua_tonumber(L, 2);
    if (fa->len == fa->cap) {
        fa->cap *= 2;
        fa->items = realloc(fa->items, fa->cap * sizeof(lua_Number));
        assert(fa && fa->items);
    }
    fa->items[fa->len++] = num;
    return 0;
}

Important part of this implementation is garbage collection. userdata will be collected by Lua automagically, but the memory behind items must be freed directly in C. To handle this we will use __gc metatable method.

static int gc(lua_State *L) {
    fasterarray *fa = lua_touserdata(L, 1);
    if (fa && fa->items) free(fa->items);
    printf("gc\n");
    return 0;
}

Full example:

fasterarray.c

#include <lua.h>
#include <lauxlib.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define NAME "fasterarray"

typedef struct {
    lua_Number *items;
    size_t len;
    size_t cap;
} fasterarray;

static int new(lua_State *L) {
    fasterarray *fa = lua_newuserdata(L, sizeof(fasterarray));
    luaL_getmetatable(L, NAME);
    lua_setmetatable(L, -2);
    fa->len = 0;
    fa->cap = 8;
    fa->items = calloc(fa->cap * sizeof(lua_Number), 1);
    return 1;
}

static int gc(lua_State *L) {
    fasterarray *fa = lua_touserdata(L, 1);
    if (fa && fa->items) free(fa->items);
    printf("gc\n");
    return 0;
}

static int insert(lua_State *L) {
    fasterarray *fa = lua_touserdata(L, 1);
    lua_Number num = lua_tonumber(L, 2);
    if (fa->len == fa->cap) {
        fa->cap *= 2;
        fa->items = realloc(fa->items, fa->cap * sizeof(lua_Number));
        assert(fa && fa->items);
    }
    fa->items[fa->len++] = num;
    return 0;
}

int luaopen_fasterarray(lua_State *L) {

    // fasterarray metatable
    luaL_newmetatable(L, NAME);
    luaL_register(L, NULL, (luaL_Reg []) {
        {"__gc", gc},
        {NULL, NULL}
    });

    // exported funcs
    luaL_register(L, NAME, (luaL_Reg []) {
        {"new", new},
        {"insert", insert},
        {NULL, NULL}
    });
    return 1;
}

example.lua

require"fasterarray"

local ar = fasterarray.new()
local i = 700000
while i > 0 do
        fasterarray.insert(ar, i)
        i = i - 1
end


Summing the digits of a number (subtracting the first digit if it is negative) I'm working on some practice problems using higher- order functions and while I was able to solve this problem. I can't help but think this code is ugly and not the most eloquent it could be. Is there a way to combined map and reduce is a cleaner way than I have done ? Additionally, is there any other methods or improvements I could have used here ? I'm just looking to get better and any feedback would be appreciated.

Problem: Given a number, "sumDigits" returns the sum of all its digits. If the number is negative, the first digit should count as negative.

function sumDigits(num) {

  //create array of number char
  var string = num.toString().split('');

  //if first char is negative symbol let the first numeric element be negative
  if (string[0] === "-") {
    string[1] = '-' + string[1];
    string.shift();
  }

  //convert string to int
  var toInteger = string.map(function(x) {
    return Number(x);
  });

  //get sum
  return toInteger.reduce(function(sum, current) {
    sum += current;
    return sum;
  })
}

sumDigits(-316);

The key to a clean solution is to make it so that the negative sign is not a special case.  Instead of splitting the string character-by-character, capture the digits, such that the first digit might be negative.

function sumDigits(num) {
  return num.toString()
            .match(/-?\d/g)
            .map(function (s) { return parseInt(s) })
            .reduce(function (a, b) { return a + b });
}

console.log(sumDigits(-316));

Also, your variable names are weird and misleading:

The result of .split() is an array, so don't call it a string.
The process of converting a string into a number (i.e. function(x) { return Number(x); }) would be appropriately called toInteger, but once you have applied the string-to-integer conversion to each element of the array, the result would be more appropriately named digits.


ActionGroupContext to know an id of the current context My services(or services that depend on services) need to know about a current action group id. To add an extra optional parameter to each service for the id was an idea but in my current environment to difficult and ugly because every service would have to take in the parameter only to pass it to other services.

My solution was a class ActionGroupContext which stores the current context in a static ThreadStore or HttpStore.

What I don't like especially with my solution is that even though you are not do web application you have to include a reference to System.Web, but the convenience is great, the user does not need any setup code.

Do you have any improvement ideas?

Demo usage:

public void SomeApplicationMehtod()
{
    using (new ActionGroupContext())
    {
        someService.SomeMehtod();
    }
}

public class SomeService
{
    public void SomeMehtod()
    {
        var id = ActionGroupContext.Id;

        //Do something with the Id.

    }
}

The code:

public class ActionGroupContext : IDisposable
{
    private static readonly GuidStore GuidStore = new GuidStore("Action-Group-Id-Store");

    private readonly Guid? oldId;
    public ActionGroupContext()
    {
        oldId = GuidStore.GetGuid();
        GuidStore.SetGuid(Id ?? Guid.NewGuid());
    }

    public static Guid? Id
    {
        get { return GuidStore.GetGuid(); }
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (disposing)
        {
            GuidStore.SetGuid(oldId);
        }
    }
}

public class ThreadStore : IStore
{
    private readonly LocalDataStoreSlot slot;
    public ThreadStore(string storeKey)
    {
        slot = Thread.GetNamedDataSlot(storeKey);
    }

    public object GetData()
    {
        return Thread.GetData(slot);
    }

    public void SetData(object data)
    {
        Thread.SetData(slot, data);
    }
}

public interface IStore
{
    object GetData();
    void SetData(object data);
}

public class ThreadStore : IStore
{
    private readonly LocalDataStoreSlot slot;
    public ThreadStore(string storeKey)
    {
        slot = Thread.GetNamedDataSlot(storeKey);
    }

    public object GetData()
    {
        return Thread.GetData(slot);
    }

    public void SetData(object data)
    {
        Thread.SetData(slot, data);
    }
}

public class HttpStore : IStore
{
    private readonly string storeKey;

    public HttpStore(string storeKey)
    {
        if (!IsContextForStoreAvailable())
        {
            throw new InvalidOperationException("HttpContext is not available");
        }
        this.storeKey = storeKey;
    }

    public object GetData()
    {
        return HttpContext.Current.Items(storeKey);
    }

    public void SetData(object data)
    {
        HttpContext.Current.Items(storeKey) = data;
    }

    public static bool IsContextForStoreAvailable()
    {
        return HttpContext.Current != null;
    }
}

Your Dispose pattern is somehow flawed.

public void Dispose()
{
    Dispose(true);
    GC.SuppressFinalize(this);
}

protected virtual void Dispose(bool disposing)
{
    if (disposing)
    {
        GuidStore.SetGuid(oldId);
    }
}

You don't check if the object already is disposed, so calling Dispose() over and over will result in each time calling GuidStore.SetGuid(oldId);.

So using a private variable for saving if the object is disposed would be the way to go.

private bool disposed = false;

public void Dispose()
{
    Dispose(true);
    GC.SuppressFinalize(this);
}

protected virtual void Dispose(bool disposing)
{
    if (!disposed && disposing)
    {
        GuidStore.SetGuid(oldId);
        disposed = true;
    }
}

Also for completeness you should also use the finalizer like so

~ActionGroupContext()
{
    Dispose(false);
}

One thing what should never happen is that a call to Dispose() throws an exception. If you are 100% sure this can't happen, you are fine. If you aren't 100% sure, you should enclose the call to SetGuid() inside a try..catch block.

Please read this: proper-use-of-the-idisposable-interface

In your posted code I see neither in the ThreadStore nor in the HttpStore any usage of this ActionGroupContext so I see no reason to reference System.Web to use this context.


How can I optimize this array.each in ruby? I'm trying to optimize this bit of code and I thought I'd throw it out here to see if anyone has any ideas. I've been testing the performance using Benchmark.measure {...} and wrapping the entire function.

Yes, the item has a date that is a Ruby Date

  puts Benchmark.measure {
    grouped_items
  }

  def grouped_items
    unless @grouped
      @grouped = {}
      @items.each do |item|
        key = item.date
        if @grouped.has_key?(key)
          @grouped[key] << item
        else
          @grouped[key] = [item]
        end
      end
    end
    @grouped
  end

Thanks for any insight you care to share.

Edit #1: My first optimization. I was aiming for a slightly more succinct function and gained a .2 seconds reduction in time to process 100_000 items.

  def grouped_items
    unless @grouped
      @grouped = Hash.new { |h, k| h[k] = [] }
      @items.map {|item| @grouped[item.date] << item }
    end
    @grouped
  end

Edit #2: My second iteration with more or less the same performance profile but with much less code.

def grouped_items
  @grouped ||= @items.group_by { |item| item.date }
end

Edit #3: An alternative way to do the same thing above.

def grouped_items
  @grouped ||= @items.group_by &:date
end

Are you aware of Enumerable#group_by?

def grouped_items
  @items.group_by{|item| item.date}
end


MySQLConnection Conn.Connect() I'm pretty new to working with databases, and I would like to know if I've made some common, major design flaws in my implementation. For context, the whole project is intended to be used by a single user.

The code I want reviewed:

class DatabaseConnection
{
    //properties
    private MySqlConnection _connection;
    public MySqlConnection Connection { get { return _connection; } }
    public AccountLogin AccountCredentials { get; }
    public DatabaseLogin DatabaseCredentials { get; }

    //constructor
    public DatabaseConnection(AccountLogin _AccCred,
                              DatabaseLogin _DBCred)
    {
        AccountCredentials = _AccCred;
        DatabaseCredentials = _DBCred;
    }

    public void Connect()
    {
        if (Connection != null)
        {
            return;
        }

        string[] UserInputs =
        {
            DatabaseCredentials?.DatabaseName,
            DatabaseCredentials?.Server,
            DatabaseCredentials?.Port,
            AccountCredentials?.Password,
            AccountCredentials?.Username
        };
        bool ChkInpts = Validators.NullStringValidator(UserInputs);

        if (!ChkInpts)
        {
            string ConnInfo = "server=" + DatabaseCredentials.Server + ";" +
                              "user=" + AccountCredentials.Username + ";" +
                              "database=" + DatabaseCredentials.DatabaseName +
                              "port=" + DatabaseCredentials.Port +
                              "password=" + AccountCredentials.Password;
            _connection = new MySqlConnection(ConnInfo);

            try
            {
                Console.WriteLine("Connecting to " + DatabaseCredentials.DatabaseName + "...");
                _connection.Open();
                Console.WriteLine("Connection to " + DatabaseCredentials.DatabaseName + " successful.");
            }

            catch (Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }
    }
    public void Close()
    {
        _connection.Close();
    }
}

Relevant code:

class AccountLogin
{
    public string Username { get; }
    public string Password { get; }

    public AccountLogin(string _username, string _password)
    {
        Username = _username;
        Password = _password;
    }
}

class DatabaseLogin
{
    public string DatabaseName { get; }
    public string Server { get; }
    public string Port { get; }

    public DatabaseLogin(string _server, string _DatabaseName, string _port)
    {
        DatabaseName = _DatabaseName;
        Server = _server;
        Port = _port;
    }
}

static class Validators
{
    public static bool NullStringValidator(string[] _inputs)
    {
        bool _result = false;
        for (int i = 0; i < _inputs.Length; i++)
        {
            if (string.IsNullOrEmpty(_inputs[i]))
            {
                return _result = true;
            }
        }
        return _result;
    }
}

The conventional naming for arguments in C# is camelCase:

  AccountLogin _AccCred

looks better as

AccountLogin accountLogin

I wonder if this: DatabaseCredentials?.DatabaseName is of any use? if DatabaseCredentials is null what database can you then connect to?

I would throw an exception if DatabaseCredentials == null. This applies probably to AccountCredentials too.

String concatenations are a rather inefficient way to  build strings:

instead of

string ConnInfo = "server=" + DatabaseCredentials.Server + ";" +
                              "user=" + AccountCredentials.Username + ";" +
                              "database=" + DatabaseCredentials.DatabaseName +
                              "port=" + DatabaseCredentials.Port +
                              "password=" + AccountCredentials.Password;

use either

StringBuilder

or

String.Format("server={0};user={1};...", DatabaseCredentials.Server, AccountCredentials.Username,...);

or

string interpolation:

$"server={DatabaseCredentials.Server};user={AccountCredentials.Username};..."

MySqlConnection implements IDisposable. Therefore your wrapper should do that as well, so you can dispose the _connection object, and the client can then use your wrapper like this:

using (DatabaseConnection dc = new DatabaseConnection(...))
{
  // Use the connection...
}

The try-catch-statement in the Connect() method is of no use to the client because, if the connection fails, it is not signaled to the client. Either rethrow the exception, throw a new exception of your own or simply ignore any exceptions here and let the client handle them.

in

public void Close()
{
    _connection.Close();
}

you should test for _connection == null.


Testable code with ORM factory I'm trying to improve the following code for testability.

public function can_apply_extension()
{

    $search_dates = [
        Carbon::createFromTimestamp(strtotime($this->billing_verified_to))->subMonth(1),
        $this->billing_verified_to
    ];

    $record = ORM::factory('a model')
                 ->where('created_at', 'BETWEEN', $search_dates)
                 ->find();

    if( !$record->loaded() )
    {
        return true;
    }

    return false;

}

Here's how I think I can improve it:

public function can_apply_extension($search_from = null, $search_to = null)
{

    $search_from = is_null($search_from) ? Carbon::createFromTimestamp(strtotime($this->billing_verified_to))->subMonth(1) : $search_from;
    $search_to = is_null($search_to) ? $this->billing_verified_to : $search_to

    $search_dates = [$search_from, $search_to];

    $record = ORM::factory('a model')
                 ->where('created_at', 'BETWEEN', $search_dates)
                 ->find();

    if( !$record->loaded() )
    {
        return true;
    }

    return false;

}

I still have to mock ORM part. I think the only option is that I pass an object as a parameter or make a method that injects the ORM object.

Are there any other better ways? I'm aware of IoC container, but I can't use it in our current environment.

Update: Beside passing ORM as a parameter so that I can just swap it out, I found another workaround.

Since ORM::factory() actually returns an object, I was able to add a method and modify the factory method.

public function testing($bool)
{
    $this->_testing = $bool;
}

public function instead($when_this_passed, ORM $use_this_instead)
{
    $this->_instead_map[$when_this_passed] = $use_this_instead;
}

public function factory($name)
{
    if($this->_testing && array_key_exists($name, $this->_instead_map))
    {
        return $this->_instead_map[$name];
    }
    else
    {
        parent::factory($name);
    }
}

(I've not coded in PHP recently, my examples are Java or Java-like pseudocode.)

In his Working Effectively with Legacy Code book Michael C. Feathers describes a lot of techniques which help making any code testable. Another good resource is the following article: Killing the Helper class, part two

The usual way to breaking static dependencies is the following: Create a non-static interface which has a similar method than the original static class:

public interface OrmFactory {
    OrmSomething create($name);
}

Then create an implementation which calls the static method/class:

public class OrmFactoryImpl implements OrmFactory {
    public OrmSomething create($name) {
        return ORM::factory($name);
    }
}

Finally, use the interface in the can_apply_extension function:

public class MyClass {

    private OrmFactory ormFactory;

    public MyClass(OrmFactory ormFactory) {
        this.ormFactory = ormFactory;
    }

    public void can_apply_extension() {
        ...
        $record = ormFactory.create('a model')
                     ->where('created_at', 'BETWEEN', $search_dates)
                     ->find();
        ...
    }
}

In tests you can pass a mocked OrmFactory to the class while in production code you can use the original one through the OrmFactoryImpl wrapper/delegate. (I guess PHP also has some mocking framework implementations which makes testing easier but you can implement a TestOrmFactory which emulates some behaviour of the original one without the need of any database.)

The second snippet in the question has test logic in production smell. I would avoid that and use the much cleaner dependency breaking above. The linked page contains some disadvantages of the smell. One of them is the following:

  Code that was not designed to work in production
  and which has not been verified to work properly
  in the production environment could accidently be
  run in production and cause serious problems.

And another one is:

  Software that is added to the SUT For Tests Only
  makes the SUT more complex. It can confuse potential
  clients of the software's interface by introducing
  additional methods that are not intended to be
  used by any code other than the tests. This
  code may have been tested only in very specific
  circumstances and might not work in the typical
  usage patterns used by real clients.

(SUT means System Under Test, in this case the class with can_apply_extension().)


Is it correct to use delegates as properties? I need to create a class with two properties:

LogOutput
ExceptionOutput

These properties (of type Action) send a message or a exception depending on the target function. This target function is set via properties.
Currently, I have the following code:

public class Output
{
    private Action<string> logOutput;
    private Action<Exception, string> exceptionOutput;

    public Action<string> LogOutput
    { set { this.logOutput = value; } get { return this.logOutput; } }
    public Action<Exception, string> ExceptionOutput
    { set { this.exceptionOutput = value; } get { return this.exceptionOutput; } }

    public Output() : this(null, null) { }

    public Output(Action<string> logAction, Action<Exception, string> exceptionAction)
    {
        this.logOutput = logAction;
        this.exceptionOutput = exceptionAction;
    }

    public void WriteLogMessage(string format, params object[] args)
    {
        if (this.logOutput != null)
        logOutput(string.Format(format, args));
    }

    public void WriteExceptionMessage(Exception ex, string format, params object[] args)
    {
        if (this.exceptionOutput != null)
        exceptionOutput(ex, string.Format(format, args));
    }
}

And this is my form code:

private void MainForm_Load(object sender, EventArgs e)
{
    Output myOutput = new Output();

    myOutput.ExceptionOutput = this.WriteExceptionMessageToTextBox;
    myOutput.LogOutput = this.WriteLogMessageToTextBox;

    myOutput.WriteLogMessage("this is my log message to text box");
    myOutput.WriteExceptionMessage(new Exception("this is my exception"),
        "this is my exception message to text box");
}

private void WriteLogMessageToTextBox(string message)
{
    if (this.txtBox.IsDisposed)
    return;

    if (this.InvokeRequired)
    {
        BeginInvoke(new MethodInvoker(delegate() { WriteLogMessageToTextBox(message); }));
    }
    else
    {
        this.txtBox.AppendText(message + Environment.NewLine);
    }
}

private void WriteExceptionMessageToTextBox(Exception ex, string message)
{
    if (this.txtBox.IsDisposed)
    return;

    if (this.InvokeRequired)
    {
        BeginInvoke(new MethodInvoker(
            delegate() { WriteExceptionMessageToTextBox(ex, message); }));
    }
    else
    {
        string msg = "";
        msg += string.Format("Program:{0}", message);
        msg += string.Format("Message{0}", ex.Message);
        msg += string.Format("StackTrace:{0}", ex.StackTrace);
        msg += string.Format("Source:{0}", ex.Source);
        this.txtBox.AppendText(msg + Environment.NewLine);
    }
}

The thing is I don't know if this is correct (although it's working). If it's not correct, how can I change it? How can I implement it with events?

Yes, I think this is reasonable code. If you want to set more delegates at the same time or unsubscribe a delegate, events would be more appropriate. But if you don't want to do that, delegate properties are fine.

There are some things to think about though:

The code you use to invoke the delegates is not thread-safe. If one thread called WriteLogMessage() and another thread set logOutput to null at the same time, you might get a NullReferenceException. The thread-safe version would be:

var logOutputTmp = this.logOutput;
if (logOutputTmp != null)
    logOutputTmp(string.Format(format, args));

Consider using automatic properties. They do the same thing as your code, only with less writing. Also, get accessor is usually written before the set accessor, but that's only a minor style issue.

public Action<string> LogOutput { get; set; }

Do you need the public setters and the parameterless constructor? If you expect that both delegates will be always set at construction, then it's better to make that clear and have only one constructor and no public setters.


Finding a loop in a directed graph in Python I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I read somewhere that you can colour mark the nodes. So this is my iterative implementation of that method. Is it an okay'ish' approach and how can I improve on it if it's correct?

These are the test cases

def dfs(graph, start):
    color = {i : 'white' for i in graph}
    stack = [start]
    visited = []

    while stack:
        vertex = stack.pop()
        if color[vertex] == 'grey':
            return True
        color[vertex] = 'grey'
        visited.append(vertex)
        stack.extend((graph[vertex]))
        if  len(graph[vertex]) == 0:
            color[vertex] = 'black'
    return False

def cycle_exists(graph):
    for vertex in graph:
         if(dfs(graph, vertex)):
             return True
    return False

# connected graph with cycle
graph1 = { 0 : [1, 2],
           1 : [],
           2 : [3],
           3 : [4],
           4 : [2] }
assert(cycle_exists(graph1) == True)
print("Graph1 has a cycle.")

#----------------------------------------------------

# disconnected graph with cycle
graph2 = { 0 : [],
           1 : [2],
           2 : [],
           3 : [4],
           4 : [5],
           5 : [3] }
assert(cycle_exists(graph2) == True)
print("Graph2 has a cycle.")

#----------------------------------------------------

# disconnected graph without a cycle
graph3 = { 0 : [],
           1 : [],
           2 : [],
           3 : [] }
assert(cycle_exists(graph3) == False)
print("Graph3 has no cycle.")

#----------------------------------------------------

# disconnected graph without a cycle
graph4 = { 0 : [1, 2],
           1 : [3, 4],
           2 : [],
           3 : [],
           4 : [],
           5 : [6, 7],
           6 : [],
           7 : [] }
assert(cycle_exists(graph4) == False)
print("Graph4 has no cycle.")

#----------------------------------------------------

# If assert raises an error, then a test case was not passed.
print("\nAlgorithm passed all test cases")

Lets first review your code, and then introduce you to one alternative on how to do unit tests in Python.

Adding comments or docstrings is good – In dfs(), not the best named function by the way, you use colors to mark something, but you don't explain what the different colors mean. I had to guess that:

white means unvisited vertex
grey means visited vertex
black means disconnected vertex

I should have to guess that, and it should be written in a docstring related to the function. This applies for all similar coded segments where it is not intuitive what the variable, function or variable values means.
Add blank lines to enhance readability – The common guidelines says two blank lines between functions, but I would like to extend that to have a blank line around most if, for and while blocks, and the occasional block of code.

You've done this to some extent, but there are two places I really would like to do this and that after the while and for loop where you do an immmediate return statement, which now seems connected to the inner loop code.
Avoid loose code at top level – In general only imports, constants, functions and classes are to be at the top level of your file. This makes it, amongst others, easy to use your file as a module, and it helps organise your code. In your code all of your tests are at the top level, and should have been within some test scope. I'll come back to this below.

In general you could/should put all this code within one or more functions, like main(), and call it from the following top level code at the end of your file:

if __name__ == '__main__':
    main()

Another nice options, when entering the world of unit tests, is to execute the unit tests when you execute the python file directly, and then otherwise use the exposed functions, i.e. cycle_exists() and dfs().
Remove the visited list in dfs() – It seems like you've forgotten to remove the visited list in dfs(), as it isn't currently used for anything besides being initialised and added to. You don't do any checks against it.
Similarily, remove black from the palette – In your current implementation you don't use the color black for anything, and as such it can be removed, which also would allow for a simpler dict, as the only thing you seem to be interested in is whether it has been visited or not. This can be achieved using a boolean.
Add more error handling – Your code doesn't do much error handling or validation of input, which some like and some don't like. I think I would have added at least a test that the graph exists at some level.
No need for the inner parentheses in dfs() when adding to stack – At least in my tests you can remove the inner set of parentheses, and no change happens.

Refactored code

Here is my refactored code, renaming dfs() to detect_cycle() and adding some comments and docstrings:

def detect_cycle(graph, start):
    """Traverse the graph, and see if we come back to a earlier visited vertex."""

    if graph is None:
        raise ValueError("We need a graph to detect cycles in")

    # Set all vertexes to None, as we don't know the status of it
    visited = {v : False for v in graph}

    stack = [start]

    # Traverse from start, adding connected nodes to the stack as we go
    while stack:
        vertex = stack.pop()

        # If we hit a vertex we've seen before, it is a cycle
        if visited[vertex]:
            return True

        # Mark this vertex as visited
        visited[vertex] = True

        # Add connected nodes to stack, if any
        stack.extend(graph[vertex])

    # If stack is empty, that means no cycle for this start vertex
    return False

def cycle_exists(graph):
    """Return whether the graph has cycles or not."""

    # Loop through each vertex, and check if it has cycles or not
    for vertex in graph:
         if detect_cycle(graph, vertex):
             return True

    return False

One thing I haven't addressed if whether this is the most effective way to check for cycles. In fact I know it isn't as for each vertex we traverse the graph over and over again.

This implies that the current algorithm has an \$O(n^2)\$ complexity, which most likely could be simplified utilising another list of visited vertexes, and instead of looping through all vertexes, one could visit only those not already visited. This is left as an exercise for the reader... :-)

Unit tests

Multiple options exists for doing unit tests in Python, and it comes down to personal preferences. Here I'll present you for the internal version, namely unittest, which suffices for this code.

A common pattern for a unit test is the following:

Arrange – Set up all needed variables, you need to execute the test
Act – Execute the actual test
Assert – Assert that the test result are as expected

In your case the tests are rather simple, so I've done some according to this scheme, and for some I've taken a few shortcuts. But even though the tests are simple, do remember to let one test method only test one thing. It is considered an anti-pattern to have multiple actions or asserts in one method.

Using unittest, I find that using a class name like test__function_to_test is a nice pattern, although not entirely according to guidelines. This should inherit from unittest.TestCase enabling us to easily run the tests using unittest.main(), which will run all tests functions starting with test_.

So here are your tests, and some more. The following code is added beneath the other code (with exception of import at top):

import unittest           # This line on the very top

class test__cycle_exits(unittest.TestCase):
    """ Helper class to test the cycle_exists function

    This class test the main method cycle_exists, which heavily
    depends on the detect_cycle method, to find whether cycles exists
    in the connected graphs.
    """

    def test_connected_graph_with_cycle(self):

        self.assertTrue(cycle_exists({
            0 : [1, 2],
            1 : [],
            2 : [3],
            3 : [4],
            4 : [2]
        }))

    def test_disconnected_graph_with_cycle(self):

        self.assertTrue(cycle_exists({
            0 : [],
            1 : [2],
            2 : [],
            3 : [4],
            4 : [5],
            5 : [3]
        }))

    def test_empty_graph_without_cycle(self):

        # Arrange
        graph = {
            0 : [],
            1 : [],
            2 : [],
            3 : []
        }

        # Act
        has_cycle = cycle_exists(graph)

        # Arrange
        self.assertFalse(has_cycle)

    def test_disconnected_graph_without_a_cycle(self):

        self.assertFalse(cycle_exists({
            0 : [1, 2],
            1 : [3, 4],
            2 : [],
            3 : [],
            4 : [],
            5 : [6, 7],
            6 : [],
            7 : []
        }))

    def test_confused_graph_result(self):

        # Arrange
        graph = {
            0: [1],
            1: [2],
            2: [0]
        }

        # Act
        has_cycle = cycle_exists(graph)

        # Arrange
        self.assertFalse(has_cycle, "Didn't expect cycles for this one! Or did I?") # Dead wrong!!!

class test__detect_cycle(unittest.TestCase):
    """Helper class to test the detect_cycle function.

    Using some simple graphs, test the various parts of this functions
    """

    def test_single_connected_graph(self):
        self.assertTrue(detect_cycle({ 0: [0]}, 0))

    def test_simple_connected_graph(self):
        self.assertTrue(detect_cycle({ 0: [1], 1 : [0]}, 0))

    def test_single_disconnected_graph(self):
        self.assertFalse(detect_cycle({ 0: []}, 0))

    def test_simple_disconnected_graph(self):
        self.assertFalse(detect_cycle({ 0: [1], 1 : []}, 0))

    def test_graph_multiple_connections(self):
        self.assertTrue(detect_cycle({
            0: [1, 2, 3],
            1: [],
            2: [],
            3: [0]
        }, 0))

    def test_multipaths(self):
        self.assertTrue(detect_cycle({
            0: [1, 2, 3],
            1: [2, 3],
            2: [3],
            3: [0]}, 0))

    def test_nonexistent_start(self):

        # Arrange
        graph = { 0: [1], 1: [0] }

        # Act and Assert an exception
        with self.assertRaises(KeyError):
            detect_cycle(graph, 2)

    def test_nonexistent_graph(self):
        # Arrange
        graph = None

        # Act and Assert an exception
        with self.assertRaises(ValueError):
            detect_cycle(graph, 0)

if __name__ == '__main__':
    unittest.main()

Notice how I tried to give meaningful names to each of the test methods so that it should be understandable what failed if/when they fail. If everything is OK the output would have been:

.............
----------------------------------------------------------------------
Ran 13 tests in 0.005s

OK

However I've deliberately added a fault, with an message, so the output if you run this code is:

F............
======================================================================
FAIL: test_confused_graph_result (__main__.test__cycle_exists)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "<filename>", line 118, in test_confused_graph_result
    self.assertFalse(has_cycle, "Didn't expect cycles for this one! Or did I?") # Dead wrong!!!
AssertionError: Didn't expect cycles for this one! Or did I?

----------------------------------------------------------------------
Ran 13 tests in 0.005s

FAILED (failures=1)

Notice how the 'dots' have changed to include an F, and that the FAIL: line names that is was the test_confused_graph_result() in the test__cycle_exists class which has failed, and you get some details as to what failed.

If the test is well written you should now easily see why it failed, and hopefully understand what went wrong.


linearly interpolate NA values in Rcpp::NumericVector I am trying to fill missing values with linearly interpolated values in an Rcpp::NumericVector -- leaving in place leading and trailing NA-values.

The desired output is below:

R> x <- c(NA, NA, NA, 1:4, NA, 6:8, NA, 10, NA, NA, NA)
R> naLinInt(x)
R> [1] NA NA NA  1  2  3  4  5  6  7  8  9 10 NA NA NA

I've implemented it via the below, but as i am very new to C++ i'd very much benefit from some help in understanding how to do this better.

I feel that i've really hacked my way through this -- in particular i suspect i've over-used pointers and that there's a better way to do this sort of indexing and offsetting.

#include<Rcpp.h>

//[[Rcpp::export]]
Rcpp::NumericVector naLinInt(Rcpp::NumericVector x) {
    // This function linearly interpolates between NA values

    Rcpp::Rcout << "We begin with: " << std::endl << x << std::endl;

    double * it1 = x.begin();
    double * it2 = x.begin();
    int step = 0;

    it1++;

    while( it1 < x.end() ) {
        if( Rcpp::NumericVector::is_na(*it1)) {
            if( Rcpp::NumericVector::is_na(*(it1 - 1))) {
                it1++;
                continue;
            } else {
            it2 = it1;
            step = 0;
            while(it2 < x.end() && Rcpp::NumericVector::is_na(*it2)) {
                step++;
                it2++;
            }
            if( it2 == x.end()) break;
            // step through missing values and replace
            for(int j = 0; j < step; j++) {
                *it1 = *(it1 - 1) + (*it2 - *(it1 - 1))/(step + 1 - j);
                it1++;
            }
            it1 = it2 + 1;
            }
        } else {
            it1++;
        }
    }

    return x;
}

As you suggest, the code does look very "pointery".  I think it might be made clearer with use of some standard algorithms:

std::adjacent_find() (with suitable predicate functions) to find a number followed by NA, or a NA followed by a number.
std::generate() (with suitable generator function) to populate a series of values from one iterator to another.

With those, you won't need any arithmetic on iterators other than a subtraction to find the number of elements you're interpreting.

The form of such a solution is something like this (untested):

#include <Rcpp.h>
#include <algorithm>

constexpr auto is_na = Rcpp::NumericVector::is_na;

//[[Rcpp::export]]
Rcpp::NumericVector naLinInt(Rcpp::NumericVector x) {
    // This function linearly interpolates to fill sequences of NA
    // values surrounded by valid numbers.
    static auto const detect_start_na = [](auto a, auto b){
        return !is_na(a) && is_na(b);
    };
    static auto const detect_end_na = [](auto a, auto b){
        return is_na(a) && !is_na(b);
    };

    auto start = x.begin();

    while (true) {
        // Find transitions to and from NA values.  If we hit end of
        // vector whilst looking, our work is done.
        auto num_to_na = std::adjacent_find(start, x.end(), detect_start_na);
        auto na_to_num = std::adjacent_find(start, x.end(), detect_end_na);
        if (na_to_num == x.end()) {
            break;
        }

        // At this point, num_to_na points to the last number before
        // an interpolation block, and na_to_num points to the last NA
        // of that block.

        ++na_to_num;            // Now, both iterators point to numbers.
        auto const base = *num_to_na;
        auto const target = *na_to_num;

        // To count rails rather than posts, measure difference before
        // incrementing the start position.
        auto const gaps = std::distance(na_to_num, num_to_na);

        ++num_to_na;
        // Now both iterators point immediately *after* transition.

        auto const make_value = [base, target, gaps, i = std::size_t{0}]()
            mutable { return base + (++i * (target - base) / gaps); };
        std::generate(na_to_num, num_to_na, make_value);

        // Advance onwards
        start = na_to_num;
    }

    return x;
}

There are a couple of iterator increments there (because std::adjacent_find returns an iterator to the first of the matching pair), but there's quite a lot less arithmetic than the original.

Although this is longer than the original, much of the difference is the comments that help the reader understand how the state changes through the loop.  That's something that I think is an improvement (though perhaps the terms "rails" and "posts" require a link to a definition of fencepost error for the uninitiated).


Resolving directory traversal I keep seeing /subsite/../global/css/file.css when I look at my website's source code, and today I decided that I want to get rid of the unnecessary traversal in the path itself, so it becomes /global/css/file.css. I made myself a function which I now use for all paths. Here is the base of my function that accomplishes this:

function djpth($pth){
    // Split path at slashes (always receives path with forward slash)
    $pth = explode('/',$pth);
    // Iterate through the new array
    foreach ($pth as $i => $part)
        // If we find a traversal mark
        if ($part == '..')
            // We get rid of the folder name before the mark and the mark itself
            array_splice($pth,$i-1,2);
    // We join the array back together
    $pth = implode('/',$pth);
    // Then we return the resolved path
    return $pth;
}

I want to know if there's a better way to go about this, or if this is the best I can get.

djpth('/parent/subsite/../../global/css/file.css')

returns

/parent/../file.css

I guess that is not what you want.
If the file exists I'd use the built-in realpath function. I guess it handles corner case like this and another ones better.

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries)
$pth is used for multiple purposes. It would be easier to read a $path and a $path_array.
Abbreviations are hard to read, like $pth. Longer names would make the code more readable since readers don't have to decode the abbreviations every time and when they write/maintain the code don't have to guess which abbreviation the author uses.

Furthermore, it's hard to pronounce (as well as djpth).

  If you can’t pronounce it, you can’t discuss it without sounding like an idiot. “Well,
  over here on the bee cee arr three cee enn tee we have a pee ess zee kyew int, see?” This
  matters because programming is a social activity.

Source: Clean Code by Robert C. Martin, Use Pronounceable Names, p21
Comments like this are just noise:

// Iterate through the new array

It's obvious from the code itself. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

$pth = implode('/',$pth);
// Then we return the resolved path
return $pth;

The comment above could be eliminated with a better variable name:

$resolved_path = implode('/', $path_array);
return $resolved_path;


condensing a list of lists with 'description' lines in Python I have a long list of data pulled in from a csv file that has comments / descriptions scattered throughout the document. I'd like to collapse the descriptions into the last element of each row of data, and my current solution seems slow and overly complex. Rows with data have values in the first index and description rows are empty strings. This gives me a list of lists like so:

data = [
    ['a', 'this', 'is', 'data', 1, 2, 3, ''],
    ['', '', '', 'this is a description', '', '', '', ''],
    ['', '', '', 'that carries onto two lines', '', '', '', ''],
    ['another', 'row', 'with', 'data', 0, 3, 1, ''],
    ['', '', '', 'this is a description', '', '', '', ''],
    ['', '', '', 'that carries onto three lines', '', '', '', ''],
    ['', '', '', 'like so', '', '', '', ''],
    ['data', 'with', 'no', 'description', 9, 2, 0, ''],
    ['b', 'this', 'is', 'data', 1, 2, 3, ''],
    ['', '', '', '', 'sometimes the description', 'is offset', '', '']
]

Here's what I'd like to see:

desired_data = [
    ['a', 'this', 'is', 'data', 1, 2, 3,
     'this is a description that carries onto two lines'],
    ['another', 'row', 'with', 'data', 0, 3, 1,
     'this is a description that carries onto three lines like so'],
    ['data', 'with', 'no', 'description', 9, 2, 0, None],
    ['b', 'this', 'is', 'data', 1, 2, 3, 'sometimes the description is offset']
]

My current solution requires creating whole new lists, one with data and one with descriptions, and then iterating over the data and searching through the descriptions each iteration:

# get numbered rows with data (first element is not '')
actual_data = [(i, x) for i, x in enumerate(data) if x[0] != '']

# get numbered rows with descriptions (first element is '')
descriptions = [(i, ' '.join([j for j in x if j != '']))
                   for i, x in enumerate(data) if x[0] == '']

# get just the indices of the rows with descriptions
description_indices = {i[0] for i in descriptions}

desired_data_attempt = []
for d in actual_data:
    # get data to insert
    x = d[1][:]

    # get first index to check
    n = d[0] + 1

    description = []
    while n in description_indices:
        # keep adding consecutive descriptions
        description.append([i[1] for i in descriptions if i[0] == n][0])
        n += 1

    # set empty descriptions to None; othewise create one string from list
    if description == []:
        x[-1] = None
    else:
        x[-1] = ' '.join(description)

    # insert data with description
    desired_data_attempt.append(x)

assert desired_data_attempt == desired_data

Ideally, I'd love to be able to construct this new object in one pass through the original data. Any suggestions would be appreciated!

You can do this in one go, just keep a data piece you are going to yield and list of comment items. If you encounter a new comment item - append to list, if you encounter a ata piece - yield one you were holding with all the comments, wipe comments and hold a new data item instead, like this:

def is_comment(item):
    return item[0] == ''

def nonempty(item):
    return [x for x in item if x]

def fuse_comments(data):
    result = data[0]
    comments = []
    for element in data[1:]:
        if is_comment(element):
            comments += nonempty(element)
        else:
            yield result + [' '.join(str(comment) for comment in comments)]
            comments = []
            result = nonempty(element)
    yield result + [' '.join(str(comment) for comment in comments)]

from pprint import pprint

pprint(list(fuse_comments(data)))


Script to fix audio level I need to fix and maintain the master volume in PulseAudio (so that I don't blow up my speakers). E.g. call gfaaudio -v 25 to fix volume at 25%. Is there a cleaner way to get this done?

gfaaudio:

#!/bin/bash

usage="Usage: `basename $0` [-v VOL] "

if [ "$1" = "-h" ] || [ "$1" = "--help" ]; then
    echo $usage
    echo "  -h, --help  for help"
    exit
fi

#############################
Dcard="alsa_card.usb-Musical_Fidelity_Musical_Fidelity_V90-DAC_24_96-00-M2496"
Dout="iec958-stereo"
Dname="alsa_output.usb-Musical_Fidelity_Musical_Fidelity_V90-DAC_24_96-00-M2496.iec958-stereo"
VOL=30
#############################

while [ $# -gt 0 ]; do
    case "$1" in
        -v)
            shift
            [ $# -gt 0 ] && VOL="$1";;
        -*)
            echo "Option not supported: $1" >&2
            echo $usage >&2
            exit 1;;
        *) break;;
    esac
    shift
done

pacmd set-card-profile "$Dcard" output:"$Dout"
pacmd set-default-sink "$Dname"
[ -z "$(pidof -x gfaaudioloop)" ] || killall gfaaudioloop
gfaaudioloop "$Dname" "$VOL" &

exit

gfaaudioloop:

#!/bin/bash

if [[ $# != 2 ]]; then
    echo "number of arguments not 2" >&2
    exit 1
fi

while : ; do
    exits=$(pactl set-sink-volume "$1" "$2"%)
    exitc=$?
    [ ! -z "$exits" -o $exitc -ne 0 ] && break
    sleep 0.5
done

exit

Use $(...) style command substitution instead of the deprecated `...` style. And double-quote variables if they might contain spaces. So instead of this:

usage="Usage: `basename $0` [-v VOL] "

Write like this:

usage="Usage: $(basename "$0") [-v VOL] "

Testing with [ ... ] is deprecated in favor of the more modern and powerful [[ ... ]]. So instead of this:

if [ "$1" = "-h" ] || [ "$1" = "--help" ]; then

Write like this:

if [[ $1 = -h || $1 = --help ]]; then

This is equivalent, but notice that it's shorter, and in this form there is no need for those double-quotes. (Strictly speaking, in [ ... ] there was no need to double-quote "-h" and "--help", only "$1", the variable).

But in any case, why not move the handling of -h and --help together with the other options of the script?

while [[ $# -gt 0 ]]; do
    case "$1" in
        -h|--help)
            echo $usage
            echo "  -h, --help  for help"
            exit;;
        -v)
            shift
            [[ $# -gt 0 ]] && VOL="$1";;
        -*)
            echo "Option not supported: $1" >&2
            echo $usage >&2
            exit 1;;
        *) break;;
    esac
    shift
done

This way it's simpler, and now you can use -h and --help anywhere on the command line, not only as the first argument.

About this bit:

[ -z "$(pidof -x gfaaudioloop)" ] || killall gfaaudioloop

I don't have the pidof command so I can't really test it, but in general it doesn't sound good to put the output of a program into a string just to check with -z if it's empty. Usually there is a more direct way, using the exit code of the program. Here's an example that should come quite close to what you want:

ps xa | grep -q gfaaudioloop && killall gfaaudioloop

Having the exit at the end of a script makes is exit with success. Without it, the exit code of the script will be that of the last command executed. If you correctly check for and handle the exit code of all commands, then you don't need to explicitly exit. Let the script exit normally, using the exit code of the last command executed.


Recursive and iterative Euclidean algorithms Is this code too cryptic?  Simple yes or no question. Feedback is optional.

int recursive_euclidean( int num1, int num2 )
{
    int gcd=0;
    if( num1 == num2 || num1 < 0 || num2 < 0 )
        ( ( num1 == num2 ) ? ( gcd = num1 ) : ( ( num1 < 0) ? ( gcd = num2 ) :
            ( gcd = num1 ) ) );
    else
        ( ( num1 > num2 ) ? ( gcd = recursive_euclidean( num1-num2, num2 ) ) :
            ( gcd = recursive_euclidean( num1, num2-num1 ) ) );
    return gcd;
}

int iterative_euclidean( int num1, int num2 )
{
    while( num1 != num2 && num1 > 0 && num2 > 0 )
       (( num1 > num2 ) ? (num1-=num2) : (num2-=num1) );
    return (num1>0) ? num1 : num2;
}

I don't like the multiple different assignments inside the operator.
They currently all assign to gcd but you need to study it in detail to work that out.
I would make the assignment explicit and the ternary operator return the correct value.

The other thing with ternary operator is that they are not trivial to read. So use white space to try and make it obvious that it's happening. Also I prefer to explicitly use '{' '}' to make sure that things don't accidentally become associated with the a different statement. I would lay it out like this:

int recursive_euclidean( int num1, int num2 )
{
    int gcd;

    if( num1 == num2 || num1 < 0 || num2 < 0 )
    {
        gcd = (num1 == num2)
                 ? num1
                 : (num1 < 0)
                      ? num2
                      : num1;
    }
    else
    {
        gcd = (num1 > num2)
                 ? recursive_euclidean( num1-num2, num2 )
                 : recursive_euclidean( num1, num2-num1 );
    }
    return gcd;
}

Actually reading this again I would refactor more to this:

int recursive_euclidean( int num1, int num2 )
{
    int gcd;

    if ( num1 == num2)
    {    gcd = num1;
    }
    else if (num1 < 0)
    {    gcd = num2;
    }
    else if (num2 < 0)
    {    gcd = num1;
    }
    else
    {
        gcd = (num1 > num2)
                 ? recursive_euclidean( num1-num2, num2 )
                 : recursive_euclidean( num1, num2-num1 );
    }
    return gcd;
}

Then here, I would not personally not use the ternary operator.

int iterative_euclidean( int num1, int num2 )
{
    while( num1 != num2 && num1 > 0 && num2 > 0 )
    {
       if (num1 > num2 )
           { num1-=num2;}
       else{ num2-=num1;}
    }
    return (num1>0) ? num1 : num2;
}


Setting the smallest number so far from user input I'm trying to teach myself C++ from Stroustrup's Principles and Practice Using C++ (second edition) and I've gotten to the drill in chapter 4. The problem tells me to make a program that takes in a number with a unit of either feet, inches, meters, and centimeters, as well as log the largest and smallest numbers the user has input. I got the code to work by initializing my smallest number as 0 and making an if statement check if the input was smaller or 0 (because you can't really have 0 length).

Is there a way to either start with an infinitely larger "smallest number" variable so it always changes it in the if statement, or a way to where it has to do as few if statements as possible? Also, I'd rather not ask for an initial starting number before the while loop.

#include "std_lib_facilities.h"

using namespace std;

int main()
{
    cout << "Please input a number followed by a unit (cm, m, in, ft). Results are read in meters. Input a '|' to terminate the program." << endl;

    double x;
    string unit = " ";;
    constexpr double cm = .01;
    constexpr double in = .0254;
    constexpr double ft = .3048;
    double smallest = 0;
    double largest;
    double sum = 0;

    while(cin >> x >> unit)
    {
        if((char)x == '|')
            break;

        cout << "Value entered: " << x << unit << endl;
        if(unit=="m" || unit=="cm" || unit=="in" || unit=="ft") //converts units to meters
        {
            if(unit == "m")
            {
                x=x;                //
            }
            else if(unit == "cm")
            {
                x*=cm;
            }
            else if(unit == "in")
            {
                x*=in;
            }
            else if(unit == "ft")
            {
                x*=ft;
            }
            else
                cout << "Something went wrong." << endl;

            if(x > largest)
            {
                largest = x;
            }
            if(x < smallest || smallest == 0)
            {
                smallest = x;
            }
            cout << "The smallest number so far is: " <<smallest<< " meters\n";
            cout << "The largest number so far is: " << largest << " meters\n";

            sum+=x;
        }
        else
            cout << "Invalid unit! Try again." << endl;
    }
    cout << "The sum of all lengths is: " << sum << " meters\n";
}

Overall, this looks pretty good. It's straightforward and readable, which is great.
Naming
One of the most important things in programming is naming things so that anyone reading the code can figure out the meaning. You've done a pretty good job, but I think you could improve it. Calling a variable x is kind of useless. You could name it something like userValue, or even input so someone reading the code at least knows from the name that it's something that's input by the user.
Your constant names are OK, but could be better. (It's great that you're using named constants at all, though!) It would be nice to add that your converting from cm or in to meters. And there are some common conventions for constants, too. Some people prefer constants to be all capital letters, and others prefer to prefix them with the letter "k" (like it's a mathematical constant). So you could name them CM_TO_METERS or kInToMeters, etc. That way if you add other types of conversions in the future (like converting to Imperial), then you might add kCmToInches or whatever.
Finding the Min and Max
You ask if there's a good constant to initialize the minimum to. I usually use the constant DBL_MAX in this case. (It's defined in <cfloat>.) If you're looking for only positive numbers, then you can use 0 as the start value for the maximum value. Then any number entered will automatically be greater than that.
Potential Problem
I see one thing that could be a problem. You declare x as a double, but the first thing you do with it is cast it to a char and check if it equals |. That seems really odd, error prone, and hard to understand. If it were me, I would probably refactor this to prompt the user to tell me what they want to do (convert another value, or quit), then after they've told me they want to enter a number, get the numeric input into x.
A Better Loop
You say you don't like having the initial prompt outside of the loop, and I agree. It's good to remind the user what input you're expecting each time through the loop. I'd probably rewrite the loop like this:
bool done = false;
do {
    cout << "What would you like to do?\n";
    cout << "1) Convert a value\n";
    cout << "2) Quit\n";
    char action;
    cin >> action;
    if (action == '2')
    {
        done = true;
    }
    else
    {
        // Your code for getting and converting a number
    }
} while (!done);

Now it will prompt the user each time through the loop, and when they decide to quit, they can simply enter "2" at the prompt.


Converting hex to integer What's the fastest way of doing this?

int hextoint(char number) {
    if (number == '0') {
        return 0;
    }
    if (number == '1') {
        return 1;
    }
    if (number == '2') {
        return 2;
    }
    /*
     *  3 through 8
     */
    if (number == '9') {
        return 9;
    }
    if (number == 'a') {
        return 10;
    }
    if (number == 'b') {
        return 11;
    }
    if (number == 'c') {
        return 12;
    }
    if (number == 'd') {
        return 13;
    }
    if (number == 'e') {
        return 14;
    }
    if (number == 'f') {
        return 15;
    }
    return -1;
}

It seems that RippeR isn't going to write a full answer, so here's my take (especially as my comments to another answer got deleted together with the little jewel that proposed std::unordered_map).

First of all, the performance charactistics of a small function like hex digit conversion depend heavily on the context where it is used, and so it's impossible to say what's fastest until a concrete usage context has been specified.

The problem of hex digit conversion is a bit special in that it has a particular solution - the lookup table - which has excellent performance characteristics across a wide range of usages, and the smallest possible code footprint at the same time. It does, however, impose a bit of overhead for the initialisation of the lookup table, either in the form of static initialisation or initialisation with code.

Anyway: regardless of how the lookup table gets initialised, it will usually be used via a litte function wrapper (or member function, if wrapped in a class):

enum {  NOT_A_DIGIT = (1 << CHAR_BIT) - 1  };
typedef unsigned char byte;
byte DigitValue[1 << CHAR_BIT];

// ...

unsigned hex_digit_value_v3 (char c)
{
   return DigitValue[byte(c)];
}

The cast to byte (i.e. unsigned char) is necessary because char can be - and often is - signed.

Modern compilers will usually inline the code even if it resides in a .cpp somewhere, so there's no need to get cute. In an actual implementation the lookup table could be integrated with the character classification table for the scanner/lexer, but here I filled all non-digit slots with NOT_A_DIGIT. For completeness' sake, here's the initialisation code I used:

void set_lookup_range_ (byte base_value, char lo, char hi)
{
   for (byte c = byte(lo); ; ++c)
   {
      DigitValue[c] = byte(base_value + (c - byte(lo)));  // cast needed since ari widens to int

      if (c >= byte(hi))
         return;
   }
}

void initialise_lookup_table ()
{
   std::memset(DigitValue, NOT_A_DIGIT, sizeof(DigitValue));
   set_lookup_range_( 0, '0', '9');
   set_lookup_range_(10, 'A', 'F');
   set_lookup_range_(10, 'a', 'f');
}

It takes more space than static initialisation but it's more flexible, which is good for experimentation. It also makes the code independent from the execution character set in the sense that it's not necessary to know up front which character maps to which code point.

To get some timings I pitted the function against three other versions. To make the test realistic, I adapted a function from a high-performance scanner:

// to be called with read_ptr pointing at a hex digit; digits that don't fit into an unsigned get
// dropped quietly (i.e. they shifted out at the upper end)

template<unsigned hex_digit_value (char c)>
DECLSPEC_NOINLINE
unsigned extract_hex_unsigned (char const **read_ptr)
{
   char const *p = *read_ptr;
   unsigned value = hex_digit_value(*p);
   unsigned digit;

   while ((digit = hex_digit_value(*++p)) < 16)
      value = (value << 4) + digit;

   *read_ptr = p;

   return value;
}

Besides allowing tests with a bunch of 8-digit hex strings, it can also be called with huge strings to get a different take on performance characteristics. Excess digits are lost because they get shifted out but hex_digit_value() gets called for each of them and that's what matters for the timings.

The first contender is the OP's own solution:

unsigned hex_digit_value_v0 (char c)
{
   if (c == '0')  return  0;
   if (c == '1')  return  1;
   // ... 18 more not shown ...
   if (c == 'e')  return 14;
   if (c == 'f')  return 15;

   return NOT_A_DIGIT;
}

The second contender looks almost the same but it uses a switch statement instead of conditionals. If you think that it has little merit then you may be in for a little surprise when you look at the timings:

unsigned hex_digit_value_v1 (char c)
{
   switch (c)
   {
      case '0':  return  0;
      case '1':  return  1;
      // ... 18 more not shown ...
      case 'e':  return 14;
      case 'f':  return 15;
   }

   return NOT_A_DIGIT;
}

Last but not least, a reasonably straightforward solution where I lent helping hand to the compiler regarding the math (something we used to do a lot with older compilers):

unsigned hex_digit_value_v2 (char c)
{
   switch (c)
   {
      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
         return byte(c - '0');
      case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
         return byte(c - 'A' + 10);
      case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
         return byte(c - 'a' + 10);
   }

   return NOT_A_DIGIT;
}

Note, however, that this depends on three character ranges being contiguous and hence might not work with execution character sets that aren't based on ASCII and its descendants. The other three solutions are completely immune to such problems.

The test frame fills a big string with random hex digits (including upper case and lower case) or with a given number of 8-digit words separated by a blank. Timings are taken with the Windows high performance counter, which is essentially the CPU's time stamp counter divided by 256.

At this low resolution the fastest version needed only 3 ticks to go through a thousand digits, hence the big test data sizes. Using the TSC directly would have been better but then the code wouldn't have been portable across compilers.

In order to exclude to vagaries caused by caches and task switches, each test was repeated a number of times and the median of the measurements returned as result. This also means that the times that got printed refer to hot caches. A global sink variable was used to make the compiler think that the produced values were actually used somehow, to keep it from simply eliding the code altogether or reducing it to bumping the read pointer.

template<unsigned digit_value_vx (char c)>
double test_m (unsigned repeats = 10)
{
   std::vector<zrbj::Timer::Ticks> measurements;
   zrbj::Timer t;

   for (unsigned repeats_left = repeats; repeats_left--; )
   {
      char const *p = test_string.c_str(), *e = p + test_string.length();
      unsigned x = 0;
      t.Start();
      while (p < e)
      {
         x += extract_hex_unsigned<digit_value_vx>(&p);
         ++p;  // skip the character that caused the scanning to stop
      }
      t.Stop();
      g_sink += x;
      measurements.push_back(t.Elapsed());
   }

   std::sort(measurements.begin(), measurements.end());

   return t.ms(measurements[measurements.size() / 2]) * 1000;
}

So here's the timings in microseconds for three compilers; the test sizes are given as (number of strings) x (string length).

*** BC++ 7.10 (RX/Seattle) 64 *** CLANG 3.3.1 (35465.f352ad3.17344af)

1 x   1000:           9.9 v0         13.2 v1          4.2 v2          1.9 v3
1 x  10000:         135.4 v0        147.6 v1         87.9 v2         18.9 v3
1 x 100000:        1359.6 v0       1472.6 v1        964.4 v2        192.5 v3
   100 x 8:           7.4 v0         10.6 v1          3.5 v2          1.9 v3
  1000 x 8:         110.4 v0        114.2 v1         74.1 v2         18.9 v3
 10000 x 8:        1124.5 v0       1182.5 v1        825.2 v2        183.5 v3

*** VC++ 12.0 (x64) *** RTTI _CPPUNWIND 180031101.0

1 x   1000:           8.3 v0          5.5 v1          2.2 v2          0.6 v3
1 x  10000:         118.4 v0        122.9 v1         60.3 v2          5.5 v3
1 x 100000:        1214.6 v0       1250.9 v1        623.0 v2         51.3 v3
   100 x 8:           6.4 v0          3.5 v1          1.9 v2          0.6 v3
  1000 x 8:          96.6 v0        120.9 v1         48.1 v2          5.5 v3
 10000 x 8:         961.5 v0        995.5 v1        553.1 v2         56.5 v3

*** g++ 4.8.1 64 ***

1 x   1000:           3.2 v0          0.6 v1          1.3 v2          0.6 v3
1 x  10000:          88.9 v0          6.7 v1         45.9 v2          5.5 v3
1 x 100000:         940.3 v0         70.3 v1        484.8 v2         52.6 v3
   100 x 8:           2.2 v0          0.6 v1          1.3 v2          0.3 v3
  1000 x 8:          67.1 v0          5.8 v1         33.4 v2          3.2 v3
 10000 x 8:         723.5 v0         58.7 v1        390.4 v2         33.4 v3

As you can see, the version with the lookup table (v3) performs best with all three compilers. And gcc manages to make v1 (with the simple switch case '0': return 0; and so on) almost as fast as the lookup-based version. I was a bit disappointed with the other two for not doing the same, though. VC++ is normally quite decent at sorting out the messy stuff under the hood without a lot of hand-holding by the programmer, and I'd have expected more of Emborlandero's clang-based compiler, after the long years of waiting for it.

As regards code size, v3 wins hands-down as it compiles to at most two machine instructions and so there's no need to keep over-eager compilers from bloating the code with overly aggressive inlining.


Given an array, find all its elements that can become a leader I was successful in solving a challenge in codility, but my solution failed performance tests. How can I improve my solution?

  Challenge:

  Integers K, M and a non-empty array A consisting of N integers, not
  bigger than M, are given.

  The leader of the array is a value that occurs in more than half of
  the elements of the array, and the segment of the array is a sequence
  of consecutive elements of the array.

  You can modify A by choosing exactly one segment of length K and
  increasing by 1 every element within that segment.

  The goal is to find all of the numbers that may become a leader after
  performing exactly one array modification as described above.

  Write a function:

def solution(K, M, A)

  that, given integers K and M and an array A consisting of N integers,
  returns an array of all numbers that can become a leader, after
  increasing by 1 every element of exactly one segment of A of length K.
  The returned array should be sorted in ascending order, and if there
  is no number that can become a leader, you should return an empty
  array. Moreover, if there are multiple ways of choosing a segment to
  turn some number into a leader, then this particular number should
  appear in an output array only once.

  For example, given integers K = 3, M = 5 and the following array A:

A[0] = 2
A[1] = 1
A[2] = 3
A[3] = 1
A[4] = 2
A[5] = 2
A[6] = 3

  the function should return [2, 3]. If we choose segment A[1], A[2],
  A[3] then we get the following array A:

A[0] = 2
A[1] = 2
A[2] = 4
A[3] = 2
A[4] = 2
A[5] = 2
A[6] = 3

  and 2 is the leader of this array. If we choose A[3], A[4], A[5] then
  A will appear as follows:

A[0] = 2
A[1] = 1
A[2] = 3
A[3] = 2
A[4] = 3
A[5] = 3
A[6] = 3

  and 3 will be the leader.

  And, for example, given integers K = 4, M = 2 and the following array:

A[0] = 1
A[1] = 2
A[2] = 2
A[3] = 1
A[4] = 2

  the function should return [2, 3], because choosing a segment A[0],
  A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the
  leaders, respectively.

  Write an efficient algorithm for the following assumptions:

  N and M are integers within the range [1..100,000];
  K is an integer within the range [1..N];
  Each element of array A is an integer within the range [1..M].

My Solution

def modify(segment):
   return [e+1 for e in segment]

def dominant(A):
   d = dict()
   lenOfHalfA = int(len(A)/2)
   domList = []

   for i in A:
       if not i in d:
           d[i] = 1
       else:
           d[i] = d[i]+1

   for key, value in d.items():
       if value > lenOfHalfA:
           domList.append(key)

   return domList

def solution(K, M, A):
   # write your code in Python 3.6
   dominantList = []

   x = 0
   while x <= len(A) - K:
       modifiedA = A[:]
       modifiedA[x:K+x] = modify(A[x:K+x])
       dominantList += dominant(modifiedA)
       x += 1

   return list(set(dominantList))

def modify(segment):
   return [e+1 for e in segment]

This function is used only in one place, and is only one line. That often means it's better to just inline it:

modifiedA[x:K+x] = modify(A[x:K+x])
# Becomes:
modifiedA[x:K+x] = [e+1 for e in A[x:K+x]]

Use meaningful variable names. No matter what your challenge says, K, M and A are not meaningful variable names. It also seems like you're not doing anything with that M, so why do we even pass it to the function?

In your dominant() function, you look like you want to use collections.Counter. For practice with a language it can be good to check how to set it up yourself, but sometimes we have a good solution ready-made and available, and much better tested than any individual developer could ever do.

With Counter, you can make it work like this:

from collections import Counter

def dominant(string):
    count = Counter(string)
    return [key for key, value in count.items() if value == count.most_common(1)[0][1]]

Yeah, it's as simple as that. You could split it out over multiple lines, for clarity:

from collections import Counter

def dominant(string):
    count = Counter(string)
    dom_list = []
    max_occurred = count.most_common(1)[0][1]
    for key, value in count.items():
        if value >= max_occurred:
            dom_list.append(key)
    return dom_list


Redux reducer with a filter I'm wondering if my approach to creating a filtered array (filteredLaunches) from an array of data (launches) is an anti-pattern, or not? Is there a better way to go about it?

Here is the code:

const initialState = {
  launches: [],
  filteredLaunches: []
};

export default function(state = initialState, action) {

  switch (action.type) {

    case 'getLaunches':
      return Object.assign({}, state, {
        launches: action.launches
      });

    case 'filterLaunches':

      let filteredLaunches = [];

      for (let i = 0; i < state.launches.length; i++) {
        if (action.location === state.launches[i].location.countryCode)
          filteredLaunches.push(state.launches[i]);
      }

      return Object.assign({}, state, {
        filteredLaunches: filteredLaunches
      });

    default:
      return state;
  }
};

Well, you could use Array.filter to filter the launches.

...
case 'filterLaunches':
  return Object.assign({}, state, {
    filteredLaunches: state.launches.filter(function(launch) {
      return action.location === launch.location.countryCode
    })
  }
default:
 return state;

The other question is, why not filtering inside the Component directly?

Because your next problem will be, that each time you add launches, you will have to filter them and copy again, and again.

So to not create duplicates, it's better to set the filter in the reducer and perform the filtering inside the render

So:

export default function(state = initialState, action) {
  case 'SET_LAUNCHES':
    return {...state, launches: action.launches };
  case 'SET_FILTER':
    return {...state, filter: action.filter };
  default:
    return state;
}

export function filterLaunches(launches, filter = {location: 'ES'} ) {
  const filterKeys = Object.keys(filter);
  return launches.filter((launch) => {
    return filterKeys.reduce((acc, key) => acc && launch[key] === filter[key], true)
  });
}

// Then in the component
import { filterLaunches } from '../launchesStore';

const LaunchesList = ({launches, filter}) => (

    {filterLaunches(launches, filter).map((launch) => (

Launch: {launch.name}

    ))}

);

export default connect(LaunchesList);

It's good to keep the filterLaunches function next to the reducer, because this function is very related to this part of the state and if you change the format like from an array to a map-by-id you would have to change that function only in one place.


Caching XmlSerializer in AppDomain To work around the XmlSerializer memory leak thing I created this:

public static class XmlSerializerCache
{
    public static XmlSerializer GetXmlSerializer(Type type, XmlRootAttribute xmlRoot)
    {
        var cache = System.AppDomain.CurrentDomain;
        var key = String.Format(CultureInfo.InvariantCulture, "CachedXmlSerializer:{0}:{1}", type, xmlRoot.ElementName);

        var serializer = cache.GetData(key) as XmlSerializer;
        if (serializer == null)
        {
            serializer = new XmlSerializer(type, xmlRoot);
            cache.SetData(key, serializer);
        }
        return serializer;
    }
}

As far as I understood, the generated assemblies get unloaded as soon as the AppDomain gets unloaded. So I thought I can use the AppDomain Cache to cache my serializers.

Is this approach a good one? Or at least a "Leak-Safe" one?

According the work around section in the kb article mentioned in the blog entry, your solution looks correct.