Book Image

Everyday data structures

By : William Smith
Book Image

Everyday data structures

By: William Smith

Overview of this book

Explore a new world of data structures and their applications easily with this data structures book. Written by software expert William Smith, you?ll learn how to master basic and advanced data structure concepts. ? Fully understand data structures using Java, C and other common languages ? Work through practical examples and learn real-world applications ? Get to grips with data structure problem solving using case studies
Table of Contents (20 chapters)
Everyday Data Structures
Credits
About the Author
About the Reviewer
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
1
Data Types: Foundational Structures

Boolean data type


Boolean data types are intended to symbolize binary values, usually denoted by 1 and 0, true and false, or even YES and NO. Boolean types are used to represent truth logic, which is based on Boolean algebra. This is just a way of saying that Boolean values are used in conditional statements, such as if or while, to evaluate logic or repeat an execution conditionally.

Equality operations include any operations that compare the value of any two entities. The equality operators are:

  • == implies equal to

  • != implies not equal to

Relational operations include any operations that test a relation between two entities. The relational operators are:

  • > implies greater than

  • >= implies greater than or equal to

  • < implies less than

  • <= implies less than or equal to

Logic operations include any operations in your program that evaluate and manipulate Boolean values. There are three primary logic operators, namely AND, OR, and NOT. Another, slightly less commonly used operator, is the exclusive or, or XOR operator. All Boolean functions and statements can be built with these four basic operators.

The AND operator is the most exclusive comparator. Given two Boolean variables A and B, AND will return true if, and only if, both A and B is true. Boolean variables are often visualized using tools called truth tables. Consider the following truth table for the AND operator:

A

B

A ^ B

0

0

0

0

1

0

1

0

0

1

1

1

This table demonstrates the AND operator. When evaluating a conditional statement, 0 is considered to be false, while any other value is considered to be true. Only when the value of both A and B is true, is the resulting comparison of A ^ B also true.

The OR operator is the inclusive operator. Given two Boolean variables A and B, OR will return true if either A or B is true, including the case when both A and B are true. Consider the following truth table for the OR operator:

A

B

A v B

0

0

0

0

1

1

1

0

1

1

1

1

Next, the NOT A operator is true when A is false, and false when A is true. Consider the following truth table for the NOT operator:

A

!A

0

1

1

0

Finally, the XOR operator is true when either A or B is true, but not both. Another way to say it is, XOR is true when A and B are different. There are many occasions where it is useful to evaluate an expression in this manner, so most computer architectures include it. Consider the following truth table for XOR:

A

B

A XOR B

0

0

0

0

1

1

1

0

1

1

1

0

Operator precedence

Just as with arithmetic, comparison and Boolean operations have operator precedence. This means the architecture will give a higher precedence to one operator over another. Generally speaking, the Boolean order of operations for all languages is as follows:

  • Parentheses

  • Relational operators

  • Equality operators

  • Bitwise operators (not discussed)

  • NOT

  • AND

  • OR

  • XOR

  • Ternary operator

  • Assignment operators

It is extremely important to understand operator precedence when working with Boolean values, because mistaking how the architecture will evaluate complex logical operations will introduce bugs in your code that you will not understand how to sort out. When in doubt, remember that, as in arithmetic parentheses, take the highest precedence and anything defined within them will be evaluated first.

Short-circuiting

As you recall, AND only returns true when both of the operands are true, and OR returns true as soon as one operand is true. These characteristics sometimes make it possible to determine the outcome of an expression by evaluating only one of the operands. When your applications stops evaluation immediately upon determining the overall outcome of an expression, it is called short-circuiting. There are three main reasons why you would want to use short-circuiting in your code.

First, short-circuiting can improve your application's performance by limiting the number of operations your code must perform. Second, when later operands could potentially generate errors based on the value of a previous operand, short-circuiting can halt execution before the higher risk operand is reached. Finally, short-circuiting can improve the readability and complexity of your code by eliminating the need for nested logical statements.

C#

C# uses the bool keyword as an alias of System.Boolean and stores the values true and false:

    //C# 
    bool a = true; 
    bool b = false; 
    bool c = a; 
 
    Console.WriteLine("a: {0}", a); 
    Console.WriteLine("b: {0}", b); 
    Console.WriteLine("c: {0}", c); 
    Console.WriteLine("a AND b: {0}", a && b); 
    Console.WriteLine("a OR b: {0}", a || b); 
    Console.WriteLine("NOT a: {0}", !a); 
    Console.WriteLine("NOT b: {0}", !b); 
    Console.WriteLine("a XOR b: {0}", a ^ b); 
    Console.WriteLine("(c OR b) AND a: {0}", (c || b) && a); 
 
    /* 
      Output 
      a: True 
      b: False 
      c: True 
      a AND b: False 
      a OR b: True 
      NOT a: False 
      NOT b: True 
      a XOR b: True 
      (c OR b) AND a: True 
    */ 

Java

Java uses the boolean keyword for the primitive Boolean data type. Java also provides a Boolean wrapper class for the same primitive type:

    //Java 
    boolean a = true; 
    boolean b = false; 
    boolean c = a; 
 
    System.out.println("a: " + a); 
    System.out.println("b: " + b); 
    System.out.println("c: " + c); 
    System.out.println("a AND b: " + (a && b)); 
    System.out.println("a OR b: " + (a || b)); 
    System.out.println("NOT a: " + !a); 
    System.out.println("NOT b: " + !b); 
    System.out.println("a XOR b: " + (a ^ b)); 
    System.out.println("(c OR b) AND a: " + ((c || b) && a)); 
 
    /* 
      Output 
      a: true 
      b: false 
      c: true 
      a AND b: false 
      a OR b: true 
      NOT a: false 
      NOT b: true 
      a XOR b: true 
     (c OR b) AND a: true 
    */ 

Objective-C

Objective-C uses the BOOL identifier to represent Boolean values:

    //Objective-C 
    BOOL a = YES; 
    BOOL b = NO; 
    BOOL c = a; 
 
    NSLog(@"a: %hhd", a); 
    NSLog(@"b: %hhd", b); 
    NSLog(@"c: %hhd", c); 
    NSLog(@"a AND b: %d", a && b); 
    NSLog(@"a OR b: %d", a || b); 
    NSLog(@"NOT a: %d", !a); 
    NSLog(@"NOT b: %d", !b); 
    NSLog(@"a XOR b: %d", a ^ b); 
    NSLog(@"(c OR b) AND a: %d", (c || b) && a); 
 
    /* 
      Output 
      a: 1 
      b: 0 
      c: 1 
      a AND b: 0 
      a OR b: 1 
      NOT a: 0 
      NOT b: 1 
      a XOR b: 1 
      (c OR b) AND a: 1 
    */ 

Note

As it happens, Boolean data types give Objective-C yet another opportunity to prove it is more complex than its counterparts. The language does not provide one identifier or class to represent logic values. It provides five. For the sake of simplicity (and because my editor won't give me the extra pages), we're only going to use BOOL in this text. If you want to know more, I encourage you to check out the Additional resources section at the end of this chapter.

Swift

Swift uses the Bool keyword for the primitive Boolean data type:

    //Swift 
    var a : Bool = true 
    var b : Bool = false 
    var c = a 
 
    print("a: \(a)") 
    print("b: \(b)") 
    print("c: \(c)") 
    print("a AND b: \(a && b)") 
    print("a OR b: \(a || b)") 
    print("NOT a: \(!a)") 
    print("NOT b: \(!b)") 
    print("a XOR b: \(a != b)") 
    print("(c OR b) AND a: \((c || b) && a)") 
 
    /* 
      Output 
      a: true 
      b: false 
      c: true 
      a AND b: false 
      a OR b: true 
      NOT a: false 
      NOT b: true 
      a XOR b: true 
      (c OR b) AND a: true 
    */ 

In the preceding example, the Boolean object c is not explicitly declared as Bool, but it is implicitly typed as a Bool. In Swift terms, the data type has been inferred in this case. Also, note that Swift does not provide a specific XOR operator, so if you need that comparison, you should use the (a != b) pattern.

Tip

Objective-C nil values

In Objective-C, the value nil also evaluates to false. Although other languages must handle NULL objects with care, Objective-C will not crash when it attempts to perform an operation on a nil object. Speaking from personal experience, this can be somewhat confusing for developers who learned C# or Java before learning Objective-C, and thus expect an unhandled NULL object to crash their app. However, it is common for Objective-C developers to use this behavior to their advantage. Many times, simply checking whether an object is nil logically confirms whether an operation was successful, saving you from writing tedious logical comparisons.