Fetch and add data to MySql Here is my very first code which fetch data and add it to MySql. Please review my code and let me know if I'm on the right path. Is there anything I can improve?

postsData class = fetch and add data blog posts

categoriesData class = fetch and add data for categories of my blog. Ex: bmw, nissan, opel, ford, etc

connect.php

class dbh{

        private $host = "localhost";
        private $user = "root";
        private $pwd = "";
        private $dbname = "test_blog";

        public $conn;

        public function __construct()
        {
            $this->conn = $this->connect();
        }

        private function connect() {
            $dsn = 'mysql:host=' . $this->host . ';dbname=' . $this->dbname;
            $pdo = new PDO ($dsn, $this->user, $this->pwd);
            $pdo->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
            $pdo->setAttribute(PDO::ATTR_DEFAULT_FETCH_MODE, PDO::FETCH_ASSOC);
            $pdo->setAttribute(PDO::ATTR_EMULATE_PREPARES, false);
            return $pdo;

    }
}

func.class.php

  class postsData extends dbh{

    public function getPosts() {

        $sql = "SELECT * FROM posts_tbl";
        $stmt = $this->conn->prepare($sql);
        $stmt->execute();
        $result = $stmt->fetchAll((PDO::FETCH_OBJ));

        return $result;

    }

    public function addPost($filter_author, $filter_title, $filter_txt) {

        $sql = "INSERT INTO posts_tbl (post_author, post_title, post_txt) VALUES (?, ?, ?)";
        $stmt = $this->conn->prepare($sql);
        $stmt->execute([$filter_author, $filter_title, $filter_txt]);

    }

}

class categoriesData extends dbh{

    public function getCategories () {

        $sql = "SELECT * FROM categories_tbl";
        $stmt = $this->conn->prepare($sql);
        $stmt->execute();
        $result = $stmt->fetchAll((PDO::FETCH_OBJ));

        return $result;

    }

    public function adCategory ($filter_name, $filter_slug) {

        $sql = "INSERT INTO categories_tbl (category_name, category_slug) VALUES (?, ?)";
        $stmt = $this->conn->prepare($sql);
        $stmt->execute([$filter_name, $filter_slug]);

    }

}

    //test
    $post = new PostsData();
    $posts = $post->getPosts();

    foreach ($posts as $post) {
        echo $post->post_title . '<br>';
    }

Your code is mostly all right, especially given it's your first code attempt.

I would say there is only on critical flaw. A post or a category is not a database connection. Hence it should be never extended from it. It would be like if you extend a human from a car simply because a human is going to ride a car. A car is a service used by a human, that needs to be injected into a human object.

Besides, the way your code is written, it will create a new connection to the database in the  every class instance. Which will result in the "Too many connections"  error.

To sum it up:

a database connection has to be made only once. and then passed as a parameter to all your classes that need it.
your dbh class is rather useless. it does't add anything to original PDO. so you can get rid of it and simply create a plain PHP file with connection code and include it in your scripts
then you have to rewrite your data classes adding a constructor, providing either vanilla PDO or your own database connection class' instance as a parameter

something like this

class categoriesData {
    protected $conn;
    public function __construct($conn) {
        $this->conn = $conn;
    }
    ...

and then use it like this

require_once 'pdo.php';
$post = new PostsData($pdo);
$posts = $post->getPosts();

foreach ($posts as $post) {
    echo $post->post_title . '<br>';
}


Generating a unique key I am coming from a Ruby background and I am learning Python. This is a method I've created to generate a URL safe unique key:

import random;

def generate_unique_key():
    array = []
    for letter in range(97,123):
        array.append(chr(letter))
    for letter in range(65,91):
        array.append(chr(letter))
    for number in range(0,10):
        array.append(number)
    for char in ["-", ".", "_", "~"]:
        array.append(char)

    random_values = random.sample(array, 15)
    random_values = map(lambda x: str(x), random_values)
    return "".join(random_values)

print(generate_unique_key())

Coming from a Ruby background I was certainly puzzled first at not being able call join directly on my list, but having to call it from a string instance.

Also in Ruby I would have written something similar to random.sample(array, 15).join("") directly without having to convert them all to string, but this I believe this is how join() works.

While this works, how can this function be more Pythonic?

You can pass str to map rather than a lambda.
You can remove the need for map if you change your third loop to append str(number).
You can use string to remove the need for chr and int in the first three loops. By using:

string.ascii_letters:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
string.digits:
0123456789

You can combine all your loops into one string concatenation.
Don't use ; to end lines.
You can define array as a constant outside the function.
I recommend using Python 3, or changing print to be Python 3 compatible.

import random
import string

CHARACTERS = (
    string.ascii_letters
    + string.digits
    + '-._~'
)

def generate_unique_key():
    return ''.join(random.sample(CHARACTERS, 15))

print(generate_unique_key())

You can also use the secrets library (thanks @MathiasEttinger) which is a CSRNG version of random. It also contains the function secrets.token_urlsafe (thanks @Graipher) which generates a random string which is safe for use in URLs. Allowing:

def generate_unique_key(size=15):
    return secrets.token_urlsafe(size)[:size]


Simple parallel foreach loop code correctness I have both the regular for each loop and its equivalent paralleled version.  The loop simply iterates through a collection, looking for the rate key in a local db instance and then updating the topic code.

using (var db = new SomeEntities())
{
    foreach (var measure in measures)
    {
        var keytofind= measure.RateKey.ToString(CultureInfo.InvariantCulture);
        var firstOrDefault = db.RatesMappings.FirstOrDefault(r => r.RateKey == keytofind);
        if (firstOrDefault != null)
            measure.TopicCode = firstOrDefault.TopicCode;
    }

    Parallel.ForEach(measures, measure=>
    {
        var keytofind= rawDataMeasure.RateKey.ToString(CultureInfo.InvariantCulture);

        lock(measure)
        {
            var firstOrDefault = db.RatesMappings.FirstOrDefault(r => r.RateKey == keytofind);
            if (firstOrDefault != null)
                measure.TopicCode = firstOrDefault.TopicCode;
        }
    });
}

Is the paralleled code correct and has the lock been placed correctly?

No, when you use the lock like that, it's completely useless. Each lock would get its own identifier, so none of he locks would keep any other thread out. To make the lock work at all, you need to use the same identifier for all locks. Demonstration:

object sync = new Object();
var keytofind = rawDataMeasure.RateKey.ToString(CultureInfo.InvariantCulture);
Parallel.ForEach(measures, measure => {
  lock(sync) {
    var firstOrDefault = db.RatesMappings.FirstOrDefault(r => r.RateKey == keytofind);
    if (firstOrDefault != null) {
      measure.TopicCode = firstOrDefault.TopicCode;
    }
  }
});

However, if you need a lock around the code in a parallel loop, then the parallel loop is pointless. The reason that you use the parallel loop is that several threads can run at once, and the lock would prevent that.


Validating Javascript Model I'm looking to create a model in JavaScript. Here is an example of the code that I have so far:

// Person model
function Person(firstName, age) {
    // Check first name
    if (firstName) {
        if (typeof firstName === 'string') {
            this.firstName = firstName;
        }
        else throw new Error('The first name is not a string.');
    }
    else throw new Error('First name is a required field.');

    // Check age
    if (age) {
        if (typeof age === 'number') {
            if (age < 0) {
                throw new Error('The age provided is a negative.');
            }
            else {
                this.age = age;
            }
        }
        else throw new Error('The age provided is not a number.');
    }
    else throw new Error('Age is a required field.');
}

// Example usage
try {
    var joel = new Person('Joel', 30);
    console.log(joel);
}

catch(err) {
    console.log(err.message);
}

Is this an idiomatic approach to the solution? And if so is there a way in which I can improve it?

I prefer to create isValid() method instead of exceptions and getValidationErrors() to get array of all errors instead of one error message with exception.

var joel = new Person('Joel', 30);
if( ! joel.isValid() ) {
    console.log(joel.getValidationErrors());
}

Also you can create some validation function like

validate({
    name: {
        type: 'string'
    },
    age: {
        type: 'number',
        minValue: 0,
        maxValue: 150
    }
}, {
    name: firstName,
    age:  age
});

Which will return array of errors. If array length is 0 then validation passed.


Concurrent LRU cache using sychronizedMap() or ReadWriteLock Trying to implement a simple, thread-safe LRU cache that's meant for "read mostly" use.

Collections.sychronizedMap()

Clean, simple, not much else to say.

public class LRUConcurrentCache<K,V> {
   private final Map<K,V> cache;
   private final int maxEntries;

   public LRUConcurrentCache(
         int maxEntries
   ){
      this.maxEntries = maxEntries;
      this.cache = Collections.synchronizedMap(
         new LinkedHashMap<K,V>(this.maxEntries, 0.75F, true){
               private static final long serialVersionUID = -1236481390177598762L;
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
                  return size() > maxEntries;
               }
            });
   }
   public void put(K key, V value){
      cache.put(key, value);
   }
   public V get(K key){
      return cache.get(key);
   }

ReadWriteLock

Seems like overkill, and frankly, I believe get() should use writeLock(), not readLock() since LinkedHashMap.get() records access by manipulating entries.

public class LRUConcurrentCache<K,V> {
   private final Map<K,V> cache;
   private final int maxEntries;
   private final ReadWriteLock readWriteLock;
   private final Lock readLock;
   private final Lock writeLock;

   public LRUConcurrentCache(
         int maxEntries
   ){
      this.maxEntries = maxEntries;
      this.cache =
         new LinkedHashMap<K,V>(this.maxEntries, 0.75F, true){
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
                  return size() > maxEntries;
               }
            };
      this.readWriteLock = new ReentrantReadWriteLock(true);
      this.readLock = readWriteLock.readLock();
      this.writeLock = readWriteLock.writeLock();
   }
   public void put(K key, V value){
      writeLock.lock();
      try{
         cache.put(key, value);
      }finally{
         writeLock.unlock();
      }
   }
   public V get(K key){
      //should use writeLock.lock()
      readLock.lock();
      try{
         return cache.get(key);
      }finally{
         //should be writeLock()
         readLock.unlock();
      }
   }

Thoughts?

My experience with variants on the java.util.concurrent.locks.* classes suggests that their sweet spot in terms of performance is when the work to be done is relatively substantial compared to the lock overhead time. Remember, when you use Reentrant or ReadWrite locks, that there is a a call at both the beginning and end of the locked block.

As a consequence, I would advise against the ReadWriteLock system you have going. Apart from other things, it is not implemented correctly because, yes, multiple threads can be 'getting' values from the backing map, and they could each be modifying the access order. get(...) is not a read-only operation. It has side-effects.

Still, I don't like alternative of using Collections.synchronizedMap(...). This also has overheads, and can cause additional members in the call-stack as one synchronized method may call another, etc.

The most simple solution, and the one I recommend, would be to use plain-old-synchronization:

   private final Map<K,V> cache;

   public LRUConcurrentCache(final int maxEntries) {
      this.cache = new LinkedHashMap<K,V>(maxEntries, 0.75F, true) {
               private static final long serialVersionUID = -1236481390177598762L;
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
                  return size() > maxEntries;
               }
            };
   }

   public void put(K key, V value) {
       synchronized(cache) {
          cache.put(key, value);
       }
   }
   public V get(K key) {
       synchronized(cache) {
           return cache.get(key);
       }
   }

Note, while going through the code, I made the following additional changes:

I made the input parameter to the constructor maxEntries a final value. This means you can reference it from the constructor and removeEldestEntry methods of the LinkedHashMap without having to re-declare it on the instance
Your indentation is all off.... 3-space indents? That's unusual.
You have a lot of trailing white-space in your code. You do a block-based select instead of text-based?
Your whitespace handling before/after braces and operators is inconsistent.

I get the impression you are using vim or some other console editor to manage your code. You should consider the gg=G shortcut in vim to re-indent all your code consistently.


Call URL x times where x is in the JSON response after the first call I have to make an HTTP POST request by passing header and body. In the body, I need to provide a pageNumber before posting data so I am starting with "1" initially. After that I will post data and I will get a JSON response back as shown below.

{
    "response": {
        "pageNumber": 1,
        "entries": 200,
        "numberOfPages": 3
    },
    "list": [
        {
            // some stuff here
        }
    ],
    "total": 1000
}

Now in the above response numberOfPages are 3 so I need to make a total of three calls to the same URL. Since we already made 1 call I will make 2 more calls with pageNumber "2" and "3" in the body.

The logic is like this but problem here is that I don't know what is the value for numberOfPages and I get to know this value after the first call with pageNumber 1.

for(int i=1; i<=numberOfPages; i++) {
    // call getBody by passing corresponding pageNumber
    // post data with header and body

}

Below is my working code. I just need to call the same URL until numberOfPages times by just changing the body. For each call, it should be made with the corresponding pageNumber.

private void collect() {
  String endpoint = "url_endpoint";
  try {
    final URI uri = URI.create(endpoint);
    int number = 1;
    while (true) {
      HttpEntity<String> requestEntity = new HttpEntity<String>(getBody(number), getHeader());
      ResponseEntity<Stuff> responseEntity =
          HttpClient.getInstance().getClient()
              .exchange(uri, HttpMethod.POST, requestEntity, Stuff.class);
      Stuff response = responseEntity.getBody();
      // do stuff with response here.
      int expectedNumber = (int) response.getPaginationResponse().getTotalPages();
      if (number == expectedNumber || expectedNumber == 0) {
        break;
      }
      number++;
    }
  } catch (Exception ex) {
    ex.printStackTrace();
  }
}

private String getBody(final int number) {
  Input input = new Input(entries, number, 0);
  Body body = new Body("Stuff", input);
  return gson.toJson(body);
}

Is this the right way to do it or is there any better and efficient way?

Instead of a for loop, consider a do {} while (pageCount <= numberOfPages)
loop and use an increment operator inside the loop. For this to work though both pageCount and numberOfPages need to have scoping outside of the loop, ie instantiated before the do{ } statement.

do{ } while () loops are guaranteed to run once, then perform the test in the while () to check if they continue. while( ){ } loops perform the check, then run until a value of false is found.

    int number = 1;
    int expectedNumber;
    do {
      HttpEntity<String> requestEntity = new HttpEntity<String>(getBody(number), getHeader());
      ResponseEntity<Stuff> responseEntity =
          HttpClient.getInstance().getClient()
              .exchange(uri, HttpMethod.POST, requestEntity, Stuff.class);
      Stuff response = responseEntity.getBody();
      // do stuff with response here.
      expectedNumber = (int) response.getPaginationResponse().getTotalPages();
      number++;
    } while (number <= expectedNumber && expectedNumber > 0);


FASTA-to-tsv conversion script I worked on a script that takes as input a multi-sequence .fasta file and outputs the number of each aminoacid/sequence in a .tsv format.
This is how a .fasta file looks:
>sp|P21515|ACPH_ECOLI Acyl carrier protein phosphodiesterase OS=Escherichia coli (strain K12) OX=83333 GN=acpH PE=1 SV=2
MNFLAHLHLAHLAESSLSGNLLADFVRGNPEESFPPDVVAGIHMHRRIDVLTDNLPEVREAREWFRSETRRVAPITLDVMWDHFLSRHWSQLSPDFPLQEFVCYAREQVMTILPDSPPRFINLNNYLWSEQWLVRYRDMDFIQNVLNGMASRRPRLDALRDSWYDLDAHYDALETRFWQFYPRMMAQASRKAL

I know there are libraries which do the same thing, however, I had to write this script as a homework, without the help of BioPython or other similar libraries.
My question is: how can I make this code more efficient?
import sys
import os

def readFasta( path ):

    seq = { }
    aCount = { }
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWYZX*-"

    for fileName in path:

        with open( fileName ) as file:
            fastaLine = file.readlines( )

            # sequence storage

            for line in fastaLine:
                if line[ 0 ] == ">" :
                    headerTitle = line.split( "|" )[ 1 ]
                    seq[ headerTitle ] = ""
                else:
                    seq[ headerTitle ] += line.strip( )

            # aminoacid count

            for id in seq:
                aCount[ id ] = { }
                for sequence in seq[ id ]:
                    if sequence not in alphabet:
                        print( "Check your sequence! Character: " + str(sequence) + " from sequence: " + id )
                    for letter in alphabet:
                        aCount[ id ][ letter ] = 0

            # count aminoacid occurence/sequence

            for name in seq:
                for char in seq[ name ]:
                    if char in aCount[ name ]:
                        aCount[ name ][ char ] += 1

    # write to .csv file

    outFile = open( "output.csv" , "w" )

    outFile.write( "Name" + '\t' )

    header = ""
    for letter in alphabet:
        header += letter + '\t'

    outFile.write( header + "Total" )
    outFile.write( '\n' )

    for name in aCount:
        entry = ""
        counter = 0
        for letter in aCount[ name ]:
            entry += str(aCount[ name ][ letter ]).strip( ) + '\t'
            counter += aCount[ name ][ letter ]
        outFile.write( name + '\t' + entry + '\t' + str( counter ) )
        outFile.write( '\n' )

# files to list

entries = os.listdir( path )

# filter for .fasta/.fa files

new_list = [ ]
for entry in entries:
    if ".fasta" in entry:
        new_list.append( entry )
    elif ".fa" in entry:
        new_list.append( entry )

# execute func

readFasta( new_list )

Welcome to Code Review!
I'll add to the other answer from Reinderien.
PEP-8
In python, it is common (and recommended) to follow the PEP-8 style guide for writing clean, maintainable and consistent code.
Functions and variables should be named in a lower_snake_case, classes as UpperCamelCase, and constants as UPPER_SNAKE_CASE.
No unnecessary whitespaces are needed around the arguments when defining or calling a function. This applies for referring array/list elements as well.
Functions
Split your code into individual smaller functions, doing singular tasks. A few examples would be, reading/parsing the fasta files, validating sequence of gene, counting occurrences (try collections.Counter package to do this).
CSV/TSV
Python comes with inbuilt package csv which can also be used to write tsv files. You do not need to modify/write each line yourself.
Glob searching for files
Python 3+ has another inbuilt package pathlib, which supports getting all files using a glob pattern. You would again, not need to manually (metaphorically) aggregate all the files with .fa or .fasta extensions.
if __name__ block
For scripts, it is a good practice to put your executable feature inside the if __name__ == "__main__" clause.


Rails validating with condition block Rails AR. validate one field, with 4 validators & 2 condition block

validates :inn,
          presence: { if: -> { user.is_a?(Client) } },
          inn: { if: -> { user.is_a?(Client) } },
          uniqueness: { if: -> { user.is_a?(Client) } },
          absence: { if: -> { user.is_a?(Department) } }

Could I have some tips on refactoring this?

You can try something like this (obviously names can be shorter):

if_user_is_a = ->(klass) { { if: -> { user.is_a?(klass) } } }
validates :inn, presence: if_user_is_a[Client], ..., absence: if_user_is_a[Department]

or

if_user_is_a = ->(klass) { { if: -> { user.is_a?(klass) } } }
if_user_is_a_client = if_user_is_a[Client]
...
validates :inn, presence: if_user_is_a_client, ...


Associating a name with each bit in a bitmask I have the following code:

dic = {}
bin_rep = [1 if digit == '1' else 0 for digit in bin(n)[2:]]
if len(bin_rep) < size_bin:
    bin_rep += [0] * (size_bin - len(bin_rep))
# turn this into dictionnary - might all be done better?
for i in range(0, size_bin):
    dic[self.p.get_agents()[i]] = bin_rep[i]
return dic

Essentially, I'm taking an number n, turning it into a list (its binary representation, potentially padded with 0 up to size_bin), say:

[0 1 1 1 1 0 0 0 0 0 0]

From that padded list, I create a dictionary, where key==agent name and value==1/0, say:

{'a1':0, 'a2':1 ... 'an':0}

(The array as a whole corresponds to a team, the 0/1 represents the inclusion of an agent into the team. So each team corresponds to a binary array which can be represented as an int.)

The code works, using list and dictionary comprehension. However, would someone have a cleaner/smarter way to perform this? It's good if it's optimal, though not crucial, and would like to keep it readable.

I absolutely need to have the ultimate result into a dictionary because other parts of the code use that representation.

EDIT: using python 3.6

Suggestions

enumerate is built-in function useful here
dict comprehensions can be used to create dictionaries from arbitrary key and value expressions
imho '{:b}'.format(n) is easier to read than bin(n)[2:]
in additional you may use OrderedDict if you often iterate over agents 1, 2, 3, 4, ...

Final code (n = 10, size_bin =  6)

{'a{}'.format(k): int(v) for k, v in enumerate('{:b}'.format(10).ljust(6, '0'), start=1)}

and with full utilize format syntax

{'a{}'.format(k): int(v) for k, v in enumerate('{:<0{}b}'.format(10, 6), start=1)}


Scraping SEDE query results with caching I use this script to scrape the results of a SEDE page and return as a BeautifulSoup object.

A small twist is that if I don't use a SEDE query manually in the browser for a few days, then non-interactive downloads get empty results. (I suspect there is a robot test there.)

Rather than fixing the robot test issue, my workaround is to cache successfully downloaded pages, and use the cache when downloading is not working well.

import logging
import os

import requests
from bs4 import BeautifulSoup

BASE_DIR = os.path.dirname(__file__)
CACHE_DIR = os.path.join(BASE_DIR, '.cache')

def fetch_sede_soup(label, url):
    def is_valid(soup):
        for script in soup.findAll('script'):
            if 'resultSets' in script.text:
                return True
        return False

    if not os.path.isdir(CACHE_DIR):
        os.mkdir(CACHE_DIR)

    logging.info('fetching {} as {}'.format(label, url))
    html = requests.get(url).text
    soup = BeautifulSoup(html)

    cache_path = os.path.join(CACHE_DIR, '{}.html'.format(label))
    debug_cache_path = os.path.join(CACHE_DIR, '{}-debug.html'.format(label))

    if is_valid(soup):
        logging.info('updating cache')
        with open(cache_path, 'w') as fh:
            fh.write(html)
        return soup

    with open(debug_cache_path, 'w') as fh:
        fh.write(html)

    logging.warning('result not valid')
    if os.path.exists(cache_path):
        logging.info('using previous cache')
        with open(cache_path) as fh:
            return BeautifulSoup(fh)

Can this be written better?

In case it helps, here are some sample output files:

sede-output.html - a successful download.
sede-output-debug.html - a "failed" download (empty results).

It shows that you've written code before, so style wise there is not much to comment upon. What I would like to comment upon is a few points on code structure:

Single responsibility concern – Your function is name fetch_sede_soup() and all actions are related to this. However it still creates the CACHE_DIR if needed, write output files, verifies validity in inner function. This could be separated into more functions, although it is not extremely large and hard to get the overview of.

One point I would at least add a new function is related to the return soup near the middle. Code after this seems to be error handling, but it is somewhat hidden by the return and as such it is not very clear. If you moved the remaining part into a function you would see a return soup followed by a else: clause calling the error handling.
Add comments and docstrings – As a side effect of the different aspects your function handles, I would at least add more comments within the code. This could justify keeping more within the larger function, whilst still maintaining readability
Add error handling around mkdir – Especially around external os calls, like mkdir, I would add try ... except code to handle potential error situations. This code related to creating the CACHE_DIR could possibly be done before this method is called as part of initialization.

But in general, nice, clean code, but a little thin on documentation and error handling of os-operations.


Function composition in C++ My aim was to create a function which behaves like the operator . in Haskell.

Here is what I made:

template <typename F>
auto compose(F&& f)
{
    return [a = std::move(f)](auto&&... args){
        return a(std::move(args)...);
    };
}

template <typename F1, typename F2, typename... Fs>
auto compose(F1&& f1, F2&& f2, Fs&&... fs)
{
    return compose(
        [first = std::move(f1), second = std::move(f2)]
        (auto&&... args){
            return second(first(std::move(args)...));
        },
        std::move(fs)...
    );
}

Possible usage:

int main()
{
const auto f = compose([](const auto a, const auto b){return a + b;},
                       [](const auto n){return n * n;},
                       [](const auto n){return n + 2;});
std::cout << f(3, 2) << std::endl;
// should output 27 ( (3 + 2) * (3 + 2) + 2 )
}

The full source with a few more examples may be found here.

I'm not sure whether to use std::move or std::forward. Which one is better? Any other suggestions?

You probably do want std::forward here. You're using forwarding references with your templated && types, which means that they might actually be lvalues which the rest of the program expects to remain valid. std::move is basicall a promise that says "The owner is done with this object; feel free to plunder it". Obviously that's dangerous if it's false! std::forward, by contrast, will intelligently say whether something is free to plunder, based on whether it was free for plundering when passed as a parameter in the first place.

One other thing that I would suggest might be helpful is adding some sort of error detection. It would take a bit of work, but stuffing compose with a few well placed static_assert lines or similar would make a world of difference when trying to get something to build which has a few layers of composition. I'm thinking you could construct something helpful with is_invocable although that would require c++17.


Sublime Text 2 R Build System (source file, send selection to interactive session) The following is the description of the R build system I am using (very happy) with Sublime Text 2 on linux (Crunchbang). With it, I am able to:

to source the current file.R to an interactive R session;
to send the current selection to an interactive R session (supports multi selection);
to output plots and *.Rout files (non-interactive);

xsel, xdotool, terminator (or some other terminal that supports custom titles) and a bash script (see below) are requisites. Please, attention for the locations of each file.

The open_and_run_r.sh script is the object of revision (see its commented lines for details). But feel free to give your considerations about the whole picture.

Build File:

  .config/sublime-text-2/Packages/User/r.sublime-build

{       // source( $file ) into interactive session
        "shell": true,
        "cmd":
        [   "echo 'source(\"'$file'\")' | xsel -i -b; if xdotool search --name 'Running R' windowactivate --sync; then xdotool key --window 0 ctrl+shift+v; else open_and_run_r.sh; fi; xsel -c -b"
        ],

    "selector": "source.r",

    "variants":
    [
        {   // send current selection of $file to interactive session; supports ST2 multi-selection as well :)
            "name":     "r_send_selection",
            "shell":    true,
            "cmd":
            [   "xdotool getactivewindow key ctrl+c; if xdotool search --name \"Running R\" windowactivate --sync; then xdotool key --window 0 ctrl+shift+v Return; fi"
            ]
        },

        {   // generate custom output.Rout file (not the output.Rout from R CMD BATCH), non-interactive
            "name":     "r_output",
            "cmd":

            [   "/usr/bin/R --quiet --slave < $file > output.Rout"
            ]
        }
    ]
}

Lets give a proper formatting to the bash commands:

# source file, note:
   # escaped \" for JSON compatibility;
   # $file is ST2 global variable;
   # 'source()' is an R command
echo 'source(\"'$file'\")' | xsel -i -b;
if xdotool search --name 'Running R' windowactivate --sync;
    then xdotool key --window 0 ctrl+shift+v;
else open_and_run_r.sh;
fi;
xsel -c -b

# send selection
xdotool getactivewindow key ctrl+c;
if xdotool search --name \"Running R\" windowactivate --sync;
    then xdotool key --window 0 ctrl+shift+v Return;
fi

Finally the open_and_run_r.sh script (run as program enabled).

  ~/bin/open_and_run_r.sh

#!/bin/sh
echo 'Initializing Terminator...'
terminator --title "Running R" --command='R' &

# in this workaround
# I could not find a better way to properly
# catch the terminator ending,
# after it receives the 'Running R' name.

a=0

while [ $a = 0 ]; do
    if xdotool search --name 'Running R' windowactivate --sync;
        then a=1;
        xdotool key --window 0 ctrl+shift+v;
        echo 'Initialized.'
    fi;
    sleep 2; # decreasing the value increases asynchrony behavior.
done

Keymap file, for keyboard shortcuts.

  .config/sublime-text-2/Packages/User/Default (Linux).sublime-keymap

[

// R Build / [ctrl+b] see r.sublime-build/source current $file into interactive R

// R build / send current selection to interactive R
    {"keys": ["super+'"], "command": "build", "args": {"variant": "r_send_selection"} },

// R build / generate output.Rout and plots files from, non-interactive
    {"keys": ["ctrl+shift+b"], "command": "build", "args": {"variant": "r_output"} }

]

In the main loop of the script,
you don't need the $a variable.
You can use an infinite loop,
and break out of it when the if condition becomes true.
You also don't need the semicolons at the end of the lines.

The script can be simplified to:

while :; do
    if xdotool search --name 'Running R' windowactivate --sync; then
        xdotool key --window 0 ctrl+shift+v
        echo 'Initialized.'
        break
    fi
    sleep 2  # decreasing the value increases asynchrony behavior.
done

As for this comment:

# in this workaround
# I could not find a better way to properly
# catch the terminator ending,
# after it receives the 'Running R' name.

Unfortunately I don't know a better way either.


Quality of custom slider Should I be using this more, instead of slider? Am I making any serious no-no's here, and is there a better design I should implement? I'm up for any pointers :)

slider = {
                selector : '#slider',
                init : function() {
                        $('#slider').hover(function(e){
                            slider.toggle();
                        });

                    $(document).bind('click', function(e){
                        slider.lock.unlock();
                        slider.state.collapse();
                    });

                    $('#slider').bind('click', function(e){
                        e.stopPropagation();
                        slider.lock.lock();
                    })
                },
                toggle : function() {
                    if (!this.lock.isLocked) {
                        this.state.toggle();
                    }
                },
                lock : {
                    isLocked   : false,
                    lock : function() {
                        this.isLocked = true;
                    },
                    unlock : function() {
                        this.isLocked = false;
                    }
                },
                state : {
                    isExtended : false,
                    toggle : function() {
                        if (this.isExtended===true) {
                            this.collapse();
                        } else {
                            this.extend();
                        }
                    },
                    extend : function() {
                        this.isExtended = true;
                        $('#slider').stop().animate({'left':'-5px'}, 'slow');
                    },
                    collapse : function() {
                        this.isExtended = false;
                        $('#slider').stop().animate({'left':'-210px'}, 'slow');
                    }
                }
            };

You never use slider.selector, so what's the point?
jQuery instances should be "cached", otherwise you are creating new jQuery object each time you call $() function.
This code permits only one slider per page. What if you need more? Will you copy-paste the whole thing?
This is not configurable at all. You have to change the objects source, just to change the way animation works.
jQuery is not really necessary here. You actually need it only for animations, which is not jQuery's strong point.
Slider object ends up in global scope.


Java generic sorting class I'm writing a class that will sort multiple types {arrays, arraylist, linkedlist} but I see there's a lot of code duplication. For instance, method to swap in list, and in arrays, method to sort list, and arrays etc. While I know code duplication is a bad practise, I am wondering if there's a better way to avoid writing duplicate code.

package utils;

import java.util.Arrays;
import java.util.List;

public class Sort {
    private static <E extends Comparable<E>> void swap(List<E> sequence,
                                                       int positionOne, int positionTwo) {
        E temp = sequence.get(positionOne);
        sequence.set(positionOne, sequence.get(positionTwo));
        sequence.set(positionTwo, temp);
    }

    private static <E extends Comparable<E>> void swap(E[] sequence,
                                                       int positionOne, int positionTwo) {
        E temp = sequence[positionOne];
        sequence[positionOne] = sequence[positionTwo];
        sequence[positionTwo] = temp;
    }

    public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
        for (int i = 0; i < sequence.size(); i++) {
            int minPosition = -1;
            E minValue = sequence.get(i);
            for (int j = i + 1; j < sequence.size(); j++) {
                E secondPosition = sequence.get(j);
                if (minValue.compareTo(secondPosition) > 0) {
                    minPosition = j;
                    minValue = sequence.get(j);
                }
            }
            if (minPosition >= 0) {
                swap(sequence, i, minPosition);
            }
        }
        return sequence;
    }

    public static <E extends Comparable<E>> E[] selectionSort(E[] sequence) {
        for (int i = 0; i < sequence.length; i++) {
            int minPosition = -1;
            E minValue = sequence[i];
            for (int j = i + 1; j < sequence.length; j++) {
                E secondPosition = sequence[j];
                if (minValue.compareTo(secondPosition) > 0) {
                    minPosition = j;
                    minValue = sequence[j];
                }
            }
            if (minPosition >= 0) {
                swap(sequence, i, minPosition);
            }
        }
        return sequence;
    }

    public static void main(String[] args) {
        Integer[] integers = {1, 6, 88, 7, 44, 3, 11};
        System.out.println("Before: " + Arrays.toString(integers));
        Sort.selectionSort(integers);
        System.out.println("Later: " + Arrays.toString(integers));
    }
}

Thanks for sharing your code.

Your example is a typical case of duplicated code you have two places where the code looks very similar (and is logically the same) but has some minor differences.

On the other hand your example is a special case because we can simply convert the input of one of the duplicated parts to the form of the other one:

public class Sort {
    private static <E extends Comparable<E>> void swap(List<E> sequence,
                                                       int positionOne, int positionTwo) {
        E temp = sequence.get(positionOne);
        sequence.set(positionOne, sequence.get(positionTwo));
        sequence.set(positionTwo, temp);
    }
    public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
        for (int i = 0; i < sequence.size(); i++) {
            int minPosition = -1;
            E minValue = sequence.get(i);
            for (int j = i + 1; j < sequence.size(); j++) {
                E secondPosition = sequence.get(j);
                if (minValue.compareTo(secondPosition) > 0) {
                    minPosition = j;
                    minValue = sequence.get(j);
                }
            }
            if (minPosition >= 0) {
                swap(sequence, i, minPosition);
            }
        }
        return sequence;
    }

    public static <E extends Comparable<E>> E[] selectionSort(E[] sequence) {
        return selectionSort(new ArrayList(Arrays.asList(sequence))).toArray(new E[sequence.length]);
    }

    public static void main(String[] args) {
        Integer[] integers = {1, 6, 88, 7, 44, 3, 11};
        System.out.println("Before: " + Arrays.toString(integers));
        Sort.selectionSort(integers);
        System.out.println("Later: " + Arrays.toString(integers));
    }
}

However...

The more general approach is to refactor one (or both) of the similar  code fragments to make them (partially) the same.

In your example the difference at both places is the way the elements are addressed and accessed. We need to introduce an indirection, to provide an input type independent way to do this.

In this example an interface is the way to go:

interface MySequence<E extends Comparable<E>>{
  E getElementAt(int index);
  void setElementAt(int index, E element);
  int elementCount();
}

You could "reuse" method names from one of the duplicated parts but I intentionally use different names to make my point...

Now in each of the methods we first create an anonymous inner class from this interface. Lets start with the two swap() methods:

private static <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    E temp = sequence.get(positionOne);
    sequence.set(positionOne, sequence.get(positionTwo));
    sequence.set(positionTwo, temp);
}

private static <E extends Comparable<E>> void swap(E[] sequence, int positionOne, int positionTwo) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence[index];
        }

        public void setElementAt(int index, E element) {
            sequence[index] = element;
        }

        public int elementCount() {
            return sequence.length;
        }
    };
    E temp = sequence[positionOne];
    sequence[positionOne] = sequence[positionTwo];
    sequence[positionTwo] = temp;
}

Then we replace any following occurrence of sequence in that method with mySequence:

  private static <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    E temp = mySequence.getElementAt(positionOne);
    mySequence.setElementAt(positionOne, mySequence.getElementAt(positionTwo));
    mySequence.setElementAt(positionTwo, temp);
}

You hopefully can do this for the other version of swap() yourself...

Now both swap() methods had a differing part (the anonymous inner class of type MySequence) and a equal part (the thee following lines).

Actually we have more code then before, but we are going to reduce it in a few minutes...

Select the three identical lines in one of the methods and
apply your IDEs automated refactoring extract method to create a new version of swap():

private static <E extends Comparable<E>> void swap(MySequence<E> mySequence, int positionOne, int positionTwo) {
    E temp = mySequence.getElementAt(positionOne);
    mySequence.setElementAt(positionOne, mySequence.getElementAt(positionTwo));
    mySequence.setElementAt(positionTwo, temp);
}

 private static  <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    swap(mySequence, positionOne, positionTwo);
}

The replace the three  duplicated lines in the other original swap() method with a call to the new one too.

private  static <E extends Comparable<E>> void swap(E[] sequence, int positionOne, int positionTwo) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence[index];
        }

        public void setElementAt(int index, E element) {
            sequence[index] = element;
        }

        public int elementCount() {
            return sequence.length;
        }
    };
    swap(mySequence, positionOne, positionTwo);
}

Next step is to remove the old versions of swap(). click on the name if one of these and invoke your IDEs automated refactoring inline method. Repeat this with the otehr old version too.

Now your selectionSort() methods look like this:

public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
    for (int i = 0; i < sequence.size(); i++) {
        int minPosition = -1;
        E minValue = sequence.get(i);
        for (int j = i + 1; j < sequence.size(); j++) {
            E secondPosition = sequence.get(j);
            if (minValue.compareTo(secondPosition) > 0) {
                minPosition = j;
                minValue = sequence.get(j);
            }
        }
        if (minPosition >= 0) {
            MySequence<E> mySequence = new MySequence<E>() {
                public E getElementAt(int index) {
                    return sequence.get(index);
                }

                public void setElementAt(int index, E element) {
                    sequence.set(index, element);
                }

                public int elementCount() {
                    return sequence.size();
                }
            };
            swap(mySequence, i, minPosition);
        }
    }
    return sequence;
}

Here we move the instantiation of MySequence to the top of each method:

public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    for (int i = 0; i < sequence.size(); i++) {
        int minPosition = -1;
        E minValue = sequence.get(i);
        for (int j = i + 1; j < sequence.size(); j++) {
            E secondPosition = sequence.get(j);
            if (minValue.compareTo(secondPosition) > 0) {
                minPosition = j;
                minValue = sequence.get(j);
            }
        }
        if (minPosition >= 0) {
            swap(mySequence, i, minPosition);
        }
    }
    return sequence;
}

And again we change any further occurence of sequence within each method to mySequence:

public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    for (int i = 0; i < mySequence.elementCount(); i++) {
        int minPosition = -1;
        E minValue = mySequence.getElementAt(i);
        for (int j = i + 1; j < mySequence.elementCount(); j++) {
            E secondPosition = mySequence.getElementAt(i);
            if (minValue.compareTo(secondPosition) > 0) {
                minPosition = j;
                minValue = mySequence.getElementAt(i);
            }
        }
        if (minPosition >= 0) {
            swap(mySequence, i, minPosition);
        }
    }
    return sequence;
}

No we apply the same technique as with the swap() method. Move the identical lines of both methods to a new method using your IDEs  automated refactoring extract method:

private static <E extends Comparable<E>> void selectionSort(MySequence<E> mySequence) {
    for (int i = 0; i < mySequence.elementCount(); i++) {
        int minPosition = -1;
        E minValue = mySequence.getElementAt(i);
        for (int j = i + 1; j < mySequence.elementCount(); j++) {
            E secondPosition = mySequence.getElementAt(i);
            if (minValue.compareTo(secondPosition) > 0) {
                minPosition = j;
                minValue = mySequence.getElementAt(i);
            }
        }
        if (minPosition >= 0) {
            swap(mySequence, i, minPosition);
        }
    }
}

public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
    MySequence<E> mySequence = new MySequence<E>() {
        public E getElementAt(int index) {
            return sequence.get(index);
        }

        public void setElementAt(int index, E element) {
            sequence.set(index, element);
        }

        public int elementCount() {
            return sequence.size();
        }
    };
    selectionSort(mySequence);
    return sequence; // ATTENTION! this line is NOT identical because of the type of sequence...
}

And replace the extracted part in the other original selectionSort() method too.

Thats it!

The code might even be shorter if we would use tree functional interfaces and lambda expression at the cost of more parameters at the new methods instead of one interface. But I doubt that it would increase readability and it definitely would add possibilities for errors.

The important insight is that we did not change the logic of the program since all changes we did are safe in that respect.

Nevertheless you should always have a set of automated UnitTest to guard your refactorings...


A Sub-string Extractor with Specific Keywords Parameter Implementation in C# I am trying to implement a sub-string extractor with "start keyword" and "end keyword" and the extracted result is from (but excluded) the given start keyword to (but excluded) end keyword. For example:

Input String
Start Keyword
End Keyword
Output

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
""(empty string)
""(empty string)
"C# was developed around 2000 by Microsoft as part of its .NET initiative"

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
""(empty string)
".NET"
"C# was developed around 2000 by Microsoft as part of its"

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
"C#"
""(empty string)
"was developed around 2000 by Microsoft as part of its .NET initiative"

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
"C#"
".NET"
"was developed around 2000 by Microsoft as part of its"

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
".NET"
""(empty string)
"initiative"

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
""(empty string)
"C#"
""(empty string)

"C# was developed around 2000 by Microsoft as part of its .NET initiative"
".NET"
"C#"
""(empty string)

The experimental implementation
The experimental implementation is as below.
private static string GetTargetString(string stringInput, string startKeywordInput, string endKeywordInput)
{
    int startIndex;
    if (String.IsNullOrEmpty(startKeywordInput))
    {
        startIndex = 0;
    }
    else
    {
        if (stringInput.IndexOf(startKeywordInput) >= 0)
        {
            startIndex = stringInput.IndexOf(startKeywordInput) + startKeywordInput.Length;
        }
        else
        {
            return "";
        }

    }

    int endIndex;
    if (String.IsNullOrEmpty(endKeywordInput))
    {
        endIndex = stringInput.Length;
    }
    else
    {
        if (stringInput.IndexOf(endKeywordInput) > startIndex)
        {
            endIndex = stringInput.IndexOf(endKeywordInput);
        }
        else
        {
            return "";
        }
    }

    //    Check startIndex and endIndex
    if (startIndex < 0 || endIndex < 0 || startIndex >= endIndex)
    {
        return "";
    }

    if (endIndex.Equals(0).Equals(true))
    {
        endIndex = stringInput.Length;
    }
    int TargetStringLength = endIndex - startIndex;
    return stringInput.Substring(startIndex, TargetStringLength).Trim();
}

Test cases
string test_string1 = "C# was developed around 2000 by Microsoft as part of its .NET initiative";

Console.WriteLine(GetTargetString(test_string1, "", ""));
Console.WriteLine(GetTargetString(test_string1, "", ".NET"));
Console.WriteLine(GetTargetString(test_string1, "C#", ""));
Console.WriteLine(GetTargetString(test_string1, "C#", ".NET"));
Console.WriteLine(GetTargetString(test_string1, ".NET", ""));
Console.WriteLine(GetTargetString(test_string1, "", "C#"));
Console.WriteLine(GetTargetString(test_string1, ".NET", "C#"));

The output of the above test cases.
C# was developed around 2000 by Microsoft as part of its .NET initiative
C# was developed around 2000 by Microsoft as part of its
was developed around 2000 by Microsoft as part of its .NET initiative
was developed around 2000 by Microsoft as part of its
initiative

If there is any possible improvement, please let me know.

I tend to have the "error handling" code at the beginning of the method, which usually makes the rest of the method more simple.
private static string GetTargetString(string input, string startKeyword, string endKeyword, StringComparison comparer)
{
    if (!string.IsNullOrEmpty(startKeyword) && input.IndexOf(startKeyword, comparer) < 0) return "";
    if (!string.IsNullOrEmpty(endKeyword) && input.IndexOf(endKeyword, comparer) < 0) return "";

    var startIndex = string.IsNullOrEmpty(startKeyword)
        ? 0
        : input.IndexOf(startKeyword, comparer) + startKeyword.Length;

    var endIndex = string.IsNullOrEmpty(endKeyword)
        ? input.Length
        : input.IndexOf(endKeyword, comparer);

    if (startIndex < 0 || endIndex < 0 || startIndex >= endIndex) return "";

    return input.Substring(startIndex, endIndex - startIndex).Trim();
}


C++ thread safe queue implementation I'm using this class for producer-consumer setup in C++:

#pragma once

#include <queue>
#include <mutex>
#include <condition_variable>
#include <memory>
#include <atomic>

template <typename T> class SafeQueue
{
public:
    SafeQueue() :
    _shutdown(false)
    {

    }

    void Enqueue(T item)
    {
        std::unique_lock<std::mutex> lock(_queue_mutex);
        bool was_empty = _queue.empty();
        _queue.push(std::move(item));
        lock.unlock();

        if (was_empty)
            _condition_variable.notify_one();
    }

    bool Dequeue(T& item)
    {
        std::unique_lock<std::mutex> lock(_queue_mutex);

        while (!_shutdown && _queue.empty())
            _condition_variable.wait(lock);

        if(!_shutdown)
        {
            item = std::move(_queue.front());
            _queue.pop();

            return true;
        }

        return false;
    }

    bool IsEmpty()
    {
        std::lock_guard<std::mutex> lock(_queue_mutex);
        return _queue.empty();
    }

    void Shutdown()
    {
        _shutdown = true;
        _condition_variable.notify_all();
    }

private:
    std::mutex _queue_mutex;
    std::condition_variable _condition_variable;
    std::queue<T> _queue;
    std::atomic<bool> _shutdown;
};

Most of it looks fine to me, but the Shutdown function looks like it might have some problems. If there are problems, what is the best way to 'unblock' a thread waiting on Dequeue when I want to stop it?

Your concerns are correct. The std::notify_one description says that

  Even if the shared variable is atomic, it must be modified under the mutex in order to correctly publish the modification to the waiting thread.

Code wise, return true/return false usually indicate a room for improvement. What you are actually returning is a state of _shutdown. Do it explicitly:

        if (!shutdown) {
            dequeue item;
        }
        return !_shutdown;

You may also notice that shutdown is always tested with negation. It indicates that the semantics is reversed. I recommend to replace shutdown with something like keep_running.


HackerRank Regex Challenge: Detect HTML Tags Problem Statement

  In this problem you will use regular expressions to help you detect
  the various Tags used in an HTML document.

  Here are a few examples of tags:

  The "p" tag for paragraphs:

This is a paragraph

  It is also okay to have one or more spaces before or after the tag
  name:

This is also a paragraph

  Then, there is also something called a void or an empty tag such as:

  Some tags can also have attributes. For example, here we see the "a"
  tag which is used for adding links to a document.

[Google](http://www.google.com)

  In the above case, "a" is the tag and "href" is an attribute, the
  value of which is http://www.google.com. Ignore any attributes. Your
  task is to find out all the tags present in the given document.

  There are also tags such as this which haven't been split into an
  opening and closing tag (i.e, self-closing tags): '
'

  Input Format

  The first line will contain N, the number of lines in the fragment. A
  valid HTML document or fragment.Leading and trailing spaces and
  indentation will be removed from the HTML lines.

  Output Format

  A list of all the tags present in the document, in lexicographical
  order, with semi-colons ";" between them. If a tag occurs multiple
  times, you just need to list it out once.

  Sample Input

2

[Example Link](http://www.quackit.com/html/tutorial/html_links.cfm)

 class="more-info">[More Link Examples...](http://www.quackit.com/html/examples/html_links_examples.cfm)

  Sample Output

a;div;p

I have used TreeSet to sort the tags lexicographically:

public class Detect_HTML_Tags {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine().trim());
        String s="";

        for(int i=0;i<N;i++)
        {
            s+=br.readLine().trim();

        }
        TreeSet<String> tree=count_html_tags(s);
        int i=0;
        String s1="";
        for(String t:tree){
            s1=t;
            if(i==tree.size()-1)
                break;
            System.out.print(t+";");
            i++;
        }
        System.out.print(s1);
    }

    private static TreeSet<String> count_html_tags(String s) {
        String pat="\\s*(?:<([a-z][a-z0-9]*)|([\\[]))\\s*";
        Pattern p=Pattern.compile(pat);
        Matcher m=p.matcher(s);
        TreeSet<String> set=new TreeSet<>();
        while(m.find())
        {
            String tag=m.group(0).trim();
            //System.out.println(tag);
            if(tag.equals("["))
                set.add("a");
            else
                set.add(m.group(1));

        }
        return set;

    }
}

My code passes all the test cases. How can this solution be improved? Is the regex efficient enough or can it be improved further?

Naming/Style

public class Detect_HTML_Tags {

Usually classes get noun names, like HTML_Tag_Lister.

        int N = Integer.parseInt(br.readLine().trim());

It's more common in Java for all upper case variables to be constants:

        final int N = Integer.parseInt(br.readLine().trim());

Note that you can assign constants at runtime in Java.

        for(int i=0;i<N;i++)
        {

Most places you put the { on the same line as the command.  Here you put it on the next line.  While both are valid, it's generally easier to read the code if you pick one style or the other.  There are some exceptional cases, but this isn't one of them.

        for (int i = 0; i < N; i++) {

As I went through your code, I added additional spaces for readability.

Favor interfaces over implementations

        TreeSet<String> tree=count_html_tags(s);

A TreeSet is a specific implementation.  As a general rule, you want variable types to be interfaces.  This allows you to switch the implementation without changing the variable type in multiple places.  You could make the type a NavigableSet, but it should be sufficient to make it a SortedSet.  It might even be enough to make it a Set or Collection with the current code.  So something like

        SortedSet<String> tags = find_html_tags(s);

Note that you don't count the HTML tags.  You find and return them.

Also, I find tags to be a more descriptive name than tree or set.

Later

    private static TreeSet<String> count_html_tags(String s) {

changes to

    private static SortedSet<String> count_html_tags(String s) {

Keep it simple if you can

In the following

        String s1="";
        for(String t:tree){
            s1=t;
            if(i==tree.size()-1)
                break;
            System.out.print(t+";");
            i++;
        }

You could change to

        if (tags.empty()) {
            return;
        }

        String last = tags.last();
        tags.remove(last);
        for (String tag : tags) {
            System.out.print(tag + ";");
        }
        System.out.println(last);

This avoids the i variable and updating the s1 variable on every iteration of the loop.  You also don't have to check on every iteration of the loop in order to end it exactly one iteration early.

Note that last is a method on SortedSet.  As best I can tell, this is the only reason why tags can't be a simple Collection in main.

Bugs?

The problem statement suggests that < p /> is a valid tag, but your regular expression won't match it because of the space between the < and the p.

The problem statement also suggests that <p> is only a valid tag if it has a matching </p>, but you never check for that.  Perhaps that's not actually necessary.  The problem statement says what is valid but doesn't mention you enforcing it.


JavaScript function to convert decimal number to binary I was recently asked this in an interview for a front-end position and I came up with something like the code below, which seems to work but is clunky.  (Number.toString() was not allowed.)

function convertBinary(number) {
  var n = 0;
  var binaryArr = [];

  var difference = Math.pow(2, n);

  //find out how many digits are needed
  while (difference <= number){
    n++;
    difference = Math.pow(2, n);
    binaryArr.push(0);
  }

  n--;

  while(number > 0) {
    if (Math.pow(2, n) <= number) {
      binaryArr[n] = 1;
      number-= Math.pow(2, n);
    }
    n--;
  }

  return binaryArr.reverse().join("") * 1
}

Also I was asked what the Big(o) of this was but had a hard time figuring it out— what is the time complexity of JavaScript reverse?

Strictly speaking, the number parameter isn't decimal; it's just an abstract number.  (This is more a criticism of the terminology in your question title than of your code.)  On the other hand, it is very weird that you coerce the result into a number (101010) rather than returning it as a string ('101010').

The implementation strategy, using Math.pow(…, 2), strikes me as extravagant.  You should be able to do this more efficiently using just arithmetic:

function convertBinary(number) {
    var binaryArr = [];
    for (; number; number /= 2) {
        binaryArr.push(number % 2);
    }
    return binaryArr.reverse().join('');
}

… or the same thing using bitwise operations:

function convertBinary(number) {
    var binaryArr = [];
    for (; number; number >>= 1) {
        binaryArr.push(number & 1);
    }
    return binaryArr.reverse().join('');
}


OOP: Need tips of my approach in .Net I am looking for some different approaches to this following OOP scenario.

 Dim pb As Object = Nothing

 If radCars.Checked = True Then

     Dim productBase As ProductsBase(Of CarColumns)
     productBase = New Cars(fileLocation)

     pb = productBase

  ElseIf radTrucks.Checked = True Then

     Dim productBase As ProductsBase(Of TruckColumns)
     productBase = New Truck(fileLocation)

     pb = productBase

  End If

  pb.Parse()
  pb.AddRows()
  ....

Having to declare the object above and losing intelisense seems off.  The base class if using generics because the Truck and Car classes use different column classes for the parsing and adding of columns in the db.

Base Class:

Public MustInherit Class ProductsBase(Of T)

    Sub New(filePathString As String)
        FilePath = filePathString
    End Sub

    MustOverride Sub Parse()
    MustOverride Sub DeleteRows()
    MustOverride Sub AddRows(ByVal rows As IEnumerable(Of T), pageNumber As Integer)

    Property ParseResult As ProductLookupContainer(Of T)

End Class

Car Class:

Public Class Cars
    Inherits ProductsBase(Of CarColumns)

    Sub New(filePath As String)
        MyBase.New(filePath)
    End Sub

    Public Overrides Sub AddRows(rows As IEnumerable(Of CarColumns), pageNumber As Integer)
        DatabaseHelper.AddItemsToDB(Of CarProduct)(ConnectionString, rows, pageNumber)
    End Sub

    Public Overrides Sub DeleteRows()
        DatabaseHelper.DeleteRows(ConnectionString, "CarProducts")
    End Sub

    Public Overrides Sub Parse()

        Dim pf As New ParseFile(FilePath)
        Dim result = New ProductLookupContainer(Of CarColumns)
        result = pf.ParseCars

       'Set object
       ParseResult = result

    End Sub

End Class

I would agree that defining pb as an object is a code smell and should be eliminated.

Either in addition or instead of having Cars and Trucks inherit from ProductsBase(of T) it should implement an interface.

Suggested Interface:

Public Interface IProducts

    Sub DeleteRows()
    Sub Parse()

End Interface

Then you would declare pb as IProducts. Add any other public properties that will be used by all the derived classes of ProductsBase.

I'd also suggest creating a class or modules that contains factory methods to generate the new objects.

Suggested Factory Class:

Public Class ProductsFactory

    Public Shared Function CreateTruck(fileLocation as string) As IProducts
         Return New Truck(fileLocation)
    End Function

    Public Shared Function CreateCar(fileLocation as string) As IProducts
         Return New Car(fileLocation)
    End Function

End Class

The final code would look like this:

  Dim pb As IProducts

  If radCars.Checked = True Then
     pb = ProductsFactory.CreateCar(fileLocation)
  ElseIf radTrucks.Checked = True Then
     pb = ProductsFactory.CreateTruck(fileLocation)
  End If

  pb.Parse()
  pb.AddRows()


Calculating the energy of a signal I have a program to read signal data from 120 files in a folder and performing the energy of the signal.

It works correctly, but execution time is more than 20 mins, so there may be a problem with the code.  Can someone look into it and suggest possible methods to reduce the execution time?

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class myclass {
  static int total = 1;
  static int r = 0;

  public static void main(String[] args) {

    ArrayList<Double> mysignal = new ArrayList<Double>();
    ArrayList<Double> mylist = new ArrayList<Double>();

    double x;
    double a;
    myclass obj = new myclass();
    String target_dir = "path for folder";
    File dir = new File(target_dir);
    File[] files = dir.listFiles();

    for (File f : files) {
      if (f.isFile()) {
        BufferedReader inputStream = null;

        try {
          inputStream = new BufferedReader(new FileReader(f));
          String line;

          while ((line = inputStream.readLine()) != null) {

            mysignal.add(Double.valueOf(line));
            total++;

          }
        } catch (IOException e) {
          // TODO Auto-generated catch block
          e.printStackTrace();
        }

        a = obj.funtioneg(mysignal, total);
        mylist.add(r, a);
        System.out.println(mylist.get(r));
        r++;

      }
    }
  }

  public double functioneg(ArrayList<Double> s, int N) {

    ArrayList<Double> y = new ArrayList<Double>();
    double sum = 0, a1 = 0;
    double[] o1 = new double[N - 1];// processed signal

    for (int n = 0; n < N - 1; n++) {
      for (int k = 0; k < 40; k++) {

        if (n - k >= 0) {
          a1 = s.get(n - k);
          sum = sum + (a1 * a1);// energy

        } else
          sum = sum + 0;
      }

      o1[n] = sum;

      sum = 0;

    }
    double sum1 = 0;
    double avg;
    for (int t = 0; t < N- 1; t++) {

      sum1 = sum1 + o1[t];
    }

    avg = sum1 / N - 1;

    return (avg);
  }
}

Avoid recomputations

You compute the energy accumulated in a sliding window. When a window slides by 1, one sample shifts out, and one sample shifts in. The accumulated energy changes by s[n]^2 - s[n-40]^2. Therefore the inner loop is superficial. This alone will give you a 40-fold improvement.
Quadratic complexity

mysignal is only getting more signals appended to it, that is its initial parts are fed to functioneg over and over again, mostly producing the same result. In fact you only need 40 last of the processed samples to ramp up the new file.
Avoid reallocations

You don't really need the o1 array. sum1 can be computed on the fly.


Sum data that needs to be joined and grouped by I have a list of patients, Patient class has Prescriptions property, which is a list of Prescription objects. Prescription has 3 important attributes, Medicament,Amount and Type(which is basically a key for joining).

I need to join a list of Prescription types, as a prescription type has an attribute Influence which servers as multiplier for the amount.

var prescriptions = (from prs in
                        (from p in patients
                             from pr in p.Prescriptions
                             join type in DatabaseService.PrescriptionTypes
                                 on pr.Type equals type.Value
                         select new { Med = pr.Medicament,Amount = pr.Amount * (int)type.Influence })
                    group prs by prs.Med into prgs
                    select new { Medicament = prgs.Key,Amount = prgs.Sum(prg => prg.Amount) }).ToList();

Basically what I do (from inner to outer queries)

Join prescriptions with prescription types, get Medicament and the multiplied Amount
Group the records by the Medicament
Run one more select to get the overall sum from all patients

Is there any simpler way?

EDIT:

So I realised couple things and simplified the query quite a bit, I think it's much more readable now. The things I missed the first time were:

SelectMany that lets me get rid of the outter select, since prescriptions are all I care about
Being able to create new objects within group statement, hence one more select can be avoided

The new code looks like

    var prescriptions = from p in patients.SelectMany(p => p.Prescriptions)
                        join type in DatabaseService.PrescriptionTypes
                            on p.Type equals type.Value
                        group new { Amount = p.Amount * (int)type.Influence } by p.Medicament into prs
                        select new { Medicament = prs.Key,Amount = prs.Sum(pr => pr.Amount) };

With that I'm pretty happy and I doubt you can simplify it anymore.

You're right, I cannot simplify it anymore ;-)

Most reviews are about commenting bad code/habits and making suggestions how to improve it. But you're lucky, to me, there is nothing bad to say about your snippet so this will be a short review (and probably a reason why there are no anwers yet).

You use clear names for the properties and variables where you use the first letter of the collection name or something derived (like type). You also use meaningfull names for the properties of the anonymous objects.

If the rest of your code looks as clean as this small sample you should be happy ;-)


A function for block allocation During Jonathan Blow's video where he muses about a games-focused programming language, he presents C++ code that allocates a single big block of memory and has N pointers into that block. The purpose being to avoid heap allocating N blocks of memory for N arrays.

That code looked to me like it could use some genericity... so I first came up with the following where we would allocate three arrays into a single block of memory:

using memory_block = std::unique_ptr<char[]>;

template<typename A, typename B, typename C>
memory_block block_allocate(A*& p, size_t a, B*& q, size_t b, C*& r, size_t c)
{
    memory_block z = std::make_unique<char[]>(a * sizeof(A) + b * sizeof(B) + c * sizeof(C));

    p = reinterpret_cast<A*>(z.get());
    q = reinterpret_cast<B*>(p + a);
    r = reinterpret_cast<C*>(q + c);

    return z;
}

Improving for any number of arrays gives us:

using memory_block = std::unique_ptr<char[]>;

namespace detail
{
    template<typename T>
    size_t block_size(T* const, size_t const n)
    {
        return sizeof(T) * n;
    }

    template<typename T, typename U, typename... Args>
    size_t block_size(T* const t, size_t const m, U* const u, size_t const n, Args&&... args)
    {
        return block_size(t, m) + block_size(u, n, args...);
    }

    template<typename T, typename U>
    void block_assign(T* const p, size_t const offset, U*& u, size_t const)
    {
        u = reinterpret_cast<U*>(p + offset);
    }

    template<typename T, typename U, typename... Args>
    void block_assign(T* const p, size_t const offset, U*& u, size_t const n, Args&&... args)
    {
        block_assign(p, offset, u, n);
        block_assign(u, n, args...);
    }
}

template<typename T, typename... Args>
memory_block block_allocate(T*& t, size_t const n, Args&&... args)
{
    memory_block b = std::make_unique<char[]>(detail::block_size(t, n, args...));

    detail::block_assign(b.get(), 0, t, n, args...);

    return b;
}

It's understood that Jonathan's Blow's desire is for a language solution to this problem and not the library solution that I present but I had fun coming up with it nonetheless.

So, after simple testing the code appears to behave as expected but do you see something missing that would make production-ready?

Memory alignment requirements is something often forgotten when implementing custom memory allocation strategies. Each native type has a minimum alignment required for its starting memory address, consequently, structured types will inherit the requirement from its members. std::aligned_storage and std::aligned_union are a good example on that. Also refer to: How to allocate aligned memory only using the standard library?

Operator new and malloc are guaranteed to always return a starting address that is aligned for the most demanding type available (like 16 bytes for a __m128 vector type), so memory returned by those system allocators will be suitable to store such objects and homogeneous arrays of them. The problem with mixing objects with different alignment requirements in the same memory block is that if one item or chunk of items in this mixed array breaks the alignment, whatever follows will be misaligned, so you run the risk of getting memory access errors at the CPU level when touching that memory.

Your block allocator has that problem, since it accepts generic types, so you need to fix it in order to have a robust implementation that can allocate anything. To do that, you just have to increment each pointer to an aligned address, and also add an extra overhead to the parent block, in account of that. Something like the following:

void * aligned_ptr(void * ptr, std::size_t alignment)
{
    // Cast to integer and align the address:
    std::uintptr_t uintPtr = reinterpret_cast<std::uintptr_t>(ptr);
    std::uintptr_t alignedPtr = (uintPtr + (alignment - 1)) & ~(alignment - 1); // Power-of-two alignment assumed!

    // Re-cast to void*, validate and return:
    void * userPtr = reinterpret_cast<void *>(alignedPtr);
    assert(is_aligned_ptr(userPtr, alignment));
    return userPtr;
}

std::size_t aligned_size(std::size_t size, std::size_t alignment)
{
    // Add the minimum extra needed to the size for pointer alignment.
    // This size can then be used to malloc() some memory
    // and then have the pointer aligned with aligned_ptr().
    return size + (alignment - 1);
};

block block_allocate(A*& pA, std::size_t nA, B*& pB, std::size_t nB, C*& pC, std::size_t nC)
{
    auto sizeBlockA = aligned_size(nA * sizeof(A), alignof(A));
    auto sizeBlockB = aligned_size(nB * sizeof(B), alignof(B));
    auto sizeBlockC = aligned_size(nC * sizeof(C), alignof(C));

    block blk = alloc_bytes(sizeBlockA + sizeBlockB + sizeBlockC);

    pA = reinterpret_cast<A*>(aligned_ptr(blk.ptr, alignof(A))); // if allocated with new, already aligned, but doesn't harm checking either...
    pB = reinterpret_cast<B*>(aligned_ptr(blk.ptr + sizeBlockA, alignof(B)));
    pC = reinterpret_cast<C*>(aligned_ptr(blk.ptr + sizeBlockA + sizeBlockB, alignof(C)));

    return blk;
}

Please note that the above example was not tested, but hopefully gives you a good idea of the procedure.

Other little things:

Instead of returning a plain unique_ptr to the memory, I'd suggest augmenting the pointer with a small structure that has some extra context, like the total size of the memory. This is oftentimes useful for debugging and profiling (the block type I invented above):

struct block
{
    std::unique_ptr<std::uint8_t[]> ptr;
    std::size_t size;
};

Or you might modify it to use of a std::vector. It is certainly possible, but might be overkill, since the block is not meant to be resized.

Very minor nitpicking, but notice that I use the std:: prefix in the extended integer types like size_t? That's the correct usage, since they are members of the standard namespace in C++. It works without because shared C headers expose them globally, but a pure C++ compiler is not required to provide that.


Document (PDF, TXT, DOCX) to text classes I wrote some classes to convert some documents (PDF, DOC, DOCX and TXT) to only text so that it can be stored in a search engine.

Here's how I use those classes :

$file = 'text.doc'; // comes from the user, hardcoded for the example
$file_extension = pathinfo($file, PATHINFO_EXTENSION);

switch($file_extension){
    case 'pdf':
        $reader = new PDFConverter($file);
        break;
    case 'text':
        $reader = new TXTConverter($file);
        break;
    case 'doc':
        $reader = new DOCConverter($file);
        break;
    case 'docx':
        $reader = new DOCXConverter($file);
        break;
}

$reader->handle();
$text = $reader->getText();

Here's the parent Converter class :

class Converter
{
    protected $file;
    protected $text;

    public function __construct($file)
    {
        $this->file = $file;
    }

    public function getText()
    {
        return $this->text;
    }
}

Here's one of the converter class, PDFConverter :

class PDFConverter extends Converter implements IConverter
{
    public function handle()
    {
        $this->text = 'Text PDF'; // just for demo
    }
}

And finally the IConverter interfaces that all subclasses implement :

interface IConverter
{
    public function handle();
}

How does this look? Is this a good use of inheritance/interfaces? Any pointers on how to structure this better would be appreciated.

I've removed the logic from the subclasses' handle() method to keep things simple for Codereview.

You have two methods getText() and handle() of which one is not needed. Doing the conversion and returning the result should be one method. So, like this:

class Converter
{
    protected $file;
    protected $text;

    public function __construct($file)
    {
        $this->file = $file;
    }
}

and:

class PDFConverter extends Converter implements IConverter
{
    public function getPlainText()
    {
      if (is_null($this->text)) // not yet converted?
      {
        $this->text = 'Text PDF'; // do the conversion
      }
      return $this->text; // return result
    }
}

This way you still buffer the result, but you get rid of the rather weird handle() method.

When using this class you don't have to think about the order in which to call the methods anymore, just ask for the plain version of the text and the method will do the conversion only once.

You might want to move the declaration of the $text field to the other class.


Reducing execution time of an HTML parsing script The script is intended to return an array with texts containing specific words in English and the equivalent texts in Polish from EUR-Lex - a website with EU documents.

The script downloads the page which address is specified by the passed variable. Then this page is parsed using regular expressions for the document codes. This code are then used to access another page. This page is then parsed for elements contained within <tr> tags, which, if their content contains words from the variable (checked with a regular expression), are saved in an array.

For variables containing 1-2 words the script works fairly well; not so well for more. I got complaints from my free hosting provider (hostinger.in) that the script uses too much resources. I have other scripts run before that script, but not simultaneously, so I don't if they contribute to the problem.

<?php
//test variables
//$var1 = 'board_of_directors';
//$var1 = 'affidavit';
$var1 = 'event_of_default';
$var1 = explode("_", $var1);
$words = implode(" ",$var1);
if (count($var1) >= 2) {
    $var1 = implode("%20",$var1);
} else {
    $var1 = implode("%",$var1);
}
$var1 = "\""."$var1"."\"";
$html = file_get_contents("http://eur-lex.europa.eu/search.html?qid=1&text=$var1&scope=EURLEX&type=quick&lang=en");
preg_match_all('/CELEX:(\w+)&/si', $html, $matches2);
$result = array_unique($matches2[1]);
$result2 = file_get_contents("http://eur-lex.europa.eu/legal-content/EN-PL/TXT/?uri=CELEX:$result[0]&from=EN");
$dom = new domDocument;
libxml_use_internal_errors(true);
$dom->loadHTML($result2);
$items = $dom->getElementsByTagName('tr');
$return_array = array();

for ($i = 0; $i < $items->length - 1; $i++) {
    $text1 = $items->item($i)->childNodes->item(0)->textContent;
    if (preg_match('/' . $words . '/i', $text1)) {
        $text2 = $items->item($i)->childNodes->item(1)->textContent;
        array_push($return_array, $text1);
        array_push($return_array, $text2);
    }
}
echo json_encode($return_array);

?>

There's a few things you can do to improve here:

Use curl instead of get_file_contents, it speeds the document retrieval up so much.
The following could be converted to a ternary statement:

if (count($var1) >= 2) {
    $var1 = implode("%20",$var1);
} else {
    $var1 = implode("%",$var1);
}

Notice that the condition is reversed:

$var1 = implode('%' + (!count($var1) >= 2 ?: "20"), $var1);

You shouldn't be joining strings like this: "\""."$var1"."\"":

Do this instead: "\"{$var1}\"" (see that the variable is wrapped in curly braces)

Don't array_push, use the $array[] notation instead.

$return_array[] = $text1;
$return_array[] = $text2;


jQuery Dialog Settings The goal of the code is to

initialize a Dialog with settings

make sure the object is reusable

Setup the options to reuse the code

I'm not quite sure if this is overkill, or I am going about this problem in the entirely wrong way. Any input would be appreciated.

var myDialog = myDialog || (function() {

  var options = {
    title: 'Attention',
    msg: 'Message Here',
    focusOn: ''
  }

    function show(opts) {

      options = $.extend({}, options, opts);

      $('<p>' + options.msg + '</p>').dialog({
        title: options.title,
        modal: true,
        draggable: false,
        show: {
          effect: "fade",
          duration: 500
        },
        hide: {
          effect: "fade",
          duration: 200
        },
        buttons: {
          'Close': function() {
            $(this).dialog("close");
          }
        },
        close: function() {
          if (options.focusOn.length !== 0) {
            $(options.focusOn).focus()
          }
          $(this).dialog("destroy");
        }
      });
    }

    function updateOptions(opts) {
      options = $.extend({}, options, opts);
    }

  return {
    fire: show,
    options: updateOptions
  };

}());

myDialog.fire({
  msg: 'Hello there',
  focusOn: '#test'
});

It is already a good attempt at making better-looking code.  Just a few improvement:

Declare all private functions one-by-one with declaring that individual just like you declare your variable (see jQuery code).
There is no need for the updateOptions() method; we don't need it.

var myDialog = myDialog || (function () {

    var options = {
        title: 'Attention',
        msg: 'Message Here',
        focusOn: ''
    }

    var show = function(opts) {
            options = $.extend({}, options, opts);
            $('<p>' + options.msg + '</p>').dialog({
                title: options.title,
                modal: true,
                draggable: false,
                show: {
                    effect: "fade",
                    duration: 500
                },
                hide: {
                    effect: "fade",
                    duration: 200
                },
                buttons: {
                    'Close': function() {
                        $(this).dialog("close");
                    }
                },
                close: function() {
                    if (options.focusOn.length !== 0) {
                        $(options.focusOn).focus();
                    }
                    $(this).dialog("destroy");
                }
            });
        },

        updateOptions = function(opts) {
            options = $.extend({}, options, opts);
        };

    return {
        fire: show,
        options: updateOptions
    };

}());


Data structure to count occurrences of words I have some code for a assignment where the main marks are awarded based on efficiency. The program uses a given wordgenerator which generates random words and adds them to a user-made data structure. You also have to provide 3 methods, one to add a item, one to remove a item and one to count how many times a word is present in the structure. Here is my code:

public class WordStoreImp implements WordStore{

public class Node{
   public String data;
   public Node next;
   public Node(String addingWord, Node theNext){
        data = addingWord;
        next = theNext;
   }
}

private Node[] array;
int usedAmount=0;

public WordStoreImp(int n){
    array = new Node[n];
}

public void add(String word){
    int position = hashFunction(word);
    array[position]=new Node(word,array[position]);
}

public int count(String word){
    int number = 0;
    int position = hashFunction(word);
    Node temp = array[position];
    while(temp!=null){
        if(temp.data.equals(word)){
            number++;
        }
        temp=temp.next;
    }
    return number;
}

    public int hashFunction(String a){
    int sum = 1;
        for(int i = 0; i<a.length(); i++){
            char b = a.charAt(i);
            int value = (int) b;
            sum *= value;
     }
     sum = sum % array.length;
     if(sum<0){
         return -sum;
     }
     return sum;
 }

public void addthings(String word, int n){
    for(int i = 0; i<n; i++){
        add(word);
    }
}

public int printSize(){
    int count = 0;
    for(int i = 0; i<array.length; i++){
        if(array[i] != null){
            count++;
        }
    }
    System.out.println(count);
    return count;
}

public static void main(String[] args) {
    WordStoreImp a = new WordStoreImp(100);
    a.addthings("abc", 100);
    System.out.println(a.count("abc"));
    System.out.println(a.count("abc"));
}
}

So far I have written two of the methods, add and count. Whilst my add function is very quick, the count method is rather slower and takes a lot more time to compute. Is there a more efficient way to write this method or change things here to make it quicker?

Also - we arent allowed to use any methods or data structures that are inbuilt Java methods, such as HashMaps.

There are many ideas to speed up hashtables, or hash maps.  Some ideas appear in an article about hashtables in PHP, and a comment describing hashtables in Ruby.  I present some ideas here, but these ideas might or might not speed up your program, because I have not tested them.

Add a counter for each word.  If the word "the" appears 20 times, your code adds 20 entries for "the".  The idea is to have 1 entry for "the", with the counter set to 20.  This would be like using Java's HashMap<String, int> to map the word to the counter.

For this idea, you would add an int count; to class Node.  To add n copies of word, you would searches for the Node with word, and add n to its count.  If the Node didn't exist, you would insert a new Node and set its count.  Your table would have fewer nodes, so searches might be faster.  Also, there would be only one node for each word, so you would stop searching if you found the node.

Change the hash function.  Your hash function seems to multiply the character codes in a string.  If a string has one even-numbered character (like 'l', 'n', 'r', 't'), then the product is a multiple of 2.  If the string hash two such characters, then the product is a multiple of 4, and so on.  With 100 buckets, your hash might put most words in the multiple-of-4 buckets, and some words in the other even buckets, and almost no words in the odd buckets.  Then your program would search for most words in the power-of-4 buckets, but those buckets would have long lists of nodes.

A better hash function might use a rotation (also known as a barrel shift) to spread the bits, with addition to mix in each character.

int hash = 0;
for (int i = 0; i < a.length(); i++) {
    hash = Integer.rotateLeft(hash, 5);
    hash += (int)a.charAt(i);
}

Use power-of-2 buckets.  Division a / b and modulus a % b tend to be slow when b isn't constant.  Your hash function has sum = sum % array.length.  If the length was a power of 2, you would use sum = sum & (array.length - 1) to get the modulus.  For this idea, your constructor WordStoreImp(n) would round up n to a power of 2, with code like

if (n < 16)
    n = 16;
else
    n = Integer.highestOneBit(n - 1) << 1;

For example, if n was 100, then the highest 1-bit in 99 is 64, and 64 shifted left by 1 is 128.  Because 128 is 2 to the 7th power, so hash & 127 extracts the low 7 bits of hash as an integer from 0 to 127.

Switch from open chaining to open addressing.  Your hash table uses an open chain (or linked list) in each bucket.  You allocate memory with new Node, but memory allocation might be slow.  The idea is to switch to open addressing and remove the new Node calls.

With open addressing, each bucket holds exactly one word.  You would allocate the buckets with

words = new String[n];
counts = new int[n];

This sets each word to null and each count to zero.  A bucket is empty when its word is null.  To search for a word, if the bucket has a different word, you check the next buckets until you find the correct word, or an empty bucket.

pos = hashFunction(word);
while (strings[pos] != null && !strings[pos].equals(word))
    pos = (pos + 1) & mask;  // where mask = strings.length - 1

At this point, count[pos] is the correct count for this word.  If the bucket is empty, then the count is still zero.  If you are adding the word, then you would put strings[pos] = word and increase the count.

In open addressing, a bucket with a word can never become empty; you can only remove a word by setting its count to zero, and leaving the word in the bucket.  To be fast, at least half of the buckets must be empty.  You would keep a count of the number of words in the table.  When the count reaches n/2, you would allocate a new table with twice as many buckets, and move all the words to the new table (skipping words where the count is zero).


Converting time in number of minutes past midnight to HH:MM format This program is a clock that only displays minutes passed since midnight. This program is supposed to be really simple but because of some "aesthetic bug", I wrote quite a lot if-else statements that I think can be simplified.

  Format Input

  The first line will contain an integer T, the number of test cases.
  Each test case will contain an number N, the number displayed by the
  strange clock.

  Format Output

  For each test case, print “Case X: “ (X starts with 1) and then print
  what time it is in 24 hours HH:MM format.

  Constraints

  1 <= T <= 1000

  0 <= N <= 1439

#include <stdio.h>

int main()
{
    int T;
    scanf("%d", &T);

    for (int i = 1; i <= T; i++) {

        int N;
        scanf("%d", &N);

        int hours = N / 60;
        int minutes = N % 60;

        printf("Case #%d: ", i);

        if (N < 10) {
            printf("00:0%d\n", N);
        } else if (N > 10 && N < 60) {
            printf("00:%d\n", N);
        } else if (N > 60 && N < 600) {
            if (minutes == 0) {
                printf("0%d:00\n", hours);
            } else if (minutes > 0 && minutes < 10) {
                printf("0%d:0%d\n", hours, minutes);
            } else {
                printf("0%d:%d\n", hours, minutes);
            }
        } else {
            if (minutes == 0) {
                printf("%d:00\n", hours);
            } else if (minutes > 0 && minutes < 10) {
                printf("%d:0%d\n", hours, minutes);
            } else {
                printf("%d:%d\n", hours, minutes);
            }
        }
    }
}

Following @Martin R's comment, I'll make my comment above a solution:

printf already supports what you're trying to achieve with your if-then-else jungle:

#include <stdio.h>

int main()
{
    int T;
    scanf("%d", &T);

    for (int i = 1; i <= T; i++) {

        int N;
        scanf("%d", &N);

        int hours = N / 60;
        int minutes = N % 60;

        printf("Case #%d: %02d:%02d\n", i, hours, minutes);
    }
}

You're also missing to check the return value of scanf. It is used to report errors in the input. What is the purpose of the first scanf?

Edit

From @chux's comment: you should validate the constraints of N after the input.

Edit

Note: additional variables should indeed have no influence on performance and are a good way to document meaning of your code, so please ignore my initial statement about "saving variables".

Old version was:

  Also, I'd change the variable naming. Use minutes instead of N to
  communicate clearly what you're handling in the variable. You can then
  write the computation directly in the parameter list of printf, saving
  you two additional variables.