Declaring an Edge Adjacency List Graph

The 3 types of Graph representations are: 1. Edge List 2. Adjacency Edge List 3. Edge Matrix The heart of the simplest representation of Edge List is the following:

LinkedList [ ] AdjLists = new LinkedList [numberOfVertices];

This implies that we are declaring an Array called AdjLists. No matter what, the Graph at the end is just an Array!!! This Array called AdjLists will hold elements of the type LinkedList which are in turn containers of type 'Edge'. Whatever Edge means... So basically, we are implementing a 3 level structure, at the end the edge objects are elements that are stored in Linked Lists, which are themselves stored in an Array! How beautiful!!!!!!!!!!!!

MaximallyBalanced or Complete Binary Tree

// Queue version -- only version totally working so far!
    public boolean isMaximallyBalanced (TreeNode x){ 

            boolean scanningNulls = false;

            Deque q = new LinkedList ();
            q.addFirst(x);

            while (q.size() != 0) {
                TreeNode n = q.remove();

                if (scanningNulls) {
                    if (n != null) 
                        return false;
                }
                else {
                    if (n == null) {
                        scanningNulls = true;
                    }
                    else {
                        q.add(n.myLeft);
                        q.add(n.myRight);
                        
                    }
                    }
                }
            
            return true;
        }

// Adopted from: www.boyet.com/Articles/CheckingForHeap.html 

Calculating the Height of a Tree

//Increase the height only when the recursive call generates a new Iterator!!!
private static int height (T x) {
     if (x.myChildren.isEmpty ( )) {
         return 1;
     } else {
         int bestSoFar = 0;
         Iterator iter = x.myChildren.iterator ( );
         while (iter.hasNext ( )) {
             T child = iter.next ( );
             bestSoFar = Math.max (height(child) + 1, bestSoFar);
         }
         return bestSoFar;
     }
 }

Adding to a Circular Doubly Linked List

public void add (Object to_Add) {
    if (isEmpty ( )) {
      myHead = new DListNode (to_Add);
    } else {
      // Insert to_Add between myHead and myHead.myPrev.
      DListNode newNode = new DListNode (to_Add, myHead.myPrev, myHead);
      // Link the new node into the list.
      myHead.myPrev.myNext = newNode; // This is the circular link stuff.
      myHead.myPrev = newNode;
    }
    mySize++;
  }

3 ways to REVERSE a list (singly linked)

There are 50 ways to leave your lover (P.Simon) but fundamentally 3 ways
 to reverse a list
1. Recursively Non-Destructive
2. Recursively Destructive
3. Iteratively

Recursively Non-Destructive:

public ListNode reverse (ListNode list) {
  ListNode sofar = new EmptyListNode();
        return reverseHelper (this, sofar);

 }


 private static ListNode reverseHelper (ListNode list1, ListNode sofar) {

        if (list1.isEmpty()) {

                return sofar;

        } else {

                return reverseHelper (list1.rest() ,  new NonemptyListNode (list1.first(), sofar) );

        }

 }
 


Recursively Destructive:




public void reverse2 () {
  myHead = reverse2Helper (myHead, null);
 }
 
 public static ListNode reverse2Helper (ListNode L, ListNode soFar){
  if (L == null){
   return soFar;
  } else {
   ListNode temp = L.myRest;
   L.myRest = soFar;
   return reverse2Helper (temp, L) ;
  }
 }




Iteratively:



public void reverse3 () {
  myHead = reverse3Helper (myHead);
 }

public static ListNode reverse3Helper (ListNode head){
  ListNode p, soFar;
  for (p = head, soFar = null; p != null;){
   ListNode temp = p.myRest;
   p.myRest = soFar;
   
   soFar = p;
   p = temp;
   
  }
  return soFar;
 
}

Reversing a List Iteratively!

public void reverse3 () {
  myHead = reverse3Helper (myHead);
 }

public static ListNode reverse3Helper (ListNode head){
  ListNode p, soFar;
  for (p = head, soFar = null; p != null;){
   ListNode temp = p.myRest;
   p.myRest = soFar;
   soFar = p;
   p = temp;
   
  }
  return soFar;
 
}

Doubling a Linked List

//couldn't find a better way to do this...

public void double2 ( ) {
  /* Invariant is L with 2 first ones and rest*/
  ListNode q, w;
  w = q = new ListNode (null);
  
  for (ListNode p = myHead; p != null; p = p.myRest) {
       
       q.myRest = new ListNode(p.myFirst, p);
       q = q.myRest.myRest;
       
               
     }
  myHead = w.myRest;
   /*ListNode p = myHead;
  ListNode p1 = myHead.myRest;
  ListNode p2 = myHead.myRest.myRest;
  
  myHead = new ListNode (p.myFirst, p);
  myHead.myRest.myRest = new ListNode (p1.myFirst, p1);
  myHead.myRest.myRest.myRest.myRest = new ListNode (p2.myFirst, p2);
   */
 }
 
 public void double3 ( ) {
  ListNode w;
  w = new ListNode (myHead.myFirst);
  for (ListNode p = myHead; p != null; p = p.myRest) {
   w.myRest= new ListNode(p.myFirst, p);
   w = w.myRest.myRest;
   System.out.println(this.toString());
  }
  myHead = new ListNode (myHead.myFirst, myHead);
 }

Access Modifiers: public, private, proctecd, package protected(default)

Public : declarations represent specifications – what clients of a package are supposed to rely on. Package Private (default): declarations are part of the implementation of a class that must be known to other classes that assist in the implementation. Protected: declarations are part of the implementation that subtypes may need, but that clients of the subtypes generally won’t. Private: declarations are part of the implementation of a class that only that class needs. *********************************************************************** Import: Does not grant any special access; it only allows abbreviation.

End of HFJ

Announcing the end of going through HFJ. Admittedly, only a first pass... But finally finished back back to back...well maybe except for code kitchens on the beat program and some of the appendices...But did finish all the chapters, didn't I? It's a great book and one that really make stuff look easy. As they say, the best always make it look easy! And this is kind of, one of the best example of that saying! Took me 5 weeks to go through it all. But it was a great experience. I'll miss, reading that book, it seems to me! In any case, on to more stuff then....

Format Specifiers

Format Specifiers:

% [argument number] [flags] [width] [.precision] type

%: says, ‘insert arument here’ and format it using these instructions.

flags: these are for special formatting options like inserting commas, or
Putting negative numbers in parentheses, or to make the numbers
Left justified

width: This defines the Minimum number of characters that will be sued.
That’s minimum not TOTAL. If the number is longer than the width,it’ll still be used in
full, but if it’s less than the width, it’ll be padded with zeroes. Most of the time
this does not need to be specified.


.precision:  It defines the precision. In other words, it sets the number of decimal places.

type: Type is mandatory and will usually be ‘d’ for a decimal integer or ‘f’ for a floating
point number.

E.g. :
format(“%,3.1f”, 91.0000000); -> 91.0

complete example code:

public class FormatTest {

static String x = "";
static double y = 91.000000;

public static void main(String[] args) {

 x = String.format("%,3.1f", y);
 System.out.println(x);

}

} // produces: 42.0

// Adopted from HFJ

Collection class tidbits...

I had to say I do > in a picture...

Generic class definitions and one implementation

Generic class definitions and one implementation

Type parameterization goes in the horizontal direction while abstraction takes care of the 
vertical direction. The idea is the same, reusability and other OOP goodness. 

“The Class, the central notion in Object Technology, can be viewed as the product of the 
corporate merger between the module and type concepts.”

A generic class declared as C[G] is, rather than a type, a type pattern covering an infinite 
set of possible types; you can obtain any one of these by providing an actual generic 
parameter – itself a type - corresponding to G.

Java allows the use of wildcards to specify bounds on what type of parameters a given
 generic object may have. E.g. List indicates a list which has an unknown object 
type.  
List  is pronounced as List of Unknowns.

Void printCollection (Collection  c) {
 For (Object e : c)
     System.out.println(e);
} // will work for any collection of objects. 
   //But if the formal argument is Collection