Pages

Wednesday, 21 May 2014

Getting Started with MongoDB Shell

Using the MongoDB shell, we will practice on how we can create, read, update, and delete (CRUD) documents plus MongoDB's query language. The query language is a bit different where you interact with the server using the JavaScript programming language and a simple API.

Starting the shell

After having a working MongoDB installation, Make sure you have a running mongod instance and then run:
 mongo
If the shell program starts successfully, you see the version of MongoDB you’re running along with some additional information about the currently selected database.

Inserts and queries

Let us start by switching to the tutorial database:
 use tutorial
You will see a message verifying that you have switched databases.
Note that creating the database is not required. Databases and collections are created only when documents are first inserted.
Now, we want to create our first document which is specified in JSON. For example:
 {username: "amir"}  
To save this document, you need to choose a collection to save it to. We will save it to the users collection.
 db.users.insert({username: "amir"})  
You can issue a simple query to verify that the document has been saved:
 db.users.find()  
Note that an _id field has been added to the document. You can think of the _id value as the document's primary key. Every MongoDB document requires an _id, and if one is not present when the document is created, then a special MongoDB object ID will be generated and added to the document at that time.
Let us add a second user to the collection:
 db.users.save({username: "Michael"})  
We can issue following to see how many documents are in a collection:
 db.users.count()  
A query selector is a document that is used to match against all documents in the collection. To query for all documents where the username is amir, you pass a simple document that acts as your query selector:
 db.users.find({username: "amir"})  

Updating documents

All updates require at least two arguments. The first specifies which documents to update, and the second defines how the selected documents should be modified.
Suppose that user "amir" decides to add his country of residence.
 db.users.update({username: "amir"}, {$set: {country: "UK"}})  
If you now issue a query, you will see that the document has been updated accordingly:
 db.users.find({username: "amir"})  
If the user later decides that he no longer wants his country stored in his profile, he can remove the value just as easily using the $unset operator:
 db.users.update({username: "amir"}, {$unset: {country: 1}})  
We can also have more complicated examples with more complex data structures:
 {  
   username: "amir",  
   favourites: {  
    cities: ["Edinburgh", "London"],  
    sports: ["Squash", "Table tennis"]  
   }  
 }  
We can update amir document to hold above example:
 db.users.update( {username: "amir"},  
 {  
   $set: {  
    favorites: {  
      cities: ["Edinburgh", "London"],  
      movies: ["Squash", "Table tennis"]  
    }  
   }  
 }  
 )  
Suppose that you want to find all users who like the city London:
 db.users.find({"favourites.movies": "London"})  
Now imagine you want to add another favourite city to all users who likes "London":

 db.users.update( {"favourites.cities": "London"},  
   {$addToSet: {"favourites.cities": "Bristol"} },  
    false,  
    true )  
Although we could use the operator $set like before, but that would require you to rewrite and send the entire array of movies. Instead we used the operator $addToSet. The fourth argument, true, indicates that this is a multi-update. By default, a MongoDB update operation will apply only to the first document matched by the query selector. If you want the operation to apply to all documents matched, then you must be explicit about that.

Deleting Data

If given no parameters, a remove operation will clear a collection of all its documents. 
 db.users.remove()  
If you want to remove a certain subset of a collection’s documents, then you can pass a query selector to the remove() method. For example if we want to remove all users whose favourite city is Brighton:
 db.users.remove({"favourites.cities": "Brighton"})  
Note that the remove() operation does not actually delete the collection; it merely removes documents from a collection.
If your intent is to delete the collection along with all of its indexes, use the drop() method:
 db.users.drop()

Tuesday, 13 May 2014

Getting Started with MongoDB in Java

MongoDB is an open-source document database, and the leading NoSQL database. MongoDB eschews the traditional table-based relational database structure in favor of JSON-like documents with dynamic schemas (MongoDB calls the format BSON), making the integration of data in certain types of applications easier and faster.

Tuesday, 6 May 2014

Binary Search Implementation in Java

A binary search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value. For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.

Overflow And Underflow in Java

Overflow and underflow is a condition where you cross the limit of prescribed size for a data type. When overflow or underflow condition is reached, either the program will crash or the underlying implementation of the programming language will have its own way of handing things.

In Java the overflow and underflow are more serious because there is no warning or exception raised by the JVM when such a condition occurs.

Overflow in int

As int data type is 32 bit in Java, any value that surpasses 32 bits gets rolled over. It means that after incrementing 1 to 2147483647 (Integer.MAX_VALUE), the returned value will be -2147483648 (Integer.MIN_VALUE).

Underflow of int

Underflow is the opposite of overflow. While we reach the upper limit in case of overflow, we reach the lower limit in case of underflow. Thus after decrementing 1 from -2147483648 (Integer.MIN_VALUE), we reach 2147483647 (Integer.MAX_VALUE). Here we have rolled over from the lowest value of int to the maximum value.

Overflow and Underflow in Java floating point operators

While using Java floating point operators, overflow will result in Infinity and underflow will result 0.0.

Saturday, 3 May 2014

Tuple Implementation and Conversion to Adjacency List Graph in Java

In this tutorial, first we will discuss about a simple implementation of Tuple in Java and then work on conversion of a list of tuples to Adjacency List Graph. Please click on this link to read the implementation of Adjacency List Graph in Java that we discussed earlier.

A tuple is an ordered list of elements. We can group together pairs of values by surrounding with parentheses like:
year_born = ("Someone", 1980)
This is an example of a data structure (a mechanism for grouping and organizing data to make it easier to use).

Following source code represents a very simple structure for tuple and it assumes a tuple consists of two entries.

Friday, 2 May 2014

Queue Implementation in Java

A queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.

Graph Implementation in Java

A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Monday, 28 April 2014

Binary Tree Implementation in Java

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Friday, 25 April 2014

Hashtable Implementation in Java

Hashtable is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions, different keys that are assigned by the hash function to the same bucket, will occur and must be accommodated in some way (Later we use Linked List data structure, that was discussed in this blog, to remedy this potential problem).

Thursday, 24 April 2014

Stack Implementation in Java

A stack is a last-in-first-out (LIFO) data structure: Elements are always removed in the reverse order
in which they were added. The add element and remove element operations are conventionally called push and pop, respectively.

One of the ways to implement a stack is by using a dynamic array, an array that changes size as needed
when elements are added. The main advantage of dynamic arrays over linked lists is that arrays offer random access to the array elements (you can immediately access any element in the array if you know its index). However, operations on a stack always work on one end of the data structure (the top of the stack), so the random accessibility of a dynamic array gains you little. In addition, as a dynamic array grows, it must occasionally be resized, which can be a time-consuming operation as elements are copied from the old array to the new array.

Linked lists usually allocate memory dynamically for each element. Depending on the overhead of the memory allocator, these allocations are often more time consuming than the copies required by a dynamic array, so a stack based on a dynamic array is usually faster than one based on a linked list.

Wednesday, 23 April 2014

Linked List Implementation in Java

Why Linked Lists?

The linked list is the basis for a number of problems regarding the handling of dynamic data.

Kinds of Linked List

There are three basic kinds of linked list: singly linked lists, doubly linked lists, and circular linked lists. Let's discuss singly linked lists in this post.

Singly Linked Lists

Each data element in the list has a link (a pointer or reference) to the element that follows it in the
list. The first element in a singly linked list is referred to as the head of the list. The last element in such a list is called the tail of the list and has an empty or null link.
Singly linked list
Because the links in a singly linked list consist only of next pointers (or references), the list can be traversed only in the forward direction. Therefore a complete traversal of the list must begin with the first element. In other words, you need a pointer or reference to the first element of a list to locate all the elements in the list.

Bitwise Manipulation in Java

Bitwise Operators

The Java programming language also provides operators that perform bitwise and bit shift operations on integral types.
  1. The unary bitwise complement operator "~" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0". For example, a byte contains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111".
  2. The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
  3. The bitwise & operator performs a bitwise AND operation.
  4. The bitwise ^ operator performs a bitwise exclusive OR operation.
  5. The bitwise | operator performs a bitwise inclusive OR operation.

Merge Sort Implementation in Java

Merge Sort

Mergesort is a divide and conquer algorithm and works as follows:
  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
During the Merge Sort process the object in the collection are divided into two collections. To split a collection, Merge Sort will take the middle of the collection and split the collection into its left and its right part.

The resulting collections are again recursively sorted via the Merge Sort algorithm.

Once the sorting process of the two collections is finished, the result of the two collections is combined. To combine both collections Merge Sort start at each collection at the beginning. It pick the object which is smaller and inserts this object into the new collection. For this collection it now selects the next elements and selects the smaller element from both collection.

Once all elements from both collections have been inserted in the new collection, Merge Sort has successfully sorted the collection.

To avoid the creation of too many collections, typically one new collection is created and the left and right side are treated as different collections.

Merge Sort Example - GIF Format

Tuesday, 22 April 2014

Quick Sort Implementation in Java

Quick Sort

Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

The steps are:
  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values.
Quick Sort Example - GIF Format

Bubble Sort Implementation in Java

Bubble Sort

A simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
Bubble Sort Example - GIF Format