[11.4] Find duplicate in N = 32,000

1. Example

Bit Vector STORE number into corresponding position
Multiple int
int[] array => array[0]     ,array[1], .......
                        32 bit       32 bit
int wordNumber = numberPos >> 5;                           ==> array Index

int bitNumber = (numberPos & 0x1F); // mod by 32  ==> array element int bit
// NOTE: divide by 32 is because each int is 32 bit
// divide by 8 is because each byte is 8 bit1~ N = 1 ~ 32000 = 32 *1000 = 2^4 * 2^10 = 2 ^14
4KB = 4*2^10*8 btis = 2 ^ 15 bits
2 ^ 15 > 2 ^14
each bit represents a integer


2. Implementation

public static void checkDuplicates(int[] array)
{


     BitSet bs = new BitSet(32000);
     for (int i =0 ; i < array.length; i++)
     {
          int num = array[i];
          int index = num-1;
          if ( bs.get(index) )
               System.out.println(num);
          else 
               bs.set(index);
     }
}


class BitSet
{
    // NOTE: divide by 32 is because each int  is 32 bit
    //       divide by 8  is because each byte is  8 bit
    
    // Field
    int[] bitSet;
    // Constructor
    public BitSet(int size)
    {
            bitSet = new int[size >> 5]; // divide by 32
    }




    boolean get(int pos)
    {
           int wordNumber = (pos >> 5);  // divide by 32
           int bitNumber = (pos & 0x1F); // mod 32 1F=1 1111 = 2^4*1+2^3*1+...+2^0
           return ( bitSet[wordNumber] & (1>>bitNumber) ) != 0;
    }
  

  

    void set(int numberPos)
    {
           int wordNumber = numberPos >> 5;
           int bitNumber = (numberPos & 0x1F); // mod by 32
           bitsSet[wordNumber] |= (1<< bitNumber);
    }

}

3. Silmilar Ones

[11.3] find ONE missing number within four billion integers

1.Example



Bit Vector   

byte[]   =>      byte[0]   byte[1]......

 int arrayIndex = n / 8;    => byte array index

 int bitIndex = n % 8;      => byte array element bit

s= {0,1,3,6}

   index   0 1  2 3 4 5 6  7    
bit array  1 1 0  1 0 0 1 0

bitArray | 1 << (0%8) = 1 0 0  0 0 0 0 0
bitArray | 1 << (1%8) = 1 1 0  0 0 0 0 0
bitArray | 1 << (3%8) = 1 1 0  1 0 0 0 0
bitArray | 1 << (6%8) = 1 1 0  1 0 0 1 0

bitArray & 1 << (6%8) =
1 1 0  1  0 0 "1" 0 & 0 0 0  0  0 0 "1" 0 = 1 ==> 6 exists in bitArray


2. Implementation

// 0                    Store 0
// 1                    Store 1
// .
// .
// .
// 2147483647 = 2^32    Store 2^32
// Assuming we are taking about 32-bit integers. 
// There are 2^32 = 4*10^9 distinct integers.






// Case1: 1GB memory = 1 * 10^9 * 8 bits = 8 billion bits.
// It is enough to use one bit correpresening one distinct integer. 
// We don't need sort 
int radix = 8;
byte[] bitField = new byte[0xffff ffff / radix];// 
void F() throws FileNotFoundException // method had sth to cause this e
{



     Scanner in = new Scanner (new FileReader("a.txt") );
     while (in.hasNextInt())
     {
           int  n = in.hasNextInt();
           int arrayIndex = n / 8;
           int bitIndex = n % 8;
           int setOnePos = 1 << bitIndex;
           bitField[ arrayIndex ] | = setOnePos;
     }



     int arrayLength = bitField.length;
     int bitLength = 8; 





     for (int i = 0 ; i < bitfield.length; i++) {
        for (int j = 0; j < 8; j++) 
        {
           // Retrieves the individual bits of each byte. When 0 bit
           // is found, finds the corresponding value. 
           if ((bitfield[i] & (1 << j)) == 0) {
              System.out.println (i * 8 + j);
              return;
           }
        }
     }

// 0          store integer 0 ~ 2^20      = 0       ~ 1048576*1
// 1          store integer 2^20+1 ~ 2^21 = 1048577 ~ 1048576*2
// .
// .
// .
// 4095       store integer ~ 2^32   =              ~ 1048576*4096 = //                                                  2147483647
// There are 4 billion =2^32 distinct integers 
// one map to one
// >= 2 ^32 bit array = 2^32 / 8 = 2 ^29 byte array


// many map to one

int bitSize  = 1048576;  // 2^20 bits (2^17 bytes)
int blockNum = 4096;    // 2^12
byte[] bitField = new byte[bitSize/8];
int[] blocks    = new int[blockNum];


// function have FileNotFOundExcpetion possibility and throws ... but don't have try and catch
// function have Exception possibility and use try catch 
void findOpenNumber() throws FileNotFoundException
{




     int stating = -1;
     Scanner in = new Scanner ( new FileReader("input_file_q11_4.txt") );

     


     // NOTE: first pass, check which block
     while (in.hasNextInt())
     { 
          int n = in.nextInt();
          blocks[ n / (bitField.length*8)]++;// n/2^20
     }




     for ( int i = 0 ; i < blocks.length ; i++ )
     {
         // Block not fill up, means probably missing a number 
         if (  block[i]  < bitField.length *8 ) // < 2^20
         {
               // If value < 2^20, then at least 1 number is missing
               // in this section
               // In last section: 4095*2^17*8 = 2^32 - 2^20
               // NOTE: ***count the starting integer in that section
               starting = i* bitField.length * 8;
               break;
         }
     }



     // NOTE: second pass, check which specific number from those 2^20 numbers
     in = new Scanner(new FileReader("input_file_q11_4.txt") );
     while (in.hasNextInt())
     {
         int n = in.nextInt();
         // If the number is inside the block that's missing 
         // numbers, we record it
         if ( n >= starting && n < starting + bitField.length *8 )
              bitField[ (n -starting) / 8] |= 1 << ((n-starting)%8) ;
         
     }




     // Find the missing number within those 2^20 integers
     // 2^20 -1 = (2^17-1)*8+7+ 0 = 2^20 -8 +7 +0 
     for (int i = 0; i < bitField.length; i++ )
     {
         for (int j = 0 ; j < 8 ; j++ )
         {
               // Retrieves the individual bits of each byte
               // When 0 bit is found, finds the corresponding value
               if (  bitField[i]  &  (1<





// Bit-vector to store integers
public class BitArray
{
     


    // Field
    private byte[] set;
    // Constructor
    public BitArray (int length)
    {
         arraySize = (length % 8 =! = 0) ? (length / 8 )+1:length / 8;
         this.set = new byte[ arraySize ];
    }




    // Set given number in the bit-array. i.e., make corresponding bit as 1
    public void storeNumber(int number)
    {


         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;

         // so bit at postiion needs to made 1
         this.set[arrayIndex] = (byte)  (this.set[arrayIndex] |  pos );

    }
    private int getArrayIndex(int number )
    {
         return number / 8;
    }
    private int getbitIndex(int number)
    {
         return number % 8;
    }




    // check if the number exists in the array if the corresponding bit is 1, then it exist
    public boolean numberExists(int number)
    {

         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;
         return ( this.set[arrayIndex] & pos ) > 0 ? true:false;       
    }



    private void printSet()
    {
           
    }



    public static void main (String[] args)
    {
           BitArray array = new BitArray(1000);
           System.out.println("length of array:" + array.set.length );


           int num1 = 17;
           array.storeNumber(num1);
           int num2 = 171;
           array.storeNumber(num2);
           int num3 = 400;
           array.storeNumber(num3);


           System.out.println("val "+ num1 + " exists ? " + array.numberExists(num1) );
           System.out.println("val" + num2 + " exists ? " + array.numberExists(num2) );
           System.out.println( "val" + num3 + " exists ? " + array.numberExists(num3) );
           
    }





3. Similar Ones
http://question.ikende.com/question/2D373139353434383837
http://geekrai.blogspot.com/2014/09/bit-array-or-vector.html

[7.10] Garbage collector

1. Example
1. reference counting
2. mark and sweep
3. copy


2. implementation

In C++, garbage collection with reference counting is almost always implemented with
smart pointers, which perform reference counting.
The main reason for using smart pointers over raw ordinary pointers is the conceptual
simplicity of implementation and usage.


With smart pointers, everything related to garbage collection is performed behind the scenes - typically in constructors / destructors / assignment operator / explicit object mangement functions.


There are two types of functions, both of which are very simple:

RefCountPointer::type1()
{
  //implements depends on reference counting organization
  // this can also be no ref. counter at all
  incrementRefCounter();
}
RefCountPointer::type2()
{
  // Implementation depends on reference counting organization
  // there can also be no ref. coutner at all
  decrementRefcounter();
  if ( referenceCounterIsZero() )
      destructObject();
}




// NOTE Method 1. Simple Reference Counting ( )
struct Object
{
};
struct RefCount
{
    int count;
};
struct RefCountPtr
{
    Object *pointee;
    RefCount *refCOunt;
};
Advantages: performance
Disadvantages: memory overhead because of two poitners





// NOTE Method 2: Alternative Reference Counting  ( )
struct Object
{
};
struct RefCountPtrImp1
{
   int count;
   Object *object;
};
struct RefCountPtr
{
   RefCountPtrImp1 * pointee;
};
Advantages:no memory overhead because of two pointers
Disadvantages: performance penalty extra level of indirection




// NOTE Method 3: Intrusive Reference Counting ( )
struct Object
{
};
struct ObjectIntrusiveReferenceCounting
{
   Object object;
   int count;
};
struct RefCountPtr
{
   ObjectIntrusiveReferenceCounting * pointee;
};
Advantages: no previous disadvantage (no overhead due to pointers)
Disadvantages: class for intrusive reference counting should be modified




// NOTE Method 4: Ownership List Reference Counting (LinkedList)
// Ownership list reference counting. It is an alternative for approach // 1-3. For 1-3 it is only important to determine that counter is zero -// its actual is not important. This is the main idea of approached #4

// 1. all smart pointers for given objects are stored in doubly-linked 
// lists. 
// 2. The constructor of a smart pointer adds the new node to a list.  
// 3. The destructor removes a node from the list.
// 4. checked if the list is empty or not. If it is empty, the object is //    deleted.

struct object
{
};
struct ListNode
{
    Object *pointee;
    ListNode *next;
};

3. Similar ones

[7.9] in-memory file system

1. Example

For datablock allocation, we can use bitmask vector and linear search  or   B+ tree
1. bitmask vector and linear search
2. B+ tree




2.Implementation
http://www.farhadsaberi.com/linux_freebsd/image/unix_file_system.gif

//NOTE: 1. "Datablock" -> INode -> File -> Direcotry
struct DataBlock 
{  
  char data[DATA_BLOCK_SIZE]; 
};
DataBlock dataBlocks[NUM_DATA_BLOCKS];



//NOTE: 2. Datablock -> "INode" -> File -> Direcotry
struct INode 
{
  std::vector datablocks;
};



//NOTE: 3. Datablock -> INode -> "File" -> Direcotry
std::mapmapFromName;
struct MetaData
{
   int size;
   Date last_modified, created;
   char extra_attributes;
}
struct FSBase;
struct File : public FSBase
{
   private:
     std::vector * nodes; 
     MetaData metaData;
};




//NOTE: 4. Datablock -> INode -> File -> "Direcotry"
Srtuct Directory :public FSBase
{
    std::vector content;
};








std::vector dataBlockUsed();






struct FileSystem
{




    init();
    mount( FileSystem* );
    unmount( FileSystem* );

    

    File createFile( const char* name ){ ... }
    Directory createDirectory( const char* name ) { ... }
    



    // mapFromName to find INode corresponding to file
    void openFile( File *file, FileMode mode){ ... }




    void closeFile( File *file){ ... }
    void writeToFile( File* file, void *data , int num ) { ... }
    void readFromFile( File* file, void *res, int numBytes, int position ){ ... }




};

.3 Similar Ones

[7.8] Othello

1. Example

Game:
1.strat
2.run
3.check rule
4.add result


    A     B   C     D     E      F     G     H
8   
7   
6
5                      W     B
4                      B     W
3
2  
1  


Start:     B W
             W B
Flip1:    W B W --> W W W
Flip2:        W                W
                  B      -->      W
                 W                 W


Rule1: Each othello piece is white on one side and black on the other(see start).

Rule2: When a piece is surrounded by its opponents on both the left and right sides(see Flip 1), or both the top and bottom(see Flip 2), it is said to be captures and its color is flipped.

Rule3: On your turn, you must capture at least one of your opponent's pieces(at least flip1 or flip2 happen).

Rule4: The game ends when wither user has no more valid moves, and the win is assigned to the person with the most pieces.


2. Implementation
Othello has three major steps:
1. Game() which would be the main function to manage all the activity in the game:
2. Initialize the game which will be done by constructor
3. Get first user input
4. Validate the input
5. Change board configuration
6. Check if someone has won the game
7. Get second input
8. Validate the input
9. Change the board configuration
10.Check if someone has won the game
private void getMove( int color ) throws Exception{...}
try 

{ 

   getMove(black); valid = true;

 } 

catch (Exception e) 

{ 

   System.out.println("Enter a valid coordinate!"); 

}

public class Question
{



     private final int white = 1;
     private final int black = 2;
     private int[][] board;


  

     // Set up the board in the standard othello starting positions, 
     // and starts the game
     public void start() {....}
     

     


     // The actual game runs continuously until a player wins
     public void game()
     {

         printBoard();


         while ( won() == 0 )
         {
              boolean valid = false;
              while ( !valid )
              {
                    try
                    {
                        getMove(black);
                        valid = true;
                    }
                    catch (Exception e)
                    {
                        System.out.println("Enter a valid coordinate!");
                    }
              }
              valid = false;
              while (  !valid ) 
              {
                    try
                    {
                        getMove(white);
                        valid = true;
                    }
                    catch
                    {
                        System.out.println("Enter a valid coordinate !");
                    }
              }
              
              printBoard(); 
             
         }


         if ( won() != 3 )
            System.out.println( won() ==1 ? "white": "black" + " won !");
         else 
            System.out.println("It's a draw !");


     }






     // NOTE(GET INPUT): Get the input - a move
     // Prompts the player for a move and the coordinates for the move. 
     // throws an exception if the input is not valid or if the entered 
     // coordinates do not make a valid move
     private void getMove( int color ) throws Exception{...}

     


     // NOTE(CHECK RULE): 1. Validate the move
     // returns if a move at coordinate (x,y) is a valid move for the specified player
     private boolean isValid(int color, int x, int y){...}



     // NOTE(ADD SUB RESULT): 2. Configure the board
     // Adds the move onto the board, and the pieces gained from that 
     // move. Assume the move is valid
     public void add(int x, int y, int color){...}




     // NOTE(CHECK RULE): 3. Check if someone Won
     // Check which color has more pieces on the board, count the pieces
     // Returns the winner, if any. If there are no winners, returns 0
     private int won()
     {
          if ( !canGo(white) && !canGo(black) )
          {


                int count = 0;
                for (int i = 0 ; i < 8 ; i++ )
                {
                     for (int j = 0 ; j < 8; j ++)
                     {
                          if (board[i][j] == white)
                          {
                                count++;
                          }
                          if (board[i][j] == black)
                          {
                               count--;
                          }
                     }
                }


   
                if ( count > 0 ) return white; 
                if ( count < 0 ) return black;
                // count == 0 --> draw
                return 3; 
                

          }


          // Still canGo()
          return 0;


     }
     



     // NOTE(CHECK RULE): 
     // Returns whether the player of the specified color has a valid 
     //  move in his turn. This will return false when 
     //  1. none of his pieces are present (no piece remaining)
     //  2. none of his moves result in him gaining new pieces
     //  3. the board is filled up
     private boolean canGo(int color){...}



}

3. Similar ones

[7.7] chat server

1. Example

A online --msg--> B online
A online --add friend-> B offline
A offline<--see-- B online

What is our chat server?
1. support a small number of users
2. ppl have a contact list to see who is online vs  offline

What specifies actions does it need to support?
- User A signs online

- User A ask for their contact list, with each person's current status
- Friends of User A now see User A as online
- User A add User B to contact list
- User A sends text-based message to User B
- User A changes status message and/or status type
- User A removes User B

- User A signs offline


What can we learn about these requirements?
- We must have
1.a concept of users,
2. add request status,
3.online status,
4. messages.


What are the core components?
1. Database
2. Server
3. XML
We' ll need a database to store items and an "always online" application as the server.
We might recommend using XML for the communication between the chat server and the clients, as it's easy for a person and a machine to read.




What are the key objects and methods?
hidden details such as how to actually push the data to a client




2. Implementation

enum StatusType
{
   online, offline, away
}
class Status
{
    StatusType status_type;
    String status_message;
}
class User
{


   // Field: my ID
   String username;
   String display_name;

   // Field: my friend list
   User[] contact_list;
   // Field: my ongoing friend list
   AddRquest[] requests;



   // Method: modify status and short description
   boolean updateStatus(  StatusType stype, Strign message ){....;}
   // Method: add people
   boolean addUserWithUsername(String name);
   // Method: I aprove someone
   boolean approveRequest(String username);
   // Method: I reject someone
   boolean denyRequest(String username);
   // Mehtod: I remove some friends
   boolean removeContact(String username);
   // Method: CHAT MAIN FUNCTION - I CHAT, send message
   boolean sendMessage(String usernname, String message);
}

/* Hold data that from_user would like to add to_user */
class AddRequest
{
    User from_user;
    User to_user;
}
class Server
{
   User getUserByUsername(String username);
}

3. Similar Ones

What problems would be the hardest to solve(or the most interesting)?
Q1 How do we know if someone is online- I mean, really ,really know?

While we would like users to tell us when they sign off, we can't know for sure. A user's connection might have died, for example. To make sure that we know when a user has signed  off. we might try regularly pining the client to male sure it's still there.

Q2 How do we deal with conflicting information ?

We have some information stored in the computer's memory and some in the database. What happens if they got out of sync? which one is "right"?

Q3  How do we make our server scale?

While we designed out chat sever without worrying -- too much --- about scalability, in real life this would be a concern. We'd need to split our data across many servers, which would increase our concern about out of sync data.

Q4  How do we prevent denial of service(DOS) attacks?

Clients can push data to us -- what if they try to DOS us? How do we prevent that?
https://msdn.microsoft.com/en-us/library/cc750213.aspx
http://static.planetminecraft.com/files/resource_media/screenshot/1306/Cisco-what-is-ddos-attack_4812859_lrg.jpg


http://docs-legacy.fortinet.com/cb/html/index.html#page/FOS_Cookbook/UTM/cb_utm_ip_dos.html

A DOS attack really shouldn't be handled by your HTTP server. Once a request has reached it the attacker has 'won' by taking up a connection (no matter how short). Even if they are short they can just slam it with thousands/sec and prevent anyone else from connecting. Also, they might not attempt to 'connect' via TCP and just flood the server with all sorts of requests.

Block/detect DOS attacks at a lower level or via a firewall, which I'm sure many software and hardware versions support some basic types of DOS detection and prevention.

http://corporatecomplianceinsights.com/what-is-a-ddos-attack-and-how-can-you-prevent-one/

While there are many varieties of DoS and DDoS attacks, they can generally be categorized as one of two types: network‐based, or application‐based. In a network‐based attack, the attacker floods the victim computer with information, clogging up the victim computer’s communication lines and overwhelming the victim computer’s ability to process the flood of information. Some of the historically more common techniques include:

• Ping Floods: In this relatively simple type of attack, the attacking computer sends a flood of requests (or “pings”) to the victim computer that ask the victim computer to acknowledge that the victim computer is able to communicate with the attacker. If enough of these ping requests are sent, it can overwhelm the victim.
• Smurf or Fraggle Attacks: In these attacks, the attacking computer falsifies (or “spoofs”) its Internet Protocol address so that it appears to be the same as the victim’s computer. The attacker, posing as the victim, then sends requests to an entire network of computers seeking an acknowledgment. The entire network then sends its acknowledgment to the victim’s computer, flooding it with information.
• SYN/ACK Flood: These attacks exploit the way computers acknowledge each other when they first communicate over the Internet. The attacking computer introduces itself, pursuant to standard Internet protocol, with a “SYN” message. The computer responds with the standard “SYN‐ACK” message and waits for the attacking computer to issue the standard “ACK” acknowledgement. The attacker never issues this acknowledgement, which has the effect of making the victim computer expend its resources waiting. A flood of these mismatched communications can take the victim computer out of commission.

The second broad category of DoS and DDoS attacks is application‐based attacks. While conceptually similar in some ways to network‐based flooding attacks, application‐based attacks, as the name suggests, focus on exploiting software programs or applications on the victim computer in an attempt to make the computer crash or slow to a crawl. An attacker carrying out such a request may seek, for example, to repeatedly run resource‐intensive search requests on a victim’s search engine or database, or to repeatedly request complex and feature‐rich web pages from a server, either of which may severely tax or exceed the victim server’s capacity.

The organized group of attacking computers used in a DDoS attack is often called a “botnet” (as in “robot network”). To assemble a botnet, an attacker often will infect the computers of unsuspecting users with malicious software that allows the attacker to remotely control those computers. The user of the infected computer often will be completely unaware that the computer has been infected. Less enterprising or technically adept attackers can simply rent botnets from the web’s black market. There also have been occasions in which botnets have consisted of volunteers who willingly allow their computers to be controlled by the DDoS attacker. This often occurs in politically‐motivated attacks, as in the Wikileaks‐related attacks coordinated by the “Anonymous” organization. The recruiting and coordination of such voluntary botnets often occurs on social media sites such as Twitter, as well as in online chat rooms.

Hardware and Structural Defense: Of course, monitoring and having a response plan alone will do nothing to stop DoS and DDoS attacks, or lessen their severity. For that, you will need to consider hardware and structural defenses. For example, most modern network hardware can be configured to prevent Ping, Smurf/Fraggle, SYN/ACK, and similar DoS network flood attacks by rejecting or limiting the Internet traffic that characterizes those types of attacks (i.e., an unusually high number of “ping” requests from one computer, or a computer that refuses to issue the “ACK” message). Hardware‐implemented access control lists can also be used to filter out traffic from particular attacking computers.

These “limiting” or “filtering” solutions, however, are less useful in defending against DDoS attacks. Because DDoS attacks are perpetrated through several different computers acting in concert (often hundreds or thousands of them), they can confuse or circumvent measures taken to limit or filter the requests coming from a small number of specifically identified computers. Planning an adequate DDoS defense therefore should involve considering structural defenses as well – in other words, defenses that involve the manner in which a computer network, and the information it contains, is organized. Even these structural defenses, however, may have limited effectiveness in preventing or remediating the attacks.

Perhaps the simplest structural solution is to have an extraordinary amount of network capacity and processing power, so that your entity can withstand nearly any DDoS “flood.” While some larger entities can do this, for most it is simply not cost effective. More practical structural solutions can include: outsourcing to a large and well‐established hosting provider that is likely to have a larger amount of capacity and in‐house methods of addressing DDoS attacks; having a backup “mirror” website hosted at a different location that can be substituted if the primary site is under attack; implementing caching systems that substitute simpler web pages in place of complex feature‐rich pages if application resources become strained; and having a system architecture that clearly separates the “front‐end” web‐facing system from the “back end” processing systems to minimize the business effects of attacks on the web server.

Reporting: It is indisputably difficult to investigate and hold accountable those who perpetrate DoS and DDoS attacks – but it does happen. As of the date of this article, for example, there are news reports that persons suspected of being involved in the Wikileaks-related attacks have been arrested and their residences searched for evidence. If your business is victimized by such an attack, you therefore should consider forensic preservation of the system logs and related documentation. It just may be that this information could lead to the perpetrator being prosecuted.

[7.6] Jigsaw puzzle

1. Example

every piece has four edges with different type: inner, outer or flat
every piece can rotate , we called orientation here
        _ _
  ___|   |___
 |                |
 |                |
 |________|

     
  ___     ___
 |      |__|     |
 |                |
 |________|


   _______
 |                |
 |                |
 |________|

2. Implementation

//
//We grounded the edges by their type. Because inners with outers, and //vice versa, this enables us to go straight to the potential matches.


//We keep track of the inner perimeter of the puzzle (Exposed_Edges) as //we work our way inwards. Exposed_Edges is initialized to be the //corner's edges.



class Edge 
{
   enum Type {inner, outer, flat}
   Piece parent; // NOTE : this edge belong to which piece, it must be some piece's lateral[left, right,top, bottom]
   Type type;
   bool fitsWith(Edge type){...}// Inners & outer fit together
}
class Piece
{
   Edge left, right, top, bottom;
   Orientation solvedOrientation = ....;// 90,180,etc
}



class Puzzle
{




   Piece[][] pieces;// Remaining pieces left to put away 
   Piece[][] solution;
   Edge[] inners, outers, flats;




   
   // NOTE: they are the outmost layer pieces with flat edge outside. 
   // we're going to solve this by working our way in-wards, starting   
   //with the corners. This is a list of the inside edges. 
   
    Edge[] exposed_edges;




   void sort() 
   {
        
        // Iterate through all edges, adding each to inners, outers, 
        // etc. as appropriate. Look for the corners-add those to  
        // solution. Add each non-flat edge of the corner to 
        // exposed_edges.
        
   }




   void solve()
   {
        // NOTE: edge1 here refers the edge inside 
        foreach edge1 in exposed_edges
        {
             // Look for a match to edge1 
             if (  edge.type == Edge.type.inner  )
             {
                   // NOTE: outers refers to those remaining pieces 
                   foreach edge2 in outers
                   {
                       if edge1.fitsWith(edges)
                       {
                             
//we found a match ! 
//1. Remove edge1 from exposed_edges. 
//2. Add edges2'piece to solution. 
//3. Check which edges of edge2 are exposed , and add those to exposed //edges.
                             
                       }
                   }
                   // Do the same thing, swapping inner & outer 
             }
        }
   }



}

3. Similar ones